MAC5711 - Análise de Algoritmos


A disciplina MAC5711

  • estuda algoritmos eficientes e elegantes para alguns problemas computacionais básicos;
  • prova a correção de algoritmos iterativos a partir de suas relações invariantes;
  • explora a estrutura recursiva dos problemas para construir algoritmos eficientes;
  • formaliza o conceito de desempenho (assintótico) de algoritmos;
  • calcula o desempenho de vários algoritmos básicos.

MAC5711 é disciplina obrigatória da Pós-graduação em Ciência da Computação da USP. A disciplina tem como pré-requisitos, prática em programação e em estruturas de dados, tais como os adquiridos em disciplinas de graduação em Ciência da Computação (MAC0122 Princípios de desenvolvimento de algoritmos e MAC0323 Estruturas de dados). Em particular, supõe-se que o aluno esteja bem familiarizado com algoritmos básicos de ordenação como Mergesort, Heapsort e Quicksort. Também é desejável que o aluno tenha algum conhecimento de probabilidade.