Análise de Algoritmos - TIN0118

Obrigatória - 60 horas - 4 créditos
Pré-requisitos: Estruturas de Dados II
Professor Responsável: Vânia Maria Félix Dias

OBJETIVOS DA DISCIPLINA

Capacitar o aluno a analisar, avaliar e comparar a eficiência computacional de algoritmos. Qualificar o aluno no conhecimento de técnicas de projeto de algoritmos eficientes, quando possível, e na identificação da estratégia mais indicada em cada caso. Habilitar o aluno na identificação e reconhecimento de classificação da complexidade de problemas computacionais.

EMENTA

Critérios de análise, correção e eficiência. Análise de algoritmos: tempo de processamento e número de operações elementares, complexidade de pior caso. Algoritmos e estruturas de dados para problemas em grafos. Teoria da Complexidade: problemas de decisão, transformações polinomiais, classe P, algoritmos não determinísticos, classes NP e NP-completa.

CONTEÚDO PROGRAMÁTICO

METODOLOGIA

Exposição de conteúdo: nas aulas presenciais serão apresentados o conteúdo teórico e as diversas técnicas de projeto de algoritmos, através do uso intensivo de exemplos de solução de problemas utilizando cada uma das técnicas estudadas.
Aprendizagem colaborativa: para o entendimento do conteúdo serão apresentados problemas cujas soluções serão propostas e discutidas pelos alunos.
Aprendizagem baseada em projeto: a partir dos exemplos de problemas computacionais e técnicas de solução apresentados em sala, o aluno deverá desenvolver projetos de algoritmos para a solução de problemas propostos.

AVALIAÇÃO

Avaliação contínua: ao longo da disciplina, o estudante apresentará em grupo aproximadamente 5 projetos de algoritmos, um para cada problema proposto, sendo cada um dos problemas correspondente a uma técnica específica de projeto de algoritmos estudada.
Avaliação somativa: ao longo da disciplina haverão duas avaliações com o objetivo de avaliar pontos específicos do conteúdo programático de forma individual.
Cálculo da nota final: (média dos trabalhos intermediários) / 2 + (média das provas) / 2.
Para ser aprovado na disciplina, o aluno precisa obter nota final acima de 5.

BIBLIOGRAFIA