Nesta disciplina, queremos entender e controlar o computador de
maneira muito mais refinada do que fazíamos antes, em Python. Iremos
introduzir rapidamente a linguagem de programação C, sua sintaxe e
os principais tipos de variáveis, além de aprender a declarar e
manipular strings, vetores e matrizes estáticos.
Iremos descobrir como a memória do computador está organizada, além
de aprender a projetar e representar estruturas mais sofisticadas
criando novos tipos abstratos de dados. Além disso, queremos distinguir
o uso de valores e referências, bem como criar e utilizar vetores e
matrizes alocados dinamicamente.
Revisaremos o projeto de algoritmos recursivos e iremos aprender a
usar recursão para resolver diversos problemas eficientemente usando
enumeração e retrocesso. Também introduziremos a notação assintótica
para estimar e medir a eficiência de algoritmos de maneira simplificada.
Introduziremos o conceito de nó alocado dinamicamente como a unidade
fundamental de estruturas de dados compostas. O uso de nó será
ilustrado por coleções de dados representadas como listas ligadas
simples, variações e outras estruturas mais avançadas.
Projetaremos os tipos abstratos de dados pilha e fila. Iremos
descobrir que esses tipos de dados são as estruturas de dados
centrais de diversos algoritmos fundamentais da Computação.
Aplicaremos a pilha em alguns exemplos, como parentização, avaliação
de expressão e simulação de recursão.
Definiremos o conceito de árvore binária para representar estruturas
de dados hierárquicas. Depois, utilizaremos árvores binárias para
armazenar e buscar eficientemente em coleções de dados ordenáveis.
Revisaremos algoritmos de ordenação iterativos e veremos como o uso
da estrutura de dados fila de prioridade leva a um algoritmo mais
eficiente. Além disso, revisitaremos e analisaremos a estratégia de
divisão e conquista para o projeto de algoritmos de ordenação.
Definiremos funções de hashing e projetaremos tabelas de
espalhamento baseadas em hashing para busca de dados eficiente.
Também, introduziremos a hierarquia de memória investigando suas
consequências e estudaremos a Árvore B para construção de índices
para busca.
Introduziremos o conceito abstrato de grafos e projetaremos
estruturas de dados correspondentes para modelar e representar
relacionamentos arbitrários entre objetos. Iremos estudar buscas em
grafos em profundidade e em largura e exemplificar o uso desses
percursos nos algoritmos de ordenação topológica e caminho mais
curto.
Vamos relembrar as estruturas de dados e algoritmos estudados e
discutir como escolher uma estrutura de dados para projetar
algoritmos robustos e eficientes. Também vamos conversar
um pouquinho sobre o curso e sobre o que vem pela frente.