Algoritmos e Estrutura de Dados [if969]

Semestre Letivo 2012.1

Local: Centro de Informática, horários: segunda (17:00-18:40), sala D-002 e quarta (18:50-20:30), Lab5.

Sistema Corretor:

Endereço do sistema corretor para submissão de exercícios: http://moreno.cin.ufpe.br/~if969/

Atenção:

Esta comunidade contém apenas notas de aulas superficiais. Estas notas não devem ser utilizadas como livro-texto. Um bom desempenho na disciplina depende muito do estudo mais profundo dos livros e, principalmente, da prática no computador.

Ementa:

Ensinar os conceitos básicos de algoritmos; algoritmos e estruturas de dados dinâmicas básicas; técnicas de construção de algoritmos; conceitos de complexidade de algoritmo. Este curso visa trabalhar principalmente introdução a algoritmos e estruturas de dados, incluindo projeto, análise e implementação na linguagem Java.

Apoio

  • Arley Ramalho Rodrigues Ristar (arrr2)
  • Lairson Emanuel Rodrigues de Alencar Oliveira (lerao)
  • Juliandson Estanislau Ferreira (jef)
  • Marcela Pereira de Oliveira (mpo)

Bibliografia sugerida:

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronaldo L.; Stein, Clifford; Introduction to Algorithms – Third Edition, MIT Press, 2009. [Supplemental Content] [google books]

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronaldo L.; Stein, Clifford; Algoritmos: teoria e prática: tradução da 2ª edição [americana], Vandenberg D. de Souza,  Ed. Campus, 2002.  ISBN 85-352-0926-3. [buscapé]

Bibliografia Complementar:

  • Introduction to the Java Collections Framework (ótimo tutorial da Sun sobre coleções, não deixe de ler).
  • Michael T. Goodrich & Roberto Tamassia. Estruturas de Dados e Algoritmos em Java. 4ª edição. Ed. Bookman, 2007 – ISBN 9788560031504 [Google Books]
  • TENENBAUM, A. M.; LANGSAN, Y.; AUGENSTEIN, M. J. Estruturas de Dados Usando C. São Paulo: Makron Books, 1995.
  • ZIVIANI, Nivio. Projeto de Algoritmos. Editora Nova Fronteira, 2004.
  • SEDGEWICK, Robert. Algorithms in C++. Addison Wesley, 2000.
  • MANBER, Udi. Introduction to Algorithms: A Creative Approach. Addison Wesley, 1989.
  • SEDGEWICK, Robert. and Flajolet, Philippe. An Introduction to the Analysis of Algorithms. Addison Wesley, 1996.
  • How to Think Like a Computer Scientist – Python Version [link]

Boas Práticas:

  • A. Hunt, D. Thoma,. The Pragmatic Programmer, Addison Wesley, 2000
  • A. Oram, G. Wilson, Beautiful Code, O’Reilly, 2007
  • R. C. Martin, Clean Code, Prentice Hall, 2009

Web:

  • Introduction to Algorithms, Third Edition Supplemental Content [link]
  • Data Structures and Algorithms in Java(4th edition) [link]
  • Apostila POO – Java – Eclipse [link]
  • Livro Virtual de Estruturas de Dados do prof. Prof. Dr. Roberto Ferrari – UFSCar [link do site]
  • JEDI (Java Education and Development Initiative) - DFJUG – Módulo 3: Estrutura de Dados [link do curso]
  • MIT OpenCourseWare - 6.006 Introduction to Algorithms, Spring 2008 [link do curso]
  • Algorithm Education in Python [link]
  • Invent Your Own Computer Games with Python [link]
  • Aprenda Computação com Python [link]

Lista de emails:

Software:

Para o aprendizado do conteúdo da disciplina, é fundamental que os alunos pratiquem programação de computadores. Para tanto, é necessário instalar um ambiente de desenvolvimento Java. Esta página disponibiliza 2 ambientes de desenvolvimento distintos:

Avaliação:

Mini-provas – Programação
Mini-provas anteriores – 2011.2
  1. Mini-prova 01 [link] – release: 01/09, data de entrega: 16/09, 12:00
  2. Mini-prova 02 [link] – release: 19/09, data de entrega: 02/10, 23:59
  3. Mini-prova 03 [link] – release: 06/10, data de entrega: 19/10, 23:59
  4. Mini-prova 04 [link] – release: 24/10, data de entrega: 02/11, 23:59
  • Planilha de Acompanhamento detalhado das Mini-Provas 2011.2 [link]

Provas anteriores

Projetos
  • Página dos projetos de 2011.1 [link]
  • Página dos projetos de 2011.2 [link]

Aulas práticas (créditos profa. Katia Silva Guimarães - IF672 – Algoritmos e Estruturas de Dados)

  • É terminantemente proibido o uso de imports no código;
  • Evitem usar readchar(), readline() e print(“\n”) em Java;
  • Vocês devem apenas se preocupar nas entradas em ler números e strings;
  • Arquivos (Entrada e Saída) em Java [transparências]
  • Download da classe Arquivo.java [link]

