Introdução à Algoritmia e Programação

Introdução à Algoritmia e Programação

José Manuel Torres
&

Fábio Mota

2013/2014

1 Algoritmos e Computação
1.1 Algoritmos
1.1.1 Noção de Algoritmo

Noção Informal:
Sequência finita e não ambígua de instruções elementares bem definidas, conducente à solução de um determinado problema, cada uma das quais pode ser executada mecanicamente, numa quantidade finita de tempo e com uma quantidade finita de esforço.

Objectivo  Sub-Objectivos  Passos de Resolução

A entidade que executa um algoritmo pode ser um humano ou um computador.

1.1.2 Algoritmo da Mudança de Lâmpada

Exemplo 1: Substituir uma lâmpada fundida de um candeeiro.

Passo Descrição
1 Seleccione uma nova lâmpada
2 Remova a Lâmpada fundida
3 Insira uma nova lâmpada

1.1 Seleccione uma lâmpada da mesma potência da fundida

2.1 Posicione a escada em baixo do candeeiro
2.2 Suba a escada até que possa atingir a lâmpada
2.3 Rode a lâmpada no sentido contrário ao dos ponteiros do relógio até que esta se solte

3.1 Coloque a nova lâmpada no orifício correspondente
3.2 Rode a lâmpada no sentido dos ponteiros do relógio até que fique presa
3.3 Desça da escada

Definição mais precisa para o passo 1.1:
Dada uma caixa com lâmpadas, seleccione uma lâmpada candidata à substituição
Se a lâmpada não for da mesma potência da antiga, então, repita os passos seguintes até encontrar uma lâmpada da potência desejada: Pouse a lâmpada seleccionada Seleccione uma nova lâmpada

1* Por exemplo, para os passos 2.2, 2.3, 3.2 e 3.3 poderiam também derivadas descrições mais precisas e detalhadas, do tipo: Repita ... até ...
2* Aumento do detalhe do algoritmo pode continuar quase indefinidamente.
3* Grau de detalhe depende das necessidades do agente que vai executar o algoritmo.

1.1.3 Algoritmo Lista-Telefónica

Exemplo 2: Encontrar o número de telefone que