SCC-501(Moacir)

De CoteiaWiki

Informações Gerais

Título: Introdução à Ciência de Computação II (SCC-501) - Bacharelado em Informática

Professor: Moacir P. Ponti Jr (moacir at icmc dot usp dot br)

Aluno PAE: Paulo Henrique Ribeiro Gabriel (phrg at icmc dot usp dot br)

Horário de Aulas
quintas das 21h00 às 22h40
sextas das 19h00 às 20h40

Horário Atendimento
Professor: segundas 13-15h, sextas 18-19h (sala 4-117)
Aluno PAE: segunda das 17h30 as 19h00 (sala 4-001)
dúvidas nos trabalhos, marcar horário por e-mail.
Haverá atendimento extra no dia 20/10 às 17h30 na sala 3-010.

Programa

  • Análise de algoritmos
  • Recursividade (e relações de recorrência)
  • Algoritmos de ordenação em memória interna
  • Algoritmos de busca em memória interna
  • Hashing (espalhamento) em memória interna
  • Paradigmas de projeto de algoritmos

Cronograma Preliminar (com datas de provas e de entrega de trabalhos) *sujeito a alterações (atualizado em 17/11)

Provas: 27/08 (P1), 21/10 (P2) e 03/12 (P3)

Material Didático

- Apresentação da Disciplina

  1. Análise de Algoritmos - parte 1
  2. Análise de Algoritmos - parte 2
  3. Análise de Algoritmos - parte 3
  4. Recursão
  5. Análise de Algoritmos - parte 4
  6. Métodos de Ordenação em Memória Interna - parte 1
  7. Métodos de Ordenação em Memória Interna - parte 2 (quicksort)
  8. Métodos de Ordenação em Memória Interna - parte 3 (shellsort)
  9. Métodos de Ordenação em Memória Interna - parte 4 (mergesort)
  10. Métodos de Ordenação em Memória Interna - parte 5 (heapsort)
  11. Métodos de Ordenação em Memória Interna - parte 6 (counting e radixsort)
  12. Busca sequencial (diversas), binária e interpolada
  13. Hashing - parte 1
  14. Hashing - parte 2
  15. Projeto de Algoritmos

Códigos-fonte das aulas 8, 9, 10 e 11: Códigos-fonte

Site interessante que ilustra o funcionamento de algoritmos de ordenação: http://www.sorting-algorithms.com/

Vídeo com o "som" produzido pelos algoritmos de ordenação: http://youtu.be/t8g-iYGHpEA

Ver exemplos em código-fonte no site: http://sites.google.com/site/moacirponti/ seção "Teaching (aulas)"

Trabalhos Práticos

Os trabalhos serão submetidos apenas pelo sistema de submissão automática de trabalhos:

[Link para submissão dos trabalhos via SQTPM ]

Atenção: a saída do seu programa deverá ser exatamente como exemplificado no enunciado do trabalho, pois o sistema irá comparar apenas as saídas geradas. Antes de submeter, retire mensagens ao usuário, espaços, tabulações ('\t') e quebras de linha extras ('\n').

Critérios de avaliação

  1. Solução correta pela representação de entrada e saída dos dados
  2. Bom uso dos recursos do sistema (memória)
  3. Prática de modularização e uso de funções
  4. Clareza, endentação e uso de comentários

Trabalhos

0. Recursividade (teste do SQTPM) - aberto de 14/08 a 24/08

1. Algoritmos de Ordenação (A): Entrega por e-mail até 06/10 (ver observação acima).

2. Algoritmos de Ordenação (B): Entrega pelo SQTPM de 03/11 até 11/11.

3. Hashing: Entrega pelo SQTPM de 26/11 até 29/11

Desenvolvam os seus próprios arquivos com casos de teste adicionais, prevendo diferentes situações

3. Trabalho Substitutivo <- entre na página do trabalho: Entrega pelo SQTPM até 9/12.

Listas de Exercícios

  1. Análise de Algoritmos
  2. Recursividade
  3. Relação de Recorrência
  4. Algoritmos de Ordenação (A) (atualizada em 13/09/2010 15/09/2010)
  5. Algoritmos de Ordenação (B)
  6. Busca
  7. Hashing + Projeto de Algoritmos

Notas

  • Recuperação (2.a Avaliação):
Data: 9 de Fevereiro de 2011 (quarta-feira) das 19h00 as 21h30
*** Local: sala 3-102 ***
Critério de Aprovação (A1 = nota final no semestre e REC = nota da prova da recuperação):
  • A1+(REC/2,5) se REC >=7,5
  • Max{A1,REC} se REC < 5,0
  • 5,0 se 5,0 <= REC < 7,5.
A prova será no estilo da última prova da disciplina (P3), mas incluindo todo o conteúdo de ICC2, inclusive análise de algoritmos, algoritmos de busca e ordenação e paradigmas de projeto de algoritmos.

Bibliografia

  • CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Campus. 2002.
  • ZIVIANI, N. Projeto de algoritmos: com implementações em Pascal e C. 2.ed., Thomson, 2004.
  • FEOFILOFF, P. Projeto de algoritmos, Campus, 2008.
  • FEOFILOFF, P. Projeto de algoritmos: em C, Disponível em: http://www.ime.usp.br/~pf/algoritmos/.

Leituras complementares

  • FEOFILOFF, P. Minicurso de Análise de Algoritmos, 2010. Disponível em: http://www.ime.usp.br/~pf/livrinho-AA/.
  • DOWNEY, A.B. Analysis of algorithms (Cap. 2), em: Computational Modeling and Complexity Science. Disponível em: http://www.greenteapress.com/compmod/html/book003.html.
  • KNUTH, D. The Art of Computer Programming, vol.3: sorting and searching, 2.ed. Addison-Wesley, 1998.
  • KNUTH, D. Selected Papers on Analysis of Algorithms, CSLI Lecture Notes, n.102, 2000.
  • SCHILD, H. C Completo e Total, 3.ed. Pearson, 1997.
  • Para verificar memory leaks em executáveis c/c++ [1]
 * $ valgrind --leak-check=full ./seu_programa_executavel
Disponível em "http://wiki.icmc.usp.br/index.php?title=SCC-501(Moacir)&oldid=17154"