SCC-601(Moacir)
==== TURMA EngComp 1 (MOACIR) ====
2014-2
Conteúdo
1. Apresentação e Introdução - 5/8
revisão sobre linguagem C e algoritmos modelo do computador (entrada, saida, processamento e memória) endereçamento da memoria em sistemas 32 e 64 bits ponteiros e tamanho de ponteiros em diversos sistemas: veja tabela com tamanhos em diferentes arquiteturas/sistemas noções de lvalue / rvalue código: aula01.tar.gz
2. Revisão: ponteiros, arranjos e alocacao dinâmica - 7/08
arranjos: formas de acessar os valores, alocação, lvalue de array não-modificável, aritmetica de ponteiros alocacao dinamica: malloc, calloc,free memory leak valgrind e depuração de gerenciamento de memória código: aula02.tar.gz
3. Revisão: mais ponteiros e alocação dinâmica - 12/08
ponteiro para ponteiro: casting de ponteiros passagem de parametros por referencia alocacao de vetores na stack e heap - diferenças operação bit-a-bit
4. Revisão: structs, macros, union, enum e typedef - 14/08
structs, ponteiros+structs, macros union: relação com ponteiros (apontando blocos de bytes) enum typedef código: aula04.tar.gz
- 18 A 22 - SEMCOMP17 !!!
5. Exercícios de Revisão - 26/08
- dia 28/08 não haverá aula
6. Análise de algoritmos e eficiência - 02/09
Eficiência de algoritmos Contagem de operações e função de eficiência com base no tamanho da entrada a ser processada Busca sequencial a partir do conteúdo de um arquivo gerado aleatoriamente código: aula06.tar.gz
7. Análise de algoritmos e eficiência - 04/09
Eficiência de algoritmos: busca sequencial e busca binária Métodos de ordenação: bubble-sort Entrevista de emprego (Obama - Google) código: aula07.tar.gz OBS: compilar também usando diretivas de otimização gcc: $ gcc -o prog source.c -O3 -march=native -march=native encontra flags "automaticamente", para visualizar use: gcc -march=native -E -v - </dev/null 2>&1 | grep cc1
- Semana da pátria: 8 a 12/9
8. Ordenação e análise de algoritmos - 16/09
Comparação entre dois métodos de busca e computadores Gráficos de funções de eficiência (complexidade computacional) Métodos de ordenação: insertion-sort Análise da complexidade dos algoritmos bubble-sort e insertion-sort Vídeos com demonstração: bubble-sort e insertion-sort Site com visualização: www.sorting-algorithms.com Recursão: primeiros exemplos código: aula08.tar.gz
09. Ordenação pelo método da divisão e conquista : mergesort - 18/09
Método de ordenação: merge-sort Paradigma de divisão e conquista Demonstração do algoritmo Etapa de intercalação (merge): análise da complexidade código: aula09.tar.gz
10. Ordenação pelo método da divisão e conquista : recursão - 23/09
Recursão e funcionamento na memória (pilha de chamadas recursivas) Implementação do merge-sort recursivo código: aula12.tar.gz
11. Prova I - 25/09
assuntos: conteúdo das aulas 1 até 10 sem consulta poderá ser utilizada calculadora (celular não)
12. Comparações e eficiência assintótica - 30/09
Notações O, Theta e Omega - slides
13. Heap-sort: parte 1 - 02/10
Max-heap e Min-heap Função de eficiência da função maxHeapify() Heapsort código: aula15.tar.gz
14. Heap-sort: parte 2 - 07/10
Comparação com o Merge-sort e o Insertion-sort (função de eficiencia de tempo e memória) Fila de prioridades usando max-heap Níveis da árvore e sua relação com a função de eificência do MaxHeap e Heapsort código (renomear para .zip para descompactar): aula16.tar.gz
15. Quick-sort: parte 1 - 09/10
Apresentação do algoritmo Escolha do pivô como elemento inicial código: aula17.tar.gz
16. Quick-sort: parte 2 - 14/10
Diferentes implementações do quick-sort Estratégias de escolha do pivô Comparação entre os algoritmos de ordenação: ver site www.sorting-algorithms.com código: aula18.tar.gz
17. Eficiência de algoritmos - 16/10
18. Eficiência assintótica de algoritmos recursivos: relações de recorrência - 21/10
19. Eficiência assintótica de algoritmos recursivos: relações de recorrência - 23/10
- 28/10 - Feriado
20. Counting-sort - 30/10
Limite inferior para algoritmos de ordenação baseados em comparação: aula gravada Counting-sort com chaves inteiras: aula gravada código: aula19.tar.gz
- 04/11 - Feriado
21. Counting-sort com registros e Bucket-sort - 06/11
Counting-sort com registros Algoritmo bucket sort Análise do Countingsort código: aula19.tar.gz
22. Radix-sort - 11/11
Exemplos usando inteiros e base 10 Exemplos e implementação usando inteiros de 32 bits e base 256 Análise do tempo de execução e memória código: aula22.tar.gz
23. Hashing: parte 1 - 13/11
Tabelas hash com endereçamento direto e endereçamento aberto Método da divisão Colisões e paradoxo do aniversário
24. Hashing: parte 2 - 18/11
Tabelas hash com endereçamento aberto Método da multiplicação Tratamento de colisão por sondagem linear e quadrática Escolha do tamanho da tabela Tabelas hash com encadeamento código: aula25.tar.gz
25. Busca: sequencial indexada, interpolada e considerações sobre árvores - 20/11
Busca sequencial x sequencial indexada Busca interpolada x busca binária Considerações sobre árvores binárias de busca
26. Visão geral sobre paradigmas de projeto de algoritmos - 25/11
Recursão e indução Divisão e conquista Tentativa e erro (backtracking) Algoritmos gulosos Programação dinâmica
27. Prova 2 - 27/11
Consulta 1 folha A4 pode ser usada calculadora