MAC122 - 2s19 - Princípios de Desenvolvimento de Algoritmos
Horário: 2a 13:10 e 4a 09:20, Sala B2-04
Objetivos
MAC0122 é uma segunda disciplina de programação de computadores. Ela pressupõe uma boa prática de programação,
em uma linguagem de alto nível como linguagem C ou Python; alguns alunos terão adquirido essa prática em MAC0110 ou MAC2166 (Introdução à Computação). A linguagem C será usada como ferramenta de programação nos exemplos discutidos em aula, por permitir uma discussão mais detalhada dos conceitos abordados.
Conteúdo
Os principais tópicos a serem discutidos no curso serão:
- Eficiência de algoritmos,
- Ponteiros,
- Alocação dinâmica de memória,
- Listas encadeadas,
- Pilhas, filas,
- Recursão e funções recursivas,
- Algoritmos de enumeração,
- Ordenação de sequências (Quick Sort, Merge Sort, Heap Sort),
- Busca binária,
- Algoritmos em grafos,
- Documentação de funções.
Avaliação
Três provas teóricas (P1, P2 e P3) e três exercícios programas (EPs) para nota.
Observações Importantes sobre EPs:
- Todos os EPs são obrigatórios!
- Não serão aceitos EPs atrasados!
- Não copie! Não faça em grupo! Exercícios realizados dessa maneira (copiados ou equivalentes) não serão válidos!
- O enunciado de cada EP deverá ser rigorosamente observado.
Seja MP = (P1 + 2*P2 + 2*P3)/5 a média ponderada das provas e MEP = (EP1 + 2*EP2 + 2*EP3)/5 a média ponderada dos EPs.
Uma prova substitutiva Psub poderá ser feita por quem faltar a alguma das provas OU por aqueles que quiserem tentar melhorar sua nota.
A nota da PSub substituirá a nota de uma das provas não realizadas (ou a pior nota), sempre com peso dois. Caso a P1 seja a substituída, o denominador do cálculo de MP passa a ter o valor 6. Caso o aluno tenha deixado de fazer a P1 e mais uma outra, será substituída a outra e o valor do denominador não se altera.
A média final MF é dada por:
Se MP >= 5.0 e MEP >= 5.0
então MF = (MEP + 2*MP)/3
senão MF = min(MP, MEP)
As normas de aprovação são:
MF >= 5.0 => Aprovado
3.0 <= MF < 5.0 => Recuperação
MF < 3.0 => Reprovado
A recuperação será feita na forma de uma prova, sendo que a data será marcada oportunamente.
Seja Prec a nota da recuperação. Então, a nota final Mrec será dada por:
Mrec = (MF + 2*Prec)/3
Nesse caso, serão aprovados os alunos que obtiverem:
Mrec >= 5.0
Cronograma
Datas das provas:
- P1 - 11 de setembro
- P2 - 16 de outubro
- P3 - 27 de novembro
- Psub - 4 de dezembro
- Prec - 11 de dezembro
Semanas de break:
- 3/SET a 7/SET, semana da Pátria
Bibliografia
Não será indicado nenhum texto em especial. Sugestões para seu estudo:
- Projeto de Algoritmos em C - Paulo Feofiloff.
- Livro "Algoritmos em linguagem C" - Paulo Feofiloff.
- Eric S. Roberts, Programming Abstractions in C: a Second Course in Computer Science, Addison-Wesley, 1998. ISBN 0-201-54541-1.
- Robert Sedgewick, Algorithms in C, 3rd. ed., Parts 1-4, Addison Wesley Longman, 1998.
- Alfred V. Aho, Jeffrey D. Ullman, Foundations of Computer Science (C edition), Computer Science Press (W.H. Freeman), 1995.
- T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to algorithms, The MIT Press, McGraw-Hill Book Company, 1990, QA758 C811i.
Se você precisa de um livro para estudar linguagem C, de uma olhada em Introdução à Ciência da Computação Usando a Linguagem C que foi escrita por Carlos Hitoshi Morimoto e Ronaldo Fumio Hashimoto. Este livro está disponível aqui.
Na página do Projeto Macmulti (http://www.ime.usp.br/~macmulti),
você pode encontrar links para a História do Computador e vários problemas simples resolvidos em C e Python.
Compiladores C/C++
Code::Blocks
Code::Blocks (ou C::B) é um ambiente de desenvolvimento integrado de código aberto e multiplataforma. Ele está sendo desenvolvido em C++, usando wxWidgets. Sua arquitetura é orientada a plugin, de forma que suas funcionalidades são definidas pelos plugins fornecidos a ele. Code::Blocks é voltado para o desenvolvimento em C/C++ e agora Fortran.
Cygwin
Cygwin é uma coleção de ferramentas de software livre de maneira a permitir que várias versões do Microsoft Windows possam, de certa forma, agir como um sistema Unix. Sua principal intenção é portar softwares que rodam em sistemas POSIX (Linux, BSD e Unix) para que rodem em Windows com pouco mais do que uma recompilação. Resumindo, ele fornece um ambiente similar ao
utilizado pelo professor em aula com gcc e emacs para Windows.
Dev-C++
DevC++ é um ambiente de desenvolvimento integrado (IDE) livre que utiliza os compiladores de licença GNU para compilar programas para os sistemas operacionais MS Windows ou MS-DOS. Suporta as linguagens de programação C e C++, e possui toda a biblioteca ANSI C.
Notas de aulas
Exercícios para entrega (EPs)
O sistema PACA será usado para a submissão dos exercícios programas.
Listas de Exercícios
A entrega dos exercícios abaixo não será cobrada,
porém os conhecimentos adquiridos na sua resolução poderão ser cobrados nas provas.