Scc-201 2017(moacir)
Site para submissão dos trabalhos http://run.codes
Atendimento, PAE e monitoria:
Grupo Google para dúvidas e atendimento: icc2_bcc2017@googlegroups.com
- emails na lista são recebidos por todos os monitores, professores e PAEs, agilizando a resposta
- obs: para entrar no grupo você pode um "subscribe" email para: icc2_bcc2017+subscribe@googlegroups.com
(você deve então responder a confirmação de inscrição no grupo)
Professor: sala 3-245 - Quartas-feiras das 13h30-15h30
PAE: -Yule Vaz - Térreo do Bloco 3 (perto do elevador e da lousa) - quartas das 14hs às 16hs -Lucas Pagliosa - Térreo do Bloco 3 (perto do elevador e da lousa) - segundas das 14hs às 16hs -Ricardo Fuzeto - Térreo do Bloco 3 (perto do elevador e da lousa) - sextas das 14hs às 16hs OBS: Atendimento PAE é feito por demanda (enviar email na lista para marcar).
Monitores - Lucas Fernandes Turci: lucas.turci@usp.br OBS: Atendimento é feito por demanda (enviar email na lista para marcar).
Conteúdo e materiais de aula
1. Apresentação e Introdução - 31/7
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 noções de lvalue / rvalue arranjos: formas de acessar os valores
2. Revisão: ponteiros, arranjos e alocacao dinâmica - 03/08
alocacao dinamica: malloc, calloc,free memory leak valgrind e depuração de gerenciamento de memória recursão
3. Análise de algoritmos e eficiência - 07/08
Recursão 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
4. Análise de algoritmos e eficiência - 10/08
Eficiência de algoritmos: busca sequencial e busca binária Recursão: primeiros exemplos com busca binária recursiva e comparação de tempo de execução
- 11 A 18 - SEMCOMPi!!!
5. Ordenação e análise de algoritmos - 21/08
Métodos de ordenação: bubble-sort
Entrevista de emprego (Obama - Google)
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
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
6. Funções de comparação e ordenação pelo método da divisão e conquista : mergesort - 24/08
Implementação do método de ordenação: merge-sort Demonstração do algoritmo
7. Ordenação pelo método da divisão e conquista : mergesort recursivo- 28/08
Etapa de intercalação (merge): análise da complexidade
8. Funções de eficiência e equações de recorrência - 31/08
Recursão e funcionamento na memória (pilha de chamadas recursivas) Funções de comparação entre insertion, selection, bubble e merge substituindo os operadores (usando ponteiro para função) Encontrando constantes experimentalmente - ajuste de polinômio usando gnuplot Encontrando as constantes de funções de eficiência
- Semana da pátria: 4 a 8/9
9. Eficiência de algoritmos - 11/09
Casos recursivos: logaritmico, linear, quadrático, log-linear
Eficiência - ver 1.o capítulo Garey & Johnson - Computers and Intractability
Exemplos de equações de recorrência e suas formas fechadas
Passos para obtenção da complexidade computacional:
Algoritmo
Contagem manual ou relações de recorrência
Notação assintótica
10. Eficiência de algoritmos e notações assintóticas (1) - 14/09
11. Eficiência de algoritmos e notações assintóticas + recorrência (2) - 18/09
12. Heap-sort - 21/09
Max-heap e Min-heap como filas de prioridade Função de eficiência da função maxHeapify() Algoritmo Heapsort
- 2/10 não haverá aula
13. Quick-sort - 28/09
Algoritmo quick-sort Comparação entre os algoritmos de ordenação: ver site www.sorting-algorithms.com
14. Prova 1 - 05/10
o foco será na interpretação de algoritmos/codigo com contagem de operações e escrita de algoritmos. CONSULTA DE 1 Folha A4 calculadora pode ser usada (computador/celular/tablet/smartwatch NÃO) individual
15.Quicksort: parte 2 - 09/10
Diferentes implementações do quick-sort Estratégias de escolha do pivô Cálculo da eficiência do quick-sort probabilístico
16. Heap-sort: parte 2 - 16/10
Eficiência do heapsort Níveis da árvore e sua relação com a função de eificência do MaxHeap e Heapsort Limite inferior para algoritmos de ordenação baseados em comparação
- 16 e 19/10 não haverá aula
17. Counting-sort - 23/10
Counting-sort com chaves inteiras: aula gravada
18. Bucket Sort e Radixsort - 26/10
Counting-sort com registros
19. Radixsort - 30/10
Exemplos usando inteiros e base 10 Exemplos e implementação usando inteiros de 32 bits e bases com potencia de 2 variaveis 256 Testes experimentais comparando os algoritmos implementados
20. Busca: indexada, interpolada e considerações sobre árvores - 06/11
Busca interpolada x busca binária x busca indexada Considerações sobre árvores binárias de busca
- 9/11 não haverá aula
21. Hashing: parte 1 - 13/11
Tabelas hash com endereçamento direto/aberto Método da divisão Colisões e paradoxo do aniversário
22. Hashing: parte 2 - 16/11
Método da multiplicação Hashing de chaves compostas: strings, double, etc.
23. Hashing: parte 3 - 20/11
Tabelas hash com encadeamento Hashing universal Outras questões sobre hashing Artigo: Denial of Service via Algorithmic Complexity Attacks: external link: https://www.usenix.org/legacy/event/sec03/tech/full_papers/crosby/crosby.pdf
24. Aplicações - 27/11
25. Revisão e exercícios - 30/11
26. Prova 2 - 04/12
SEM CONSULTA individual calculadora pode ser usada (computador/celular/tablet/smartwatch NÃO)
27. Revisão e fechamento da disciplina - 07/12
Revisão da prova e fechamento da disciplina
