Cronograma de MAC0122
Segundo semestre de 2024
Agosto
- 5 de agosto (Aula 1):
- Apresentação da disciplina
- Recursão: Hanoi, fatorial e máximo de um vetor
- EP1
Slides: [pdf]
Leitura recomendada:
Apêndice A e capítulos 1 e 2 do
livro do Prof. Paulo,
ou então seções
Leiaute,
Documentação e
Recursão e Algoritmos Recursivos.
Exercício sobre Hanoi: Quantas linhas a função Hanoi imprime
para um certo n?
Exercício sobre Fibonacci: A função de Fibonacci é definida assim:
F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) para n > 1. Descreva a função F em linguagem C.
Faça uma versão recursiva e uma iterativa. Sua função recursiva é tão eficiente quanto a
iterativa? Por que?
- 7 de agosto (Aula 2):
- Quantas linhas a função Hanoi da aula passada imprime?
- Recursão: Fibonacci
- Quando recursão não é recomendada?
- Bate-papo sobre o EP1
Slides: [pdf]
Leitura recomendada: Capítulos 1 e 2 do
livro do Prof. Paulo,
ou então seções
Leiaute,
Documentação e
Recursão e Algoritmos Recursivos.
Exercício sobre binomiais: O binomial de n e k, denotado por
binom(n,k), é definido como n! dividido por k!.
O binomial satisfaz a seguinte propriedade, conhecida como regra de Pascal:
binom(0,k) = 0 para k > 0, binom(n,0) = 1 para n &ge k
e binom(n,k) = binom(n-1,k) + binom(n-1,k-1) para n e k &ge 1.
Escreva uma função Binom em linguagem C, recursiva, que calcule o binomial de n e k,
baseando-se na regra de Pascal.
Reflita sobre o tempo que essa função recursiva vai gastar.
Pense em um jeito iterativo de implementar a mesma função, que consuma menos tempo
ao executar.
Arquivos ps:
[teste1.ps | teste2.ps | teste3.ps].
Ao clicar em um destes arquivos ps, talvez o seu browser já baixe o arquivo no seu computador
e abrá-o com um leitor padrão de arquivos ps, exibindo a visualização já:
uma página em branco com uma moldura bem próxima à borda.
Experimente abrir esse arquivo ps no seu editor; pode ser o mesmo editor que
você usa para escrever os seus programas. Ao fazer isso, você verá os comandos que mostramos nos slides.
Sua missão para segunda-feira:
- escrever um arquivo ps que desenhe numa página a curva de Koch de ordem 1.
- escrever um programa com uma função que recebe como parâmetro um inteiro n
e imprime os comandos para imprimir a curva de Koch de ordem n a partir do ponto e
direção em que a caneta se encontra, e usando como largura do desenho o valor que se
encontra no topo da pilha do postscript. Na função main do seu programa, imprima os
comandos iniciais e finais: coloque a caneta na posição inicial, empilhe a largura
desejada do desenho, acione a sua função com o n que quiser, e não se esqueça do stroke no final.
- 12 de agosto (Aula 3):
- Mais recursão: binomial e curvas de Hilbert
- Lista 1 - recursão
Slides: [pdf]
Nos programas disponibilizados, coloquei o fonte do programa em C que desenha
a curva de Hilbert usando uma biblioteca gráfica chamada OpenGL.
- 14 de agosto (Aula 4):
- Mais recursão: mdc
- Argumentos na linha de comando
- Registros e estruturas
Slides: [pdf]
Leitura recomendada: Capítulos 2 e 3 do
livro do
Prof. Paulo, ou então Seções Recursão e algoritmos
recursivos.
- 19 de agosto (Aula 5):
- Endereços e ponteiros
- Alocação dinâmica
Slides: [pdf]
- 21 de agosto (Aula 6):
- Listas em vetores
- Listas encadeadas
- Listas encadeadas com vetores
- EP2
Slides: [pdf]
- 26 de agosto (Aula 7):
Slides: [pdf]
- 28 de agosto (Aula 8):
- Mais listas encadeadas com ponteiros
- Listas encadeadas com cabeça
- Inversão de lista encadeada - se der tempo...
Slides: [pdf]
Setembro e demais meses