Departamento de Ciência da Computação  |  Instituto de Matemática e Estatística  |  USP

MAC0122
Princípios de Desenvolvimento de Algoritmos

ano 2002 semestre 2

 


Home |  Administração |  Livros |  WWW |  Diário | 
Veja Projeto de Algoritmos

 

Professores devem ajudar alunos a transformar
informação em conhecimento
.
—Anônimo

Ao verificar que um dado programa está muito lento,
uma pessoa prática pede uma máquina mais rápida
ao seu chefe.
Mas o ganho potencial
que uma máquina mais rápida pode proporcionar
é tipicamente limitado por um fator de 10,
por razões técnicas ou econômicas.
Para obter um ganho maior,
é preciso buscar melhores algoritmos.
Um bom algoritmo,
mesmo rodando em uma máquina lenta,
sempre acaba derrotando
(para instâncias grandes do problema)
um algoritmo pior rodando em uma máquina rápida.
Sempre.

—S. S. Skiena, The Algorithm Design Manual

 

MAC0122 é a segunda disciplina de computação no currículo do BCC.  Ela pressupõe uma boa prática de programação, particularmente em linguagem C;  o aluno deve ter adquirido essa prática em MAC0110 (Introdução à Computação).

MAC0122 estuda algoritmos para alguns problemas computacionais básicos. Isso serve de motivação para introduzir vários conceitos e ideias importantes:

  • prova da correção de algoritmos
  • invariantes de algoritmos iterativos
  • eficiência (= desempenho) de algoritmos
  • estruturas de dados
  • recursão e a estrutura recursiva de problemas
  • documentação de funções
  • elegância de algoritmos
  • leiaute de programas

Principais tópicos de MAC0122:

  • Estruturas de dados básicas (listas lineares, listas encadeadas, etc.)
  • Recursão e algoritmos recursivos
  • Busca sequencial e busca binária
  • Árvores de busca
  • Ordenação de sequências (algoritmos de inserção, de selecão, mergesort, quicksort, heapsort, etc.)
  • Pilhas, filas, filas com prioridades, tabelas de símbolos, etc.
  • Algoritmos de enumeração (backtracking)
  • Busca de padrões em texto

MAC0122 não é um curso de linguagem C.  A linguagem  C é apenas uma ferramenta: ela será usada para representar e testar algoritmos, que são o verdadeiro assunto da disciplina. (Apesar disso, eu sei que muitos alunos vão aprender muito C, por conta própria, no decorrer de MAC0122.)

 

Notas de aulas

Apêndices:

 


URL of this page: http://www.ime.usp.br/~pf/mac0122-2002/
Last modified: Thu Jul 30 12:29:43 BRT 2015
Paulo Feofiloff
DCC  |  IME  |  USP

 

Busca no sítio mac0122-2002

Valid HTML 4.01 Transitional    Valid CSS!

Outros assuntos:   Projeto de Algoritmos em C  |  Estruturas de Dados  |  Literate Programming & CWEB  |  Análise de Algoritmos  |  Fluxo em Redes  |  Algoritmos de Programação Linear  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Exercícios de Teoria dos Grafos  |  Algoritmos em Grafos com Stanford GraphBase  |  Algoritmos para Grafos via Sedgewick  |  Digrafos |  O que é uma prova?  |  Opiniões e notícias