Prazos flexíveis

Prazos flexíveis
Redefinir os prazos de acordo com sua programação.
Certificado compartilhável
Ganhe um certificado após a conclusão
100% online
Comece instantaneamente e aprenda em sua própria programação.
Curso 2 de 6 no
Estruturas de dados e especialização de algoritmos
Nível intermediário
Conhecimento básico de pelo menos uma linguagem de programação: C ++, Java, Python, C, C#, JavaScript, Haskell, Kotlin, Ruby, Rust, Scala.
Aproximadamente. 25 horas para concluir
Inglês
Legendas: árabe, francês, português (europeu), italiano, vietnamita, alemão, russo, inglês, espanhol

Alexander S. Kulikov
Professor
Departamento de Matemática e Ciência da Computação
Daniel M Kane
Professor assistente
Departamento de Ciência da Computação e Engenharia / Departamento de Matemática
Neil Rhodes
Faculdade adjunta
Ciência da Computação e Engenharia do Sablabus – O que você aprenderá com este curso
Estruturas de dados básicas
Neste módulo, você aprenderá sobre as estruturas básicas de dados usadas ao longo deste curso. Iniciamos este módulo olhando em detalhes nos blocos fundamentais de construção: matrizes e listas vinculadas. A partir daí, construímos duas estruturas de dados importantes: pilhas e filas. Em seguida, olhamos para as árvores: exemplos de como eles são usados ​​na ciência da computação, como são implementados e as várias maneiras pelas quais podem ser atravessadas. Depois de concluir este módulo, você poderá implementar qualquer uma dessas estruturas de dados, bem como ter um sólido entendimento dos custos das operações, bem como as trocas envolvidas no uso de cada estrutura de dados.
Matrizes dinâmicas e análise amortizada
Neste módulo, discutimos matrizes dinâmicas: uma maneira de usar matrizes quando é desconhecido com antecedência quantos elementos serão necessários. Aqui, também discutimos análises amortizadas: um método para determinar o custo amortizado de uma operação em uma sequência de operações. A análise amortizada é frequentemente usada para analisar o desempenho dos algoritmos quando a análise direta produz resultados insatisfatórios, mas a análise amortizada ajuda a mostrar que o algoritmo é realmente eficiente. É usado tanto para análise de matrizes dinâmicas quanto também será usada no final deste curso para analisar árvores espalhadas.
Filas prioritárias e conjuntos disjuntos
Iniciamos este módulo, considerando filas prioritárias que são usadas para agendar com eficiência empregos, seja no contexto de um sistema operacional de computador ou na vida real, para classificar arquivos enormes, que é o bloco de construção mais importante para qualquer algoritmo de processamento de big data e, e Para calcular com eficiência caminhos mais curtos nos gráficos, que é um tópico que abordaremos em nosso próximo curso. Por esse motivo, as filas prioritárias têm implementações internas em muitas linguagens de programação, incluindo C ++, Java e Python. Veremos que essas implementações são baseadas em uma bela idéia de armazenar uma árvore binária completa em uma matriz que permite implementar todos os métodos de fila de prioridade em apenas algumas linhas de código. Em seguida, mudaremos para a estrutura de dados Disjunt Sets que é usada, por exemplo, na conectividade dinâmica de gráfico e no processamento da imagem. Veremos novamente como as idéias simples e naturais levam a uma implementação fácil de codificar e muito eficiente. Ao concluir este módulo, você poderá implementar essas duas estruturas de dados eficientemente do zero.
Tabelas de hash
Neste módulo, você aprenderá sobre técnica muito poderosa e amplamente usada chamada hash. Seus aplicativos incluem a implementação de linguagens de programação, sistemas de arquivos, pesquisa de padrões, armazenamento de valor-chave distribuído e muito mais. Você aprenderá como implementar estruturas de dados para armazenar e modificar conjuntos de objetos e mapeamentos de um tipo de objetos para outro. Você verá que implementações ingênuas consomem uma quantidade enorme de memória ou são lentas e, em seguida, aprenderá a implementar tabelas de hash que usam memória linear e trabalham em O (1) em média! No final, você aprenderá como as funções de hash são usadas em sistemas desbotados modernos e como eles são usados ​​para otimizar o armazenamento de serviços como Dropbox, Google Drive e Yandex Disk!
Árvores de pesquisa binária
Neste módulo, estudamos árvores de busca binária, que são uma estrutura de dados para fazer pesquisas em conjuntos ordenados dinamicamente em alterações. Você aprenderá sobre muitas das dificuldades em realizar essa tarefa e as maneiras pelas quais podemos superá -las. Para fazer isso, você precisará aprender a estrutura básica das árvores de pesquisa binária, como inserir e excluir sem destruir essa estrutura e como garantir que a árvore permaneça equilibrada.
Árvores de pesquisa binária 2
Neste módulo, continuamos estudando árvores de pesquisa binária. Estudamos algumas aplicações não triviais. Em seguida, estudamos o novo tipo de árvores de busca equilibrada – árvores espalhadas. Eles se adaptam às consultas dinamicamente e são ideais de várias maneiras.