Buscar

apostila-alg-prog-uergs

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 87 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 87 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 87 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Universidade Estadual do Rio Grande do Sul - UERGS
Unidade de Guaíba
Curso de Engenharia em Sistemas Digitais
Apostila da Disciplina de
Algoritmos e Programação
Prof. João Carlos Gluz
Guaíba, 2003
UERGS - Algoritmos e Programação Sumário
Copyright  2002,03 João Carlos Gluzii
Sumário
CAPÍTULO 1 - INTRODUÇÃO ..................................................................................................................... 1
1.1. UMA BREVE HISTÓRIA DA COMPUTAÇÃO............................................................................................. 1
1.2. CONCEITOS ELEMENTARES DE COMPUTAÇÃO E INFORMÁTICA............................................................. 7
1.3. PROGRAMAS, ALGORITMOS E PROGRAMAÇÃO ................................................................................... 10
1.4. ESTRUTURA DE UM PROGRAMA .......................................................................................................... 12
1.5. LINGUAGENS DE PROGRAMAÇÃO........................................................................................................ 13
1.6. TRADUÇÃO DE LINGUAGENS............................................................................................................... 15
1.7. CARGA E EXECUÇÃO DE PROGRAMAS................................................................................................. 16
CAPÍTULO 2 - ALGORITMOS E LINGUAGEM C................................................................................. 18
2.1. ALGORITMOS ...................................................................................................................................... 18
2.2. FORMAS DE DESCRIÇÃO DE ALGORITMOS .......................................................................................... 19
2.3. A NOÇÃO DE PROGRAMA.................................................................................................................... 19
2.4. A LINGUAGEM C ................................................................................................................................ 20
CAPÍTULO 3 - ELEMENTOS BÁSICOS DE C......................................................................................... 22
3.1. CONSTANTES ...................................................................................................................................... 22
3.2. VARIÁVEIS.......................................................................................................................................... 22
3.3. TIPOS DE DADOS PRIMITIVOS ............................................................................................................. 23
3.4. COMENTÁRIOS .................................................................................................................................... 24
3.5. EXPRESSÕES ARITMÉTICAS................................................................................................................. 24
3.6. EXPRESSÕES RELACIONAIS ................................................................................................................. 27
3.7. EXPRESSÕES LÓGICAS ........................................................................................................................ 28
3.8. TIPOS DE DADOS DAS EXPRESSÕES..................................................................................................... 29
3.9. EXPRESSÕES (COMANDOS) DE ATRIBUIÇÃO ....................................................................................... 30
CAPÍTULO 4 - COMANDOS SIMPLES E BLOCO DE COMANDOS .................................................. 32
4.1. COMANDO DE ATRIBUIÇÃO E SEQUÊNCIA DE COMANDOS .................................................................. 32
4.2. COMANDOS DE ENTRADA E SAÍDA...................................................................................................... 33
4.2.1. A Função scanf ......................................................................................................................... 33
4.2.2. A Função printf......................................................................................................................... 34
4.2.3. Comandos de Formatação de scanf e printf ............................................................................. 35
4.3. BLOCOS DE COMANDO........................................................................................................................ 37
4.4. UM PROGRAMA C BÁSICO .................................................................................................................. 37
CAPÍTULO 5 - COMANDOS DE SELEÇÃO............................................................................................. 40
5.1. COMANDO CONDICIONAL IF................................................................................................................ 40
5.2. COMANDO DE SELEÇÃO IF ... ELSE ...................................................................................................... 41
5.3. COMANDO DE SELEÇÃO SWITCH ......................................................................................................... 42
5.4. USANDO COMANDOS CONDICIONAIS .................................................................................................. 43
CAPÍTULO 6 - COMANDOS DE REPETIÇÃO........................................................................................ 47
6.1. COMANDO DE REPETIÇÃO WHILE........................................................................................................ 48
6.2. COMANDO DE REPETIÇÃO FOR............................................................................................................ 50
6.3. COMANDO DE REPETIÇÃO DO...WHILE ................................................................................................ 52
CAPÍTULO 7 - FUNÇÕES E MÓDULOS .................................................................................................. 54
7.1. DECLARAÇÃO DE FUNÇÃO.................................................................................................................. 54
7.2. ESTRUTURA DE UM PROGRAMA .......................................................................................................... 56
7.3. CHAMADA DE FUNÇÃO ....................................................................................................................... 57
7.4. CABEÇALHOS DE FUNÇÃO................................................................................................................... 58
7.5. MÓDULOS ........................................................................................................................................... 58
UERGS - Algoritmos e Programação Sumário
Copyright  2002,03 João Carlos Gluziii
7.6. PARÂMETROS, VARIÁVEIS LOCAIS E VARIÁVEIS GLOBAIS ................................................................. 61
7.7. RECURSIVIDADE ................................................................................................................................. 61
CAPÍTULO 8 - ARRAYS, STRINGS E MATRIZES................................................................................... 63
8.1. DECLARAÇÃO DE VETORES................................................................................................................. 64
8.2. USO DOS VETORES.............................................................................................................................. 64
8.3. CADEIAS DE CARACTERES (STRINGS).................................................................................................. 65
8.4. DECLARAÇÃO DE MATRIZES............................................................................................................... 68
8.5. USO DAS MATRIZES ............................................................................................................................ 69
CAPÍTULO 9 - APONTADORES (OUPONTEIROS) .............................................................................. 71
9.1. DECLARAÇÃO DE VARIÁVEIS APONTADORAS..................................................................................... 72
9.2. INICIALIZAÇÃO DE APONTADORES...................................................................................................... 72
9.3. USO DOS APONTADORES..................................................................................................................... 74
9.4. MANIPULAÇÃO DE APONTADORES...................................................................................................... 74
9.5. APONTADORES COMO PARÂMETROS DE FUNÇÕES.............................................................................. 75
CAPÍTULO 10 - ESTRUTURAS (STRUCTS) ............................................................................................. 78
10.1. DECLARAÇÃO DE ESTRUTURAS...................................................................................................... 78
10.2. UTILIZAÇÃO DAS ESTRUTURAS ...................................................................................................... 80
10.3. APONTADORES PARA ESTRUTURAS................................................................................................ 81
BIBLIOGRAFIA ............................................................................................................................................ 83
UERGS - Algoritmos e Programação Sumário
Copyright  2002,03 João Carlos Gluziv
Lista de Figuras
Figura 1 -Compilação de um Programa em C ...................................................................... 38
Figura 2 - Um Vetor com n Posições ................................................................................... 63
Figura 3 - Uma Matriz com m x n Posições ......................................................................... 63
Figura 4 - Apontador para Variável...................................................................................... 71
Figura 5 - Formato de Variáveis de Tipo struct na Memória ............................................... 79
Lista de Tabelas
Tabela 1 - Exemplos de Constantes...................................................................................... 22
Tabela 2 - Operações Aritméticas Binárias .......................................................................... 25
Tabela 3 - Operações Aritméticas Unárias ........................................................................... 26
Tabela 4 - Operadores Relacionais....................................................................................... 27
Tabela 5 - Operadores Lógicos............................................................................................. 28
Tabela 6 - Tabela Verdade do NOT (!) ................................................................................ 28
Tabela 7 - Tabela Verdade do AND(&&) e do OR(||). ........................................................ 29
Tabela 8 - Expressões Abreviadas........................................................................................ 31
Tabela 9 - Caracteres Especiais do printf ............................................................................ 35
Tabela 10 - Comandos de Formatação do scanf e printf .................................................... 36
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
1 Copyright  2002,03 João Carlos Gluz
Capítulo 1
Introdução
Antes de iniciar a aprendizagem das técnicas e conceitos envolvidos com a criação de
algoritmos e programas é importante saber claramente quais são os conceitos básicos da
Ciência da Computação (ou da Informática, que pode ser considerado como sinônimo de
Ciência da Computação).
Este texto introdutório tem como objetivo apresentar de forma simples, lógica e coerente
como a Ciência da Computação está sistematizada e organizada como corpo de
conhecimento humano. Neste contexto também será apresentado o histórico desta ciência,
sendo esclarecida a relação da computação com outras disciplinas do pensamento humano e
a fundamentação da informática em termos de conceitos de outras áreas.
1.1. Uma Breve História da Computação
A computação tem uma longa história por trás de si. Na verdade, pode-se dizer que o
objetivo de se conseguir efetuar cálculos aritméticos de uma forma automatizada e
mecânica vem sendo perseguido há milhares de anos. De uma forma geral a atividade de
executar uma grande quantidade repetitiva de cálculos aritméticos não é apenas uma tarefa
estafante mas também uma atividade muito sujeita a erros, devido a dificuldade normal que
nós, seres humanos, temos em seguir uma sequência excruciante e repetitiva de ações
(geralmente se diz, justamente, que este tipo de tarefa é desumano). Sendo assim um
mecanismo automático que efetuasse uma boa parte destes cálculos não apenas facilitaria a
tarefa mas também reduziria em muito a chance de erro no final das contas.
Por exemplo, a própria palavra cálculo, que deriva do latin calculus, originalmente
designava as pequenas pedras usadas para contar e manter o registro de operações de soma
quando dispostas sobre sulcos escavados no chão, ou seja, a própria etimologia da palavra
cálculo já aponta para uma espécie de mecanismo mecânico de cálculo, uma espécie de
ábaco primitivo.
São justamente os ábacos que podem ser classificados como os primeiros dispositivos de
“computação” automatizada. O mais antigo ábaco data de aproximadamente 3500 AC
proveniente da antiga Mesopotâmia (no atual Iraque). Em torno de 2600 AC o ábaco surge
na China e evoluiu rapidamente, sendo posteriormente adotado no Japão com o nome de
Sokoban.
Os ábacos permitiram um grande avanço na execução de repetitivas tarefas de cálculo. Os
resultados que se pode alcançar com o uso de um ábaco ainda hoje podem ser
surpreendentes mesmo quando comparados com a moderna tecnologia das calculadoras
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
2 Copyright  2002,03 João Carlos Gluz
eletromecânicas ou eletrônicas. Um usuário proficiente de ábaco ainda pode conseguir
efetuar sequências de cálculos de soma e subtração mais rapidamente do que um usuário
não muito experiente de uma calculadora.
Durante muito tempo este foi o avanço principal no que se poderia denominar de
“computação” ou cálculo automatizado. Outro avanço de igual magnitude somente iria
ocorrer no século XVII de nossa era quando o matemático, físico e filósofo francês Blaise
Pascal criou, no ano de 1648, uma máquina automática de calcular, que era um dispositivo
mecânico que simulava o funcionamento de um ábaco através de rodas dentadas. Esta
máquina de calcular, que é a “mãe” de todas as calculadoras mecânicas ou eletro-mecânicas
realizava operações de soma e subtração mostrando o resultado numa espécie de “display”
ou visor composto de uma série de janelinhas.
A máquina de calcular de Pascal, efetuava apenas somas e subtrações aritméticas de
números inteiros tendo sendo muito útil em diversas atividade humanas como o comércio, a
administração, a contabilidade, etc. Porém para os cálculos mais complexos envolvendo
não apenas somas e subtrações de inteiros mas multiplicações, divisões e potenciações de
números reais, que estavam sendo necessários pela crescente matematização que estava
ocorrendo na Física Natural, a máquina de Pascal não era suficiente. Entretanto, um auxílio
para ajudar nestes cálculos já estava a caminha com a criação, em 1650, por Partridge da
régua de cálculo, baseada nas tabelas de logaritmos naturais criadas pelo matemático
escocês John Napier no final do século XVI.
O interessante em relação a estes dois dispositivos, a máquina de calcular mecânica e a
régua de cálculo, é ambos permaneceram em uso, com mudanças relativamente menores,
até meados do século XX, cada uma ainda relacionada as atividades que ajudarama
avançar: a máquina de calcular transmutada em caixa registradora, ferramenta
indispensável ao comércio e a contabilidade (e a cobrança de impostos), e a régua de
cálculo também como instrumento indispensável da engenharia mecânica e da cívil, ou
seja, instrumento de áreas de conhecimento que podem ser consideradas como aplicações
da física moderna.
A partir daí os avanços começaram a se acelerar. Em 1672 foi desenvolvida, pelo famoso
matemático alemão Gottfried Wilhelm von Leibnitz (co-criador com Newton do Cálculo
Integral), uma máquina calculador “universal”, que efetuava operações soma, subtração,
multiplicação, divisão e extração da raiz quadrada. O trabalho de Leibnitz não foi a partir
do zero, tendo sido essencialmente uma aprimoramento da máquina de calcular de Pascal.
No início do século XIX ocorreram importantes avanços no conceito de “programação”
(este conceito realmente começou a aparecer na sua forma moderna). O ponto interessante
destes avanços, é que o precursor de todos os dispositivos “programáveis” modernos, não é
uma das máquinas de calcular em voga na época, mas um outro dispositivo mecânico
totalmente desvinculado da atividade de cálculo: um simples tear. Em 1801, Joseph Marie
Jacquard construiu na Inglaterra um tear automático cuja “programação” era feita através
de cartões (de madeira) perfurados. A “programação” deste tear controlava justamente
como seria a confecção do tecido e seus desenhos. Este tear pode ser considerada a primeira
máquina programável da história.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
3 Copyright  2002,03 João Carlos Gluz
A seguir e ainda na Inglaterra, Charles Babbage, matemático e professor da Universidade
de Cambridge, começou uma série de desenvolvimentos importantes que viriam a culminar
no projeto do que se poderia chamar de verdadeiro “ancestral” de todos os computadores
modernos. O primeiro destes desenvolvimentos foi o projeto e construção, em 1822, da
Máquina Diferencial, que era um dispositivo mecânico sofisticado que permitia o cálculo
de tabelas de números úteis a marinha comercial e de guerra (algo de extrema importância
para a Inglaterra, maior potência naval dos séculos XVIII e XIX). Esta máquina que chegou
a ter um protótipo construído, executava um algoritmo simples e fixo de diferenças finitas
por polinômios para calcular suas tabelas de funções.
Avançando esta idéia de forma a permitir a programação de qualquer tipo de função
desejada, Babbage começou, em 1833, a projetar o ancestral dos computadores: a Máquina
Analítica. Esta máquina nunca chegou a ser construída devido as dificuldades tecnológicas
de fabricação de componentes mecânicos da época, porém o seu projeto e as suas idéias
formam as base práticas da computação moderna. Por exemplo, além de ser uma máquina
programável, dispondo de uma verdadeira “linguagem” ou código de programação
(baseado em formalismos matemáticos), o dispositivo de Babbage teria uma “arquitetura”
organizada de uma forma muito similar aos computadores modernos: a Máquina Analítica
seria dividida em quatro subcomponentes ou unidades básicas:
• a unidade de entrada de dados: uma leitora de cartões perfurados
• a unidade de saída de dados: uma impressora e perfuradora de cartões
• um “silo” ou unidade de armazenagem: uma memória capaz de guardar até 1000
números de 50 algarismos cada um
• e finalmente um “moinho” ou engenho que executaria um programa de cálculo
sobre os dados de entrada, colocando os resultados na unidade de saída e usando
a armazenagem para guardar resultados intermediários. O programa seria
fornecido ao engenho por uma série de cartões perfurados, de maneira similar ao
tear de Jacquard.
É interessante observar que estas quatro unidades, continuam a ser considerados, do ponto
de vista conceitual, os elementos mais básicos de qualquer tipo de computador.
Mesmo que a máquina nunca viesse a ser construída, Babbage precisava demonstrar, pelo
menos em teoria, que a sua programação seria viável. Para tanto ele contratou Ada
Augusta Lovelace, condessa de Lovelace e filha do famoso poeta Lord Byron. Ada
Lovelace deu conta do recado, codificando os primeiros programas de cálculo numérico de
funções. Estes códigos eram instruções reais a serem carregadas na máquina de Babbage e
tinha uma forma muito similar a códigos em linguagem de máquina modernos, sendo assim
Ada Lovelace deve ser considerada, de uma forma bem realista, como sendo a primeira
programadora ou programador de computadores em toda a história.
Em termos de desenvolvimentos práticos, não ocorreram muitas outras coisas em todo o
século XIX, exceto pelo desenvolvimento em torno de 1885 de máquinas de tabulação de
dados automáticas que usavam cartões de dados perfurados de papel já em formato
moderno. Estas máquinas, com seus respectivos cartões, foram criadas por Herman
Hollerith, um (ex)funcionário do departamento de Recenseamento dos Estados Unidos,
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
4 Copyright  2002,03 João Carlos Gluz
extremamente preocupado com o fato de que o censo executado a cada 10 anos, tinha
levado, na sua última edição de 1870, exatos dez anos para ser tabulado e somado. Hollerith
criou uma companhia, a Tabulating Machines Company, que 1924 se juntou a outras
empresas para se transformar na atual International Business Machines.
A relativa falta de avanços tinha a ver com as limitações da tecnologia da época: as
máquinas diferenciais e de tabulação realmente atingiram os limites da tecnologia mecânica
(a máquina analítica, que foi apenas um projeto inconcluso, ultrapassou de longe estes
limites). Outros avanços práticos teriam que esperar um avanço tecnológico real, um
verdadeiro salto que deixaria de lado as limitações dos dispositivos mecânicos e abriria as
portas para as capacidades incríveis das novas tecnologias baseadas na eletricidade e na
eletrônica.
Entrementes, houveram avanços significativos no processo de desenvolvimento teórico da
computação. Em 1854, George Boole, matemático inglês, com a publicação do livro
“Investigation of the Laws of Thought” estabeleceu as bases da Álgebra de Boole ou
Álgebra Booleana, que fornece, entre outras coisas, o fundamento matemático da teoria
dos circuitos digitais modernos e, portanto, é uma das base teóricas da computação. O
trabalho de Boole, também não foi um desenvolvimento individual, tendo sido baseado em
trabalhos anteriores do seu amigo pessoal Augustos De Morgan, que desde a década de
1830 vinha trabalhando com os conceitos da álgebra simbólica e da lógica formal.
É importante salientar que esta visão de que os desenvolvimentos de Boole e De Morgam
formam uma das bases teóricas da computação é uma visão moderna, com uma perspectiva
um tanto “invertida” em relação ao trabalho destes matemáticos. O trabalho deles, em
conjunto com o de um sem-número de outros matemáticos no período, era parte de um
imenso esforço empreendido no final do século XIX e início do século XX para se definir
uma fundamentação teórica absolutamente precisa da própria Matemática, incluindo todas
as suas subdivisões: a Aritmética, o Cálculo, a Álgebra, a Lógica e demais áreas. É dentro
deste processo que estes desenvolvimentos devem ser encarados, entretanto, o fato curioso
neste processo é que todos os resultados positivos no sentido da formalização precisa, da
simbolização e da aritmetização da matemática permitiram, posteriormente, uma utilização
direta como bases formais do processo de cálculo automático ou de computação.
Dos vários desenvolvimentos importantes que ocorreram no período, vinculados àquele
tema maior de fundamentação da matemática, um se destaca no que tange ao impacto
ocasionado na Ciência da Computação: o trabalho, publicado em 1936, pelo grande
matemático inglês Alan Turing que lançou as bases da Teoria Matemática da
Computação. De uma forma simples, neste trabalho Turing criou uma máquina“virtual”,
existente apenas no pensamento, que poderia executar qualquer tipo de computação que se
pudesse imaginar. Precisando um pouco mais: se um problema tiver uma solução que possa
ser calculada automaticamente, ou seja, resolvida através de um programa composto de
pequenos passos, cada passo precisamente definido, então obrigatoriamente deve existir
uma máquina destas para representá-lo. Do ponto de vista técnico este resultado nunca foi
contradito: todo e qualquer computador moderno, por mais avançado, sofisticado, veloz ou
capaz que tenha sido criado pode ser representado por uma máquina de Turing, que é o
nome atribuído a estes computadores teóricos universais. Da mesma forma todo e qualquer
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
5 Copyright  2002,03 João Carlos Gluz
programa em qualquer linguagem também pode ser representado por alguma máquina de
Turing. Apenas por curiosidade, em relação ao esforço de fundamentação matemática, esta
proposição define uma tese, denominada de Tese de Church-Turing, que diz que tudo que
pode ser computável, pode ser computável por uma máquina de Turing. Esta declaração,
embora seja normalmente considerada verdadeira (quase uma tautologia por muitos) é
definida como uma tese por ser impossível de ser “demonstrada”: tudo depende de quais
serão as operações básicas (de quais serão os menores passos) usados nesta computação.
Em geral, até hoje, não parece válido assumir que existem passos menores diferentes do
que àqueles já definidos por Turing, sendo assim parece não fazer sentido pensar na
existência de outros tipos de “computações”, mas nunca se sabe...
Voltando ao desenvolvimento tecnológico, o início do século XX foi pródigo em
desenvolvimentos práticos da computação, acompanhando o próprio desenvolvimento
acelerado das tecnologias de projeto e construção de dispositivos eletro-mecânicos,
elétricos e eletrônicos.
Em 1937, Howard H. Aiken da Universidade de Harvard, começou a construir o primeiro
computador eletro-mecânico baseado em relés e engrenagens, seguindo as idéias de
Babbage. Este computador, denominado de MARK I, foi construído com o apoio da IBM e
concluído em 1944. Ele possuia unidades de entrada de dados, memória principal, unidade
de controle e aritmética e unidade de saída. Esta máquina, que chegou a ser usada por
pouco tempo, foi rapidademente deixada de lado porque o desenvolvimento da eletrônica e
dos computadores eletrônicos obsoletou os computadores eletro-mecânicos.
Já em 1940 os professores John W. Mauchly e J. Presper Eckert Jr. construiram, com o
financiamento do Exército dos Estados Unidos, o primeiro computador eletrônico: o
ENIAC (Electronic Numerical Integrator and Calculator). Este computador construído na
Universidade da Pensylvania era 1000 mais rápido que o MARK I, mas pesava apenas a
metade (pesava “apenas” 30 toneladas contra as 70 toneladas do MARK I). O ENIAC, cujo
projeto de construção foi aceito como parte do “esforço de guerra”, somente foi concluído
após a guerra terminar, em 1946. Apesar disso o ENIAC lançou as bases da computação
moderna: não só mostrou a viabilidade destes dispositivos, como também demonstrou o
poder e velocidade de cálculo que se poderiam alcançar. Além disso vários pesquisadores
importantes posteriormente para a computação, como John V. Atanasoff e John von
Neumann, começaram os seus estudos na área justamente trabalhando com o pessoal do
projeto do ENIAC.
Embora tenham existido alguns computadores eletrônicos ou parcialmente eletrônicos que
antecederam o ENIAC, este último pode ser considerado tranquilamente como o antecessor
dos computadores modernos, principalmente em razão de sua “visibilidade” e da
publicação dos seus resultados. Antecessores como o COLOSSUS que foi o primeiro
computador eletrônico da História, construído já em 1943 na Inglaterra com o trabalho do
grupo liderado pelo matemático Alan Turing permaceram em segredo até a década de 70,
perdendo, portanto, a chance de influenciar o desenvolvimento da computação. Da mesma
forma o trabalho do professor Zuse na Alemanha Nazista nas décadas de 30 e 40 e que
chegou a construir um computador eletro-mecânico completamente operacional já no início
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
6 Copyright  2002,03 João Carlos Gluz
década de 40, também foi completamente perdido com a derrota da Alemanha, somente
tendo sido recuperado 20 ou 30 anos depois.
Um outro fato interessante de se comentar é que a criação dos computadores no início da
década de 1940, parecece, em retrospectiva, um desenvolvimento quase “inevitável” da
época. O fato é que durante a década de 1940, nada menos do que 4 computadores
inteiramente distintos, mas usando tecnologia similares e respeitando os mesmos
princípios, foram construídos de forma completamente independentes. Mesmo que o
ENIAC se transformasse na vedete, sendo considerado durante muito tempo o ancestral
único dos computadores, a verdade é que ele foi apenas o mais bem divulgado. Uma
explicação para o fato de tantos computadores surgirem ao mesmo tempo, surge quase que
imediatamente, como relacionada ao imenso esforço econômico, social e militar provocado
pela II Guerra Mundial. No início da guerra já haviam sido desenvolvidos todos os
elementos e componentes (válvulas, relés, etc.) que permitiriam construir um computador.
Além disso, em virtude de trabalhos teóricos anteriores de Turing, Babbage e outros, não só
já se sabia como construí-los, mas também do custo quase que astronômico que uma
máquina destas teria. Com a guerra, entretanto, as razões e princípios econômicos normais
deixam de “funcionar”, numa “economia de guerra” somente há um objetivo final:
sobreviver e se a posse de um computador melhora, ainda que marginalmente, a
possibilidade de se atingir este objetivo final então ele deve ser construído. Embora os
Americanos não tivessem usado o seu computador na guerra, para os Ingleses esta não foi
uma questão apenas de cunho acadêmico: o uso dos sistemas de computação COLOSSUS
foi extremamente importante para a vitória da sua nação durante a Batalha do Atlântico o
que garantiu a sobrevivência deste país e a possibilidade do contra-ataque e vitória final
contra a Alemanha Nazista.
O ENIAC e alguns sucessores, formaram o que se convencionou chamar de “primeira
geração” dos computadores. Este termo “geração de computadores” embora esteja caindo
em desuso, ainda é usado para designar, pelo menos, as primeiras 3 tecnologias básicas
usadas na fabricação de computadores:
Primeira Geração: Computadores fabricados com válvulas eletrônicas, começou
na década de 40 e terminou na década de 50.
Segunda Geração: Computadores fabricados com transístores, ou seja, com
dispositivos semicondutores individuais, começou na década de 50 e durou até a
década de 60.
Terceira Geração: Computadores fabricados com dispositivos semicondutores
integrados, ou seja, com “Circuitos Integrados” ou CIs. Considera-se que esta
geração apenas designe os computadores fabricados com CIs de “baixa” ou “média”
integração (apenas algumas centenas ou poucos milhares de transístores por CI).
Esta geração começou na década de 60 e terminou na década de 70.
Após estas três gerações “clássicas” a computação, pelo menos a parte física ou hardware,
passou a ser cada vez mais dominado pelos computadores completamente integrados num
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
7 Copyright  2002,03 João Carlos Gluz
CI, os famosos Microprocessadores, que deram origem aos microcomputadores e que,
hoje em dia, perderam o adjetivo “micro” e são chamados apenas de computadores.
Os microprocessadores, que foram inventados pela Intel ainda no início da década de 70,
hoje correspondem pela quase totalidade dos computadores fabricados no mercado. Apesar
desta “simplificação” ocorrida de se colocar um computador num CI, hoje os sistemas de
computação se transformaramem entidade bem mais complexa, envolvendo não apenas o
que se denominada anteriormente de computadores, mais vários outros tipos de dispositivos
de comunicação, de entrada e saída de dados, multimídia, sofisticadas redes de
interconexão, etc.
Na verdade o processo evolutivo, apenas delineado muito superficialmente nesta seção,
continua muito mais acelerado do que nunca, aperfeiçoando não apenas os aspectos físicos
da computação, o seu hardware, mas também mudando e recriando continuamente todos os
seus aspectos lógicos e de programação.
1.2. Conceitos Elementares de Computação e Informática
Cência da Computação e Informática
Em primeiro lugar seria importante precisar um pouco mais o significado dos termos
“Ciência da Computação” e “Informática”. A Ciência da Computação é a ciência, ou
corpo sistematizado do conhecimento humano, que trata das formas de se executar
computações de forma automática e independente da intervenção humana. Vale ressaltar,
entretanto, que no contexto desta expressão a palavra computação não deve ser
compreendida como apenas designando cálculos ou operações numéricas, mas deve ser
entendida como denominando qualquer tipo de processamento de informações (que, no
caso, possa ser automatizado). Esta é justamente a relação da Ciência da Computação com
a Informática, que é apenas uma outra forma de denominar este mesmo conceito, ou seja,
informática é a ciência que estuda o tratamento automático do processamento das
informações.
Computador
Prosseguindo, deve-se aclarar a relação existente entre a computação ou informática e os
computadores. Normalmente as explanações ou definições da Ciência da Computação,
começavam por dizer que ela era a ciência que estudava os computadores. Esta entretando é
uma definição exageradamente limitadora, porque, é importante notar, não é
necessariamente obrigatório se trabalhar com computadores para se fazer Ciência da
Computação. Muito antes pelo contrário, existe, na verdade, todo um ramo teórico desta
ciência que pesquisa as características mais fundamentais e também os limites mais
avançados dos processos de computação sem a necessidade de se usar computadores reais
nesta pesquisa. Por exemplo, de acordo com o histórico visto anteriormente, pode se ver
que as definições teóricas precisas do processo de computação antecedem em quase dez
anos a construção real do primeiro computador digital.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
8 Copyright  2002,03 João Carlos Gluz
Feitas estas ressalvas, pode-se definir um computador como qualquer dispositivo real que
execute computações ou processem de informações de forma automatizada. A definição do
que é um computador independe de tecnologia, no decorrer de sua longa história os
computadores já foram incorporados das mais diversas formas: como projeto mecânico
(Babbage), como dispositivo eletro-mecânico (MARK I), como dispositivo eletrônico
baseado em válvulas e finalmente na sua incarnação moderna como dispositivo baseado em
semicondutores. Dito isto deve ficar claro que não interessa muito a tecnologia em que o
computador está baseado (exceto por questões de capacidade e desempenho), mas sim se
este dispositivo consegue executar processos ou mais precisamente programas que
manipulem informações de forma automática.
Hardware e Software
Justamente aí começa uma das divisões mais importantes da informática: a divisão entre os
componentes físicos de um computador, usualmente agrupados sob o termo inglês
hardware, e os elementos lógicos e de controle deste computador, usualmente agrupados
sob o termo inglês software. O hardware de um computador se refere a todos os
componentes físicos necessários para a construção deste dispositivo. De uma forma bem
prática, o hardware designa os elementos que não podem ser mudados ou “programados”
num computador, exceto pela troca física de peças. Já o termo software tem uma conotação
muito mais “soft” ou leve (como o próprio termo indica), normalmente ele designa o
conjunto de programas ou sequências de instruções que comandam a execução de um
computador, fazendo com que este execute alguma computação útil. O software também se
refere, de uma forma mais geral, aos elementos lógicos ou de controle de um computador
que podem ser facilmente alterados, recarregados ou reconfigurados neste.
Programa e Algoritmo
O software de uma máquina ou computador está intimamente ligado aos programas que
executam neste computador. Estas idéias de que é um “programa” ou do que é a
“execução” deste programa no computador são extremamente importantes, elas formam a
própria base de toda a informática: embora possa existir uma Ciência da Computação
teórica sem computadores, não existe processamento de informações prático ou teórico sem
programas, ou de sua contrapartida mais abstrata, sem algoritmos. Apesar disso, a definição
mais precisa destes termos será deixada para um próximo capítulo, por agora, basta a idéia
intuitiva de que um programa ou algoritmo é uma sequência de passos que executam
alguma função. A diferença entre um algoritmo e um programa é que este último deve
poder ser executado por um computador real.
Informação e Dado
Se olharmos para um dicionário veremos que o termo informação designa tudo aquilo que
permite adquirir conhecimento, ou seja, informação é aquilo que dá a conhecer alguma
coisa que se desconhecia anteriormente. Dito desta forma o conceito parece muito abstrato
e filosófico e realmente o é, uma vez que fundamenta o conceito de informação sobre um
outro conceito muito mais complexo: o “conhecimento”.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
9 Copyright  2002,03 João Carlos Gluz
O problema aqui é que, se quisermos que a computação ou a engenharia possam trabalhar
com a informação é necessário ter um conceito mais preciso e “quantificável” (numérico)
sobre o que é informação. A solução encontrada, para evitar uma discussão filosófica
praticamente interminável sobre o que seria ou o que não seria informação, dada a natureza
particularmente intratável de se definir o que é conhecimento, foi tomada através de um
caminho “lateral” que permitiu definir precisamente e quantitativamente o que seria
informação.
A definição quantitativa inicial para o conceito de informação é devida ao pesquisador e
engenheiro Claude Shannon, que definiu este conceito ainda na década de 1940. Na
definição de Shannon, não interessa muito o que é ou seria o conhecimento em si, mas
interessa o fato de que a informação permite “transferi-lo” e “aumentá-lo”, ou seja,
informação é um veículo de transporte de conhecimentos de um “lugar” para outro.
Seguindo por este caminho (e usando uma pequena ajuda da Física Moderna) é possível se
chegar até a quantização da informação, que é o objetivo final da Engenharia: geralmente
se considera, em Engenharia, que somente é possível se trabalhar apropriadamente sobre
um determinado conceito quando ele pode ser completamente matematizado e quantizado.
Seguindo este raciocínio, Shannon chegou a menor unidade possível de transporte e
manipulação de informação, o menor “pedaço” de informação ou conhecimento que se
pode ter sobre qualquer tipo de tema. A pressuposição filosófica implícita neste raciocíonio
é que, quando questionado sobre algum tema, ou você sabe a resposta e responde
afirmativamente (representado por “sim”, por “verdadeiro” ou pelo número 1) ou você não
sabe e responde negativamente (representado por “não”, por “falso” ou pelo número 0). De
qualquer forma, após a resposta ter sido dada, certamente quem perguntou tem mais
conhecimento do que tinha antes. Ele na verdade resolveu uma dúvida, ele não sabia de
algo e agora passou a saber, portanto teve seu conhecimento “aumentado” na menor
“quantidade” possível: uma resposta sim ou não.
O nome dado a este menor pedaço de informação ou dado, tanto na Ciência da Computação
quanto na Engenharia ou Telecomunicações é bit,que é a contração para a expressão
inglesa “binary digit” ou “dígito binário” que pode valer, portanto, 0 ou 1 (e pode
representar, portanto, qualquer tipo de resposta sim/não, verdadeiro/falso, etc.).
Quanto aos dados, se a informação pode ser pensada como um tipo de “veículo” para
transportar conhecimentos, então um dado pode ser compreendido como a instanciação
concreta deste veículo. Um dado é, portanto, o elemento concreto (um símbolo concreto)
responsável pelo próprio transporte (ou armazenamento) da informação. Qualquer símbolo
concreto pode ser usado: uma letra, um antigo hieroglifo egípcio, um trecho de música num
disco de vinil, um arquivo na memória de um computador, um texto gravado sobre um
disco de CD, etc. podem ser considerado como dados.
É redundante afirmar que na Ciência da Computação os únicos tipos de dados que são
realmente tratados são os dados armazenados em bits, isto é, os dados binários. Todos os
demais tipos de dados são construídos sobre estes bits.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
10 Copyright  2002,03 João Carlos Gluz
1.3. Programas, Algoritmos e Programação
Programa
Provavelmente o conceito individual mais importante na Ciência da Computação é o de um
programa de computador ou simplesmente programa. A compreensão correta deste
conceito é fundamental para se avançar no estudo desta ciência. Posto de uma forma bem
intuitiva um programa nada mais é do que um conjunto de comandos ou instruções que
uma máquina ou computador deve executar para resolver um problema. Esta idéia apesar
de simples é incompleta porque, embora traga a baila os pontos mais significativos do
conceito de programa: conjunto de comandos, computador, execução e resolução de
problemas (automatizada), lhe faz falta detalhar algumas facetas e aspectos importantes
destes:
• A estrutura e organização do conjunto de instruções é um fator extremamente
importante para que um programa funcione corretamente: esta estrutura e
organização definem a “lógica” do programa, ou seja aquilo que define a razão do
seu próprio funcionamento;
• Um programa deve definir claramente e com todo o detalhamento necessário como
um problema deve ser resolvido num computador, ou seja, não basta detalhar as
características ou descrições do que o problema é ou de porque o problema é
importante, mas, isto sim, é necessário saber claramente como ele pode ser
resolvido tanto do ponto de vista puramente lógico mas também do ponto de vista
do que pode ser executado no computador;
• Em relação ao ítem anterior, também é usual se separar os conceitos de sequência
de passos “lógicos” que devem ser empregados para resolver um problema, que
normalmente é denominado de algoritmo e a sequência similar de passos ou
instruções que já estão prontos para serem executados por algum computador ou
máquina, que é um programa propriamente dito.
Um comentário final: um programa deve comandar a operação de um dado computador, ou,
dito de outra forma um computador deve executar as instruções ou comandos do programa,
ou mais simplesmente, um computador deve executar um programa.
Programação e Análise
Embora as vezes seja usada num contexto mais limitado, do ponto de vista mais geral o
termo programação designa a atividade humana de buscar soluções para problemas
através da criação de programas de computador. A programação está intimamente
relacionada e as vezes até se confunde ou entra em conflito com uma outra atividade,
denominada de análise, que geralmente designa o processo de se tentar compreender e
dissecar um problema em partes menores que possam ser resolvidas diretamente, isto é, em
problemas menores cujo algoritmo que os resolve já é conhecido. Em geral faz mais sentido
tentar compreeder ambas atividades como complementares e necessárias para a busca de
soluções e o desenvolvimento de programas, do que tentar buscar algum conflito na
interação entre as duas.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
11 Copyright  2002,03 João Carlos Gluz
O primeiro passo para a elaboração de qualquer programa é, justamente, proceder com a
cuidadosa análise do programa em questão. O resultado deste trabalho deve ser uma
especificação lógica e precisa de como ele pode ser resolvido, um algoritmo em outras
palavras. De posse deste algoritmo pode-se passar para a tarefa mais especializado de fazer
com que um computador compreenda e seja dirigido por este algoritmo, ou seja, a tarefa de
programação.
Testes e Depuração
Isto entretanto não é tudo, porque no mundo real os erros são praticamente inevitáveis (isto
é denominado pelos programadores e analistas com a famosa “Lei de Murphy”, que afirma
que se alguma coisa tem a chance de dar errado ela vai dar errado e provavelmente isto
acontecerá no pior momento possível). Sendo assim é muito provavel que um programa não
funcione corretamente, ou seja, não resolva o problema, na primeira vez que for executado
(se diz também “rodado”). Normalmente um programador pode ser considerado experiente
não porque seus programas funcionam bem desde o início, muito antes pelo contrário, um
programador é realmente experiente quando sabe perfeitamente que as primeiras versões de
qualquer programa que produzir certamente não irão funcionar a contento e está
plenamente preparado para isto, pronto para testar o programa e corrigir seus erros até
resolver a situação.
Dessa forma logo após a construção de um programa, existe toda uma série de atividades,
direcionadas primeiro em fazer com que o programa funcione corretamente e
posteriormente para estender as capacidades deste programa para atender a novas
requisições.
Em geral se denominam a fase em que se tenta fazer com que um programa uncione de fase
de teste e depuração do programa. Nesta fase o programa é testado, sendo confrontado
com o problema que pretende resolver. Cada vez que um erro é detectado ele deve ser
depurado, ou seja, devem ser feitas adaptações e correções para garantir o seu bom
funcionamento. Muitas vezes também são feitos testes do programa por pessoas não
relacionadas ao seu desenvolvimento, isto é chamado normalmente de validação do
programa. Quando esta validação é deixada a cargo do mercado, sendo feita por pessoas de
fora da organização ou empresa responsável pelo programa isto é, as vezes, denominado de
fase de testes em beta ou apenas de beta-teste do programa.
Manutenção
Uma vez que os problemas sejam encontrados e corrigidos, então o programa entra em fase
“de produção” podendo ser usados pelas pessoas que necessitam resolver o problema que
motivou a construção do programa. Pessoas que usam programas de computador
(computadores em geral) para executar alguma tarefa ou resolver algum problema são
usuários de computador ou simplesmente usuários.
Mesmo quando um programa já está em uso há bastante tempo, sempre existe alguma
atividade de teste e programação associada a ele. Não só as situações, problemas e tarefas
para qual o programa foi projetado podem mudar com o passar do tempo, como também
novas possibilidades e características podem ser vislumbradas para a sua utilização.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
12 Copyright  2002,03 João Carlos Gluz
Quando isto ocorre e são necessárias modificações no programa, se diz que o programa
deve passar por uma manutenção. Além disso, exceto em casos triviais, nunca é possível
se estar 100% certo de que todos os erros foram encontrados e depurados, logo quando
novos erros forem encontrados e tenham que ser corrigidos o programa também entrará em
manutenção.
1.4. Estrutura de um Programa
Um programa de computador não é uma estrutura isolada dentro do computador,
independente do mundo externo. Muito pelo contrário, para resolver o problema que lhe
deu origem, para executar alguma tarefa em particular normalmente é necessário que exista
uma forte interação deste programa com o mundoexterno, que exista um processo contínuo
de troca de informações entre o programa e o ambiente externo. Desta forma, do ponto de
vista funcional, um programa pode ser subdivi em três grandes partes:
• Entrada de Dados ou Informações: formada por todas as instruções que obtém
dados do ambiente externo, guardando estes dados numa área de armazenamento
(uma memória) interna para que possam ser processados posteriormente.
• Processamento das Informações: parte do programa responsável por resolver o
problema a partir dos dados recém obtidos pela entrada de dados. Além das
instruções e operações executadas sobre estes dados de entrada, o processamento de
informações também faz uso da memória para guardar informações temporárias e
para preparar informações para saída.
• Saída de dados ou informações: uma vez que existam resultados que possam ser
apresentados externamente, então eles devem ser preparados e enviados para o
ambiente externo, através de um conjunto específico de instruções.
É importante salientar que estes três elementos básicos de qualquer programa não estão
necessariamente separados e identificados claramente dentro do programa. O normal,
inclusive, é encontrar as operações e instruções referentes a cada parte misturadas entre si,
de acordo com a necessidade que o programa tenha de obter novos dados ou de informar
algum resultado intermediário. Apesar disto sempre se pode analisar e decompor qualquer
problema, identificando os trecho correspondentes a entrada de informações, ao
processamento destas e a saída destas informações para o ambiente externo.
Em relação ao ambiente externo e a forma como se dá esta interação, valem algumas
considerações:
• O objetivo da entrada e saída de dados é geralmente a comunicação com algum
usuário.
• Apesar disso deve-se ter em mente que tanto a entrada quanto a saída de
informações é mediada através de dispositivos especiais de entrada e saída, ou
periféricos de entrada e saída.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
13 Copyright  2002,03 João Carlos Gluz
• Também não é incomum que um programa se comunique apenas com um
dispositivo, por exemplo um sensor externo, sem a intervenção de nenhum usuário.
Isto é comum em controle de processos industriais, por exemplo.
• Outra possibilidade que existe é que um programa se comunique com outro
programa através da entrada e saída de dados. As Redes de Computadores e os
Sistemas Distribuídos são os exemplos mais evidentes deste tipo de interação.
Uma outra estruturação que se faz comumente em relação aos programas tem a ver com a
metodologia empregada para organizar logicamente as solução de problema através de
computadores. Dada as características que os computadores tem para manipular dados e
informações, cada programa deve ser dividido em duas grandes partes:
• Especificação dos Dados: onde se define como serão estruturados os dados a serem
usados pelo programa, ou seja, onde se declara como serão as estruturas de dados
usadas pelo programa.
• Especificação do Algoritmo: onde se define o conjunto de instruções que o
computador terá que executar para resolver o problema.
Resumindo um programa é a soma das suas estruturas de dados com o seu algoritmo,
escritos em alguma linguagem própria para ser executada por um computador (uma
linguagem de programação).
1.5. Linguagens de Programação
Como visto anteriormente, um programa é um conjunto de instruções que dirigem a
operação de um computador. Porém existem muitas maneiras de se construir um programa,
porque existem inúmeras formas como este conjunto de instruções pode ser organizado e
estruturado e também existem muitos tipos distintos de instruções, operações ou comandos
que podem ser executados por um computador. O ramo da computação que estuda como os
programas podem ser construídos é o de Linguagens de Programação.
Linguagem, Símbolos e Gramática
Uma linguagem é uma notação ou convenção que se pode usar como meio de comunicação
de informações, conhecimentos, sentimentos, etc. entre seres humanos. Uma linguagem de
programação é, então, uma forma de notação que nos permite comunicar a um computador
os comandos e instruções que ele deve executar. Dito desta forma é evidente que qualquer
programa deve ser escrito em algum tipo de linguagem de programação, ou seja, em
alguma linguagem que possa ser compreendida por um computador (embora evidente, as
vezes é esquecido, principalmente por programação mal feita, um programa também deve
ser compreendido por um ser humano).
Qualquer linguagem contém um conjunto de simbolos básicos e atende um conjunto de
regras precisas que diz como estes símbolos são organizados em expressões, frases,
orações, etc. Estas regras definem a gramática da linguagem. Uma grande diferença entre
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
14 Copyright  2002,03 João Carlos Gluz
as linguagens usadas pelos seres humanos e as linguagens de programação, é que as
linguagens humanas, também denominadas de linguagens naturais, embora certamente
contenham símbolos (letras, palavras, fonemas, ideogramas, etc) e sigam regras
gramaticais, nem sempre tem estes elementos precisamente identificados ou formalmente
definidos, isto é, linguagens naturais não são completamente formais. Por outro lado as
linguagens de programação devem, pela própria natureza formal e “mecânica” dos
computadores ser linguagens formais, com regras precisamente definidas de como as
expressões linguísticas podem ser construídas.
Sintaxe e Semântica
De agora em diante, se nada for dito em contrário, o termo linguagem se referirá
exclusivamente às linguagens de programação. A regras gramaticais de uma linguagem
definem a sintaxe destas linguagem que é a forma como se pode construir expressões
corretas da linguagem. O fato de se ter uma expressão correta gramaticalmente, isto é, com
uma sintaxe correta não quer dizer necessariamente que a expressão tem algum sentido ou
significado. O significado atribuído a uma dada construção linguística é denominado de
semântica desta construção. Embora a semântica das linguagens naturais seja
extremamente complexa e relacionada ao pensamento, à razão, as emoções, sentimentos e
inúmeras outras características humanas, a semântica das linguagens de programação não
segue um território tão perigoso. Todas as construções de uma linguagem de programação
tem seu significado precisamente fundamentado sobre as operações e instruções básicas
que um computador pode executar.
Entretanto, o principal objetivo de pesquisa da área de linguagens de programação é de
buscar formas de se escrever programas que sejam cada vez mais parecidas ou similares
com a nossa forma de se comunicar e trocar idéias e informações, isto é, o objetivo é tentar
trazer as linguagens de programação o mais próximo possível das linguagens e conceitos
usados por nós.
Níveis de Linguagens
Para tanto o usual é dividir este problema, considerando que as linguagens possam ser
classificadas em diferentes níveis de linguagens, sendo os níveis inferiores mais próximos
das máquinas e os níveis superiores mais próximos dos seres humanas. Assim linguagens
dos níveis inferiores, as linguagens de baixo nível, teriam suas construções linguísticas
mais próximas das operações e estruturas de dados disponibilizados pelos computadores,
enquanto que as linguagens superiores ou de alto nível, teriam suas construções mais
próximas da linguagem natural ou pelo menos de mais fácil compreensão pelas pessoas.
Uma outra diferença importante seria a de que as linguagens de alto nível conseguiriam
atingir independência em relação à máquina, podendo um mesmo programa ser utilizado
em diferentes equipamentos com a única condição de disporem de um programa de
tradução compatível com a linguagem. Esta característica, idealmente, permitiria isolar ou
diminuir a necessidade de se ter conhecimento do hardware para se programaro sistema.
Embora ainda existam alguns defensores para o desenvolvimento de aplicações em
linguagens de máquina, tendo como argumento principalmente questões de desempenho e
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
15 Copyright  2002,03 João Carlos Gluz
uso de recurso de máquina que supostamente poderiam ser melhor administrados
diretamente em linguagem de baixo nível do que em linguagens de alto nível, a verdade é
que atualmente essa questão já está praticamente resolvida em favor da programação em
alto nível.
Primeiro, existem vários pontos desejáveis atendidos pelas linguagens de alto nível, quando
estas são comparadas às de baixo nível:
• Facilidade de programação, por usar conceitos mais próximos das pessoas do que
das máquinas.
• Independência de arquitetura de máquina: no caso das linguagens de baixo nível
existe uma linguagem para cada tipo distinto de computador ou máquina.
Além disso é muito importante salientar que, no caso de certas arquiteturas de computador
(como as arquiteturas RISC), simplesmente não é mais humanamente possível gerar um
“bom” código de máquina, um código bem otimizado, pela quantidade de efeitos colaterais
associados a execução de cada instrução e a relação destes efeitos com as 4 ou 5 instruções
anteriormente executadas e as outras tantas possíveis instruções a serem executadas.
Somente um compilador consegue manter o registro destes efeitos de forma precisa, tirando
o máximo possível da máquina.
Apesar disso, a programação em linguagem de montagem ainda é necessária em alguns
casos específicos, como nos estágios iniciais de carga e inicialização de um compuador e
também quando se deve programar a comunicação com alguns periféricos de entrada e
saída.
1.6. Tradução de Linguagens
Afora programas escritos diretamente em linguagem de máquina, que são código objeto
pronto para execução, todos os demais tipos de programas precisam de algum tipo de
processo de tradução para poderem ser executados num computador.
A tradução de um programa de alto nível pode ser feita de duas grandes formas, através da
compilação deste programa ou através da interpretação do mesmo. Já um programa em
linguagem de montagem passa por um processo similar ao da compilação, denominado de
montagem.
Compilação
A compilação de um programa é um processo que traduz um programa escrito numa
linguagem origem, denominado de programa fonte, para um outro programa escrito numa
linguagem objeto, denominado de programa ou código objeto. Idealmente o código objeto
pode ser executado diretamente pelo computador, porém geralmente existem ainda alguns
passos posteriores que devem ser executados para que o programa objeto possa ser
executado. O programa que realiza este processo de tradução é denominado de compilador.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
16 Copyright  2002,03 João Carlos Gluz
Liguagens que são tipicamente implementadas através de compiladores são: Pascal, C,
C++, Java, Fortran, etc.
Interpretação
Quando um programa fonte não é traduzido integralmente, “de uma só vez” para um outro
programa equivalente objeto, mas ao invés, cada expressão ou comando deste programa é
traduzido e interpretado num conjunto de instruções de linguagem de máquina que são
prontamente executadas, denomina-se este tipo de tradução de interpretação. Os programas
que interpretam uma linguagem são denominados de interpretadores. Linguagens de alto
nível que são tipicamente interpretadas são as interfaces (shells) de comando dos sistemas
operacionais, a linguagem BASIC e as linguagens script usadas na programação para
sistemas da Web: ASP, PHP, JavaScript
Montagem
A montagem é um processo muito parecido com a compilação, a diferença é apenas que o
programa fonte está escrito em linguagem de montagem e não numa linguagem de alto
nível. Este programa fonte em linguagem de montagem também é traduzido para um
programa em código objeto.
Embora certos tipos de linguagens sejam normalmente implementadas através de
compiladores e outros através de interpretadores, esta divisão não é absoluta ou irreversível,
ou seja, o fato de se implementar uma linguagem por compilação ou interpretação está mais
associado ao uso que se pretende dar a linguagem e com características de desempenho,
capacidade e flexibilidade do que com algum tipo de características intrísecas da mesma.
Por exemplo, embora a maior parte das implementações de C e C++ seja através de
compiladores, teoricamente nada impede que se implemente estas linguagens através de
compiladores. A questão aqui é que, embora não exista empecilho teórico para a
implementação através de interpretadores, se espera que a implementação compilada atinja
melhores índices de desempenho e gaste menos recursos que uma versão interpretada e
para o uso pretendido para sistemas escritos em C e C++ estes objetivos de desempenho e
capacidade são mais importantes do que a flexibiliade em se modificar ou atualizar um
sistema. Por outro lado para sistemas e aplicações escritas em linguagens interpretadas,
como por exemplo sistemas vinculados a páginas da Web, pesam mais os ítens como
flexibilidade e facilidade de implantação e atualização, que são melhor servidos por
interpretadores.
1.7. Carga e Execução de Programas
A execução dos programas interpretados é direta, sendo feita pelo próprio programa
interpretados. Por outro lado os programas compilados e montados, tem um caminho um
pouco mais tortuoso. Em primeiro lugar o código objeto gerado tanto pelos compiladores
quanto pelos montadores normalmente não está “pronto” para ser executado pela máquina,
sendo necessário mais dois processos auxiliares antes desta execução: a ligação e a carga do
programa.
UERGS - Algoritmos e Programação Capítulo 1 -Introdução
17 Copyright  2002,03 João Carlos Gluz
Um programa final que será executado numa máquina não precisa estar contido em apenas
um único programa fonte, ou seja, o programa executável final pode ser o produto de vários
programas fontes distintos. O processo que “pega” estes vários programas fontes distintos,
já compilados, e junta num grande executável final é denominado de ligação (em inglês
linking). O programa que faz isto é denominado de ligador (linker). Apesar de parecer
laborioso, este processo é vantajoso sob vários pontos de vista, porque permite que
programas que foram criados para outros fins possam ser reaproveitados e permite também
que se possa criar verdadeiras bibliotecas de programas, procedimentos e funções que
podem posteriormente ser utilizadas por uma grande variedade de programas. Basta ligar a
biblioteca previamente compilada ao seu programa que você pode usar as rotinas desta
biblioteca nele.
Um último processo, aparentemente invisível e executado pelo Sistema Operacional é o
processo de carga do programa e posterior execução deste. Este processo é um pouco mais
complicado do que parece porque implica não apenas em trazer o código executável de um
arquivo para a memória principal, mas também de se alocar ou reservar previamente os
recursos (memória, dispositivos de entrada e saída, arquivos de disco, terminais de teclado,
mouse, vídeo, etc.) que poderão ser usados pelo programa.
Após a carga do programa pelo Sistema Operacional começa o processo de execução
propriamente dito, que é feito, evidentemente, diretamente pelo processador. Existem
alguns casos, entretanto, quando o sistema operacional poderá entrar novamente em ação:
quando for necessário executar uma operação de entrada de dados ou de saída de dados,
que são usualmente executadas através de chamadas do Sistema Operacional, quando for
necessário usar algum recurso novo dinâmico, não previsto quando o programa foi
compilado, tipicamente mais memória. Além disso no caso de sistemas multi-tarefa a
execução do programa poderá ser interrompida arbitrariamente pelo Sistema Operacional
para permitir que algumoutro programa ou tarefa possa ser executado concorrentemente.
UERGS - Algoritmos e Programação Capítulo 2 - Algoritmos e Linguagem C
18 Copyright  2002,03 João Carlos Gluz
Capítulo 2 
Algoritmos e Linguagem C
2.1. Algoritmos
Para se definir o conceito de algoritmo de forma precisa é necessário estabelecer antes o
conceito de ação finita ou apenas ação:
Uma ação é um determinado acontecimento que, a partir de um dado estado inicial
e após um período de tempo finito, produz um um estado final que é previsível e
também bem definido.
Também se deve definir o conceito de comando:
Um comando é o ato de ordenação da execução de uma ação, ou seja, um
comando força a execução de uma ação (note que uma ação é um acontecimento e
acontecimentos podem ser fortuitos ou não, isto é, podem acontecer ao acaso ou
serem comandados).
Um algoritmo fica caracterizado então como:
Um algoritmo é a descrição de um conjunto de comandos que, se obedecidos,
resultam numa sucessão finita de ações.
Alguns pontos importantes devem ser salientados da definição acima:
(1) Um algoritmo deve ser finito, ou seja, deve executar num tempo limitado e
obrigatoriamente parar após algum tempo.
(2) Como todas as ações tem efeitos previsíveis e bem definidos, diz-se que um algoritmo
que esteja de acordo com a definição acima é determinístico.
(3) Existe uma diferença importante entre o algoritmo e sua execução: um algoritmo é uma
descrição, ou seja, uma espécie de receita que diz que ações teriam que ser feitas para
executar alguma tarefa, porém ele não é a tarefa em si.
Exercícios:
(2.a) Um algoritmo pode conter comandos como “Escreva todos os números primos” ou
“Descubra quantas frases possíveis podem ser escritas na língua portuguesa”? Responda
sim ou não e justifique.
UERGS - Algoritmos e Programação Capítulo 2 - Algoritmos e Linguagem C
19 Copyright  2002,03 João Carlos Gluz
(2.b) Um algoritmo pode conter comandos como “Escolha um número primo qualquer” ou
“Escolha uma palavra qualquer do dicionário”? Responda sim ou não e justifique.
(2.c) Um algoritmo pode ter comandos como “Ache algo que sirva” ou “Calcule o resultado
para mim”? Responda sim ou não e justifique.
(2.d) Um algoritmo pode ter comandos como “Conte quantas vezes a letra ‘p’ aparece nas
palavras do dicionário Aurélio” ou “Descubra todos os primos maiores que 1.000 e
menores que 1.000.000.000”? Responda sim ou não e justifique.
(2.e) Escreva um algoritmo que verifique se um número é par.
(2.f) Escreva um algoritmo que verifique se um número é primo.
(2.g) Escreva um algoritmo que verifique se uma palavra está no plural.
(2.h) Escreva um algoritmo que verifique se uma palavra é um pronome ou não?
(2.i) Escreva um algoritmo que verifique se um triângulo é obtuso, agudo ou reto.
(2.j) Escreva um algoritmo que verifique se um quadrilátero é: um quadrado, um retângulo,
um losango ou nenhum dos três casos anteriores.
2.2. Formas de Descrição de Algoritmos
Um algoritmo é uma descrição de um conjunto de comandos que deve ser feito em algum
formato específico. Existem várias maneiras de se definir um algoritmo:
1. pode-se descrevê-lo como um texto em língua portuguesa;
2. pode-se criar um diagrama gráfico que indique claramente o que deve ser feito;
3. pode-se construir uma fórmula matemática que defina como deve ser calculado
4. etc.
A única condição que esta descrição deve atender é que ela seja perfeitamente
compreendida tanto por quem escreve o algoritmo quanto por quem terá que executá-lo. No
caso genérico de algoritmos feitos para uso por seres humanos todos os esquemas acima (e
outros mais) com diversos graus de detalhamento já foram empregados.
2.3. A Noção de Programa
Entretanto, existe um caso particular de algoritmos que são escritos para serem executados
apenas por computadores. Estes algoritmos são denominados de programas, e a forma
principal de descrição destes programas é através de versões extremamente limitadas,
rígidas e formalizadas de línguas naturais: as linguagens de programação (normalmente
usando subconjuntos da língua inglesa).
UERGS - Algoritmos e Programação Capítulo 2 - Algoritmos e Linguagem C
20 Copyright  2002,03 João Carlos Gluz
Todas as linguagens de programação compartilham de um conjunto básico de conceitos
elementares que dizem:
• Como são definidos os valores constantes no programa (constantes numéricas,
caracteres, textos, valores lógicos, etc.).
• Como se pode criar variáveis para o programa (como elas são identificadas, criadas e
usadas).
• Quais são os tipos de dados básicos ou primitivos da linguagem.
• Como se pode colocar comentários no programa, que esclareçam detalhes de como ele
deveria funcionar.
• Como se pode construir expressões aritméticas e expressões comparativas (relacionais).
• Como se pode construir comandos que manipulem e alterem os dados (variáveis).
Por fim, toda a linguagem de programação deve possuir comandos que permitem controlar
o fluxo de execução do programa.
Além disso as linguagems estruturadas modernas apresentam também ferramentas
(construtores de tipos de dados) que permitem definir novos tipos de dados a partir dos
tipos de dados primitivos ou básicos.
Estes conceitos serão apresentados nas seções e capítulos a seguir. Antes, entretanto,
faremos uma breve apresentação das características gerais da linguagem C.
Exercício:
(2.k) Existe algum empecilho mais sério que um diagrama gráfico possa ser empregado
também para comunicar um algoritmo para um computador, ou seja, poderia se usar
diagramas gráficos para programar computadores. Discuta a questão.
2.4. A Linguagem C
A linguagem C foi criada por Dennis Ritchie, em 1972, no centro de Pesquisas da AT&T
Bell Laboratories, como sucessora da linguagem de programação de sistemas B (por isso o
nome C). Sua primeira utilização importante foi a reescrita do Sistema Operacional UNIX,
que até então havia sido escrito em assembly pelo pesquisador Ken Thompsom, também do
AT&T Bell Labs. Em meados de 1970 o UNIX saiu do laboratório para ser liberado para as
universidades. Foi o suficiente para que o sucesso da linguagem atingisse proporções tais
que, por volta de 1980, já existiam várias versões de compiladores C oferecidas por várias
empresas, não sendo mais restritas apenas ao ambiente UNIX, porém compatíveis com
vários outros sistemas operacionais.
A linguagem C é uma linguagem de propósito geral, sendo adequada à programação
estruturada. Ela pode ser considerada uma linguagem de “nível-médio”, porque, embora
possua todas as características de estruturação de dados e programa em linguagens de alto
nível, ela permite o acesso direto as estruturas de hardware de uma máquina, se isto for
necessário. Ela é principalmente utilizada para escrever sistemas de software básico tais
como o próprio sistema operacional, seus compiladores, analisadores léxicos, gerenciadores
UERGS - Algoritmos e Programação Capítulo 2 - Algoritmos e Linguagem C
21 Copyright  2002,03 João Carlos Gluz
de bancos de dados, drivers de periféricos e dispositivos de estrada e saída, editores de
texto, etc. A principais características características de C são: portabilidade, modularidade,
compilação separada, recursos de baixo nível, geração de código eficiente, confiabilidade,
regularidade, simplicidade e facilidade de uso.
UERGS - Algoritmos e Programação Capítulo 3 - Elementos Básicos de C
22 Copyright  2002,03 João Carlos Gluz
Capítulo 3
Elementos Básicos de C
Este capítulo apresenta os elementos básicos que compõem um programa em C:
• Constantes numéricas, caracteres, textuais e valores lógicos.
• Variáveis
• Tipos de dados básicos (ou primitivos).
• Comentários.
• Expressões aritméticas, relacionais e lógicas
• Expressões (comandos) de atribuição de valor a variável
3.1. Constantes
Uma constante é um determinado valor fixo que não se modificaao longo do tempo,
durante a execução do algoritmo ou programa. As constantes podem ser de diversos tipos,
dependendo se ela for um número inteiro, um número real, um valor lógico (verdadeiro ou
falso), um caracter ou então se for uma sequência (também chamada de cadeia ou string) de
caracteres.
Tabela 1 - Exemplos de Constantes
Inteiro Real Lógicas Caracter String
0 0.0 TRUE ‘a’ “palavra”
-12 -2.23 FALSE ‘B’ “Uma pequena frase.”
0x1b2 2e4 ‘\n’
4.3e-2 ‘\x00’
Exercício:
(3.a) Identificar o tipo de cada uma das constantes abaixo:
0xFACA “TRUE”
“0x12” 3.0
1e3 0x1e3
‘4’
3.2. Variáveis
Na matemática uma variável representa um elemento qualquer de um dado conjunto dentro
de uma fórmula ou expressão matemática.
UERGS - Algoritmos e Programação Capítulo 3 - Elementos Básicos de C
23 Copyright  2002,03 João Carlos Gluz
Na computação, entretanto, uma variável irá corresponder a uma posição de memória que
poderá variar de conteúdo durante a execução do programa. Uma variável pode armazenar
um valor nesta posição de memória. Este valor é o conteúdo da variável. Embora uma
variável possa assumir diferentes valores, ela somente pode assumí-los um de cada vez, ou
seja, ela só pode armazenar um valor de cada vez.
Toda variável deve ter um identificador ou nome que começa com uma letra (A,B,C,...Z
ou a,b,c,...,z) seguido de uma sequência de letras, dígitos ou do caracter especial de
sublinhado (‘_’). Não são aceitos caracteres acentuados. Exemplos: Valor_maximo,
TotalPorAluno, TAXA_DE_CAMBIO.
Exercício:
(3.b) Quais termos abaixo são identificadores válidos:
VALOR SALARIO-LIQUIDO B24S
X2 Nota_do_Aluno A1b3C4
2*4 K/H “NOTA”
XYz NOMEDAEMPRESAQUEVENDEUOPRODUTO M(A)
Importante: na linguagem que usaremos na disciplina faz-se diferença entre letras
maiúsculas e minúsculas no nome das variáveis, sendo assim os seguintes nomes de
variáveis são todos diferentes: ABC, ABc, AbC, Abc, aBC, ABc, abC e abc. Portanto eles
correspondem a variáveis diferentes dentro do programa. Da mesma forma o caracter
sublinha é levado em conta, sendo assim, varíaveis como: Custo_Do_Produto e
CustoDoProduto são diferentes.
3.3. Tipos de Dados Primitivos
Além disso toda variável, da mesma forma que as constantes, também tem que ter um tipo
de dados: inteiro, real, lógico, caracter ou string. Embora não seja obrigatório em todas as
linguagems de programação, geralmente as variáveis tem que ser declaradas antes de ser
usadas. A declaração serve para avisar (ao computador) que uma dada variável com um
dado nome e tipo de dados deve ser criada. Na nossa disciplina estaremos assumindo que
todas as variáveis tem que ser declaradas antes de ser usadas.
As declarações de variáveis são expressões na forma:
<tipo-de-dados> <nome-da-variável> , ... , <nome-da-variável>. ;
Onde <tipo-de-dados> e <nome-da-variável> são termos que podem ser substituidos por
palavras que definem, respectivamente, o tipo de dados da variável e o nome da variável.
Como pode ser visto na definição acima, também pode-se definir mais de uma variável por
vez, bastando separar seus nomes por vírgulas. O caracter ponto-e-vírgula no fim da
declaração é obrigatório.
O termo <tipo-de-dados> pode ser substituído por:
UERGS - Algoritmos e Programação Capítulo 3 - Elementos Básicos de C
24 Copyright  2002,03 João Carlos Gluz
int para indicar que será uma variável de tipo numérico inteiro
float para indicar que será uma variável de tipo numérico real
char para indicar que será uma variável para um caracter
bool para indicar que será uma variável lógica (booleana).
As variáveis string são definidas através do tipo caracter (char), dizendo-se qual o tamanho
do string (ou cadeia) de caracteres. A definição é um pouco diferenta da apresentada acima:
char <nome-da-varável> [<tamanho-do-string>] ;
onde os abre e fecha colchetes são obrigatórios e onde <tamanho-do-string> é uma
constante numérica inteira.
Exemplos:
int nota,codigo,X1;
bool teste,sim;
char c1,c2;
char nome[50], cargo[50], descricao_do_produto[200];
3.4. Comentários
Um comentário, num algoritmo ou programa, é um trecho de texto que serve apenas para
aclarar para um leitor humano, detalhes do que está sendo feito. Os comentários poderão
ser colocados nos programas/algoritmos de duas formas:
/* entre barra-asterisco e asterisco-barra */
ou
// após duas barras e até o fim da linha.
no caso de comentários entre /* e */ eles podem se estender por várias linhas:
/*
Este e’ um comentario
que se estende por
cinco linhas distintas
*/
3.5. Expressões Aritméticas
Denomina-se expressão aritmética aquela cujos operadores são aritméticos e cujos
operandos são constantes e/ou variáveis numéricas. O conjunto básico de operadores é o
tradicionalmente empregado na matemática, apenas que adaptado aos teclados e caracteres
disponíveis nos computadores:
UERGS - Algoritmos e Programação Capítulo 3 - Elementos Básicos de C
25 Copyright  2002,03 João Carlos Gluz
Tabela 2 - Operações Aritméticas Binárias
operação símbolo (caracter)
soma +
subtração -
multiplicação *
divisão /
resto da divisão inteira %
O operador / serve tanto para a divisão de números inteiros quanto reais. O operador %
quando usado entre números inteiros retorna o resto da divisão inteira e quando usado entre
reais retorna apenas o resultado da divisão (igual ao operador /). Exemplos:
A + 12 x - 25 0.23 * 44
12 / 13 17 % 3 2.3 + 8.2 * y
6 + b / 4 - 34
A precedência é a usual da matemática: primeiro são feitas as operações multiplicativas: *,
/ e %, depois são feitas as aditivas: +. -.
Quando várias operações aritméticas de mesmo nível de precedências são postas em
sequência, normalmente se considera que a execução das operações começa da esquerda
para a direita, isto é, a associatividade usual das operações aritméticas é da esquerda para a
direita.
O uso de parênteses é livre, devendo ser utilizados quando se quer forçar uma precedência
ou associtiavidade não usual ou quando se quer deixar a expressão mais clara e legível.
Podem existir expressões entre parênteses aninhadas dentro de outras expressões entre
parênteses. A única restrição é que os parêntese estejam “pareados”, ou seja, que nunca
falte parênteses a esquerda ou a direita. Exemplos:
(2+3) * X Y/(2 * (Z+44 % C)) ((indice+1)/(total*2)) % valor_maximo
Exercícios:
(3.c) Descubrir a ordem em que são feitas as operações nas seguintes expressões:
8 * 23 % 14 + 86 - 23 + 78 / 12
14 * 8 - 4 + 7 * 17
(3.d) Coloque parênteses nas duas expressões da questão (a) para explicitar como é a
precedência e associatividade usual.
(3.e) Coloque parênteses nas duas expressões da questão (a) de forma a forçar que as
operações aditivas sejam feitas antes das multiplicativas.
Além das operações que necessitam de dois operandos (operações binárias), existem
também as operações unárias (com apenas um operando):
UERGS - Algoritmos e Programação Capítulo 3 - Elementos Básicos de C
26 Copyright  2002,03 João Carlos Gluz
Tabela 3 - Operações Aritméticas Unárias
operação símbolo (caracter)
número positivo +
número negativo -
incremento ++
decremento --
Os símbolos - e + podem ser usados apenas na frente de uma constante numérica para
indicar o sinal da constante (se é positiva ou negativa). Dessa forma as expressões abaixo
(como nas fórmulas matemáticas comuns) são perfeitamente corretas:
2 + -4 -3 * +4 -4 * (16 + -2)
Os símbolos ++ e -- são usados para executar operações de, respectivamente, incremento
(somar 1) e decremento (subtrair 1) sobre uma variável. Estes operadores podem ser usados
tanto na frente (pré-fixados) quanto atrás (pós-fixados) de um operando. Exemplos:
3 * ++n 4 + i--
Importante:
• Note que os símbolos + e - somente podem ser usados como sinais de positivo e
negativo se estiverem na frente do número (são operadores unários pré-
fixados).
• Os

Outros materiais