Plano de Ensino

IDENTIFICAÇÃO

EMENTA

Técnicas de projeto e análise de algoritmos. Relações de Recorrência. Projeto de algoritmos por indução. Divisão e conquista. Programação dinâmica. Algoritmos gulosos. Classes de problemas. Problemas NP-completos. Reduções

JUSTIFICATIVA

A disciplina de projeto e análise de algoritmos é fundamental para um curso de graduação em Engenharia da Computação. O curso estuda técnicas de resolução de problemas clássicas e analisa a correção e desempenho de algoritmos.

OBJETIVO

PROGRAMA

1. Introdução

   1. Crescimento de Funções e Notação Assintótica

   2. Relações de Recorrência e Métodos de Resolução

   3. Análise assintótica de custo (tempo, espaço, etc.)

2. Projeto de Algoritmos por Indução

   1. Subgrafo Induzido Máximo

   2. O problema da Celebridade

   3. Subsequência Consecutiva Máxima

3. Divisão e Conquista

   1. Ordenação: Merge-sort e Quick-sort

   2. Máximo e Mínimo

   3. Mediana e k-ésimo menor elemento

4. Programação Dinâmica

   1. Maior Subsequência Crescente

   2. Distância de Edição

   3. Problema da Mochila

5. Algoritmos Gulosos

   1. Árvore geradora mínima: Kruskal e Prim

   2. Códigos de Huffman

   3. Problema da seleção de atividades

6. Classes de Problemas

   1. As classes P e NP

   2. Problemas NP-completos

   3. Reduções
       

METODOLOGIA

Distribuição das atividades:

• Carga-horária de atividades presenciais (aulas): 54 horas-aula

Moodle:

• Todas as informações relativas à disciplina estarão no Moodle.

• Página da disciplina: https://www.moodle.ufu.br/course/view.php?id=10973

• Os alunos matriculados receberão a senha de acesso à disciplina no Moodle por email na primeira semana de aula.

Cronograma:

• Serão realizadas aulas presenciais expositivas com uso de projetor, quadro negro, e demais materiais, conforme o cronograma apresentado na tabela a seguir.

Atendimento aos alunos:

• O atendimento aos alunos será realizado uma vez por semana na sala do professor na modalidade presencial, ou através do Fórum de Dúvidas no Moodle.

AVALIAÇÃO

Sistema de Avaliação

• Serão realizadas 02 provas individuais, conforme apresentado na tabela a seguir.

• Serão realizados 04 provas individuais, conforme apresentado na tabela a seguir.

* O enunciado de cada trabalho será disponibilizado no início de cada semana, na segunda-feira às 08h00, e prazo para a entrega será na sexta-feira (da mesma semana) até às 17h59.

Sobre os trabalhos:

• Cada trabalho abordará um tema referente ao conteúdo apresentado até a semana correspondente.

• Os trabalhos serão propostos no modelo de programação para resolução de problemas e competições (ex: ICPC, OBI, maratona de programação da SBC) e serão avaliados por um sistema de correção automática e posteriormente verificados pelo professor.

• Caso haja a detecção de plágio em um trabalho, todos os envolvidos receberão nota zero.

Distribuição da Pontuação da disciplina:

• A nota final NF será calculada da seguinte forma: 

NF = (P1*0,4 + P2*0,4 + (T1+T2+T3+T4)*0,2)) / 10

Obs.: Ti é a nota do Trabalho i.

Avaliação de recuperação:

• Será oferecida uma avaliação de recuperação para os discentes que não obtiverem o rendimento mínimo para aprovação e com frequência mínima de 75%.

• A avaliação de recuperação será composta por uma prova escrita no dia 22/06/2023, e será cobrado todo o conteúdo ministrado.

• A nota da recuperação substituirá a menor nota de prova obtida pelo estudante.

• O estudante que realizar a atividade de recuperação e for aprovado terá limitada a sua nota final em 60 pontos. 

BIBLIOGRAFIA

Básica

1. CORMEN, Thomas H.; RIVEST, Ronald l.; LEISERSON, Charles E. e STEIN, Cliford. Algoritmos: teoria e prática. Rio de Janeiro: Campus, 2012. 926 p., il. Inclui bibliografia e índice. ISBN 9788535236996 (broch.).
2. DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algoritmos. Porto Alegre: AMGH, 2011. Livros. (1 recurso online). ISBN 9788563308535. Disponível em: https://www.sistemas.ufu.br/biblioteca-gateway/minhabiblioteca/9788563308535. Acesso em: 30 jun. 2022.
3. MANBER, Udi. Introduction to algorithms: a creative approach. Reading: Addison-Wesley, c1989. xiv, 478. ISBN 0201120372 (broch.).

Complementar

1. SEDGEWICK, Robert. Algorithms in C. 3rd. ed. Boston: Addison-Wesley, c1998-2002. v., il. Inclui bibliografia e índice. ISBN 0201314525 (broch.).
2. KLEINBERG, Jon. Algorithm design. Boston: Addison-Wesley, c2006. xxiii, 838 p., il. Inclui bibliografia (p. [805]-814) e índice. ISBN 0321295358 (enc.).
3. ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Pascal e C. 3. ed., rev. e ampl São Paulo: Cengage Learning, c2011. 639 p., il. Inclui bibliografia e índice. ISBN 9788522110506 (broch.).
4. CORMEN, Thomas H. Desmistificando algoritmos. Rio de Janeiro: GEN LTC, 2013. Livros. (1 recurso online). ISBN 9788595153929. Disponível em: https://www.sistemas.ufu.br/biblioteca-gateway/minhabiblioteca/9788595153929. Acesso em: 30 jun. 2022.
5. SKIENA, Steven S. The algorithm design manual. Santa Clara: TELOS--the Electronic Library of Science, c1998. xvi, 486 p., il., 25 cm. . + 1 CD-Rom (4 3/4 in.). Inclui bibliografia e índice. ISBN 0387948600.

APROVAÇÃO

Aprovado em reunião do Colegiado realizada em: ____/____/______

Coordenação do Curso de Graduação: _________________________

---

Documento assinado eletronicamente por Felipe Alves da Louza, Professor(a) do Magistério Superior, em 03/02/2023, às 15:11, conforme horário oficial de Brasília, com fundamento no art. 6º, § 1º, do Decreto nº 8.539, de 8 de outubro de 2015.

---

A autenticidade deste documento pode ser conferida no site https://www.sei.ufu.br/sei/controlador_externo.php?acao=documento_conferir&id_orgao_acesso_externo=0, informando o código verificador 4233953 e o código CRC 31843DFC.

---