(Parte 1 de 3)

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

Algoritmos I

Marco Aurélio Freitas Santos

M.Sc. Ciência da Computação

UNIGRAN - Dourados/MS marcoafs@unigran.br marco@unigran.br marco@dourados.br

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN APRESENTAÇÃO DO AUTOR

Marco Aurélio Freitas Santos, nascido em Coronel Fabriciano-MG é graduado em Ciência da Computação e mestre em Ciência da Computação pela UFRGS-Universidade Federal do Rio Grande do Sul. Analista de Sistemas, atua no mercado de informática de Mato Grosso do Sul e em outros Estados desde 1992, desenvolvendo sistemas para empresas de diversos ramos de atividade. É professor no curso de Ciência da

Computação da Unigran desde 1995. Já ministrou aulas nas disciplinas de Linguagens e técnicas de programação, Inteligência Artificial, Programação Comercial e Análise de Algoritmos. Atualmente ministra aulas de Engenharia de Software, Análise e Projeto de Sistemas, Tópicos Especiais em Sistemas de Informação, Algoritmos e Programação de Computadores, Paradigmas de Linguagens de Programação e Banco de Dados. É Analista de Sistemas do Departamento de Informática da Unigran, projetando e desenvolvendo sistemas desta instituição. Foi professor da Universidade Estadual de Mato Grosso do Sul e de instituições particulares.

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN APRESENTAÇÃO DA DISCIPLINA

Caros alunos,

A disciplina de Algoritmos I possui uma carga horária de 80 horas. Os objetivos da disciplina são: Estudar os conceitos de algoritmos, estruturas de controle e princípios de programação estruturada, modularização e estruturas de dados.

- Gerais: Incentivar a capacidade de pesquisa e desenvolvimento científico. Capacitar o aluno a aplicar o conhecimento adquirido de forma independente e inovadora e que possa acompanhar as constantes evoluções para contribuir na busca de soluções nas diferentes áreas de aplicação.

- Específicos: Propiciar ao aluno o desenvolvimento da lógica de programação através da matemática e da elaboração de algoritmos. Dotar o aluno com princípios do bom desenvolvimento de algoritmos através do estudo de algoritmos básicos e sua correção.

A disciplina introduz o aluno em uma lógica de programação proporcionando o conhecimento básico em estruturas que serão necessários para o aprendizado de qualquer linguagem de programação tendo como objetivo desenvolver suas habilidades para a resolução de problemas computacionais independentemente da linguagem de programação. Também temos como objetivo exercitar o raciocínio lógico e desenvolver a capacidade de abstração do aluno.

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

1. ALGORITMOS E ETAPAS DE PROGRAMAÇÃO 1.1. Introdução à Computação 1.2. Tipos Primitivos 1.3. Variáveis e Funções Pré-Definidas 1.4. Comandos de Atribuição, Entrada e Saída 1.5. Estruturas de Controle 1.5.1. Seqüencial 1.5.2. Condicional 1.5.3. Repetição 1.6. Modularização 1.6.1. Procedimentos 1.6.2. Funções

CRITÉRIOS DE AVALIAÇÃO: A avaliação será feita com trabalhos em classe e extra-classe, individuais e em equipe e provas bimestrais teóricas e práticas. A média bimestral será calculada da seguinte forma: Mb = (Mt + Pb) / 10

Onde: Mb = Média bimestral

Pb = Prova bimestral multiplicada pelo peso (que pode variar em cada prova) Mt = Média dos trabalhos multiplicados pelo peso (que pode variar em cada trabalho)

Sejam bem-vindos! Prof. Marco Aurélio Freitas Santos

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

1 INTRODUÇÃO

lgoritmos são seqüências de ações ou instruções organizadas logicamente para resolver um problema. Os algoritmos são o primeiro passo para a construção de programas. Através deles desenvolvemos o raciocínio lógico necessário para a resolução do problema proposto. Guimarães & Lages definem algoritmo como:

“[] é a descrição de um padrão de comportamento,

expressado em termos de um repertório bem definido e finito de ações primitivas, das quais damos por certo que elas podem ser executadas.” (GUIMARÃES; LAGES, 1994) ou ainda:

“[...] uma norma executável para estabelecer um certo efeito desejado, que na prática será geralmente a obtenção de uma solução a um certo tipo de problema.” (GUIMARÃES, 1994)

Para todas as tarefas que executamos no dia a dia, nosso cérebro constrói algoritmos, porém isso acontece de uma forma tão natural que nem percebemos, mas para cada problema ou atividade a ser trabalhada, definimos uma seqüência lógica de ações. Podemos afirmar então que construímos vários algoritmos todos os dias, mas não nos damos conta disso.

Capítulo 1

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

Os algoritmos são utilizados em praticamente todas as áreas do conhecimento existentes, pois as pessoas envolvidas na resolução dos mais diversos tipos de problemas precisam formular uma seqüência de ações para chegar a um resultado satisfatório.

