The life so short
the craft so long to learn.
A vida tão curta,
o ofício tão longo de aprender.
— Geoffrey Chaucer
What I hear, I forget.
What I see, I remember.
What I do, I understand.
— Confucius
MAC0338 é disciplina obrigatória (4-o semestre) do BCC (Bacharelado em Ciência da Computação).
O início das aulas está previsto para o dia 31/8/2020 (segunda-feira) e o término está previsto para o dia 16/12/2020 (quarta-feira). As aulas acontecerão às 10h das segundas-feiras e às 8hm das quartas-feiras.
As aulas serão dadas pelo professor Paulo Feofiloff. A monitora da disciplina será Lais Baum.
As aulas serão dadas à distância, online, numa sala do Zoom. Para discussões, perguntas, avisos, mensagens, e entrega de exercícios, usaremos o site e-Disciplinas da USP.
Livros texto:
Referências adicionais:
Teremos várias listas de exercícios ao longo do semestre. Cada aluno deverá resolver as listas de exercícios sem a ajuda de outras pessoas e sem buscar soluções na rede WWW.
Além das listas de exercícios, teremos duas provas. A nota final será composta por 70% da média das provas e 30% da média das listas de exercícios. Entretanto, se a média das provas ou a média dos exercícios ficar abaixo de 5, a nota final será a menor das duas.
Quando nos deparamos com
vários algoritmos para um mesmo problema,
é natural perguntar qual o melhor deles?
Também é natural perguntar
existe um algoritmo ainda melhor?
A Análise de Algoritmos estabelece
critérios e métodos
que permitem responder essas perguntas.
1. Formalizar e organizar as noções de projeto e análise de algoritmos que os alunos já adquiriram em disciplinas anteriores. 2. Apresentar algoritmos de vários tipos para diversos problemas computacionais básicos. 3. Discutir as abordagens e técnicas que levaram à concepção desses algoritmos. 4. Apresentar conceitos e métodos que permitem avaliar a qualidade (correção e eficiência) de algoritmos e a projetar bons algoritmos. 5. Apresentar noções da teoria de complexidade, que trata de classificar problemas de acordo com sua dificuldade.
Espera-se que o aluno aprenda a distinguir a análise matemática formal de um algoritmo de uma mera lista de frases intuitivas desencontradas. Devem contribuir para isso a leitura do livro texto, os exercícios, as discussões nas aulas e no fórum, e as discussões entre os alunos.
Ementa oficial (conforme página no apoio@bcc, catálogo de graduação do IME, e catálogo de graduação da USP):
(Não prometo seguir esta ementa à risca.)
O requisito oficial desta disciplina é MAC0323 (Algoritmos e Estruturas de Dados II).
Outros assuntos: Projeto de Algoritmos em C | Estruturas de Dados | Literate Programming & CWEB | Exercícios de Teoria dos Grafos | Graph Theory Exercises | Uma Introdução Sucinta à Teoria dos Grafos | Otimização Combinatória | Algoritmos em Grafos | Digrafos | Minicurso de Análise de Algoritmos | Análise de Algoritmos | O que é uma prova? | Algoritmos para Grafos via Sedgewick | Algoritmos de Programação Linear | Uma Introdução Sucinta a Algoritmos de Aproximação