Atualizada para o semestre 2018-1.

Algoritmos e Programação III

Avaliação | Trabalhos | Atividades Práticas Supervisionadas | Avaliação | Cronograma | Material de Apoio

A disciplina de Algoritmos e Programação III tem como objetivo principal, desenvolver os conhecimentos sobre estruturas de dados não-lineares, algoritmos de ordenação, e a compreensão de suas características para a sua correta aplicação no desenvolvimento de sistemas. Nesta disciplina são estudados os principais algoritmos de ordenação, sua implementação e suas características. São estudadas estruturas de dados com acesso não-linear, como tabelas de espalhamento (Hashtables), árvores, e grafos, e algoritmos que trabalham com estas estruturas.

Entre os conteúdos estudados, encontram-se:

  • Conceitos básicos de algoritmos como recursividade, e comparação de algoritmos baseado na notação Big-O.
  • Compreensão e avaliação de algoritmos de ordenação.
  • Tabelas de Espalhamento abertas e fechadas.
  • Diferentes modelos de tabelas de espalhamento: Cuckoo Hashing, Robin Hood Hashing e Hopscotch Hashing.
  • Conceitos, aplicações e representações de árvores.
  • Árvores Binárias de Pesquisa e modelos auto-balanceáveis (AVL e Red-Black).
  • Modelos de árvores para diferentes aplicações, como heaps, Árvores B, Radix, e KD.
  • Código de Huffman.
  • Conceitos, aplicações e representações de Grafos.
  • Busca, conectividade e topologia em grafos.
  • Árvore Geradora Mínima, e os algoritmos de Prim e Kruskal.
  • Algoritmo para encontrar o menor caminho em um grafo, utilizando o algoritmo de Dijkstra.

Avaliação

Nesta disciplina, o aluno deve demonstrar a capacidade de compreender, alterar e desenvolver aplicações que utilizam estruturas de dados não-lineares.

Para isso, serão realizadas duas provas, dois trabalhos com escopo definido, e um projeto de implementação cujo escopo será proposto pelo aluno.

Linguagens de Programação

Na disciplina serãoapresentados exemplos utilizando a linguagem de programação Java (versão 8).

Para a implementação dos trabalhos, o aluno poderá escolher entre as linguagens C/C++ (C11/C++14), Python (2.7 ou 3.3+), Javascript (utilizando Node.js), Ruby (2.3), Lua (5.3), Objective-C ou Swift.

Ao utilizar qualquer linguagem de programação, nenhuma dependência extra pode ser requerida. Por exemplo, componentes que não sejam instalados a partir do processo de instalação padrão e mínimo dos compiladores ou interpretadores da linguagem. Todos os trabalhos devem executar a partir de um console (linha de comandos), e os trabalhos podem requerer a criação ou utilização de arquivos com formatos texto (normalmente CSV) ou binários.

Assuma, para a avaliação do trabalho, que o computador onde o sistema será executado, contém a instalação mínima necessária para a linguagem escolhida, e que este é um computador stand-alone, ou seja, não está conectado a nenhuma rede.

Trabalhos

Os enunciados dos trabalhos serão disponibilizados até a \(4^a\) aula.

Cronograma

Material de Apoio

Além do material desse site, e do material entregue via Blackboard, é sugerido que o aluno consulte estes materiais ao longo do semestre.

Livros

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein
    Introduction to Algorithms. 3rd Edition.
  • Robert Sedgewick e Kevin Wayne
    Algorithms. 4th Edition.
  • Michael T. Goodrich e Roberto Tamassia
    Estruturas de dados e algoritmos em Java. 5.ed.
  • Sandra Puga e Gerson Rissetti
    Lógica de Programação e Estruturas de Dados com aplicações em Java.
  • Barnes e Kölling
    Programação Orientada a Objetos com Java: uma introdução prática utilizando o BlueJ.
  • Maurício Aniche
    Orientação a Objetos e SOLID para Ninjas: Projetando classes flexíveis.
  • Bruno Preiss
    Estruturas de Dados e Algoritmos
  • Sierra e Bates
    Use a Cabeça! Java
  • Deitel e Deitel
    Java: Como Programar
  • Horstmann e Cornell
    Core Java 2
  • Bruce Eckel
    Thinking in Java
  • Anthony Sintes
    Aprenda Programação Orientada a Objetos em 21 dias.
  • James Raumbaugh et al.
    Modelagem e Projeto Orientado a Objetos
  • Loiane Groner
    Estruturas de dados e algoritmos em JavaScript
  • Bjarne Stroustrup
    Princípios e Práticas de Programação em C++
  • Nilo Ney Coutinho Menezes
    Introdução a Programação com Python
  • Victorine Viviane Mizrahi
    Treinamento em Linguagem C
  • Nivio Zivani
    Projeto de algoritmos: com implementações em Java e C++

Apostilas on-line

Documentação oficial Java

Cursos em Vídeo

Cursos on-line