Vamos imaginar uma situação da vida real, onde podemos perceber a criação de um algoritmo. Por exemplo, para assistir um filme em DVD, algumas seqüências de ações deverão ser executadas. Vamos considerar que o aparelho de DVD já está conectado a uma TV e que ambos estão prontos para funcionar, deveremos então executar os seguintes passos:

1 – Ligar a TV 2 – Ligar o DVD 3 – Abrir o compartimento do disco 4 – Inserir o disco 5 – Fechar o compartimento do disco 6 – Pressionar a tecla PLAY para iniciar o filme

Esta seqüência de instruções precisou ser definida para que fosse possível assistir o filme no aparelho de DVD. Pra nós pode parecer uma coisa muito simples, mas tivemos que montar uma seqüência de instruções para que fosse possível atender à necessidade (problema) em questão.

Em nossa vida cotidiana encontraremos diversas situações em que teremos que desenvolver algoritmos para resolver determinados problemas, tais como: trocar o pneu de um carro, preparar um bolo, arrumar o filho para a escola, etc.

É importante notar que para cada problema a ser resolvido, existem diversos caminhos que levam à solução desejada, ou seja, um problema pode ser resolvido de duas ou mais maneiras diferentes, obtendo o mesmo resultado, ou ainda poderemos ter umas soluções melhores que outras pra atingir o mesmo objetivo. No exemplo do DVD, por exemplo, ao invés de primeiro ligar a TV, poderíamos ligar o DVD e depois a TV, isto seria uma outra seqüência para a solução do problema, porém teríamos o mesmo resultado. Outra solução para o problema seria criar uma lista de ações com mais detalhes, como por exemplo acrescentar a ação de ajustar o canal da TV ou pressionar a tecla TV/VÍDEO para ajustar a sintonia com o aparelho de DVD.

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

O nível de detalhamento do algoritmo varia de acordo com o problema a ser resolvido. Isto não quer dizer que uma solução mais detalhada seja melhor ou pior que outra menos detalhada. A decisão de usar mais ou menos ações para atingir o objetivo deve ser analisada em cada situação separadamente.

No computador vale a mesma regra, um problema poderá ter duas ou mais soluções diferentes para chegar ao objetivo, que é a solução do problema proposto.

1.1 Percepção do problema Diferente do que muitos profissionais que trabalham com algoritmos e programação, a primeira coisa a se pensar não é na solução do problema, o primeiro passo para a criação de um algoritmo é a percepção do problema. Muitas pessoas sentem dificuldade em iniciar o desenvolvimento do algoritmo porque focam suas idéias iniciais na solução e não no problema. Nenhum problema poderá ser resolvido se não for minuciosamente entendido, portanto o foco inicial deve ser em cima do problema para depois se pensar na solução.

O entendimento detalhado do problema é um fator que diferencia uma solução algorítmica da outra. Quanto mais se conhece sobre o problema em questão, maiores as chances de se criar soluções melhores. Daí surgem alguns desafios para a criação do algoritmo, o primeiro é o de usar uma boa parcela de criatividade para criar uma ou mais alternativas de solução para o problema, em seguida, transformar esta idéia abstrata em algo em forma de seqüência de ações.

A arte de criar algoritmos não deve ser encarada apenas como a criação de uma solução para o problema, mas sim como a criação da melhor solução possível. Como já foi comentado anteriormente, podem existir várias soluções para o mesmo problema, cabe então ao desenvolvedor do algoritmo pensar em duas ou mais soluções diferentes para poder analisá-las, compará-las e decidir qual delas é a melhor. Vale lembrar que o tamanho ou complexidade do algoritmo não é relativamente proporcional à sua qualidade. Paulo A. S. Veloso afirma que:

“A construção metódica de programas confiáveis é, sem dúvida, uma das questões centrais da Ciência da Computação”. (VELOSO, 1987).

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

Para cada problema a ser levado ao computador, deve-se planejar as operações correspondentes. O automatismo exige que o planejamento destas operações seja feito previamente, antes de se utilizar o computador.

Então, a utilização de um computador para se resolver qualquer problema exige, antes de mais nada, que se desenvolva um algoritmo, isto é, que se faça a descrição do conjunto de comandos ordenados que, quando obedecidos, resultarão na realização da tarefa desejada obtendo os resultados esperados. Os algoritmos encontram-se entre a idéia de se resolver um problema através do computador e o sistema desenvolvido pelas linguagens de programação.

A elaboração de algoritmos é, para estudantes de Ciência da Computação e áreas afins, o passo inicial para a solução de qualquer problema computacional. Isto significa que, identificado o problema, será necessária a escrita de uma série de instruções, normalmente escritas em português, ou bem próximas dele, numa ordem logicamente definida, para que se obtenha a solução final do problema. É deste modo que se torna possível a construção de programas em qualquer linguagem de computador.

Figura 1.1 - Resolução do problema e programação.

