SCC-503(Yah)

SCC-0503 Algoritmos e Estruturas de Dados II

Aulas: Terças as 21h e Sextas as 19h - Sala 5-003

Professor: Mario Gazziro (Yah!) (yah [arroba] icmc . usp . br)

Horário Atendimento: Quintas das 16h as 19h - Sala 3-245

Estagiário PAE: Odair Bis Rosa (odair [arroba] icmc . usp . br)

Horário Atendimento: Terças e Quinta das 18h às 19h - Sala 3-101.

Monitor PEEG: Israel Jacob Galego Cassimiro (israelcass [arroba] gmail . com )

Horário Atendimento: Segunda, das 17:00 as 19:00 - Sala 3-101.

[1]: programa, avaliação, bibliografia, e outros.

Material Didático

1. Grafos - introdução
2. Grafos - estruturas de dados --> código: lista de arcos e lista de adjacencia em C
3. Grafos - percursos em grafos, grafos ponderados --> código: lista de adjacencia com ponderacao e percursos
4. Grafos - caminhos e coloracao de grafos
5. Grafos - ordenação topológica
6. Grafos - caminhos mínimos (ver também material sobre fila de prioridades do Prof. Siang Wun Song)
7. Grafos - árvores geradoras mínimas --> código: lista de adjacencia com dijkstra e prim
8. HDF5 Tutorial: [2]
9. Árvores B - parte 1
10. Árvores B - parte 2
11. Hashing Externo - até o slide 10

• Hashing: [3] Slides novos!

• Huffman: Slides prof. Paulovich [4]

Filas de Prioridade com HEAP (código extra para implementação do Huffman): [5]

• Árvore Rubro-Negras: [6] - Slides prof. Paulovich

• MD5

1. RFC (Request for Comments) 1321: [7]
2. Gerador de MD5 para frases pequenas: [8]
3. Passo-a-passo (NSF): [9]
4. Implementação: [10]

• SALSA20 - Cifra de Criptofrafia: [11]

TRABALHOS

Trabalho 1: Malha Ferroviária [12]

Data de Entrega: 30/04/2013, até 19:00. A apresentação do mesmo será no horário da aula

O trabalha deve ser feito individualmente; Identifique seu nome e número usp em cada inicio de arquivo fonte; A entrega do trabalho deverá ser feita através do código fonte. Quem entregar somente o arquivo compilado terá nota zero; O trabalho deve ser enviado para o monitor Odair odair@icmc.usp.br. Mande também uma cópia para Israel israelcass@gmail.com para não haver problemas.

Trabalho 2: Agência de Modelos 3D

Data de Entrega: 28/06/2013, até 19:00

Construir um software para uma agência de modelos, o qual armazena (em uma base HDF5) o nome, idade, altura, sexo do(a) modelo, assim como o modelo 3D se seu corpo.

Os modelos iniciais são fornecidos aqui: [13] [14]

e a leitura e visualização gráfica dos mesmos se dá utilizando a biblioteca de visualização VTK dentro do framework de janelas Qt, conforme especificações abaixo:

http://www.vtk.org/doc/nightly/html/classvtkPLYReader.html

http://www.vtk.org/Wiki/VTK/Examples/Cxx/IO/ReadPLY

GRUPOS:

G1 - Darlan * Vitor Guerra Pedro Josepetti Vitor Wender Rodrigo Pires

G2 - Diego * Eduardo Guilherme Renato Dhiogo

G3 - Mariana Luiz Roberto Junior Karina Padua * Suellen Aparecida Vitor Augusto Pastor

G4 - Alexis Sama * Jackson Eduardo Boccato Bruno Siqueira

G5 - Daniele Eduardo Cicliato Hiero * William Fagner Guilherme Nardari

G6 - Bruno Gonçalves Roman * Tais Naomi Watanabe Gabriel Souza Ribeiro Noel Ferreira Rafael A.T.

G7 - Wellington Vieira Victor Tokubo Eveton Fernando Hicaro * Fernando Neves

G8 - Andrey Gobbo Fernando Jurdi Guilherme Soares Jessica Janazi Marcos Demetrio Monteiro

G9 - Marcos Vinicius Costa Pedro dos Reis Junior Sidney de Oliveira Freitas Thiago Machado de Almeida

LISTAS

Lista 01: [15]

Lista 03 (base para Prova 1): [16]

Lista Hash - [17]

Lista Huffman - [18]

Provas

P1 (02/04/13) -> PROVA PASSOU PARA 05/04/13 em funcao do LUTO de 22/03!

P2 21/05/13 -> CANCELADA!! Serão 2 provas na disciplina!

P3 25/06/13

Avisos

NOTAS FINAIS: [19]

Recuperação: 16 de julho. Forma de avaliação: Apresentação do trabalho 2 (individual) com entrevista presencial (entrevistas no período noturno, a partir das 19:00h até as 21:00h, na sala 3-245 - minha sala)

=======================================================

---

Exercicios realizados na Revisão de Linguagem C na segunda aula:

Exercicios de 1 a 20 com exceção dos números: 4, 7, 9, 13 e 15 http://www.indiabix.com/online-test/c-programming-test/11

Applets animados demonstrando a a criação de árvores geradoras mínimas

http://weierstrass.is.tokushima-u.ac.jp/ikeda/suuri/dijkstra/Prim.shtml : [20]

Dias sem aula: 19 de abril (Scanner 3D SESC) e 28 de maio (Aleijadinho 3D)

Link Exercicios aula laboratório HDF5: http://www.hdfgroup.org/HDF5/Tutor/introductory.html

---

Aula Laboratório 16 de Abril

Base HDF5 para prática: [21]

Existem 2 datasets na base HDF: dois FIDs (frequency inductance decays) sobre dois experimentos diferentes em espectroscopia.

Obter a magnitude (sqrt(real^2+imag^2)) e a fase (arctan imaginario/real) desses sinais, escrevendo os resultados em dois novos datasets na mesma base.

Extra: importar um arquivo binário para dentro da base, utilizando a ferramenta H5IMPORT

Apostila

• Criação de Bibliotecas e Makefiles em C/C++

Bibliografia

• SEDGEWICK, R. Algorithms in C: part 5 -- graph algorithms, 3.ed., Addison-Wesley, 2002.
• FOLK, M.J. File Structures. Addison-Wesley, 1992.
• ZIVIANI, N. Projeto de Algoritmos, 3.ed. Cengage, 2010.
• CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Campus. 2002.

Leituras complementares

• FEOFILOFF, P. Algoritmos para Grafos, 2011. Disponível em: [22].