Curso

Para atingir os nossos Objetivos de Aprendizagem, o curso é organizado nas 5 etapas a seguir.

Primeira Etapa: Análise de Algoritmos

Inicialmente, é apresentada a motivação para a análise de complexidade de algoritmos. O objetivo é fazer com que o aluno compreenda que o projeto de um algoritmo deve levar em consideração sua eficiência, uma vez que o tamanho da entrada a ser processada pode ser ordens de magnitude maior do que as até então vistas nas disciplinas anteriores. Posteriormente, são abordadas técnicas analíticas para determinar a eficiência assintótica de algoritmos.

• Introdução à análise de algoritmos
• Análise assintótica
• Análise de algoritmos recursivos

Segunda Etapa: Algoritmos de Ordenação

O foco nessa etapa está no projeto, implementação e análise assintótica de algoritmos iterativos e recursivos de ordenação. A ideia é não somente entender as estratégias utilizadas por esses algoritmos, mas também ter uma ideia clara de suas eficiências e classes de complexidade.

• Bubble sort, insertion sort e selection sort
• Quick sort e merge sort
• Counting sort e radix sort

Terceira Etapa: Estruturas de dados lineares e Tabelas Hash

A partir desta etapa, o objetivo é apresentar o funcionamento interno de diversas estruturas de dados, bem como explorar suas aplicações. Nesta etapa, em particular, serão abordados array, filas, pilhas e Tabelas Hash. Inicialmente, o foco está na implementação utilizando vetores de estruturas com diferentes políticas de acesso. Nesse momento há uma discussão a respeito de 2 pontos negativos relacionados ao uso de vetores: desperdício de memória e complexidade e ineficiência à medida em que é preciso aumentar significativamente a quantidade de elementos a serem armazenados. Diante desse cenário, introduz-se a necessidade de estruturas de dados dinâmicas. Assim, filas e pilhas são novamente abordadas, mas como o foco na implementação utilizando listas encadeadas.

• Filas e Pilhas baseadas em arrays
• Listas encadeadas
• Tabelas Hash

Quarta Etapa: Árvores Binárias

Nesta etapa abordaremos o conceito de árvores binárias de pesquisa e Heaps. Inicialmente, abordamos as propriedades de árvores binárias de pesquisa e suas operações básicas. Exploramos o uso de nós ligados para a implementação de BSTs. Depois, exploramos uma estratégia de implementação de árvores binárias baseadas em arrays – Heap. Há uma discussão importante sobre o problema de árvores desbalanceadas e como Heap resolve esse problema por construção.

• BST
• Heap

Quinta Etapa: Árvores Binárias Balanceadas

Por último, abordaremos estratégias de balancamento de árvores binárias de pesquisa. Em particular, o foco está em rotações e nas estratégias para aplicá-las, como cálculo do balanceamento de nós (AVL) ou coloração dos nós (Árvores Vermelho-Preto). Além disso, abordamos também a estratégia de balanceamento aplicada por Árvores B, além da técnica de agregar mais informação em um nó.

• AVL
• Árvores Vermelho-Preto
• Árvores B