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.
Índice
Material Didático
- Grafos - introdução
- Grafos - estruturas de dados --> código: lista de arcos e lista de adjacencia em C
- Grafos - percursos em grafos, grafos ponderados --> código: lista de adjacencia com ponderacao e percursos
- Grafos - caminhos e coloracao de grafos
- Grafos - ordenação topológica
- Grafos - caminhos mínimos (ver também material sobre fila de prioridades do Prof. Siang Wun Song)
- Grafos - árvores geradoras mínimas --> código: lista de adjacencia com dijkstra e prim
- HDF5 Tutorial: [2]
- Árvores B - parte 1
- Árvores B - parte 2
- 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
- RFC (Request for Comments) 1321: [7]
- Gerador de MD5 para frases pequenas: [8]
- Passo-a-passo (NSF): [9]
- 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
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].
