Algoritmos-e-Estrutura-de-Dados Volume 1

Algoritmos-e-Estrutura-de-Dados Volume 1

(Parte 1 de 9)

Recife,2009

Algoritmos e Estrutura de Dados

Rodrigo de Souza Hugo Rodrigues

Universidade Federal Rural de Pernambuco

Reitor: Prof. Valmar Corrêa de Andrade Vice-Reitor: Prof. Reginaldo Barros Pró-Reitor de Administração: Prof. Francisco Fernando Ramos Carvalho Pró-Reitor de Extensão: Prof. Paulo Donizeti Siepierski Pró-Reitor de Pesquisa e Pós-Graduação: Prof. Fernando José Freire Pró-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo Ferreira Pró-Reitora de Ensino de Graduação: Profª. Maria José de Sena Coordenação Geral de Ensino a Distância: Profª Marizete Silva Santos

Produção Gráfica e Editorial Capa e Editoração: Allyson Vila Nova, Rafael Lira e Italo Amorim Revisão Ortográfica: Marcelo Melo Ilustrações: Roberto Costa e Diego Almeida Coordenação de Produção: Marizete Silva Santos

Apresentação4
Conhecendo o Volume 15
Capítulo 1 – História do conceito de algoritmo6
1. O que é um algoritmo?6
2. De onde vem a ideia de algoritmo?8
3. Algoritmos versus programas10
Capítulo 2 – Exemplos de algoritmos16
1. O algoritmo de Euclides17
2. A linguagem Portucal20
Capítulo 3 – Algoritmos recursivos39
1. O conceito de recursão39
2. Deve-se sempre usar recursão?43
Capítulo 4 – Análise de um algoritmo47
1. Uma experiência: eficiência de soma-subconjunto48
2. Análise assintótica5
Considerações Finais63

Apresentação

Caro(a) cursista

Seja bem-vindo(a) ao primeiro módulo do curso Algoritmos e Estruturas de Dados.

Nele, teremos nosso primeiro contato com o conceito de algoritmo, que é fundamental em Computação, pois algoritmos são a essência de qualquer programa em execução num computador real.

Começaremos esse volume com um pouco de História. Veremos que algoritmos já eram utilizados por civilizações da Antiguidade e que a formalização desse conceito foi uma das descobertas mais importantes do século vinte para a Computação.

Vamos, logo em seguida, estudar nossos primeiros algoritmos. Veremos que podemos descrever algoritmos com uma linguagem bastante simples e natural, e não muito distante das linguagens de programação populares. Também descobriremos que um algoritmo pode, em sua execução, iniciar uma nova execução de si mesmo, e que esse recurso é bastante poderoso. Tais algoritmos são chamados de algoritmos recursivos.

Finalmente, consideraremos o fato de que, normalmente, podemos resolver um problema de diversas maneiras, ou seja, usando uma variedade de algoritmos. Contudo, perceberemos que certos algoritmos podem ser mais eficientes do que outros. Para isso, vamos introduzir uma ferramenta para medir a eficiência de algoritmos, a análise de complexidade.

Bons estudos! Professores Rodrigo de Souza e Hugo Rodrigues

Algoritmos e Estrutura de Dados Conhecendo o Volume 1

Neste primeiro volume, você irá encontrar o módulo 01 da disciplina

Algoritmos e Estruturas de Dados. Para facilitar seus estudos, veja a organização deste primeiro módulo.

Módulo 1 – Noções básicas de algoritmos Carga horária do Módulo 1: 15h/aula

Objetivo do Módulo 1: Introduzir os conceitos de algoritmo e algoritmo recursivo. Fixar uma notação para apresentação de algoritmos. Introduzir elementos de análise de algoritmos.

Conteúdo Programático do Módulo 1 • História do conceito de algoritmo

Algoritmos e Estrutura de Dados

Capítulo 1 – História do conceito de algoritmo

Vamos conversar sobre o assunto?

suas despesas, orientar-se através de um GPS de bordoTalvez

Você provavelmente já usou um computador para alguma tarefa cotidiana – escrever uma carta, comunicar-se por e-mail, calcular já tenha precisado buscar uma palavra num texto, executar uma operação repetida numa planilha, ou determinar o caminho mínimo entre dois pontos em um mapa para percorrer com seu veículo. Já parou para pensar como o computador encontra a solução para esses problemas? Ou então já se perguntou se os computadores podem resolver qualquer problema?

Do ponto de vista do usuário, o computador é uma caixa preta que lhe fornece certas funcionalidades – como um eletrodoméstico comum. Para o estudioso de Computação, o computador, como objeto não-pensante, é meramente um mecanismo executor de sequências precisas de instruções. Tais sequências de instruções são o que chamamos de algoritmos. Algoritmos são, assim, o princípio do funcionamento de qualquer computador, e mais: desde a Antiguidade, o homem executa algoritmos, e é possível que cada um de nós tenha executado, ao longo de nossas vidas, algoritmos diversos. Quem nunca precisou ordenar as cartas de um baralho ou de um fichário?

A noção de algoritmo, sendo natural, pode ser compreendida mesmo por quem não utiliza computadores. É com esse espírito que vamos estudá-los nesse volume. Por outro lado, o domínio da noção de algoritmos vai nos fornecer uma compreensão mais profunda dos limites dos computadores e uma visão diferente da do usuário comum. Bom estudo!

1. O que é um algoritmo?

De forma geral, um algoritmo é uma sequência finita de instruções.

