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