Mudanças entre as edições de "SCC-601(Moacir)"
Linha 2: | Linha 2: | ||
2014-2 | 2014-2 | ||
− | Conteúdo | + | Conteúdo e materiais de aula |
1. Apresentação e Introdução - 5/8 | 1. Apresentação e Introdução - 5/8 | ||
Linha 28: | Linha 28: | ||
operação bit-a-bit | operação bit-a-bit | ||
− | 4. Revisão: structs, macros, union, enum | + | 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) | union: relação com ponteiros (apontando blocos de bytes) | ||
enum | enum | ||
− | |||
código: aula04.tar.gz | código: aula04.tar.gz | ||
− | * | + | ** 18 A 22 - SEMCOMP17 !!! |
5. Exercícios de Revisão - 26/08 | 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 | 6. Análise de algoritmos e eficiência - 02/09 | ||
Linha 59: | Linha 59: | ||
-march=native encontra flags "automaticamente", para visualizar use: gcc -march=native -E -v - </dev/null 2>&1 | grep cc1 | -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 | 8. Ordenação e análise de algoritmos - 16/09 | ||
Linha 83: | Linha 83: | ||
Recursão e funcionamento na memória (pilha de chamadas recursivas) | 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. | + | 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 | 12. Prova I - 30/09 | ||
− | assuntos: conteúdo das aulas 1 até | + | 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 | sem consulta | ||
poderá ser utilizada calculadora (celular não) | poderá ser utilizada calculadora (celular não) | ||
− | 13. Heap-sort: parte 1 - | + | 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 | Max-heap e Min-heap | ||
Função de eficiência da função maxHeapify() | 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) | 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 | 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 | Apresentação do algoritmo | ||
Linha 116: | Linha 124: | ||
código: aula17.tar.gz | código: aula17.tar.gz | ||
− | + | 18. Quick-sort: parte 2 - 21/10 | |
Diferentes implementações do quick-sort | Diferentes implementações do quick-sort | ||
Estratégias de escolha do pivô | Estratégias de escolha do pivô | ||
Comparação entre os algoritmos de ordenação: ver site www.sorting-algorithms.com | 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. | + | 19. Counting-sort - 23/10 |
− | |||
− | |||
− | |||
− | |||
− | |||
Counting-sort com chaves inteiras: aula gravada | Counting-sort com chaves inteiras: aula gravada | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Counting-sort com registros | Counting-sort com registros | ||
Algoritmo bucket sort | Algoritmo bucket sort | ||
− | |||
− | |||
− | + | * 28/10 - Feriado | |
+ | |||
+ | 20. Radix-sort - 30/10 | ||
Exemplos usando inteiros e base 10 | Exemplos usando inteiros e base 10 | ||
Linha 153: | Linha 146: | ||
código: aula22.tar.gz | código: aula22.tar.gz | ||
− | 23. Hashing: parte 1 - | + | * 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 | Tabelas hash com endereçamento direto e endereçamento aberto | ||
Linha 159: | Linha 160: | ||
Colisões e paradoxo do aniversário | Colisões e paradoxo do aniversário | ||
− | 24. Hashing: parte 2 - | + | 24. Hashing: parte 2 - 13/11 |
Tabelas hash com endereçamento aberto | Tabelas hash com endereçamento aberto | ||
Linha 168: | Linha 169: | ||
código: aula25.tar.gz | código: aula25.tar.gz | ||
− | 25 | + | 25. Visão geral sobre paradigmas de projeto de algoritmos - 18/11 |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Divisão e conquista | Divisão e conquista | ||
Tentativa e erro (backtracking) | Tentativa e erro (backtracking) | ||
Linha 182: | Linha 176: | ||
Programação dinâmica | Programação dinâmica | ||
− | 27. Prova 2 - | + | 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 | Consulta 1 folha A4 | ||
+ | pode ser usada calculadora | ||
+ | |||
+ | 28. Prova Substitutiva - 27/11 | ||
+ | |||
+ | SEM CONSULTA | ||
pode ser usada calculadora | pode ser usada calculadora |
Edição atual tal como às 17h38min de 29 de julho de 2015
==== 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