apostila de algoritimos

Algoritmos e Estruturas de Dados I
Marcos Castilho

Fabiano Silva
Vers˜o 0.7 a Maio de 2011

Daniel Weingaertner

2
Algoritmos e Estruturas de Dados I - Notas de Aula est´ licena ciado segundo a licen¸a da Creative Commons Atribui¸ao-Uso c c˜
N˜o-Comercial-Vedada a Cria¸˜o de Obras Derivadas 2.5 Braa ca sil License.http://creativecommons.org/licenses/by-nc-nd/
2.5/br/
Algoritmos e Estruturas de Dados I - Notas de Aula is licensed under a Creative Commons Atribui¸ao-Uso N˜o-Comercialc˜ a Vedada a Cria¸ao de Obras Derivadas 2.5 Brasil License.http: c˜ //creativecommons.org/licenses/by-nc-nd/2.5/br/

AVISO: Este texto ainda est´ em constru¸˜o. a ca

Sum´rio a 1 Introdu¸˜o ca 7

2 Sobre problemas e solu¸˜es co 9
2.1 Contando o n´mero de presentes em um evento . . . . . . . . . . . . . 9 u 2.2 Trocando os quatro pneus . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Conclus˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 a 3 Sobre algoritmos e programas
15
3.1 O que ´ um algoritmo? . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 e 3.2 O que ´ um programa? . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 e 3.3 Exerc´ ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4 O modelo do computador
4.1 Hist´rico . . . . . . . . . . . . . . . . . . . . . . . . . . o 4.2 Princ´ ıpios do modelo . . . . . . . . . . . . . . . . . . .
4.2.1 Endere¸os versus conte´dos . . . . . . . . . . . c u
4.2.2 O repert´rio de instru¸oes . . . . . . . . . . . . o c˜
4.2.3 O ciclo de execu¸˜o de instru¸oes . . . . . . . . ca c˜
4.2.4 Exemplo de execu¸ao de um programa . . . . . c˜ 4.3 Humanos versus computadores . . . . . . . . . . . . . .
4.3.1 Abstra¸˜o dos endere¸os . . . . . . . . . . . . . ca c
4.3.2 Abstra¸˜o dos c´digos das instru¸oes . . . . . . ca o c˜ 4.3.3 Abstra¸˜o do repert´rio de instru¸˜es . . . . . . ca o co 4.3.4 Abstra¸˜o