Embed Size (px)
Citation preview
ALGORITMOS E LÓGICA DE PROGRAMAÇÃOCesar Bezerra Teixeira,MSc
PREFÁCIO
Programação é a arte de escrever roteiros para execução no computador. Tais
roteiros destinam-se às mais diversas tarefas, indo desde arte até software embarcado
em aviões e naves espaciais. É um fascinante ramo do Conhecimento, mesmo para
aqueles que não a utilizam como profissão. Desde o primeiro contato que tive com essa
arte, fui capturado por uma “febre”, que nos leva a passar horas tentando montar
programas e a cada dia somos apresentados a uma fonte que parece inesgotável. Na
verdade estar atualizado é um eterno desafio, a tecnologia muda constantemente,
surgindo a cada dia novas linguagens e técnicas.
Destarte a grande necessidade de atualização tecnológica, a programação
necessita de algumas características fundamentais, sendo as mais importantes, um bom
conhecimento de Matemática e Lógica. Em todos os cursos que utilizam programação
como ferramenta (Computação, Engenharia, Tecnologia da Informação,...), a cadeira de
Algoritmos e Lógica de programação é básica, mas cada curso tem um propósito
específico e encontrar um material didático que atenda a um determinado conteúdo
programático é uma tarefa bastante árdua.
Com finalidade de suprir essa deficiência e baseado nos anos como professor e
nos muitos cursos de programação que ministrei, procurei preparar um material que fosse
comum a todos aqueles que querem dar seus primeiros passos na Lógica de
Programação. Espero conseguir transmitir de uma maneira fácil, esta matéria tão
importante para aqueles que desejam tornar-se profissionais dos “bits e bytes” ou para os
apaixonados por essa Arte. Finalmente gostaria de ressaltar que por melhores que
tenham sido meus esforços para produzir um bom material, muitos erros devem ser
encontrados e me coloco inteiramente à disposição de meus leitores, para
esclarecimentos adicionais ou para receber suas sugestões.
Boa Leitura !!!
Cesar Bezerra Teixeira
SUMÁRIOCAP 1 - INTRODUÇÃO
1.1) Generalidades
1.2) Conceitos Básicos:
1.3) Desenvolvimento de SI e o Programador
1.4) O Computador à gaveta
1.5) Exercícios
CAP 2 - SOLUÇÃO DE PROBLEMAS USANDO ALGORITMOS2.1) Problemas e Soluções
2.2) Definições de Algoritmos
2.3) Técnicas de Representação de Algoritmos
2.4) Algoritmos Estruturados
2.5) Pseudo-Código:
2.5.1) Identificadores, Constantes, Variáveis e tipos Básicos
2.5.2) Palavras Reservadas
2.5.3) Comando de Atribuição
2.5.4) Operadores
2.5.5) Entrada e Saída de Dados
2.5.6) Estrutura de um Algoritmo em pseudo-código
2.6) Documentação
2.7) Exercícios
CAP 3 - ESTRUTURAS BÁSICAS DE CONTROLE3.1) Seqüência
3.2) Seleção:
3.3) Repetição:
3.4) Como construir bons algoritmos
3.5)Exercícios
CAP 4 - REGISTROS4.1) Introdução
4.2) Registros:
4.3) Arquivos:
4.4)Exercícios
CAP 5 - VETORES E MATRIZES5.1) Vetores:
5.2) Matrizes
5.3) Exercícios
CAP 6 - MODULARIZAÇÃO DE ALGORITMOS6.1) Procedimentos
6.2)Funções
6.3) Estruturação dos Módulos de um Algoritmo
6.4)Exercícios
CAP 7 - ALGORITMOS DE PESQUISA E ORDENAÇÃO7.1) Introdução
7.2) Algoritmos de Pesquisa:
7.3) Algoritmos de Ordenação:
CAP 8 – TÓPICOS AVANÇADOS8.1) Introdução
8.2) O processo de tradução;
8.3) Introdução à Teoria de Sistemas
8.4) Programas, Algoritmos e Estruturas de Dados
CAPÍTULO 1OBJETIVO
"Apresentar os principais conceitos relativos à Arte de Programar Computadores."
SUMÁRIO1.1) Generalidades
1.2) Conceitos Básicos:
1.3) Desenvolvimento de SI e o Programador
1.4) O Computador à Gaveta
1.5) Exercícios
1.1) GENERALIDADESProgramação de Computadores Digitais, é uma atividade que remonta o início do
século XX, desde o surgimento das primeiras linguagens de programação. Inicialmente
aprendia-se a programar usando-se a própria linguagem como ferramenta. A linguagem
FORTRAN criada em 1954, tendo seu primeiro compilador terminado em 1957 e foi
durante muito tempo usada para o ensino da arte da programação, inclusive no Brasil.
Nas décadas de 60 e 70, com o aparecimento de outras linguagens, um método gráfico, o
FLUXOGRAMA, foi grandemente utilizado em complemento ao anterior.
Atualmente após o aparecimento de centenas de linguagens de programação e
vários métodos de representação da solução de problemas, pode-se estudar
programação, sem que se utilize uma linguagem em particular, aprendendo-se como
construir Algoritmos. O objetivo a alcançar com o estudo de algoritmos é desenvolver a
capacidade de transformar um problema complexo em um algoritmo de boa qualidade,,
utilizando os conceitos da teoria de sistemas e o princípio do “dividir para conquistar”, ou
seja um grande problema deve ser dividido em partes menores, tratáveis. A soma da
solução das partes menores, resolverá o problema como um todo.
1.2) CONCEITOS BÁSICOS
Dados Elementos brutos que podem ser processados por um
computador digital, para se obter alguma conclusão ou resultado.
Computador Máquina (hardware) muito rápida que pode processar dados,
Digital realizando cálculos e operações repetitivas, integrantes de um
programa (software), fornecendo resultados corretos e precisos.
Informação É o resultado do processamento de dados pelo computador,
representa um estágio superior ao do simples dado, possui valor
agregado, em relação àquele.
Hardware Termo de origem americana que engloba todo o equipamento
principal e periférico de um computador(parte física).
Software Outro termo de origem americana que engloba programas,
documentação, procedimentos, dados, utilizados em um
computador para resolução de problemas.
Programa de Seqüência de instruções não ambíguas, finitas, escritas em uma
Computador linguagem de programação específica, que resolvem um
determinado problema.
Linguagem É a linguagem binária (composta de zeros e uns)
de Máquina utilizada pelos computadores, internamente, para representar
dados, programas e informações. É tediosa, difícil de se
compreender e fácil de gerar erros na programação. É a
linguagem de programação mais baixo nível.
Linguagem É uma linguagem mnemônica, particular para cada processador,
Assembler que codifica as instruções em linguagens de máquina, visando
facilitar um pouco o trabalho do programador. É também
considerada uma linguagem de baixo nível.
Linguagem Também chamada de linguagem de alto nível, engloba todas as
de 3a linguagens de programação que utilizam compiladores e
Geração interpretadores. Possuem instruções mais poderosas e mais
fáceis de se compreender que a linguagem ASSEMBLER,
facilitando o trabalho do programador.
Linguagem São linguagens não procedurais, utilizadas para sistemas de
de 4a gerenciamento de banco de dados, planilhas e outros
Geração aplicativos que utilizam comandos mais poderosos que as de 3ª
Geração, sendo mais fáceis de programar(Ex.: SQL).
Compilador É um programa utilizado para traduzir os programas escritos
pelo programador nas linguagens de alto nível (programa
fonte) para a linguagem de máquina (programa executável), a
fim de que possa ser executado no computador.
Interpretador É um programa que traduz os programas escritos pelo programa-
dor para a linguagem de máquina, no momento da execução, não
existindo portanto o programa executável.
Um importante conceito é de que o computador é uma máquina elétrica, ou seja, o
final do processo da execução de um programa será a ativação de sinais elétricos, que
farão o computador se comportar como planejamos. Num nível acima dos circuitos está a
linguagem de máquina fornecida pelo fabricante. Neste nível também há grande
complexidade e por esta razão surgiram as linguagens de programação. O diagrama a
seguir ilustra de forma bastante sucinta, o processo que transforma um roteiro escrito
numa linguagem de programação, para um roteiro em linguagem de máquina que pode
ser executado diretamente pelo computador.
FONTE => COMPILADOR / INTERPRETADOR => LINGUAGEM DE MÁQUINA
HARDWARE
O hardware de um computador, segundo a arquitetura básica proposta por
Von Neumann, é composto dos seguintes elementos principais:
a) Unidade Central de Processamento, composta de:
- Unidade de Aritmética e Lógica, responsável pela realização de todas as operações
lógicas e aritméticas no computador;e
- Unidade de Controle, responsável pelo controle de todos os elementos do computador e
periféricos, recebendo sinais de estado destes e gerando sinais de controle para estes.
b) Memória Principal, é o elemento que armazena programas, dados e informações
(resultados)durante a execução de um programa. Cada posição de memória possui um
endereço e um conteúdo.
c) Dispositivos de Entrada/Saída ou Periféricos, são os responsáveis pela entrada de
dados na UCP/MP e a saída de informações da UCP/MP.
A Figura a seguir ilustra a Arquitetura de Von Neumann:
A memória (secundária) é a responsável pelo armazenamento em caráter
permanente de programas e dados, é onde se localizam os arquivos de dados, de
programas ou de saída (resultados). A memória primária é normalmente volátil,
perdendo seus dados ao desligarmos o computador.
SOFTWARE
O software de um computador é o que determina seu uso e os resultados que
serão produzidos e apresentados. Em um computador digital existem diversos tipos de
software, em camadas, com finalidades e complexidades diferentes. Normalmente,
quanto mais relacionado e próximo ao hardware, mais complexo e difícil de se
desenvolver e manter ele é. O diagrama a seguir procura ilustrar as diversas camadas de
software:
1) ALGORITMOS
2) PROGRAMAS APLICATIVOS
3) COMPILADORES / INTERPRETADORES
UTILITÁRIOS
PROCESSADORES DE TEXTO
BANCO DE DADOS
PLANILHAS
4) SISTEMA OPERACIONAL
5) HARDWARE
UNIDADESDE
ENTRADA
UNIDADEDE
PROCESSAMENTO
UNIDADESDESAÍDA
MEMÓRIA
1.3) DESENVOLVIMENTO DE SI E O PROGRAMADORUm sistema de informação pode ser definido como um sistema baseado em
computador, que auxilia, automatiza e otimiza o funcionamento de qualquer atividade,
através de:
1. Redução da participação do homem em atividades rotineiras e repetitivas;
2. Aumento da facilidade na coleta e armazenamento de dados e na rapidez de
recuperação e manuseio destes;
3. Redução do número de erros produzidos em operações de coleta, arquivamento e
recuperação de dados e informações;
4. Aumento da facilidade e flexibilidade na geração de relatórios, entre outros.
Para entender o papel do analista de sistemas e do programador é necessário
entender as etapas componentes do ciclo de vida:
1ª Fase = Estudo de Viabilidade (Estudos Iniciais)
2ª Fase = Análise Detalhada do Sistema (Projeto Lógico)
3ª Fase = Projeto Preliminar do Sistema (Projeto Físico)
4ª Fase = Projeto Detalhado do Sistema (Algoritmos)
5ª Fase = Codificação
6ª Fase = Teste
7ª Fase = Implantação
8ª Fase = Entrega
9ª Fase = Manutenção
No desenvolvimento de um projeto, quanto mais tarde um erro é detectado, mais
dinheiro e tempo são gastos para repará-lo.
1.4) O COMPUTADOR “À GAVETA”Para uma compreensão inicial do conceito de algoritmo e como ele pode ser
executado num computador, será utilizado um modelo imaginário de computador, o computador à gaveta . Tal dispositivo tem as características básicas de um computador
real, possuindo, no entanto, um mecanismo extremamente simples para poder ser
compreendido, no lugar de sofisticados circuitos eletrônicos. Tal modelo aproxima-se
bastante da arquitetura de um computador real e da forma como são executadas as
instruções, bem como apresenta de forma simbólica a linguagem de máquina.
COMPONENTES DESCRIÇÃO
GAVETEIRO COM
99 GAVETAS
AS GAVETAS SIMBOLIZAM A MEMÓRIA PRINCIPAL. CADA GAVETA É UM ENDEREÇO, QUE CONTÉM UM PEQUENO
QUADRO NEGRO , ONDE É ESCRITO UM NÚMERO SEMPRE DE 3 ALGARISMOS E OUTRAS INFORMAÇÕES. O
GAVETEIRO OBEDECE ÀS SEGUINTES REGRAS DE UTILIZAÇÃO:
1. EM QUALQUER MOMENTO, NO MÁXIMO UMA GAVETA PODE ESTAR ABERTA;
2. A LEITURA DO QUADRO NEGRO DE UMA GAVETA NÃO ALTERA O CONTEÚDO QUE NELE ESTÁ
GRAVADO;
3. A ESCRITA DE UMA INFORMAÇÃO NO QUADRO NEGRO DE UMA GAVETA É SEMPRE PRECEDIDA DE
SEU APAGAMENTO;
4. SOMENTE O OPERADOR CHICO PODE TER ACESSO AO GAVETEIRO;
CALCULADORA
A CALCULADORA POSSUI UM MOSTRADOR, INTITULADO ACUMULADOR E UM TECLADO, QUE NO CONJUNTO
SIMBOLIZAM A UNIDADE DE ARITMÉTICA E LÓGICA DE UM PROCESSADOR. PODEM SER REALIZADAS 2 TIPOS
DE OPERAÇÕES: (1) CARGA DE UM NÚMERO NO ACUMULADOR;
(2) REALIZAÇÃO DE UMA OPERAÇÃO ARITMÉTICA.
QUADRO NEGRODENOMINADO EPI(ENDEREÇO DA PRÓXIMA INSTRUÇÃO) ,SIMBOLIZANDO O REGISTRADOR
QUE INDICA O ENDEREÇO DA PRÓXIMA INSTRUÇÃO A SER EXECUTADA;
PORTA-CARTÕES
SIMBOLIZANDO UMA UNIDADE DE ENTRADA DE DADOS COMO, POR EXEMPLO, UM TECLADO, DE
FUNCIONAMENTO SIMILAR A UM PORTA GUARDANAPOS, QUE OS EMPILHA PARA SEREM LIDOS E
INTERPRETADOS, OBEDECENDO AS SEGUINTES REGRAS:
1. CARTÕES COM INFORMAÇÕES SÃO COLOCADOS EXCLUSIVAMENTE NA PARTE SUPERIOR, CONTENDO
UM NÚMERO DE 3 ALGARISMOS;
2. CARTÕES SÃO RETIRADOS DA EXTREMIDADE INFERIOR, UM DE CADA VEZ, APARECENDO NA MESMA
ORDEM EM QUE FORAM COLOCADOS NO DISPOSITIVO;
3. A RETIRADA DE CARTÕES SÓ PODE SER FEITA PELO CHICO ;
4. A COLOCAÇÃO DE CARTÕES SÓ PODE SER FEITA PELO USUÁRIO ;
FOLHA DE SAÍDA
SIMBOLIZANDO UMA UNIDADE DE SAÍDA COMO, POR EXEMPLO, UM MONITOR, CONSISTINDO
DE UMA FOLHA DE PAPEL ONDE PODE SER ESCRITO UM NÚMERO EM CADA LINHA,
UTILIZANDO-SE SEMPRE LINHAS CONSECUTIVAS. SOMENTE O CHICO PODE ESCREVER
NESTA FOLHA;
OPERADOR DE
SISTEMA
UMA PESSOA CHAMADA CHICO, COM LÁPIS, APAGADOR E GIZ (SIMBOLIZANDO O SISTEMA OPERACIONAL). O
CHICO É O ÚNICO QUE TEM ACESSO AO GAVETEIRO, À CALCULADORA, AO EPI E É O ÚNICO QUE PODE
RETIRAR CARTÕES DO PORTA-CARTÕES E ESCREVER NA FOLHA DE SAÍDA. ELE EXECUTA ESTRITAMENTE
ORDENS RECEBIDAS, NÃO PODENDO TOMAR NENHUMA INICIATIVA PRÓPRIA. O CHICO SABE FAZER DE
“CABEÇA” UMA ÚNICA OPERAÇÃO ARITMÉTICA: INCREMENTAR DE 1 O CONTEÚDO DO EPI E TRABALHA
SEMPRE EM UM DE DOIS ESTADOS DIFERENTES:
1. ESTADO DE CARGA , ONDE ELE EXCLUSIVAMENTE TRANSFERE INFORMAÇÕES DE CARTÕES,
LIDOS DO PORTA-CARTÕES, PARA GAVETAS DO GAVETEIRO;
2. ESTADO DE EXECUÇÃO , ONDE ELE EXECUTA ORDENS GRAVADAS NAS GAVETAS;
Para resolver um problema usando o computador de papel o usuário deve planejar
uma seqüência de ordens a serem executadas pelo CHICO. Essa seqüência é escrita nas
gavetas do gaveteiro, na seqüência adequada. Para executar uma instrução da
seqüência, o CHICO segue os seguintes passos, simbolizando o ciclo de execução de
instruções de um computador:
1. Consultar o EPI (próxima instrução);
2. Incrementar de 1 o conteúdo do EPI;
3. Abrir a gaveta do endereço “E”, onde deve encontrar uma instrução I, que é lida;
4. Fechar a gaveta “E”;
5. Executar a instrução “I”;
As instruções escritas nas gavetas constituem um programa armazenado. O usuário
deve formular o método de resolução de seu problema sob a forma de programa. As
instruções deste programa obedecem ao seguinte ciclo:
1. usuário escreve cada instrução(I) em um cartão, precedida de um endereço(E). Cada cartão possui
um par ordenado (E,I);
2. CHICO é colocado em estado de carga de programa;
3. usuário coloca o conjunto de cartões do programa no porta-cartões, em qualquer ordem;
4. Com o CHICO em estado de carga, ele executa as seguintes operações:
Lê um cartão com um par (E,I);
Abre a gaveta de endereço E;
Escreve em seu quadro negro (EPI) a instrução I;
Fecha essa gaveta;
CHICO repete o passo anterior até ler o último cartão de programa, após o que ele
é colocado em estado de execução de programa. O computador a gaveta suporta uma
linguagem de programação, com instruções semelhantes à uma linguagem de máquina,
fornecida pelos fabricantes juntamente com os processadores. Tais instruções são as
seguintes:
1. SOMA;
2. CARGA NO AC (ACUMULADOR);
3. ARMAZENAMENTO NO AC;
4. IMPRESSÃO;
5. LEITURA;
6. DESVIO CONDICIONAL;
7. PARE;
EXEMPLO DE PROGRAMA COM O COMPUTADOR À GAVETA
PROBLEMA “DADA UMA SEQÜÊNCIA DE NÚMEROS INTEIROS POSITIVOS, DETERMINAR SUA SOMA.”
SOLUÇÃOEscrever cada número da seqüência num cartão;
COLOCAR DOIS CARTÕES COM O NÚMERO “0”, APÓS O PRIMEIRO E O ÚLTIMO CARTÃO DO ALGORITMO ;
ALGORITMO
01 leia um cartão e guarde em 11
02 leia um cartão e guarde em 12
03 Imprima o conteúdo de 12
04 carregue no Acumulador(AC) o Conteúdo de 11
05 some o Conteúdo de 12 ao AC
06 armazene o conteúdo do AC em 11
07 carregue o C-12 no AC
08 Se o conteúdo do acumulador for diferente de 0, desvie para 02
09 imprima o conteúdo de C-11
10 pare
Para resolver o problema no computador à gaveta, deve ser formada uma pilha de
cartões e colocada no porta-cartões, com o seguinte conteúdo e na seguinte ordem:
1. PROGRAMA2. EXECUTE 013. CARTÕES DE DADOS (A e B)Terminada a execução é recebida a folha de saída, onde estarão impressos os
números da seqüência, seguidos da soma desejada.
RASTREIO DO PROGRAMA COM DADOS REAIS
Seja a seqüência 100,5 e 31. Suponhamos que CHICO tenha carregado o
programa e tenha encontrado o cartão “EXECUTE 01”. CHICO apaga o conteúdo do EPI,
escreve nele o número 01 e começa e executar as instruções do programa. A tabela a
seguir ilustra o estado do computador ao longo da execução do programa (rastreio):
GAVETA PORTA-CARTÕES AC 11 12 FOLHA EPI
- 000,100,005,031,000 - - - - 01
01 100,005,031,000 - 000 - - 02
02 005,031,000 - 000 100 X 03
03 005,031,000 - 000 100 100 04
04 005,031,000 000 000 100 100 05
05 005,031,000 100 000 100 100 06
06 005,031,000 100 100 100 100 07
07 005,031,000 100 100 100 100 08
08 005,031,000 100 100 100 100 09
02 031,000 100 100 005 100 03
03 031,000 100 100 005 100,005 04
04 031,000 100 100 005 100,005 05
05 031,000 105 100 005 100,005 06
06 031,000 105 105 005 100,005 07
07 031,000 005 105 005 100,005 08
08 031,000 005 105 005 100,005 02
02 000 005 105 031 100,005 03
03 000 005 105 031 100,005,031 04
04 000 105 105 031 100,005,031 05
05 000 136 105 031 100,005,031 06
06 000 136 136 031 100,005,031 07
07 000 031 136 031 100,005,031 08
08 000 031 136 031 100,005,031 02
02 - 031 136 000 100,005,031 03
03 - 031 136 000 100,005,031,000 04
04 - 136 136 000 100,005,031,000 05
05 - 136 136 000 100,005,031,000 06
06 - 136 136 000 100,005,031,000 07
07 - 000 136 000 100,005,031,000 08
08 - 000 136 000 100,005,031,000 09
09 - 000 136 000 100,005,031,000,136 10
10 - 000 136 000 100,005,031,000,136 -
O programa será considerado correto, se ele resolver o problema para qualquer
seqüência de números, parando após a leitura da seqüência e execução dos cálculos,
obtendo a resposta esperada. A capacidade de repetir instruções é uma característica
fundamental dos programas de computador. A partir dela é que se obtém um programa
com um número finito de instruções, mas capaz de representar a execução de um número
potencialmente infinito das mesmas (ou seja, tão grande quanto se queira).
1.4) EXERCÍCIOS
1) Qual foi e quando surgiu a primeira linguagem de programação?
2) Que ferramenta gráfica foi amplamente utilizada na década de 70, para
representação de algoritmos?
3) Qual a diferença entre dados e informação?
4) Defina hardware e software.
5) O que é linguagem de máquina?
6) Quais são as fases componentes do ciclo de vida de um SI?
7) Quais as camadas componentes de um software?
8) Para que serve a memória secundária?
9) O que é um programa armazrnado?
10)Desenhe a Arquitetura de Von Neumann, explicando a função de cada um de seus
componentes .
SUGESTÕES DE CONSULTA
1. Museu Virtual de Informática – http://piano.dsi.uminho.pt/museuv/index.html;
2. Dicionário de Informática – http://www.netpedia.com.br/;
3. Wikipedia – http://pt.wikipedia.org.
CAPÍTULO 2"A arte de programar consiste na arte de organizar e dominar a complexidade."
[Dijkstra]
OBJETIVO"Apresentar o conceito de algoritmo e os principais tópicos referentes à sua elaboração."
SUMÁRIO2.1) Problemas e Soluções
2.2) Definições de Algoritmos
2.3) Técnicas de Representação de Algoritmos
2.4) Algoritmos Estruturados
2.5) Pseudo-Código:
2.5.1) Identificadores, Constantes, Variáveis e tipos Básicos
2.5.2) Palavras Reservadas
2.5.3) Comando de Atribuição
2.5.4) Operadores
2.5.5) Entrada e Saída de Dados
2.5.6) Estrutura de um Algoritmo em pseudo-código
2.6) Documentação
2.7) Exercícios
2.1) PROBLEMAS E SOLUÇÕESVejamos alguns exemplos de tarefas que realizamos rotineiramente:
EXEMPLO 1 Após um banho uma pessoa deseja vestir cada uma das peças em uma seqüência
que pode variar. A seguir é estabelecida uma solução para esse problema:
1º - Vestir a cueca
2º - Colocar as meias
3º - Vestir a camisa
4º - Vestir a calça
5º - Calçar os sapatos
6º - Colocar o cinto
7º - Colocar a gravata
8º - Vestir o paletó
EXEMPLO 2Pregar um prego numa madeira:
1º - Segurar o prego sobre a madeira com a mão esquerda
2º - Bater com o martelo no prego, com a mão direita
3º - Se o prego estiver todo dentro da madeira encerre as ações
Senão volte ao passo 1 e repita a seqüência.
Naturalmente os algoritmos que serão resolvidos pelos computadores não serão
tão simples. De uma maneira geral as fases que compreendem a solução de um
problema em um computador são apresentadas a seguir:
Fase de Resolução do Problema
PROBLEMA ========================
||
\/
ALGORITMO||
\/
PROGRAMA ========================
Fase da Implementação do Programa
A tentativa de se produzir um programa diretamente de um problema, sem passar
pela elaboração de um algoritmo é de grande complexidade e com grande probabilidade
de ocorrência de erros.
2.2) DEFINIÇÕES DE ALGORITMOSUm algoritmo é a descrição de um padrão de comportamento, expresso em termos
de um repertório bem definido e finito de ações primitivas, que temos certeza que podem
ser executadas. Também podemos definir um algoritmo como uma seqüência de passos
ordenados, finitos, não ambíguos que levam à solução de um determinado problema. Tais
definições mostram que um algoritmo precisa possuir os seguintes elementos:
a) Ter início e fim;
b) Ser descrito em termos de ações não ambíguas e bem definidas;
c) As ações devem seguir uma seqüência ordenada
Exemplos de algoritmos:
a) Instruções de operação de um equipamento;
b) Receita de um bolo ou de um prato;
c) Instruções de montagem;
d) Partituras de músicas;
e) Programa de computador (algoritmo representado numa LP)
2.3) TÉCNICAS DE REPRESENTAÇÃO DE ALGORITMOSOs algoritmos podem ser representados de diversas forma:
(a) Em uma língua (português, inglês): É utilizado nas receitas, instruções, etc... . É
inadequado para solução de problemas computacionais pois pode apresentar
ambigüidade em alguns termos;
(b) Diretamente numa linguagem de programação, apresentando o inconveniente de
utilizar apenas as instruções da linguagem, preocupando-se com sintaxe,
desviando a atenção do programador, para o problema em si;
(c) Representações Gráficas: São bastante recomendáveis, já que um desenho
substitui com vantagem mil palavras. Como exemplos pode-se citar o fluxograma.
(d) Pseudo-Linguagem: Não tem os inconvenientes da ambigüidade de uma língua,
nem os rigores de uma linguagem de programação(LP), sendo bastante
recomendada.
2.4) ALGORITMOS ESTRUTURADOS
Quando queremos resolver um problema no computador, a seqüência de passos
que conduzem à solução é detalhada, até que se chegue a um conjunto de ações
primitivas que chamamos de comandos ou instruções, que podem ser entendidas e
executadas pela máquina. Este algoritmo de maior nível de detalhamento possível,
quando traduzido para uma linguagem de programação constituirá um programa.
Uma das vantagens de programar utilizando um algoritmo é que o problema está
documentado e pode ser implementado em outras linguagens de programação, dando
portabilidade. A programação estruturada ou o desenvolvimento de algoritmos
estruturados consiste na utilização de técnicas que permitem a sistematização do
desenvolvimento, o que simplifica bastante a solução de problemas grandes e
complexos. Os objetivos desta técnica são:
a) Facilitar o desenvolvimento e representação dos algoritmos;
b) Facilitar a leitura e entendimento dos algoritmos pelas pessoas;
c) Antecipar a comprovação de sua correção;
d) Facilitar a manutenção (correções e modificações) dos programas e algoritmos;
e) Permitir que o desenvolvimento de algoritmos possa ser empreendido
simultaneamente por uma equipe de pessoas;
Para alcançar tais objetivos, os algoritmos devem observar 3 premissas básicas:
(1) Devem ser desenvolvidos em diferentes fases de detalhamento crescente, do
geral para o particular, por refinamentos sucessivos;
(2) Devem ser decompostos em módulos funcionais, organizados de preferência
em um sistema hierárquico. Tais módulos trazem vantagens adicionais, tais como:
- cada módulo pode ser desenvolvido por um programador diferente;
- são mais fáceis de testar, permitindo testes independentes;
- Permite a reutilização de um módulo em outro algoritmo;
(3) Dentro de cada módulo devem ser utilizados poucos e bem definidos comandos
e estruturas de controle;
2.5) PSEUDO CÓDIGO:Nos tópicos seguintes será apresentado um pseudo código que guarda grande
semelhança com a linguagem PASCAL.
a) IDENTIFICADORConjunto de caracteres (letras, números ou símbolos), normalmente iniciados por
uma letra, que identificam ou nomeiam de forma única uma constante, variável, tipo,
arquivo, módulo, algoritmo, etc... Nas LP existem regras rígidas para a criação de
identificadores, o que não acontece nos algoritmos. A qualidade dos algoritmos está
diretamente ligada à significação dos identificadores, ou seja deve ser possível imaginar
para que serve um elemento, pelo seu identificador.
b) CONSTANTEUma constante é um “conteiner” de armazenamento, que possui um identificador e
armazena um valor fixo e imutável, durante a execução do programa ou algoritmo.
c) VARIÁVELUma variável é um “conteiner” de armazenamento, que possui um identificador e
seu conteúdo variável, durante a execução do programa ou algoritmo. Uma variável está
associada à uma posição de memória (endereço), podendo-se armazenar valores nesse
endereço. Os tipos básicos de variáveis são:
- Inteiro (Integer);
- Real (real);
- Caracter (char);
- Texto (string);
- Lógico (boolean);
d) DECLARAÇÃO DE VARIÁVEIS E CONSTANTESConsiste na definição dos nomes e valores das constantes e dos nomes e tipos das
variáveis que serão utilizadas pelos algoritmos, previamente à sua utilização. As
constantes são declaradas antes das variáveis, com o seguinte formato:
IDENTIFICADOR DA CONSTANTE = VALOR
Ex.: MAXNUM = 100;
TOTALALUNOS = 125;
As variáveis são declaradas com o seguinte formato:
TIPO DA VARIÁVEL: IDENTIFICADOR;
Ex.: Inteiro: NUM, QUANTALUNO;
Real: MEDIA, PREÇO;
Texto: NOME;
Lógico: ACHOU;
Caracter: C;
Os identificadores estão associados à posições de memória no computador.
E) PALAVRAS RESERVADASSão palavras que terão uso específico no pseudo-código e não deverão ser
usadas como identificadores, para não causar confusão na interpretação. Exemplos:
ALGORITMO PROGRAMABLOCO PROCEDIMENTO
INTEIRO REAL TEXTO CONST
VARIÁVEL TIPO INÍCIO FIM
IMPRIMA SE ENTÃO ENQUANTO
REPITA FAÇA VETOR EXECUTE
F) COMANDO DE ATRIBUIÇÃOEste comando permite que se forneça ou se altere o valor de uma variável, onde o
tipo desse valor tem que ser compatível ao tipo da variável que o armazenará. A seguir é
listado o formato do comando e apresentados exemplos:
IDENTIFICADOR DA VARIÁVEL <===== VALOR OU EXPRESSÃO OU VARIÁVEL
Exemplos:
NUM <== 8;
NOME <== 'MARIA';
CONT <== 0;
ACHOU <== 'FALSO;
G) OPERADORESPodem ser aritméticos, relacionais ou lógicos:
a) Operadores Aritméticos e Funções:
São os mais usados em expressões aritméticas. Permitem que se façam
operações com variáveis, constantes e valores inteiros ou reais. São eles:
+ = SOMA
- = SUBTRAÇÃO OU MENOS UNITÁRIO (SINAL)
* = MULTIPLICAÇÃO
/ = DIVISÃO
** = POTENCIAÇÃO
MOD = RESTO DA DIVISÃO DE INTEIROS
DIV = QUOCIENTE DA DIVISÃO DE INTEIROS
As funções mais comuns da Matemática estão presentes nas linguagens de
programação e também no pseudo-código. Alguns Exemplos:
LOG = LOGARITMO NA BASE 10
SEN = SENO
COS = COS
ABS = VALOR ABSOLUTO
RAIZ = RAIZ
b) Operadores Relacionais:
São utilizados com 2 operadores que podem ser expressos em valores, constantes
ou variáveis do tipo inteiro, real ou texto. Dão como resultado um valor lógico (verdadeiro
ou falso). São eles:
= = IGUAL
<> = DIFERENTE
> = MAIOR
< = MENOR
<= = MENOR OU IGUAL
>= = MAIOR OU IGUAL
c) Operadores Lógicos
São operadores utilizados com operandos do tipo lógico (podem ser expressões
relacionais ou lógicas) e dão resultado do tipo lógico, expresso por tabelas-verdade. São
eles: E (AND), OU(OR) e NÃO(NOT)
OPERADOR 1 OPERADOR 2 AND OR0 0 O O
0 1 0 1
1 0 0 1
1 1 1 1
d) Prioridade entre Operadores:
Caso não existam parênteses, deverá ser observada a seguinte ordem:
1) Parênteses e funções
2) + e – unitários
3) **
4) * e /
5) + e –
6) Relacionais
7) Não
8) E
9) OU
H) Entrada e Saída de DadosPara que possamos obter dados do meio exterior para uso no computador
(memória principal), estes tem que vir através dos dispositivos de entrada. Da mesma
forma as informações que são produzidas, tem de ser levadas ao meio externo através de
um dispositivo de saída. Para as operações de entrada e saída são usados os seguintes
comandos:
LEIA (IDENTIFICADOR, VARIÁVEL)IMPRIMA (IDENTIFICADOR, VARIÁVEL) ou (TEXTO)
I) Estrutura de um Algoritmo em pseudo-código
Algoritmo IDENTIFICADOR
{Comentários}
Const idt1 = valor1
idt2 = valor2
Var Inteiro = idt1,...
Real = idt1,...
Início
Comando 1
...
Comando n
Fim
2.6) DOCUMENTAÇÃO
A documentação deve observar alguns princípios básicos:
1. Utilizar nomes semânticos ao criar constantes e variáveis;
2. Identar o algoritmo;
3. Utilizar parentescos para evitar ambigüidades;
4. Utilizar um dicionário de dados que especifique o conteúdo de cada
constante e variável e descreva sua utilização;
2.7) EXERCÍCIOS
Faça algoritmos que implementem as funcionalidades abaixo
1. Ler duas notas e o nome do aluno, calcule a média e imprima o nome e a média.
2. Obtenha o valor em dinheiro guardado no bolso direito e o valor do bolso esquerdo,
que serão digitados, some-os e imprima o valor total e o valor total multiplicado por
3 e por 10.
3. Leia o nome, salário base e o número de dependentes de um funcionário e imprima
o nome, salário bruto (=salário base +R$100,00/depedente) e o salário liquido
(salário bruto – desconto INSS), sabendo que o desconto de INSS é de 10% do
salário base.
4. Calcule a quantidade de tinta necessária e o número de latas a comprar, para
pintar uma parede de 5m de largura e 3m de altura. Considere que o consumo da
lata é de 3 litros por metro quadrado e a quantidade de tinta por lata é de 2 litros.
5. Calcule o somatório de uma série de 5 números naturais, inseridos pelo teclado,
exibindo seu resultado na tela.
6. Calcule o produtório de 5 números naturais, inseridos pelo teclado, exibindo o
resultado na tela
SUGESTÕES DE CONSULTA
1. ALGORITMOS – http://pt.wikipedia.org/wiki/Algoritmo;
2. PROGRAMAÇÃO – http://www.linhadecodigo.com.br;
CAPÍTULO 3OBJETIVO"Apresentar as principais estruturas de controle, integrantes dos algoritmos."
SUMÁRIO3.1) Seqüência
3.2) Seleção:
3.3) Repetição:
3.4) Como construir bons algoritmos
3.5) Exercícios
3.1) SEQÜÊNCIAOs algoritmos são compostos por 5 tipos de instruções:
1. Instruções de atribuição;
2. Instruções de seleção;
3. Instruções de Repetição;
4. Instruções de entrada/saída;
5. Instruções Especiais
Normalmente um algoritmo é composto por uma seqüência, quando há
necessidade de controle de fluxo é que ocorrem outras estruturas. Uma seqüência pode
ser entendida como um grupo de comandos que são executados um após o outro.
Início
comando 1
...
comando n
Fim
É a forma normalmente encontrada no algoritmos.
3.2) SELEÇÃOUm dos tipos de instrução que controlam o fluxo de execução de um algoritmo,
também chamada de estrutura de decisão ou de processamento condicional, é utilizada
quando a execução de um comando ou seqüência de comandos, depende de um teste
anterior (uma ou mais comparações). Uma seleção pode ser simples ou composta.
A) SELEÇÃO SIMPLESQuando a execução de um comando (ou de uma seqüência de comandos)
depender de uma condição verdadeira, e não há comandos se a condição for falsa.
Ex.: Início
Leia (num);
Se num <> 0 então Imprima num
Fim SE
Fim
B) SELEÇÃO COMPOSTAQuando a execução de um comando (ou de uma seqüência de comandos)
depender de uma condição verdadeira, e há comandos se a condição for falsa.
Ex.: Início
Leia (num)
Se num <> 0 então Imprima (num );
senão Imprima (O número é zero !);
Fim SE
Fim
C) ANINHAMENTO DE SELEÇÕESUm comando de seleção pode ser executado dentro do outro, formando um
aninhamento. Uma boa edentação ajudará a compreensão do algoritmo.
3.3) REPETIÇÃO (LOOP OU LAÇO):A estrutura de repetição é utilizada quando um conjunto de comandos deve ser
executado repetidamente, enquanto uma determinada condição (expressão lógica)
permanecer verdadeira.
Dependendo do resultado do teste da condição, o conjunto de comandos poderá
não ser executado nem uma vez (se for falsa no primeiro teste), ou será executado várias
vezes (enquanto for verdadeira). Um loop pode ser aninhado, da mesma forma que uma
instrução de seleção, como lambem poderão haver aninhamento de seleções dentro de
loops e vice-versa. Duas recomendações devem ser seguidas, ao criar-se estruturas de
repetição:
1. Inicializar a(s) variável(eis) que controla(m) o loop, antes de seu início;
2. Modificar a(s) variável(eis) que controla(m) o loop dentro do mesmo (seja
por leitura ou atribuição), para que não geremos um loop infinito;
EX 1: CONST IDADELIMITE = 65
VAR INTEIRO: IDADE, I;
TEXTO: NOME;
INÍCIO
LEIA (NOME,IDADE);
ENQUANTO (IDADE <> IDADELIMITE) FAÇA
INÍCIO
IMPRIMA (NOME,IDADE);
LEIA (NOME, IDADE);
FIM
PARA I := 1 TO 10 FAÇA
INÍCIO
IMPRIMA (I);
FIM
FIM
EX2.: VAR INTEIRO: MÊS
INÍCIO
REPITA
IMPRIMA(DIGITE O MÊS DESEJADO (1 A 12));
LEIA (MÊS);
ATÉ (mês <= 12 ) E (MES >= 1)
FIM
SINALIZADOR (FLAG)O flag é um valor que quando lido, sinaliza a saída de um loop, o fim de um
programa, de uma lista de dados, ou o fim de um arquivo. É identificado como uma
constante nos algoritmos.
EX.: CONST FLAG =999
VAR INTEIRO: NUM,I
INÍCIO
I = 0;
ENQUANTO I < 10 FAÇA
INÍCIO
LEIA (NUM);
SE NUM <> FLAG ENTÃO IMPRIMA (NUM);
I = I+1;
FIM;
FIM
3.4) COMO CONSTRUIR BONS ALGORITMOS1. Leia o problema proposto até entendê-lo;
2. Determine as necessidades de constantes e variáveis de entrada e saída,
necessárias à resolução do problema;
3. Determine de forma bem geral os passos para a solução do problema;
4. Detalhar os passos, até obter comandos primitivos;
5. Escrever o algoritmo em pseudo-código;
6. Rastrear o algoritmo;
Os algoritmos seguem normalmente a seguinte estrutura:
1. Cabeçalho
2. Declaração e inicialização de variáveis e constantes
3. Início
4. Instruções
5. Fim
3.5) EXERCÍCIOS
Faça algoritmos para os problemas abaixo, usando pseudo código e fluxogramas:
1. Ler 2 números inteiros, descobrindo o maior.
2. Fazer um loop para ler o nome e o salário de uma pessoa, exibindo na tela seu
salário, com abono de 10%, até que seja digitado um salário maior que 1.000.
3. Imprimir na tela todos os números inteiros positivos pares, menores que 999 .
4. Imprimir na tela todos os números inteiros positivos, menores que 999, divisíveis
por 5. Exiba ao final sua quantidade.
5. Ler uma seqüência de n números inteiros positivos do teclado, exibindo seu
somatório e sua média.
6. Calcular a seqüência de Fibonacci, exibindo-a na tela;
7. Colocar em ordem crescente, uma seqüência de 3 números inseridos pelo teclado;
8. Calcular a raiz de uma equação do primeiro grau;
9. Calcular as raízes de uma equação do segundo grau;
10.Calcular o fatorial de um número.
CAPÍTULO 4OBJETIVO"Apresentar algumas estruturas de dados avançadas e suas aplicações."
SUMÁRIO4.1)Introdução
4.2)Registros
4.3)Arquivos
4.4)Exercícios
4.1) INTRODUÇÃOOs registros são um dos mais importantes tipos de dados agregados ou estrutura
de dados (ED). Pode-se definir uma ED como um conjunto de dados relacionados entre
si, agrupados na memória principal ou secundária, com a finalidade de facilitar a
manipulação de dados pelo programador, na medida em que se tornam mais complexos.
As principais estruturas de dados são:
● Registros ou agregados heterogêneos;
● Vetores, matrizes ou agregados homogêneos;
● Listas lineares (encadeadas);
● Pilhas;
● Filas;
● Árvores;
4.2) REGISTROS:São variáveis compostas heterogêneas. Os registros representam conjunto de
informações relacionadas entre si, que podem ser referenciadas como uma unidade (o
registro), sendo normalmente composta de informações de tipos diferentes (tipos).
Um registro representa um tipo de dado definido pelo usuário, constituindo um tipo
de dado não primitivo. O quadro a seguir representa o formato de declaração de um
registro.
TIPOIDENTIFICADOR DO REGISTRO = REGISTRO
tipo do campo 1: identificador do campo 1;
.......
tipo do campo n: identificador do campo n;
FIM
EX.: REGALUNO = REGISTRO
TEXTO : NOME;
CARACTER: SEXO;
INTEIRO: CIDADE;
REAL: MÉDIA;
FIM REGALUNO.
A partir da definição do tipo, temos à disposição um novo tipo de variável.
EX.: VARIÁVEL REGALUNO : RALUNO;
4.3) ARQUIVOS:Um arquivo é um conjunto de dados ou informações de tamanho limitado,
identificado por um nome e que está localizado na memória secundária. Os dados e
informações contidos num arquivo não são perdidos quando se desliga o computador. O
acesso a um arquivo pode ser seqüencial ou randômico..
Um arquivo pode ser usado como fonte de dados de entrada ou como destino das
informações de saída. Pode-se imaginar um arquivo como uma gaveta de um arquivo de
aço, que contém fichas de cadastros (de funcionários por exemplo).
Os arquivos são definidos ou declarados nos algoritmos na declaração de
variáveis, especificando-se de que tipo são os dados contidos no arquivo.
Formato:
Variável Arquivo de Tipo : Identificador do arquivo
Ex.: Arquivo de Inteiro: ARQNUM
Arquivo de Texto: ARQNOME.
Existem basicamente 2 operações possíveis de serem feitas com arquivos:
● Leitura
● Escrita
A seguir é apresentado um exemplo de leitura dos nomes de 50 alunos, que estão
armazenados no arquivo “ARQNOMES” , gravando-os no arquivo “TURMA”.
ALGORITMO LE_GRAVA
CONST TOTNOMES = 50;
VAR TEXTO: NOME;
ARQUIVO DE TEXTO: ARQNOMES, TURMA;
INTEIRO: CONT;
INÍCIO
CONT := 0;
ENQUANTO (CONT < TOTNOMES) FAÇA
INÍCIO
LEIA (ARQNOMES, NOME);
GRAVE (TURMA, NOME);
CONT := CONT + 1;
FIM
FIM
4.4) EXERCÍCIOS
1) Crie registros para conter:
a) Os dados de uma peça em estoque);
b) Os dados de um cliente no banco;
c) Os dados de um aluno;
2) O arquivo ARQNOMES contém os nomes e o arquivo ARQNOTAS, as 3 notas de
cada um dos 60 alunos da turma X. Faça um algoritmo que calcule a média de
cada aluno, gravando o resultado no arquivo ARQMEDIA_X.
CAPÍTULO 5
OBJETIVO"Apresentar as estruturas de dados vetores e matrizes e suas aplicações."
SUMÁRIO5.1) Vetores:
5.2) Matrizes
5.3) Exercícios
5.1) VETORESUm vetor é uma estrutura de dados que contêm elementos do mesmo tipo, que
podem ser referenciados como um todo. Os vetores podem ser uni ou multi dimensionais
(matrizes) . O exemplo a seguir ilustra um vetor e sua declaração:
[1] [2] [3] [n]
000
IDENTIFICADOR DO VETOR: VETOR[LI .. LS] de TIPO
LI = LIMITE INFERIOR
LS = LIMITE SUPERIOR
EX.: TIPO
VETNOTA = VETOR [1 .. 50] DE REAL
VAR VETNOTA : VNOTA, AUX;
5.2) MATRIZESMatrizes, tabelas ou vetores multi-dimensionais são estruturas de dados similares
ao vetor, com a diferença de que podem ter várias dimensões. Cada célula de uma matriz
pode ser identificada por um nome e tantos índices, quantas forem suas dimensões.
5.3) EXERCÍCIOS
Faça algoritmos para os problemas abaixo:
1. Somar duas matrizes 3 por 3.
2. Calcular o determinante de uma matriz 3x3.
3. Ler um arquivo com 50 números inteiros, colocando-os em um vetor, na ordem
decrescente.
4. Ler de um arquivo uma lista de 100 números inteiros, armazenando-os em um
vetor e informando o menor valor.
5. Ler uma série de 10 números inteiros do teclado, armazenando-os num vetor em
ordem crescente.
CAPÍTULO 6
OBJETIVO"Apresentar o conceito e as vantagens da modularização de algoritmos."
SUMÁRIO6.1) Procedimentos
6.2) Funções
6.3) Estruturação dos Módulos de um Algoritmo
6.4) Exercícios
6.1) PROCEDIMENTOSUm procedimento é uma seqüência de instruções precedidas por uma seqüência
de declarações, que possui um identificador (nome do procedimento), uma lista de
parâmetros opcionais (para comunicação com o exterior) e pode realizar qualquer tipo de
procedimento, estabelecido pelo programador.
As variáveis, os tipos e as constantes declaradas dentro de um procedimento só
são acessáveis dentro do procedimento, são chamadas variáveis locais, só sendo
acessáveis de dentro do procedimento. O uso de procedimentos modulariza o algoritmo,
dividindo o problema a ser resolvido em partes.
EX.: PROCEDIMENTO <IDENTIFICADOR DO PROCEDIMENTO> (LISTA DE PARÃMETROS)
CONST ...
VAR ...
INÍCIO
INSTRUÇÕES
FIM
6.2) FUNÇÕESUma função é um módulo que tem por objetivo calcular e retornar ao algoritmo o
resultado desse cálculo.
EX.: FUNÇÃO <IDENTIFICADOR> (LISTA DE PARÂMETROS) : <TIPO>
INÍCIO
INSTRUÇÕES
FIM
6.3) ESTRUTURAÇÃO DOS MÓDULOS DE UM ALGORITMOUm procedimento nada mais que um algoritmo hierarquicamente subordinando a
outro algoritmo, chamado de módulo principal ou programa principal, ou ainda algoritmo
principal. Da mesma forma, um procedimento poderá conter outros procedimentos (e
também funções) aninhados.
Uma boa prática ao definir as fases de um algoritmo é transformar as mesmas em
procedimentos.
6.4) EXERCÍCIOS1. Faça um procedimento para calcular o valor da diagonal de um retângulo,
sendo fornecidos os lados como parâmetros.
2. Resolva o mesmo problema usando uma função.
3. Faça um procedimento que receba as notas de um aluno (3) e calcule sua
média.
CAPÍTULO 7 OBJETIVO"Apresentar o conceito de pesquisa e ordenação de dados."
SUMÁRIO7.1) Introdução
7.2) Algoritmos de Pesquisa:
7.3) Algoritmos de Ordenação:
7.1) INTRODUÇÃOQuando temos um vetor (ou matriz) com muitos elementos e precisamos descobrir
se um determinado elemento que procuramos, se encontra no vetor, uma solução que
nos vem à mente é compararmos cada elemento do vetor com o elemento procurado, até
que o encontremos ou concluamos que o vetor não o contém.
Esta é a base de raciocínio dos algoritmos de pesquisa, a diferença entre eles é
basicamente a rapidez com que varremos o espaço de procura. Um fator que muito
influencia na rapidez do algoritmo é a disposição dos elementos no vetor.
Os algoritmos de ordenação são usados para ordenar os elementos de um vetor de
forma a facilitar a pesquisa.
7.2) ALGORITMOS DE PESQUISA:Para fazer uma pesquisa em um vetor precisa-se de 4 parâmetros:
a) O vetor no qual realizaremos a pesquisa;
b) O número de elementos desse vetor que devem ser pesquisados;
c)O elemento procurado;
d) Um índice que vai ser preenchido com a posição onde o elemento foi
encontrado.
Como os algoritmos de pesquisa podem ser utilizados muitas vezes na solução de
diferentes problemas, vamos defini-los como procedimento de um algoritmo principal:
A) PESQUISA SEQÜENCIAL SIMPLESNuma pesquisa seqüencial simples como o vetor a ser pesquisado não está
ordenado pelo elemento procurado, teremos de comparar um a um o ELEMPROC, com
cada elemento do vetor.
PROCEDIMENTO PESQSEQ (VETIPO : Vet; INTEIRO: Totelem, Pos; ELEMPROC)
VAR Inteiro : j,i;
INÍCIO
Pos = 0;
j = 1;
PARA I = 1 ATÉ TOTELEM FAÇA
INÍCIO
IF VETIPO [I] = ELEMPROC ENTÃO ACHEI;
FIM
FIM.
B) PESQUISA SEQÜÊNCIAL ORDENADAPara se utilizar a pesquisa seqüencial ordenada, o vetor de busca deverá estar
ordenado pelo campo chave da pesquisa, com isso se encontramos no vetor um elemento
maior que o procurado, podemos encerrar a pesquisa. Tal estratégia reduz sensivelmente
o tempo de busca.
7.3) ALGORITMOS DE ORDENAÇÃO:O propósito dos algoritmos de ordenação é o de facilitar e acelerar a busca
posterior de um elemento no vetor. Os algoritmos de ordenação são utilizados
normalmente uma vez em cada execução do programa, ou poucas vezes, se comparados
com os de pesquisas. Os principais métodos de ordenação são:
● Ordenação por seleção;
● Ordenação por inserção;
● Ordenação por troca;
CAPÍTULO 8 OBJETIVO
"Apresentar o conceito avançados sobre algoritmos, com sua transformação em
programas de computador, o processo de compilação e assuntos correlatos."
SUMÁRIO8.1) Introdução
8.2) O processo de tradução;
8.3) Introdução à Teoria de Sistemas
8.4) Programas, Algoritmos e Estruturas de Dados
8.1) INTRODUÇÃOUm computador é uma máquina elétrica, independentemente do processo de
produção de programas que adotemos, as ações acontecem por meio de sinais elétricos.
Em outras palavras podemos abordar o problema de elaboração de programas do ponto
de vista de alto nível (próximo ao ser humano) ou baixo nível (próximo à máquina),
estabelecendo uma organização hierárquica.
O computador na verdade só é capaz de executar um conjunto pequeno de
instruções, que são sua linguagem de máquina, ou seja instruções que vem de fábrica
com o processador. Existem programadores que trabalham neste nível (0 e 1) mas
consiste numa tarefa bastante árdua e pouco produtiva.
Para resolver este problema surgiu o processo de tradução, que consiste em
transformar um programa escrito numa determinada linguagem em outro, que atenda a
um interesse específico.
8.2) O PROCESSO DE TRADUÇÃO
O processo de tradução consiste basicamente na transformação de um tipo de
programa em outro. O primeiro processo foi a transformação da linguagem de máquina na
linguagem Assembler. A figura a seguir ilustra tal processo:
O programa original é chamado de programa fonte e o final, programa alvo.
Existem dois tipos básicos de tradução: a compilação e a interpretação. No processo de
compilação o programa fonte é totalmente traduzido em instruções da máquina alvo,
enquanto na interpretação, é traduzida linha a linha. Abordaremos apenas o processo de
compilação. O processo completo é ilustrado abaixo:
8.3) INTRODUÇÃO À TEORIA DE SISTEMASUm sistema é um conjunto de elementos integrados, cada um realizando uma
tarefa específica, concorrendo todos para execução de um objetivo. Um programa e seu
ambiente de produção são sistemas.
8.4) PROGRAMAS, ALGORITMOS E ESTRUTURAS DE DADOS Os programas processam dados, que são representações para o computador de
informações do mundo real. Tais representações podem ser simples, quando a
informação é simples (exemplo: nota de um aluno) ou estruturadas, quando a informação
é por sua natureza estruturada (exemplo: conjunto de informações sobre o aluno).
PROGRAMAFONTE TRADUTOR LINK
EDIÇÃOCÓDIGOOBJETO
PROGRAMAALVO
BIBLIOTECA
LINGUAGEMDE
MÁQUINA
PROGRAMATRADUTOR
LINGUAGEMASSEMBLER
Um programa é constituído por um conjunto de ações que devem ser executadas
sobre os dados, obedecendo a uma determinada seqüência.. Essas ações são
especificadas por meio de um “algoritmo”, que define a seqüência e o conjunto de ações
que devem ser executadas sobre um conjunto de dados, com o propósito de obter
informações.
Ação é um conceito central na programação. Uma ação deve ser bem definida,
efetiva e de duração finita. Uma ação pressupõe a existência de dados sobre os quais ela
será executada. Uma ação é uma operação que pode provocar alterações sobre os
dados.
Um algoritmo é uma seqüência de passos ordenados, finitos, não ambíguos, que
levam à execução de um objetivo. Um algoritmo é um padrão de comportamento, que
estabelece um conjunto finito de passos, onde cada passo pode requerer uma ou mais
ações. Um algoritmo é um projeto de programa, que deve ser implementado em uma
linguagem de programação e transformado em um programa executável. Um programa
de computador é composto de dois elementos:
PROGRAMA = ALGORITMO + ESTRUTURA DE DADOS
Assim como numa linguagem humana, uma linguagem de programação é
constituída de um conjunto de vocábulos, regras de sintaxe e semântica, permitindo a
especificação dos dados e operações, numa forma que o computador entenda e possa
executar. A especificação de um algoritmo e de suas estruturas de dados devem constituir
uma base sólida para a construção de um programa.
A construção de um programa começa com um levantamento e análise das
informações do mundo real, produzindo um ENUNCIADO. Com base no enunciado
desenvolve-se um projeto que especifica uma ALGORITMO e as REPRESENTAÇÕES DOS DADOS.
O algoritmo e as representações dos dados devem ser codificados para uma
linguagem de programação. O código fonte do programa deve ser convertido para um
código executável pelo sistema operacional da máquina alvo. De uma maneira genérica o
processo de desenvolvimento de programas cumpre as seguintes fases:
FASE DESCRIÇÃO
1ªANÁLISE E ESPECIFICAÇÃO DE REQUISITOS, DEFININDO-SE O QUE O PROGRAMA DEVE FAZER PARA ATENDER ÀS
NECESSIDADES DOS USUÁRIOS (ENUNCIADO).
2ªPROJETO DE PROGRAMAS , ESPECIFICANDO-SE COMO O PROGRAMA DEVE SER PARA ATENDER AOS SEUS
REQUISITOS. A METODOLOGIA DESTA FASE TEM GRANDE IMPACTO NA ESCOLHA DA LINGUAGEM DE PROGRAMAÇÃO.
3ªIMPLEMENTAÇÃO , QUANDO SE CODIFICA O PROGRAMA, COM UMA LINGUAGEM DE PROGRAMAÇÃO, QUE SUPORTE A
METODOLOGIA DE PROJETO, CRIANDO-SE UM CÓDIGO EXECUTÁVEL ..
4ª VALIDAÇÃO , QUANDO PROGRAMA É TESTADO E SUA CORREÇÃO VERIFICADA.
5ªMANUTENÇÃO, QUANDO SÃO FEITAS ALTERAÇÕES DECORRENTES DE MELHORIAS, NECESSIDADES DE OUTROS SERVIÇOS,
ERROS ENCONTRADOS, ETC ...
