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. Comparações e eficiência assintótica - 25/09

   Notações O, Theta e Omega - slides

12. Prova I - 30/09

   assuntos: conteúdo das aulas 1 até 10
   sem consulta
   poderá ser utilizada calculadora (celular não)

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