Algoritmos e Logica de Programação

Algoritmos e Logica de Programação

(Parte 1 de 3)

Sumário

Prefácio xix

1.1 O desenvolvimento de um software1
1.2 Algoritmos e lógica de programação3
1.2.1 O significado de um algoritmo4
1.2.2 Exemplo de algoritmo5
1.3 A formalização de um algoritmo12
1.3.1 A sintaxe de um algoritmo12
1.3.2 Exemplo de sintaxe de um algoritmo13
1.3.3 A semântica de um algoritmo15
1.4 Como resolver problemas16
1.4.1 A análise e a síntese de um problema16
1.4.2 Modelagem de problemas17
1.4.3 O papel da lógica em programação19
1.5 Como se portar em um curso de computação21
1.6 Exercícios24

1 Introdução 1

2.1 Origens da computação27
2.1.1 A necessidade de calcular27
2.1.2 O desenvolvimento de sistemas de numeração28
2.2 A evolução dos computadores3
2.2.1 Geração zero – Computadores puramente mecânicos3
2.2.2 Primeira geração – Computadores a válvula e relé37
2.2.3 Segunda geração – Computadores transistorizados43

2 Conceitos de Computação e Computadores 27 2.2.4 Terceira geração – Computadores com circuitos integrados . . . 4

2.2.5 Quarta geração – Computadores com chips VLSI45
2.3 A representação da informação em um computador47
2.3.1 A eletrônica digital do computador47
2.3.2 Conceitos de bits e seus múltiplos48
2.3.3 Caracteres e cadeias de caracteres50
2.3.4 Imagens52
2.3.5 Sons56
2.4 A arquitetura de um computador59
2.5 O funcionamento da UCP na execução dos programas60
2.6 O projeto lógico na construção de programas64

viii Algoritmos e Lógica de Programação

3.1 Revisão do conceito de algoritmo67
3.2 Aplicabilidade dos algoritmos68
3.2.1 Exemplo não computacional de um algoritmo68
3.2.2 Exemplo computacional de um algoritmo69
3.3 Propriedades de um algoritmo71
3.4 Fluxogramas72
3.5 Construindo fluxogramas73
3.5.1 Fluxograma mínimo73
3.5.2 Fluxograma com comandos seqüenciais74
3.5.3 Fluxograma com comandos de decisão80
3.5.4 Fluxograma com comandos de repetição83
3.5.5 Simulação de algoritmos com fluxogramas87
3.6 Convenções para tipos de dados93
3.6.1 Números94
3.6.2 Caracteres e cadeias de caracteres95
3.6.3 Valores lógicos95
3.7 Convenções para os nomes de variáveis95
3.8 Convenções para as expressões96
3.8.1 Operação de atribuição96
3.8.2 Operações aritméticas97
3.8.3 Operações relacionais9
3.8.4 Operações lógicas9
3.8.5 Expressões100
3.9 Sub-rotinas predefinidas102
3.9.1 Funções matemáticas102
3.10 Exercícios105

Sumário ix

4.1 Estruturas de programação115
4.2 Estruturas seqüenciais116
4.3 Estruturas de decisão117
4.3.1 Estrutura SE-ENTÃO117
4.3.2 Estrutura SE-ENTÃO-SENÃO118
4.3.3 Estrutura CASO119
4.3.4 Exemplos de estruturas de decisão120
4.4 Estruturas de repetição122
4.4.1 Estrutura ENQUANTO-FAÇA122
4.4.2 Estrutura REPITA-ATÉ123
4.4.3 Estrutura PARA-ATÉ-FAÇA124
4.4.4 Exemplos de estruturas de repetição126
4.4.5 Símbolos específicos para estruturas de repetição (ISO 5807)133
4.5 Outras representações de algoritmos136
4.5.1 Portugol136
4.5.2 Diagramas de Nassi-Schneidermann139
4.6 Exercícios142

4 Estruturas de Programação 115

5.1 Motivação149
5.2 Variáveis indexadas unidimensionais151
5.3 Representação de vetores na memória do computador152
5.4 Utilização de vetores153
5.5 Exemplos de fluxogramas com vetores155
5.5.1 Localização de um elemento do vetor155
5.5.2 Média aritmética dos elementos de um vetor158
5.5.3 Localização de elementos de um vetor por algum critério158
5.5.4 Determinação do maior e menor elemento de um vetor160
5.5.5 Cálculo de um polinômio pelo método de Horner161
5.6 Variáveis indexadas bidimensionais163
5.7 Exemplos de fluxogramas com matrizes164
5.7.1 Leitura de elementos para uma matriz164
5.7.2 Produto de um vetor por uma matriz165

x Algoritmos e Lógica de Programação

6.1 A técnica top-down175
6.1.1 Exemplo de aplicação176
6.2 Sub-rotinas181
6.2.1 Funções181
6.2.2 Exemplos de funções183
6.2.3 O mecanismo de chamada de funções187
6.2.4 Procedimentos188
6.3 Exercícios191

