Baixe o app para aproveitar ainda mais
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
Compartilhar