Curso Em Algoritmos, USA Online, EUA 2018
Curso Em Algoritmos
Este curso abrange as informações essenciais que todo programador sério precisa saber sobre algoritmos e estruturas de dados, com ênfase em aplicações e análise de desempenho científico de implementações Java. A Parte I abrange estruturas de dados elementares, triagem e algoritmos de busca. A Parte II centra-se em algoritmos de processamento de caracteres e gráficos.
Bem-vindo à Algoritmos, Parte I.
Ilustramos nossa abordagem básica para desenvolver e analisar algoritmos, considerando o problema de conectividade dinâmico. Apresentamos o tipo de dados de encontro de união e consideramos várias implementações (busca rápida, união rápida, união rápida ponderada e união rápida ponderada com a compressão do caminho). Finalmente, aplicamos o tipo de dados de encontro de união ao problema de percolação da química física.
A base de nossa abordagem para analisar o desempenho de algoritmos é o método científico. Começamos por realizar experimentos computacionais para medir os tempos de execução de nossos programas. Usamos essas medidas para desenvolver hipóteses sobre o desempenho. Em seguida, criamos modelos matemáticos para explicar seu comportamento. Finalmente, consideramos analisar o uso da memória de nossos programas Java.
Consideramos dois tipos de dados fundamentais para armazenar coleções de objetos: a pilha e a fila. Implementamos cada um usando uma lista de links separados ou uma matriz de redimensionamento. Apresentamos dois recursos Java avançados - genéricos e iteradores - que simplificam o código do cliente. Finalmente, consideramos várias aplicações de pilhas e filas que vão desde a análise de expressões aritméticas até a simulação de sistemas de enfileiramento.
Classes elementares
Apresentamos o problema de classificação e a interface Comparável de Java. Estudamos dois métodos de classificação elementares (classificação de seleção e classificação de inserção) e uma variação de um deles (shellsort). Também consideramos dois algoritmos para arrasar uniformemente uma matriz. Concluímos com uma aplicação de classificação para computar o casco convexo através do algoritmo de varredura de Graham.
Estudamos o algoritmo mergesort e mostramos que ele garante a classificação de qualquer matriz de n itens com no máximo n lg n compara. Também consideramos uma versão não recursiva, de baixo para cima. Provamos que qualquer algoritmo de classificação baseado em comparação deve fazer pelo menos n lg n se compara no pior dos casos. Discutimos o uso de diferentes pedidos para os objetos que estamos ordenando e o conceito de estabilidade relacionado.
Apresentamos e implementamos o algoritmo de quicksort randomizado e analisamos seu desempenho. Também consideramos quickselect randomizado, uma variante de quicksort que encontra o menor item menor em tempo linear. Finalmente, consideramos 3-way quicksort, uma variante de quicksort que funciona especialmente bem na presença de chaves duplicadas.
Apresentamos o tipo de dados da fila de prioridade e uma implementação eficiente usando a estrutura de dados do heap binário. Esta implementação também leva a um algoritmo de classificação eficiente conhecido como heapsort. Concluímos com aplicações de filas de prioridade onde simulamos o movimento de n partículas sujeitas às leis de colisão elástica.
Tabelas de símbolos elementares
Definimos uma API para tabelas de símbolos (também conhecidas como matrizes associativas, mapas ou dicionários) e descrevemos duas implementações elementares usando uma matriz ordenada (pesquisa binária) e uma lista não ordenada (pesquisa seqüencial). Quando as chaves são comparáveis, definimos uma API estendida que inclui os métodos adicionais min, máximo de piso, teto, classificação e seleção. Para desenvolver uma implementação eficiente desta API, estudamos a estrutura de dados da árvore de pesquisa binária e analisamos seu desempenho.
Árvores de pesquisa equilibrada
Nesta palestra, nosso objetivo é desenvolver uma tabela de símbolos com desempenho logarítmico garantido para pesquisa e inserção (e muitas outras operações). Começamos com 2-3 árvores, que são fáceis de analisar, mas difíceis de implementar. Em seguida, consideramos árvores de busca binária vermelho-preto, que vemos como uma nova maneira de implementar 2-3 árvores como árvores de busca binária. Finalmente, apresentamos árvores B, uma generalização de 2-3 árvores que são amplamente utilizadas para implementar sistemas de arquivos.
Aplicações geométricas de BSTs
Começamos com pesquisas de 1d e 2d, onde o objetivo é encontrar todos os pontos em um dado intervalo 1d ou 2d. Para realizar isso, consideramos kd-trees, uma generalização natural de BSTs quando as chaves são pontos no plano (ou dimensões mais altas). Também consideramos problemas de interseção, onde o objetivo é encontrar todas as interseções entre um conjunto de segmentos de linha ou retângulos.
Começamos por descrever as propriedades desejáveis ​​da função hash e como implementá-las em Java, incluindo um princípio fundamental conhecido como o pressuposto de hash uniforme que está subjacente ao sucesso potencial de uma aplicação de hash. Então, consideramos duas estratégias para implementar tabelas de hash - encadeamento separado e sondagem linear. Ambas as estratégias produzem desempenho de tempo constante para pesquisa e insira-se sob a suposição de hash uniforme.
Aplicações da tabela de símbolos
Consideramos várias aplicações de tabelas de símbolos, incluindo conjuntos, clientes de dicionário, clientes de indexação e vetores esparsos.