Análise e Projeto de Algoritmos - TCC-00.167
Segundo Semestre de 2013 - Turma B-1
Prof. Fábio Protti
- sala 301
(3o. andar - Bloco E - Instituto de Computação) – fabio@ic.uff.br
Horário da disciplina: segunda e sexta, das 18:00 às 20:00
Local: Bloco H – sala 402
Baixem as LISTAS
DE EXERCÍCIOS para estudo.
ATENÇÃO! OBSERVEM O CALENDÁRIO
DE AULAS DO MÊS DE OUTUBRO:
07/10 – não haverá aula (professor estará fora do Rio)
11/10 – aula normal, que será dada pelo Uéverton (aluno de doutorado)
14/10 – não haverá aula (feriado antecipado: Dia do Servidor Público)
18/10 – aula normal
21/10 – não haverá aula (Agenda Acadêmica UFF)
25/10 – não haverá aula (Agenda Acadêmica
UFF)
28/10 – aula normal
01/11 – Primeira Prova
PROGRAMA DO CURSO:
Problemas e Algoritmos. Complexidade
de algoritmos. Algoritmos ótimos.
Limites Inferiores de Problemas:
Máximos e Mínimos de Listas.
Recursividade e recorrências. Busca
Binária. Torre de Hanói.
Método da Divisão-e-Conquista. Min-Max
e outros exemplos.
Algoritmos de Ordenação: Selection Sort, Bubblesort, Mergesort. Quicksort. Limite inferior para ordenação.
Método Guloso e aplicações: Árvore
Geradora Mínima, Escalonamento, Códigos de Huffman.
Programação Dinâmica – Problema da
Mochila, Sequência Ótima de Multiplicação de Matrizes, Distância Mínima de
Edição.
Backtracking – Algoritmo Geral e Aplicações:
Permutações, Problema das Damas, Coloração de Vértices, Passeio de Cavalo.
Problemas de Decisão e Otimização. As Classes P e NP. Problemas NP-Completos.
Estrutura do Curso
Aulas Teóricas. Lista de Exercícios Sugeridos. Trabalho de Implementação.
Recomendo fortemente que os alunos resolvam
a Lista de Exercícios Sugeridos.
Calendário de Provas
Prova 1: dia 01 de novembro de 2013
Prova 2: dia 20 de dezembro de 2013
VS: dia 10 de janeiro de 2014
Avaliação
Seja M=(2*P1+2*P2+T)/5, onde T é a nota do Trabalho de Implementação.
Se M >= 6,0, o aluno está aprovado.
Se M < 4,0, o aluno está reprovado.
Se 4 <= M < 6,0, o aluno deve fazer a VS.
A nota da VS deverá ser
maior ou igual a 6,0.
Sobre o Trabalho de Implementação...
O Trabalho consistirá na implementação de um algoritmo.
Cada equipe receberá o seu próprio
algoritmo para implementar.
A linguagem de implementação pode ser Pascal, C, C++ ou Java.
Use o site http://uva.onlinejudge.org
A equipe deve enviar um e-mail com o fonte do algoritmo (arquivo texto)
até o prazo máximo de 15 de dezembro de 2013
(domingo) às 23:59:59.
Trabalhos enviados em
data/horário posterior receberão descontos proporcionais ao tempo de atraso.
Bibliografia
Listas Antigas (não é
para entregar)
Trabalhos de Implementação
1. Apresentação no dia 9/12
Evandro da
Silva Mendonça
Fabiane Lucas da Silva
Felipe Álvaro Vieira de Lima
Jefferson Lessa
Jéssica Soares dos Santos
Letícia Motta Braga
Emanuel Merayo
Luciano
Nascimento
Patrick
Barreto
Pedro Moises
Carlos Ramon
Braz
Carlos de
Oliveira
Carlos Alberto Dantas
Luana Uchoa
Abraao Miranda
Danilo Souza
Juscelino
Maria Clara
Wallace
Coelho
Andre Mendes
Frederico
Barbara
Borges
2. Apresentação no dia 13/12
Ian Bastos
Lucas de Azevedo
Rafael Grillo
Tayane Moura
Thayanne Viegas
Victor Sousa
Igor
Souza
Guilhermo Montoya
Lucas Soares
Matheus Guilarducci
Guilherme Miranda
Leandro Galuzzi
Víviann Magaly
Priscila Terra
Juan Diniz
Fernando Moutinho
Aiquis Rodrigues
Felipe Alkaim
João Paulo Forny
Robison Meirelles
Victor Rempto
Tiago Santos