Complexidade de Algoritmos e Análise de Desempenho

lasalle - 2023/2

Objetivos

São objetivos da disciplina:

Pré-requisitos

Embora os pré-requisitos não sejam obrigatórios, o seu domínio auxiliará muito na evolução do aprendizado:

Competências trabalhadas

As competências trabalhadas na disciplina são:

Unidades de Aprendizagem

As unidades de aprendizagem abordadas na disciplina são:

Estratégias metodológicas

Aulas expositivas, atividades de pesquisa relacionadas às unidades de aprendizagem, exemplos práticos e exercícios individuais ou em grupo.

Cronograma

AulaConteúdo ProgramadoData
01
  • Apresentação da Disciplina.
  • Revisão de algoritmos e estruturas de dados.
  • Pensamento algorítmico.
07/08
02
  • Revisão da teoria de autômatos e máquinas universais.
  • Equivalência de máquinas universais.
  • Linguagens regulares e livres de contexto.
14/08
03
  • Complexidade e desempenho de algoritmos.
  • Medidas de desempenho.
  • Análise assintótica.
  • Notações Omega, Theta e Big-O.
  • Algoritmos de Busca.
  • Alogritmos de Ordenação.
21/08
04
  • Correção de exercícios.
  • Revisão de conteúdo.
28/08
05
  • Ordenação (Sorting).
  • Algoritmos de ordenação eficientes.
  • Algoritmos de ordenação de tempo linear (O(n)).
04/09
06
  • Recursão.
  • Árvores binárias de pesquisa.
  • Árvores AVL.
11/09
07
  • Hashing.
  • Hashtables.
18/09
08
  • Heaps.
  • Heapsort.
25/09
09
  • Grafos.
  • Representação de grafos.
  • Algoritmos de busca em grafos.
02/10
10
  • Problema do Menor Caminho.
  • Algoritmo de Dijkstra.
09/10
11
  • Procura em Strings.
16/10
12
  • Evento da Universidade: Sapiens.
23/10
13
  • Programação Dinâmica.
30/10
14
  • Projeto e análise de algoritmos.
  • Divisão e Conquista.
  • Algoritmos Gulosos (Greedy Algorithms).
  • Programação Dinâmica.
06/11
15
  • Indecidibilidade e algortimos não-computáveis.
  • Intratabilidade e complexidade de algoritmos.
  • Classes de problemas P, NP, NP-hard, NP-Complete, EXP e R.
13/11
16
  • Exercícios e Revisão.
20/11
17
  • Exercícios e Revisão.
27/11
18
  • Avaliação P2.
04/12
19
  • Entrega de resultados.
  • Revisão para substituição de grau.
11/12
20
  • Prova de substituição de grau.
18/12

Procedimento e critérios de avaliação

A nota final será composta por trabalhos/exercícios e prova, que serão desenvolvidos durante as aulas e em atividades extraclasse.

O grau 1 será composto por G1 = E1(3.0) + T1(3.0) + A1(4.0)

O grau 2 será composto por G2 = E2(3.0) + T2(3.0) + P2(4.0)

A nota final será a média (M) dada pela regra M = (G1 + G2) / 2

A recuperação será realizada com a aplicação de uma prova escrita. A nota desta substituirá a nota mais baixa e a média (M) será recalculada.

Para obter a aprovação, o aluno deve obter uma média (M) igual ou superior a 6, com frequência igual ou superior à 75%. A frequência será medida a partir de chamada nominal, realizada em todas as aulas.

Recursos para a disciplina

Recursos online

  1. Introduction to Algorithms MIT OpenCourseWare. 2020. (Também disponíveis os cursos de 2011 e 2008.)
  2. Theory of Computation MIT OpenCourseWare. 2020.
  3. Design and Analysis of Algorithms MIT OpenCourseWare. 2015.