Bacharelado em Ciências de Computação(203) e Engenharia de Computação(603)
1º Semestre - 2010
ICMC - USP - São Carlos
email: jbatista at icmc usp br -- João do E.S. Batista Neto
email: glenda at icmc usp br -- Glenda Michele Botelho (PAE)
NOTA e MÉDIA PROVAS (SCC203): aqui
NOTA e MÉDIA PROVAS (SCC603): aqui
PROVA REC ---> Quinta-Feira, dia 5, das 13:00 - 15:30hs, SALA 3-104
- Apresentação do curso, avaliação, excentricidades do professor, etc..
- GRAFOS
- Definições
- Representações e operações TAD
- Busca em Profundidade e Largura
- Aplicações de busca em grafos
- Ordenação Topológica e aplicações
- Caminhos mínimos
- Árvores Geradoras Mínimas (MST)
- Arquivos
- Fundamentos: estrutura física, Sistemas de arquivos
- Organização de campos e registros
- Acesso Direto, compactação
- Remoção de Registros
- Índices
- Processamento Cossequencial
- Árvores-B e variações
- Árvores não binárias: definição e aplicações
- Árvores B: inserção, remoção, busca
- Hashing externo
[Índice]
[Índice]
Aula 1
Apresentação da Disciplina e introdução a Grafos
Extras...
Aula 2
Grafos: parte 2
- Grafos: Estruturas de Dados e caminhamento
- Estrura de Dados para Grafos
- Material online Prof. Gustavo Nonato
- Caminhamento em grafos: profundidade
- Caminhamento em grafos: largura
- Trabalhinho para tirar a ferrugem:
- Descrição. Arquivo do grafo
- Por que não usar o CODEBLOCKS???
- dica de OURO: utilize Linux (você é um ser humano ou é um rato ????)
- Se for pra Windows, pegue a versão que já vem com o GCC. É fácil instalar..
- dica de OURO 2: utilize o depurador gdb (ou ddd - versão gráfica, maravilhosa!)
- Data de entrega 7 dias, a partir da aula
- DESAFIO :
- Descrição. Arquivo do grafo
- Escreva um programa, usando o ferramental acima (escolha apenas um TAD), que verifique se existe uma
rota entre as cidades c1 e c2, de comprimento x
- Solucao
- Lembre-se: entradas sempre por argumentos. Neste caso prog_executavel <arquivo.txt c1 c2 x >
Aula 3
Grafos
- Heuristica/Algoritmos Gulosos
- Caminho mínimo / O algoritmo de Dijkstra
- Material do Gustavo
- Material do Kruse
- Lista de exercícios Grafos tres
- O algoritmo de Dijkstra animação
- Dijkstra funciona para grafos cujas arestas têm peso negativo
- Alg. Belmman-Ford???
não
Aula 4
Grafos - Árvore geradora Mínima
Aula 5
Grafos - Ordenação Topológica
- Definição
- Aplicações: Redes de Atividades, ordenação,
- Algoritmo: ordenação topológica em Profundidade
- Material de referencia
Aula 6
Discos, Arquivos, etc...- Conceitos Gerais
- Como é o processo de : BOOT de um computador??
- Booting : Wikipedia
- Geometria de : Discos
- Setores, trilhas, cilindros, etc Disco1 , Disco2
, Disco3
- Guia do PC - Ótimo sitio (embora descontinuado!) sobre (quase)
tudo do
PC
- FAT especificação
- Programinha que gera uma imagem no formato .pgm (binário ou ASCII). Note como é simples misturar
dados no formato ASCII e binário no mesmo arquivo. Note também a diferença no tamanho do arquivo
gerado para cada um dos tipos. Por que?? aqui
Aula 7
Arquivos - Armazenamento Secundário, tempo de acesso, etc.
Aula 8
Arquivos - Estruturas de Arquivo
- Arquivos 1 (Caps 5 e 6 - Folk)
Aula 9
Arquivos - Compressão
Aula 10
Arquivos - Indices
Momento "cultural" Barao Vermelho tb é cultura 1
Momento "cultural" Barao Vermelho tb é cultura 2
Aula 11
Processamento Cossequencial
Momento "cultural" Tchaikovsky é cultura
(concerto violino)
Momento "cultural" Tchaikovsky é cultura
(concerto piano)
Aula 12
Árvores - B
Aula 13
Árvores - B
Representação de uma Árvore 5-way
Representação de uma Árvore-B de ordem 5
Exemplo de inserção em Árvore-B de ordem 5
Exemplo de remoção em Árvore-B de ordem 5
Codigo Algoritmo de Insercao em Arvore - B
Codigo Algoritmo de Remoção em Arvore - B
[Índice]
Informações gerais para entrega dos trabalhos
- Entregar no formato .zip, .tar.gz, ou .rar
- ANEXAR UM ARQUIVO grupo.txt com os NOMES e NRO USP dos membros
- !!!! TRABALHOS SEM o arquivo grupo.txt NÃO SERAO CORRIGIDOS e valerão ZERO !!!!
- Descrição e Entrega: Online via Xexeu
- Trabalhos serão entregues em grupo de duas pessoas ou individualmente
- Trabalhos podem ser entregues com atraso, mas com "desconto" na nota (via de regra: -1,0 ponto por
dia)
- Trabalhos iguais ou copiados terão a mesma nota = Zero
Critérios para avaliação de projetos
- Funcionamento correto e estruturacao em classes: 75%
- documentação interna: 10%
- Interface (facilidade de uso, legibilidade):15%
Projeto Nro UM
Projeto Nro DOIS
- Arquivos e Índices
- Descrição: aqui
- Importante 1: VOCÊ TRATOU A QUESTÃO DA CONSISTÊNCIA ENTRE O ARQUIVO
PRINCIPAL E O ARQUIVO DE ÍNDICE PRIMÁRIO?? LEMBRE-SE DE QUE O ARQ. DE
ÍNDICE PRIMÁRIO É MANIPULADO NA MEMÓRIA E APENAS ATUALIZADO EM DISCO
QUANDO O PROGRAMA TERMINA. VOCÊ IMPLEMENTOU A QUESTÃO DOS FLAGS???
- Importante II: BONUS NA NOTA PARA QUEM FIZER O SEGUINTE> Implemente também
os índices secundários para carro. Assim, é possível fazer o seguinte
tipo de consulta: liste todos os "fuscas" existentes no banco, sem
fazer na força bruta (que seria percorrer linearmente o arquivo
principal, verificando qual registro é de carro=fusca). Esta pesquisa
seria feita VIA INDICE SECUNDÁRIO (sec_carro.ndx). Você terá que manter
este arquivo consistente com os demais, ou seja, nas operações de
inserção, remoção e alteração, o arquivo deve ser atualizado de acordo
assim como foi feito para o índice primário. À exemplo do arquivo
primário, o arquivo secundário pode ser manipulado em memória principal.
- Tabela Inicial com os dados de entrada
- Programas de auxilio para ler uma linha da tabela e devolver os 3 campos requisitados aqui
- DATA DE ENTREGA: a combinar
Projeto Nro TRÊS
- Árvore B
- Descrição: aqui
- DATA DE ENTREGA:
[Índice]
3 Provas, sem substitutiva (e com pesos diferentes - 2, 2 e 3, respectivamente)
Média Final = (Med_Prova + Med_Projetos)/2
- Se Med_prova E Med_Projetos >= 5,0. Caso contrário, Média Final = MENOR(Med_Prova, Med_Projetos)
Med_Projetos = (Trab1 + Trab2 + Trab3)/3
- Se Trab1 E Trab2 E Trab3 >= zero. Caso contrário, Med_Projetos = 0 (ZERO)
IMPORTANTE: Se não entregar ou tirar zero em UM dos trabalhos, reprovado sem REC!
Formas alternativas de aprovação na disciplina (dispensa os trabalhos e provas acima)
[Índice]
[Índice]
Bibliografia Básica
TENEMBAUM,A.M., et all. Data Structures Using C, Prentice-Hall, 1990
FOLK, M., ZOELLICK, B. File Structures. Addison-Wesley, 1998
WIRTH,N. Algorithms + Data Structures = Programs, Prentice-Hall, 1986
KRUSE, R. Data Structure and Programming Design. Prentice Hall, 1994
HOROWITZ e SAHNI - Fundamentos de Estrutura de Dados, Rio de Janeiro, Campus, 1986
TREMBLAY, S. - An Introduction to Data Structures with Applications, 1976
CORMEN T.H., LEISERSON C.E, RIVEST R.L. - Introduction to Algorithms, The MIT Elect. Engineering and Computer Science Series, 1997.
[Índice]
[Índice]