2 ALGORITMOS ESTRUTURADOS

Desenvolver algoritmos estruturados é basicamente utilizar uma metodologia de projeto de programas, com os seguintes objetivos:

Problema

Solução como um programa

Solução em forma de algoritmo

Passo difícil

Fase da resolução do problema

Fase da Implementação

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

Facilitar a escrita dos algoritmos; Facilitar a leitura e o entendimento dos algoritmos; Facilitar a manutenção e modificação dos algoritmos.

O grande desafio da escrita de programas e reduzir a complexidade dos mesmos.

Muitos programas são escritos de uma forma tão complicada que até o próprio autor tem dificuldade de interpretá-lo depois. Para reduzir a complexidade dos algoritmos deve-se:

Escrever o algoritmo fazendo refinamentos sucessivos (chamado de Desenvolvimento Top-Down) – esta técnica consiste em ir escrevendo as funções principais do programa e depois detalhar cada uma delas em funções menores, até que se tenha um último nível que não é mais possível detalhar; Decompor o algoritmo todo em módulos funcionais – é mais fácil compreender uma solução se a analisarmos por partes, ao invés de olharmos a solução como um todo. A este processo chamamos de Modularização; Usar soluções simples e não muito extensas em cada um dos módulos, com poucas estruturas de controle para facilitar o entendimento.

2.1 Desenvolvimento Top-Down

Depois de entendermos o problema a ser solucionado, precisamos formular alternativas de solução para o mesmo. Para isto, formulamos uma possível solução, porém, esta solução precisa ser refinada, ou seja, detalhada em partes menores até que se tenha uma visão de todos os detalhes.

2.2 Modularização

A modularização consiste em dividir a solução do problema em partes, ou módulos, cada um com funções bem definidas, dando maior agilidade ao desenvolvimento.

2.3 Estruturas de controle

O uso de estruturas de controle adequadas afeta diretamente a qualidade do algoritmo. Muitos programadores tem o costume de usar comandos de desvio

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN incondicional ou de interrupção do algoritmo. Um desvio incondicional é aquele em que o programa muda seu fluxo de execução arbitrariamente. Este artifício é muito usado quando não se tem um completo domínio da lógica do programa, mas deve ser evitado, pois ele provoca a quebra da estrutura lógica do algoritmo.

3 PROGRAMAS E LINGUAGENS DE PROGRAMAÇÃO

Escrever um programa é o mesmo que traduzir um algoritmo para uma linguagem de programação qualquer. As linguagens de programação são softwares que permitem transformar um algoritmo em um programa de computador.

Aprender uma nova linguagem de programação é uma tarefa fácil quando se tem um bom conhecimento de algoritmos, pois o maior problema na criação de um programa não é a linguagem em si, mas sim as dificuldades na percepção do problema e na formulação de uma solução, ou melhor, de uma boa solução.

Existem linguagens para os mais diversos domínios de aplicação, cada uma com seus propósitos. Algumas são destinadas ao desenvolvimento de aplicações comerciais, outras têm propósito científico, para aplicações em inteligência artificial e também aquelas para criação de programas para internet, etc. As linguagens podem ser interpretadas, compiladas ou híbridas.

3.1 LINGUAGENS INTERPRETADAS Nas linguagens interpretadas, o interpretador lê, analisa e executa cada instrução do programa fonte, sem traduzir para uma linguagem de máquina. Cada linha ou instrução é executada na seqüência. Quando um erro é encontrado, a execução do programa é interrompida.

O interpretador simula por software uma máquina virtual, onde o ciclo de execução entende os comandos da linguagem de alto nível.

Este tipo de linguagem oferece algumas desvantagens, como a necessidade da presença do código fonte para a execução do programa. Também o interpretador da linguagem precisa estar instalado no computador onde está o programa. A execução do programa é bem mais lenta que nas linguagens compiladas, pois o interpretador precisa analisar as instruções do programa sempre que vai executá-las.

Algoritmos I – Marco Aurélio Freitas Santos - UNIGRAN

Figura 1.2 – Funcionamento das linguagens interpretadas

3.2 LINGUAGENS COMPILADAS

Os compiladores tem a tarefa de ler e analisar o programa escrito em uma linguagem de programação, o programa fonte ou código fonte, e traduzi-los para a linguagem de máquina, executando-os diretamente no computador. Diferente da interpretação, a compilação analisa todo o código fonte a procura de erros, só depois que esta análise termina e que nenhum erro tenha sido encontrado, é que será criado um código intermediário chamado de “código objeto”. Este código objeto será então linkeditado (ou ligado) e um código executável será gerado.

Nos programas compilados, não há a necessidade da presença do código fonte para a sua execução, assim como o compilador não precisa estar instalado para isto. O programa executável criado é independente da linguagem. Neste caso, a execução do programa é mais rápida, uma vez que o programa fonte não precisará ser analisado em cada execução.

(Parte 1 de 3)

Comentários