SCC-601(Moacir)

==== TURMA EngComp 1 (MOACIR) ====

2014-2

Conteúdo e materiais de aula

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 - 14/08

   realloc e criacao de uma matriz com linhas infinitas (enquanto houver memoria XD)
   macros
   union: relação com ponteiros (apontando blocos de bytes)
   enum
   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)
   Eficiência - ver 1.o capítulo Garey & Johnson - Computers and Intractability
   Casos recursivos: linear e quadrático
   Passos para obtenção da complexidade computacional:
       Algoritmo
       Contagem manual ou relações de recorrência
       Notação assintótica

11.Funções de eficiência e equações de recorrência - 25/09

   Encontrando constantes experimentalmente
   Exemplos de equações de recorrência e suas formas fechadas

12. Prova I - 30/09

   assuntos: conteúdo das aulas 1 até 11.
   o foco será na interpretação de algoritmos/codigo com contagem de operações, funções de eficiência e codificação de algoritmos.
   sem consulta
   poderá ser utilizada calculadora (celular não)

13. Resolução da prova + Eficiência de algoritmos - 02/10

14. Eficiência de algoritmos e notações assintóticas - 07/10

15. Heap-sort: parte 1 - 09/10

   Max-heap e Min-heap
   Função de eficiência da função maxHeapify()

16. Heap-sort: parte 2 - 14/10

   Heapsort
   Comparação com o Merge-sort e o Insertion-sort (função de eficiencia de tempo e memória)
   Níveis da árvore e sua relação com a função de eificência do MaxHeap e Heapsort
   Introdução ao quick-sort

17. Quick-sort: parte 1 - 16/10

   Apresentação do algoritmo
   Escolha do pivô como elemento inicial
   código: aula17.tar.gz

18. Quick-sort: parte 2 - 21/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
   Limite inferior para algoritmos de ordenação baseados em comparação: aula gravada

19. Counting-sort - 23/10

   Counting-sort com chaves inteiras: aula gravada
   Counting-sort com registros
   Algoritmo bucket sort

• 28/10 - Feriado

20. Radix-sort - 30/10

   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

• 04/11 - Feriado

22. Busca: sequencial indexada, interpolada e considerações sobre árvores - 06/11

   Busca sequencial x sequencial indexada
   Busca interpolada x busca binária
   Considerações sobre árvores binárias de busca

23. Hashing: parte 1 - 11/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 - 13/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. Visão geral sobre paradigmas de projeto de algoritmos - 18/11

   Divisão e conquista
   Tentativa e erro (backtracking)
   Algoritmos gulosos
   Programação dinâmica

26. Aula extra de revisão - 19/11 * as 14h00 na sala 3-011 (ICMC)

   Algoritmos de ordenação, busca e problemas
   Hashing e problemas
   Contagem de operações e eficiência assintótica utilizando relações de recorrência

27. Prova 2 - 20/11

   Consulta 1 folha A4
   pode ser usada calculadora

28. Prova Substitutiva - 27/11

   SEM CONSULTA
   pode ser usada calculadora