6 Técnicas para a Solução de Problemas 175

A.1 Linha do tempo195

A Pequeno Histórico da Computação 195

B.1 Os símbolos202
B.1.1 Símbolos relativos a dados203
B.1.2 Símbolos relativos a processos204
B.1.3 Símbolos de linhas205
B.1.4 Símbolos especiais206
B.1.5 Textos internos207
C.1 Operadores matemáticos210
C.2 Funções predefinidas211

C Operadores e Funções Predefinidas 209 Referências Bibliográficas 214

Prefácio

A quem se destina este livro?

Este livro destina-se a um curso introdutório de lógica de programação, especialmente para aqueles ministrados em escolas de Engenharia. Um dos principais problemas encontrados pelo estudante de Engenharia em um primeiro curso de lógica de programação é a carência de textos que abordem de forma direta e clara as etapas necessárias para suportar o processo de resolução de problemas (computacionais ou não), a saber: a análise, com a identificação e solução de subproblemas, e a síntese, união das soluções encontradas para compor a solução do problema original. O resultado dessas etapas é sintetizado em passos que devem ser seguidos em determinada ordem e que constituem os algoritmos.

Abordagem empregada

Pretende-se aqui seguir uma apresentação incremental dos tópicos. Inicialmente são propostos problemas simples que envolvem raciocínio lógico e que possuem solução livre, de modo a ambientar e a incentivar o estudante na descrição dos passos elementares necessários à resolução de problemas. Isso é fundamental, pois grande parte dos estudantes que tem um primeiro contato com lógica de programação apresenta deficiências na organização de suas soluções e em abstrações. Além disso, neste primeiro contato, um processo genérico de solução de problemas é apresentado de maneira a fornecer um conjunto de dicas ou heurísticas que podem ser aplicadas em todos os problemas a serem resolvidos, fortalecendo assim o processo de abstração, essencial em programação.

A seguir são apresentados os conceitos de computação e computadores. Embora um primeiro curso de lógica de programação possa ser ministrado sem referências a como um computador é organizado e como funciona, verifica-se na prática que esse enfoque não é adequado. Como se sabe, o grande problema do estudante nesses cursos x Algoritmos e Lógica de Programação introdutórios é a abstração de procedimentos e dados. Nesse ponto apresenta-se uma arquitetura de computador bem simples, baseada na arquitetura de Von Neumann, para fixar de modo tangível os conceitos relacionados a instruções e dados operados em computadores. Objetiva-se aqui que o estudante futuramente consiga relacionar os aspectos abstratos de computação, tais como variáveis, estruturas de programas e decomposição funcional com sua implementação. Essa parte serve ainda como incentivo para a necessidade de se descrever algoritmos antes de sua implementação propriamente dita.

Depois, e acompanhando todo o livro, emprega-se uma notação formal para a solução de problemas. Utiliza-se neste texto a descrição de algoritmos sob a forma de fluxogramas baseados na norma ISO 5807/1985. Os fluxogramas são compostos por símbolos básicos que representam as menores partes em um processo de solução: estruturas seqüenciais, de decisão e de repetição. O uso de fluxogramas nesta obra é justificado pelo fato de que o engenheiro tem a obrigação de desenvolver um raciocínio lógico bem-estruturado e que o fluxograma ainda representa uma poderosa ferramenta para a verificação e teste da lógica empregada na solução de problemas. A utilização de fluxogramas em Engenharia é ampla: de descrições de programas até descrições de processos de fabricação ou processos químicos, seu emprego é similar e regido única e exclusivamente pela lógica utilizada na composição de seus blocos, até se alcançar a solução de um determinado problema.

Além do uso de fluxogramas, são apresentadas ainda duas outras formas conhecidas para a representação de algoritmos: diagramas de Nassi-Schneidermann e o pseudocódigo baseado na língua portuguesa, o Portugol. Os diagramas de Nassi-Schneidermann empregam uma representação em “caixas” aninhadas, em que cada uma é relacionada a um determinado tipo de comando ou estrutura de programação. Já o Portugol usa uma descrição textual e estruturada da solução de um problema na qual os comandos são descritos por palavras-chave reservadas e extraídas da língua portuguesa.

Descrição dos capítulos

No Capítulo 1 são apresentados os conceitos básicos sobre modelagem de problemas em Engenharia e como organizar suas soluções utilizando passos elementares. Faz-se aqui um prelúdio ao estudo dos algoritmos, com uma descrição de métodos para auxiliar o estudante no processo de identificação e resolução de problemas, bem como a proposição de problemas de lógica com solução livre para ambientar o estudante nesse processo.

No Capítulo 2 são discutidos os conceitos de computação e computadores. Inicia-se com a discussão da origem da palavra computação, seu significado e aplicações. A seguir são discutidos os conceitos básicos sobre a organização de computadores utilizando a

