1) Disciplina : MAC 122 – Princípios de Desenvolvimento de Algoritmos
a) Professor : Manoel MARCILIO Sanches
b) Objetivos : Desenvolvimento de algoritmos e de suas estruturas de dados básicas. Estudo, através de exemplos, da correção e da análise de eficiência e dos algoritmos.
c) Pré-requisitos
- MAC11x – Introdução à Computação
- Algoritmos e Linguagem C
d) Página na internet:
http://www.ime.usp.br/~mms/mac1222s2014/mac1222s2014.htm
Consulte sempre a página na Internet para ver as novidades
Inscreva-se também no PACA para ter acesso aos e-mails de notícias e discussões
e) E-mail do professor: mms@ime.usp.br
f) Horário das aulas: 3.feira (19:20hs) 5.feira (21:10hs)
g) Compilador C : Dev C++ ou GCC
2) Programa da disciplina
a) Linguagem C (revisão) – funções e estruturas de blocos; funções, vetores e matrizes; char e strings; ponteiros, ponteiros e vetores/matrizes e alocação dinâmica de memória.
b) Alocação Sequencial - Alguns exemplos de algoritmos usando pilhas e filas.
c) Linguagem C (revisão) - Ponteiros e Structs.
d) Alocação Dinâmica - Introdução aos conceitos de listas ligadas e ponteiros.
e) Busca, inserção e remoção em listas ligadas.
f) Tipos abstratos de dados.
g) Algoritmos recursivos.
h) Introdução à análise de algoritmos – A notação O(f(x)).
i) Algoritmos de classificação (inserção, seleção, mergesort, heapsort, quicksort, etc.).
j) Algoritmos de busca sequencial e binária em tabelas.
k) Algoritmos de busca em tabelas HASH.
l) Algoritmos de busca de palavras em texto.
m) Algoritmos de enumeração.
n) Prova informal da correção de algoritmos.
3) Bibliografia
a) Notas de aula – disponíveis na página da disciplina
b) R. Sedgewick, "Algorithms in C", 3rd. ed, vol. 1, Addison-Wesley/Longman, 1998.
4) Avaliação
2 provas e uma sub aberta (p1, p2, ps).
A prova ps (substitutiva) sempre substitui uma das provas (a que for melhor para o aluno).
3 exercícios-programa eps (ep1, ep2, ep3)
Média de provas : p = (p1+2p2)/3 – note que a p2 tem peso maior
Média de eps : ep = (p1+2p2+3p3)/6 - note que os pesos são crescentes
Média final m: Se (p>=5 e ep>=6) então m = (3p+ep)/4;
Senão m = mínimo entre 4.5, p e ep
Note que tem que ter média >=5 em provas e >=6 em eps. As dus notas são independentes. Uma não ajuda a outra a não ser na média final.
Se (m >= 5) aprovado ;
Se (3 <= m < 5) recuperação ;
Se (m < 3) reprovado ;
Prova de recuperação pr em data a ser divulgada.
5) Datas das Provas
P1 – 02/Outubro/2014 – 5.feira
P2 – 27/Novembro/2014 – 5.feira
PS – 04/Dezembro/2014 – 5.feira
6) Lembretes sobre os EPs
- Não deixe para a última hora
- Não serão aceitos EPs com atraso
- Os EPs devem ser individuais. Você pode discutir suas dúvidas de cada projeto com seus colegas, mas a elaboração e implementação devem ser de sua autoria.
7) Monitoria
a) Monitor :
b) e-mail do monitor :
c) Atendimento: Às 3.feiras das 17:20hs às 19:20hs no CEC do IME-USP
- Professor: Manoel Marcílio Sanches