Uma receita de cozinha, se bem definida (especificando-se as quantidades de cada ingrediente e como eles serão misturados, por exemplo), é um algoritmo legítimo! Toda receita bem definida especifica com precisão os passos necessários para a elaboração

Algoritmos e Estrutura de Dados de um produto final. A execução de um algoritmo, nesse exemplo culinário, é simplesmente seguir a receita criteriosamente, passo a passo. Portanto, um algoritmo não tem necessariamente relação com um computador digital.

Mas essa definição parece muito geral e, para o estudioso de

Computação, uma definição formal é necessária. De fato, esse estudioso desejará demonstrar fatos sobre algoritmos – o quão eficiente um algoritmo pode ser, se o mesmo resolve corretamente o problema a que se propõe solucionar. Não é à toa que muitas vezes a Computação confunde-se com a Matemática. Dessa forma, qual a resposta definitiva à nossa questão, “O que é um algoritmo?”

A resposta parece misteriosa, mas é simples. Vamos respondêla com alguma precisão no Capítulo 2, onde entraremos em acordo sobre uma notação para apresentação de algoritmos. Por enquanto, podemos manter em mente a idéia intuitiva de sequência de instruções, com algumas restrições importantes:

• cada instrução pode ser executada de forma finita e mecânica (por um ser-humano usando apenas lápis e papel, por exemplo);

Essas restrições são importantes: se tudo é permitido, então a noção de algoritmo perde o interesse do ponto de vista prático. Quem quer esperar toda a eternidade para saber o saldo de sua conta quando vai consultar um terminal eletrônico?

Também é preciso considerar que um algoritmo dialoga com o mundo externo. Ele recebe uma entrada, alguma informação a ser processada, e fornece uma saída, o resultado desse processamento.

Algoritmos e Estrutura de Dados

No exemplo da receita, a entrada são os ingredientes, a saída é o produto que vamos cozinhar – um bolo, por exemplo.

Dissemos que a resposta é misteriosa, mas é simples. Também poderíamos dizer: a resposta é simples, mas por um bom tempo, foi misteriosa. A seguir, vamos sobrevoar o caminho trilhado pela civilização até a conquista da ideia precisa de algoritmos.

2. De onde vem a ideia de algoritmo?

A etimologia da palavra algoritmo revela um pouco de sua história.

Historiadores da Matemática concluíram que ela vem do nome de um matemático persa do século nove, Abu Já’far Mohammed ibn Mûsâ Al-Khowârizmî. Literalmente: “Pai de Ja’far Mohammed, filho de Moisés, nativo de Khowârizm”. Al-Khowârizmî deu origem, durante a Idade Média, ao termo algoritmo (seu nome foi latinizado como Algorismus), e este foi usado com significados diversos. Por exemplo, alguns dicionários antigos definem essa palavra como todo processo de cálculo combinando às quatro operações aritméticas fundamentais. O que é compreensível, pois Al-Khowârizmî era um autor importante de livros matemáticos, e supostamente inventou algoritmos para a realização dessas operações.

Mas como dissemos, algoritmos são processos que ocorrem naturalmente em nosso dia-a-dia, sendo nós estudiosos da Computação ou não. Mencionamos o exemplo da cozinha. Poderíamos considerar também o processo de montagem de uma estante, ou da busca de um nome numa lista telefônica. Dessa forma, fica evidente que desde a Antiguidade o homem imagina e executa algoritmos em sua rotina. E com relação a algoritmos mais complexos, como os que são executados mecanicamente por computadores?

Como você ordena comumente um baralho?

Será que você utiliza algum algoritmo para isso?

Algoritmos e Estrutura de Dados

Novamente, voltamos à Antiguidade: desde há muito tempo, o homem executa algoritmo não tão simples para realizar operações com números. Considera-se como primeiro exemplo de algoritmo não-trivial um procedimento descrito entre 400 e 300 antes de Cristo pelo matemático grego Euclides para encontrar o maior divisor comum entre dois números. O algoritmo de Euclides é hoje universalmente conhecido. Vamos ainda nesse módulo entender como ele funciona.

Da Antiguidade até hoje, além da invenção de novos algoritmos, o homem também se preocupou com a invenção de máquinas para executá-los. O exemplo mais clássico é o ábaco, que permite a realização de operações aritméticas com rapidez (de fato, a realização de uma operação aritmética obedece a um algoritmo, e tais algoritmos são introduzidos às crianças nos primeiros anos escolares). No século XIX, alguns nomes se destacam por tentativas de construção de máquinas executoras de instruções: o francês Joseph Jacquard, o inglês Charles Babbage e o estadunidense Herman Hollerith. Em particular, a máquina de Hollerith, que usava cartões perfurados, foi usada com sucesso no censo dos Estados Unidos de 1890. Tais máquinas foram precursoras dos computadores modernos.

Figura 1 - Três máquinas projetadas para auxiliar na execução de algoritmos: um ábaco, uma máquina de cartão perfurado e um computador.

O passo definitivo para a compreensão do conceito de algoritmo, tal como o conhecemos atualmente, foi dado no início do século X. O termo “procedimento efetivo”, que podemos entender como “método possível de realizar por meios mecânicos”, pairava no ar entre os matemáticos dessa época. Mas uma definição formal dessa idéia estava em falta. Questões como “encontre um procedimento efetivo para testar se uma fórmula é logicamente válida“ estavam

(Parte 1 de 9)

Comentários