Prefácio xxi arquitetura de Von Neumann. Um computador hipotético com instruções simplificadas é apresentado de forma a proporcionar ao estudante simulações de como as instruções e os dados são realmente processados.

Os conceitos de algoritmo e fluxograma são formalizados no Capítulo 3. São discutidos o conceito e as propriedades de um algoritmo, a representação de algoritmos por fluxogramas, como criar um fluxograma utilizando os símbolos básicos da norma ISO 5807/1985, bem como convenções para os tipos de dados, os nomes de variáveis e operadores.

Já no Capítulo 4 formalizam-se as estruturas de programação. São apresentados os nomes e as topologias das estruturas típicas de um programa: as estruturas seqüenciais, de decisão e de repetição. Apresentam-se ainda nesse capítulo duas outras formas de representação de algoritmos: os diagramas de Nassi-Schneidermann e a pseudolinguagem Portugol.

É apresentado, no Capítulo 5, o conceito de variáveis indexadas e seu uso. As variáveis indexadas são aquelas que referenciam de forma ordenada uma seqüência de dados homogêneos. Separam-se aqui, para melhor compreensão, o conceito e a utilização de variável indexada unidimensional (ou vetor) do conceito de variável indexada bidimensional e multidimensional. Com essa separação, espera-se que o estudante consiga estender os conceitos e operações relacionados a variáveis indexadas unidimensionais para dimensões maiores.

Por fim, no Capítulo 6 são discutidas as técnicas para a solução de problemas, mais especificamente as técnicas para modularizar a solução utilizando sub-rotinas. São apontados os dois tipos básicos de sub-rotinas (função e procedimento) e como empregá-los de acordo com a técnica top-down de modularização. A Figura da página xi exibe a organização dos capítulos deste livro.

Convenções tipográficas

Algumas convenções tipográficas foram utilizadas neste livro para tornar mais clara a sua compreensão:

• Negrito é empregado para destacar os conceitos importantes.

• Itálico é utilizado para enfatizar os conceitos essenciais e para palavras estrangeiras.

xi Algoritmos e Lógica de Programação

Capítulo 1 - Introdução

Capítulo 2 - Conceitos de Computação e Computadores

Capítulo 3 - Algoritmos e Fluxogramas

Capítulo 4 - Estruturas de Programação

Capítulo 6 - Técnicas para a Solução de Problemas

Capítulo 5 - Variáveis Indexadas

• Nos exercícios existem símbolos para identificar aqueles que são básicos, de resolução imediata; médios, nos quais o estudante deve pensar um pouco mais na solução; e desafios, a fim de empenhar-se mais na sua solução:

exercício fácil ffi exercício médio fi exercício desafiador

Capítulo 1 Introdução

Um programa de computador é um produto resultante da atividade intelectual de um programador. Essa atividade, por sua vez, depende de um treinamento prévio em abstração e modelagem de problemas, bem como o uso da lógica na verificação das soluções. Neste capítulo são apresentados os conceitos introdutórios sobre a tarefa de programar computadores, a necessidade do uso de lógica na programação, a importância de se abstrair e modelar os problemas antes de partir para as soluções. Por fim, são apresentadas algumas dicas úteis que podem ser utilizadas na solução de problemas em geral.

1.1 O desenvolvimento de um software

Um programa de computador ou simplesmente software é representado pelas instruções e dados que algum ser humano definiu e que ao serem executados por alguma máquina cumprem algum objetivo. A máquina a que este texto se refere é um compu- tador digital1 .

Os computadores digitais são máquinas eletrônicas contendo processadores e circuitos digitais adequados, operando com sinais elétricos em dois níveis ou binários (a ser detalhados no Capítulo 2).

Os dados são organizados em um computador de acordo com sua representação binária, isto é, seqüências de 0s e 1s. O objetivo de se utilizar um computador é extrair as informações resultantes de computações, isto é, o resultado das execuções das instruções de algum programa. Deve-se observar a diferença entre informação e dado: o dado

1Existem também computadores analógicos.

2 Algoritmos e Lógica de Programação por si só é um valor qualquer armazenado em um computador enquanto a informação representa a interpretação desse dado, ou seja, qual o seu significado.

Parte dos dados processados durante a execução de um software é fornecida pelo ser humano (ou outra máquina) e denominada dados de entrada. Por outro lado, os dados de saída são aqueles fornecidos ao ser humano (ou outra máquina) após o processamento dos dados de entrada.

De qualquer forma, é importante notar que o objetivo do software é que motiva sua construção. Este pode ser definido como alguma necessidade humana, por exemplo, um programa para simular o funcionamento de um circuito digital, um programa para comandar um robô em uma linha de montagem, um sistema de gerenciamento de informações em uma empresa, somente para citar algumas. A Figura 1.1 descreve uma simplificação do processo de desenvolvimento de um software.

(Parte 1 de 3)

Comentários