SCC-201(Moacir)

Informações Gerais

Título: Introdução à Ciência de Computação II (SCC-201) - Bacharelado em Ciências de Computação

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

Aluna PAE: Pâmela Michele Cândida (pamela at icmc usp br; sala 1-008)

Monitor especial: Gabriel Coelho (amorimdecoelho at gmail com)

Horário de Aulas
segundas e quartas das 08h10 às 09h50 (sala 4-001)

Horários de Atendimento

Professor: segundas 13-15h, sextas 18-19h (sala 4-117)

Aluna PAE: segunda das 17h30 às 19h00 (sala 4-001)

dúvidas nos trabalhos, marcar horário por e-mail.

enviar mail com o trabalho 1 com o assunto: [bcc]trab1 até 06/10/2010

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

Provas: 25/08 (P1), 20/10 (P2) e 06/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

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

Site interessante que ilustra o funcionamento de algoritmos de ordenação: http://cg.scs.carleton.ca/~morin/misc/sortalg/

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 até 06/10 para pamela at icmc.usp.br

• Enunciado (pdf) versao nova, corrigida em 15/09
• Casos de Teste (tar.gz) versao nova, corrigida em 15/09

1. Algoritmos de Ordenação (B)
2. Hashing

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
8. Projeto de Algoritmos

Notas

• Prova 1
• Prova 2
• Prova 3

• Trabalho 1
• Trabalho 2
• Trabalho 3
• Trabalho 4
• Trabalho 5

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.