/* @licstart The following is the entire license notice for the JavaScript code in this tag. Copyright (C) 2012-2020 Free Software Foundation, Inc. The JavaScript code in this tag is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License (GNU GPL) as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. The code is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU GPL for more details. As additional permission under GNU GPL version 3 section 7, you may distribute non-source (e.g., minimized or compacted) forms of that code without the copy of the GNU GPL normally required by section 4, provided you include this license notice and a URL through which recipients can access the Corresponding Source. @licend The above is the entire license notice for the JavaScript code in this tag. */

Plano de Ensino
Projeto e Análise de Algoritmos - 2020/2

1 Objetivos

Compreender os fundamentos matemáticos para a análise de algoritmos por meio de ferramentas matemáticas e de implementações de soluções eficientes para problemas usuais nas aplicações computacionais. Ao final do curso o aluno dever ser capaz de:

  1. Analisar a complexidade quanto aos recursos de tempo e espaço de algoritmos utilizando análise assintótica;
  2. Provar a correção de algoritmos elementares;
  3. Conhecer aos paradigmas de projeto por indução, divisão e conquista, algoritmos gulosos e programação dinâmica para o projeto de algoritmos;
  4. Compreender os fundamentos da teoria de NP-completude.

2 Conteúdo programático

  • Fundamentos matemáticos para análise de algoritmos;
  • Análise assintótica de algoritmos;
  • Paradigmas de projeto de algoritmos;
  • Algoritmos eficientes;
  • Fundamentos de complexidade computacional.

3 Metodologia de ensino

O conteúdo será abordado por meio de atividades:

  1. Leituras dirigidas que serão disponibilizadas na página web da disciplina1 e/ou na plataforma Microsoft Teams institucional;
  2. Assíncronas (videoaulas) que ficarão disponíveis na plataforma Youtube, e cujos links serão disponibilizados na página web da disciplina1 e/ou na plataforma Microsoft Teams institucional;
  3. Síncronas (aulas virtuais) via a plataforma Microsoft Teams institucional.

A plataforma institucional Microsoft Teams será utilizada para troca de mensagens e discussão de dúvidas.

4 Avaliação

A avaliação será composta das seguintes partes:

  1. Atividades individuais a serem enviadas em prazo determinado.
    1. Serão 30 atividades, cada uma valendo 2 pontos, perfazendo um total de 60 pontos.
    2. Cada atividade individual será contabilizada como uma frequência, se enviada no prazo determinado; e contabilizada como falta da aula correspondente, se enviada com atraso ou se não for enviada.
    3. A pontuação de cada uma das 30 atividades será contabilizada como a seguir:
      • até 2 pontos, se enviada no prazo determinado;
      • até 1 ponto, se enviada em até 24 horas depois do prazo determinado;
      • 0, nas outras situações.
    4. As atividades individuais que não tenham sido realizadas por alguma razão amparada por lei poderão ser repostas no final do semestre por meio de uma avaliação envolvendo todo o conteúdo do semestre.
  2. Uma avaliação escrita individual a ser enviada em formato pdf em prazo determinado, perfazendo um total de 10 pontos.
  3. Uma formalização (a ser feita individualmente ou em dupla) a ser feita no assistente de provas Coq, e enviada pela plataforma GitHub em prazo determinado, perfazendo um total de 30 pontos.

Para ser aprovado o aluno deve cumprir simultaneamente os seguintes itens:

  • Frequência maior ou igual a 75% nas aulas;
  • Obter pelo menos 50 pontos considerando as duas etapas de avaliação do curso.

A menção final é definida como a seguir:

Menção Pontos
SS (Superior) 90 – 100
MS (Médio Superior) 70 - 89
MM (Médio) 50 - 69
MI (Médio Inferior) 30 - 49
II (Inferior) 01 - 29
SR (Sem Rendimento) 00 ou mais de 25% de faltas

5 Material didático

A referência principal é cormenIntroductionAlgorithmsThird2009. Materiais de leitura complementar serão disponibilizados no ambiente virtual, assim como links para outras referências que estiverem disponíveis na internet.

Bibliografia complementar: baaseComputerAlgorithmsIntroduction1999,levitinIntroductionDesignAnalysis2012,manberIntroductionAlgorithmsCreative1989,roughgardenAlgorithmsIlluminatedPart2017,roughgardenAlgorithmsIlluminatedPart2018,roughgardenAlgorithmsIlluminatedPart2019.

Bibliography

Notas de Rodapé:

Data: \today

Autor: Flávio L. C. de Moura

Criado em: 2021-02-02 Ter 22:19

Validate