Plano de aulas:

Aula Data Local Descrição Anexos
1 05/03 Apresentação dos Objetivos da Disciplina [link] e Conceitos básicos de programação Java [link] - Sugestão: The Design Patterns Page [link]
2 07/03 Projeto Orientado a Objetos em Java [link]
3 12/03 Aula de Revisão de Java - Sugestão: listas de exercício 1 [link] e 2 [link]
- Exercício 01 – String de conexão [link]
4 14/03 Fundamentação: Algoritmos, para que servem? [link] - Sugestão: Leitura dos capítulos 1 e 2 do livro do Cormen
- InsertionSort (python) [link]
5 19/03 Notações [link] e Recorrência [link] - Sugestão: Leitura dos capítulos 3 e 4 do livro do Cormen
6 21/03 Lab Exercícios Práticos de Revisão – Lista #0
7 26/03 Algoritmos de Ordenação: Heap Sort [link] - Atenção: Exercícios no último slide
- Revisão: Ordenação: Bubble Sort; Selection Sort; Insertion Sort; Merge Sort [link]
- Sugestão: Leitura do Capítulo 6 do livro do Cormen & Hints for implementing HeapSort & Priority Queues in Python [link]
- HeapSort (python) [link]
8 28/03 Algoritmos de Ordenação: Quick Sort [link] - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 7 do livro do Cormen
- QuickSort (python) [link]
- RandomizedQuickSort (python) [link]
9 02/04 Exercícios Práticos de Revisão – Lista #01
10 04/04 Estrutura de Dados Lista  [link] - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 10 do livro do Cormen
- Na web: JVALL: Java Automated Linked List
- TAD List e TAD Node (python) [link]
- Driver para teste da TAD List (python) [link]
11 09/04 Estrutura de Dados Pilha e Fila  [link] - Atenção: Exercícios nos últimos slides
- Sugestão: Leitura do Capítulo 10 do livro do Cormen
- Na web: Demonstração de Pilha por LSE (by UC Prof. John Franco)[link]
- TAD Pilha (python) [link]
- Driver para teste da TAD Pilha (python) [link]
12 11/04 Tabelas Hash (Parte I) [link]  - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 11 do livro do Cormen
13 16/04 Lab Exercícios Práticos de Revisão – Lista #02
14 18/04 Tabelas Hash (Parte II) [link] - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 11 do livro do Cormen
15 23/04 Aula de Revisão
16 25/04 Primeiro Exercício Escolar
17 07/05 Lab Prova Prática – Lista #03
18 09/05 Estruturas de Dados Árvores Genéricas [link] e Binárias  [link] - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 10 (Seção 4) e 12 do livro do Cormen
- Na web: Demonstração de árvore genérica (by UC Prof. John Franco)[link]; Busca em Árvores Binárias [link]; Árvores invertidas [link]; Árvores Binárias de Pesquisa [link]; Inserção e remoção em Árvores Binárias [link]
- TreeNode (python) [link]
- Tree (python) [link]
- DriverTrees (python) [link]
19 14/05 Estruturas de Dados Árvores AVL [link]  - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 12 do livro do Cormen
- Na web: Demonstrações (by UC Prof. John Franco): Inserção/remoção em árvores AVL [link]; Rotação trinodo [link]
20 16/05 Estruturas de Dados Árvores Red-Black [link] - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 13 do livro do Cormen
- Na web: Demonstrações (by UC Prof. John Franco): Inserção/remoção em árvores rubro-negras [link] [código]
- Árvore rubro-negra (Wikipedia)
- Red/Black Tree Demonstration (link)
- Red-Black Trees Animation(link)
- RBTree.py The Red/Black Trees Module
- RedBlack Balanced Tree Searching and Sorting Library by Damian Ivereigh
- Red black tree (Python recipe)
21 21/05 Estruturas de Dados Grafo: Introdução [link] - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 22 do livro do Cormen
22 23/05 Estruturas de Dados Grafo: Busca em Profundidade [link] e em Largura [link] - Atenção: Exercícios no último slide
- Sugestão: Leitura do Capítulo 22 do livro do Cormen
23 28/05 Complexidade e Completude [link] - Sugestão: Leitura do Capítulo 34 do livro do Cormen
24 30/05 Exercícios Práticos de Revisão – Lista #04
25 04/06 Acompanhamento do Projeto
26 06/06 Acompanhamento do Projeto
27 11/06 Acompanhamento do Projeto
28 13/06 Acompanhamento do Projeto
29 18/06 Segundo Exercício Escolar
30 20/06 Apresentação do Projeto
31 25/06 Prova Final + 2ª Chamada


  1. Nenhum comentário ainda.
  1. 4 de abril de 2011 às 9:33 | #1
Os comentários estão desativados.
Seguir

Obtenha todo post novo entregue na sua caixa de entrada.

Junte-se a 1.661 outros seguidores

%d blogueiros gostam disto: