Upload
phamnga
View
225
Download
0
Embed Size (px)
Citation preview
Informática Aplicada à Engenharia Florestal
Renato Dourado MaiaInstituto de Ciências Agrárias
Universidade Federal de Minas Gerais
INTRODUÇÃO AOS ALGORITMOS E À PROGRAMAÇÃO DE COMPUTADORES – PARTE 1
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 2/42
Programas e Programação
• Quando vocês utilizam um computador, sempre executam um programa.
• Para que um computador “faça algo”, ele precisa de ins-truções precisas.– Os humanos (apenas os humanos?) escrevem e utilizam progra-
mas para dizer ao computador exatamente o que fazer.• Algumas pessoas dizem que a programação, no futuro, se-
rá tão importante quanto ler e escrever!
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 3/42
Programas e Programação
The great thing about computers is that they do exactly what you tell them. The terrible thing about computers is that they do exactly what you tell them.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 4/42
Programas e Programação
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 5/42
Programas e Programação
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 6/42
Programas e Programação
• Programar é basicamente construir programas, que são formulações concretas de algoritmos abstratos, baseados em representações e estruturas específicas de dados.
• A programação estruturada é a arte ou técnica de cons-truir e formular algoritmos de forma sistemática.
Algoritmos, programas, estruturas de dados?
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 7/42
O que é um Programa?
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 8/42
Programa
Um programa é uma sequência de instruções para o computador, escrita em uma linguagem de progra-
mação, que é normalmente similar à língua inglesa, porém muito mais simples e muito mais rigorosa.
”Programming demands significantly higher standard of accuracy.Things don’t simply have to make sense to another human being, they must make sense to a computer.” – Donald Knuth
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 9/42
Programas e Estruturas de Dados
• As estruturas de dados podem ser entendidas como mé-todo ou meio para organizar os dados de uma forma que o seu acesso e a sua modificação sejam facilitados.
• Programa = algoritmo(s) + estruturas de dados, utili-zando-se uma forma de expressão que possa ser entendi-da por um computador.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 10/42
Algoritmo
• O conceito central da programação e da computação é o de algoritmo.
• A palavra algoritmo vem de algoritmi, forma latina do nome do matemático iraniano Abu Abdullah Mohammad Ibn Musa al-Khawarizmi, que viveu no século XVII.
• O termo algoritmo é utilizado em diversas áreas além da computação, tais como administração, engenharia, dentre outras.
• Um algoritmo é, essencialmente, um método para a reso-lução de um problema.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 11/42
Algoritmo
• Há diferentes definições para o que é um algoritmo:– Algoritmo é uma sequência de passos que visa atingir um objeti-
vo bem definido.– Algoritmo é a descrição de uma sequência de passos que deve
ser seguida para a realização de uma tarefa.– Algoritmo é uma sequência finita de instruções ou operações cu-
ja execução, em tempo finito, resolve um problema computaci-onal, qualquer que seja a sua instância.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 12/42
Algoritmo
• Há diferentes definições para o que é um algoritmo:– Algoritmo são regras formais para a obtenção de um resultado
ou da solução de um problema, englobando formas de expres-sões aritméticas.
– Ação é um acontecimento que, a partir de um estado inicial, a-pós um período de tempo finito, produz um estado final previsí-vel e bem definido. Portanto, um algoritmo é a descrição de um conjunto de comandos que, obedecidos, resultam numa suces-são finita de ações.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 13/42
Exemplos de Algoritmos?
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 14/42
Programas
• Programas tipicamente processam dados de entrada e produzem dados de saída.
ProgramaEntrada Saída
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 15/42
Linguagens de Programação
• Uma linguagem de programação é uma linguagem artifici-al com sintaxe e semântica bem definidas que é utilizada para escrever programas.– É mais “técnica” do que as linguagens naturais e menos “técni-
ca” do que a linguagem nativa dos computadores (linguagem de máquina).
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 16/42
Linguagens de Programação
• As linguagens de programação semelhantes à linguagem de máquina são conhecidas como linguagens de baixo ní-vel.
• Escrever programas na linguagem de máquina é uma tare-fa pouco intuitiva e complicada para ser realizada por se-res humanos.
• Para facilitar a programação de computadores, existem linguagens de alto nível que relacionam a linguagem de máquina a uma linguagem de compreensão mais simples.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 17/42
Linguagens de Programação
• A linguagem de montagem (assembly) é um código com instruções alfanuméricas (ou mnemônicas) equivalentes a cada instrução da linguagem de máquina.
• A tradução de um programa escrito em linguagem assem-bly é realizada por meio da utilização de um programa cha-mado assembler (ou montador).
Código em linguagem de
montagemAssembler
Código em linguagem de
máquina
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 18/42
Linguagens de Programação
• A linguagem de montagem é uma linguagem de baixo ní-vel, específica para cada processador (cada um tem o seu repertório de instruções), o que faz com que o código não seja portável.
• A implementação de programas em linguagem de monta-gem é uma tarefa complexa e exige conhecimentos sobre o processador.
• As linguagens de alto nível são independentes do proces-sador, são mais elaboradas e contemplam operações mais complexas e mais próximas da “lógica humana”.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 19/42
Linguagens de Programação
• Para serem executados por um processador, os comandos de linguagem de alto nível precisam ser traduzidos para a linguagem de máquina.
• Essa tradução pode ser feita por um programa compilador ou por um programa interpretador.– A partir de um arquivo com o código em linguagem de alto nível –
o código-fonte, o compilador gera um arquivo contendo o código em linguagem de máquina – o código-objeto, que será utilizado para a geração de um arquivo executável por um link-editor.
– O interpretador realiza a mesma tarefa, mas a execução não en-volve a geração de um arquivo executável: ele traduz as instruções em linguagem de montagem em tempo de execução.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 20/42
Compiladores
• Compiladores são programas que traduzem programas es-critos em linguagem de programação para programas e-quivalentes escritos em linguagem de máquina.
CompiladorPrograma-Fonte
Programa-Objeto
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 21/42
Link-Editores
• O programa-objeto nem sempre está pronto para ser exe-cutado.– Pode ser necessário incluir outros trechos de código:
✔ Bibliotecas.✔ Subprogramas.
● O programa executável é montado por um programa cha-mado link-editor ou linking-loader.– O compilador normalmente chama o link-editor automaticamen-
te.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 22/42
Link-Editor
Programa-Objeto 1
Programa-Objeto N
.
.
.
Biblioteca Biblioteca
ProgramaExecutável
Link-Editores
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 23/42
Interpretadores
• Os interpretadores simulam uma “máquina virtual”.– O programa-fonte é lido, entendido e as instruções são executa-
das imediatamente.
InterpretadorEntrada Saída
Programa-Fonte
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 24/42
Compiladores e Interpretadores
Código em linguagem de
alto nívelCompilador
Código em linguagem de
máquina
Código em linguagem de
alto nívelInterpretador
Código em linguagem de
máquina
Tradução de cada instrução em tem-
po de execução
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 25/42
Esquemas Híbridos
• O compilador gera código para uma máquina virtual (códi-go pseudo-executável).
• A máquina virtual é executada separadamente, lendo o pseudo-código e interpretando-o.
Interpretador
Entrada
Saída
Programa-Fonte
Compilador Programa-Objeto
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 26/42
Programas de Computador
• A programação utilizando linguagens de alto nível é mais simples, facilitando a implementação de programas mais elaborados e capazes de atenderem a demandas mais complexas.
• Os códigos escritos em linguagens de alto nível são portá-veis, ou seja, independentes da plataforma, desde que seja realizada uma nova compilação do código-fonte.
• Existem diversas linguagens de alto nível:– Pascal, C, Java, Python...
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 27/42
Programas de Computador
• A realização de algumas operações em linguagem de máquina é bastante complexa.
• Para facilitar essas operações, foram criados os sistemas operacionais.
• Um sistema operacional representa uma camada entre o hardware e o software (máquina virtual).– A máquina virtual é mais simples de ser utilizada do que a má-
quina real. – Os sistemas operacionais gerenciam os recursos da máquina, e-
vitando que o programador os utilize de forma indevida.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 28/42
Programas de Computador
• Os sistemas operacionais fornecem uma interface (chama-das ao sistema) que pode ser utilizada pelos programas.
• Os compiladores utilizam essa interface em lugar de im-plementarem operações complexas.
• Chamadas ao sistema encontradas pelo compilador no código-fonte em linguagem de alto nível são transforma-das em referências no código-objeto em linguagem de máquina.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 29/42
Programas de Computador
• Numa segunda etapa da compilação, o compilador liga o código do programa ao código do sistema operacional (li-gação de código ou linking).
• A integração de compiladores e sistemas operacionais tor-na o código-objeto portável para qualquer máquina que utilize o mesmo sistema operacional: – O código fica dependente do sistema operacional, e não do pro-
cessador!
• Para executar um mesmo programa em outro sistema o-peracional, o código-fonte deve ser compilado novamen-te.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 30/42
Programas de Computador
Código em linguagem de
alto nível
CompiladorEtapa I
Código em linguagem de
máquina
CompiladorEtapa II
Código-objetoexecutávelMemória
Biblioteca dosistema
operacional
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 31/42
Estruturação de Algoritmos
• As linguagens de programação de alto nível são mais sim-ples do que a linguagem de máquina, mas ainda assim po-dem parecer complexas, especialmente para iniciantes.
• O principal problema reside no fato de que as pessoas não estão acostumadas a construir algoritmos, ou seja, a ex-pressar o raciocínio de forma organizada, padronizada e estruturada.
• É importante destacar que, diferentemente da linguagem natural, as linguagens de programação são dirigidas a u-ma máquina, e não a pessoas.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 32/42
Estruturação de Algoritmos
• Máquinas não podem tomar decisões com base em pre-missas, não podem escolher alternativas, não podem cor-rigir comandos mal redigidos, etc.
• As pessoas são capazes de fazer isso instintiva e intuitiva-mente.
• Assim, a linguagem de programação deve possuir algumas características que não são inerentes à linguagem natural, que não é apropriada para a escrita de algoritmos:– Rigidez sintática: as construções devem ser bem definidas.– Rigidez semântica: não podem existir ambiguidades.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 33/42
Linguagens de Programação
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 34/42
Estruturação de Algoritmos – Fluxogramas
• Fluxogramas representam algoritmos de forma gráfica, sendo formados por “caixas” que contêm as instruções a serem executadas.
• As “caixas” são ligadas por setas que indicam o fluxo das ações.
• Algumas “caixas” especializadas indicam a possibilidade de o fluxo seguir caminhos distintos, dependendo de certas situações/condições que podem ocorrer durante a execu-ção do algoritmo.
• Há representações para o início e o fim do algoritmo.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 35/42
Estruturação de Algoritmos – Fluxogramas
• Fluxograma para escolher o maior entre dois números in-teiros distintos:
Início
Fim
leia Num1, Num2
Num1 > Num2
escreva Maior
Maior ← Num1 Maior ← Num2
S N
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 36/42
Estruturação de Algoritmos – Fluxogramas
• Vantagens da representação por fluxogramas:– É útil para a apresentação de algoritmos considerando um alto
nível de abstração.– Facilita a compreensão do funcionamento do algoritmo, mesmo
para leigos.– As pessoas se adaptam bem ao desenvolvimento de algoritmos
utilizando essa representação.
• Desvantagens da representação por fluxogramas:– É pouco prática, especialmente para a correção de erros.– Torna a construção de algoritmos complexos trabalhosa.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 37/42
Estruturação de Algoritmos – Pseudocódigo
• O pseudocódigo é uma forma de representação de algorit-mos que tenta eliminar as desvantagens da implementação direta em linguagem de programação.
• Utilizando essa representação é possível elaborar um código menos dependente das peculiaridades das linguagens de programação e dos compiladores.
• O grau de rigidez sintática é intermediário entre as lingua-gens natural e de programação.
• O pseudocódigo deve manter a rigidez semântica, funcio-nando como uma linguagem intermediária entre a lingua-gem natural e a linguagem de programação.
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 38/42
• Após a elaboração do algoritmo em pseudocódigo, é ne-cessária a sua conversão para uma linguagem de progra-mação para que ele possa ser compilado e executado, ou interpretado.
• O pseudocódigo é independente do compilador e pode ser traduzido de uma forma quase direta para diversas lingua-gens de programação.
• No Brasil, o pseudocódigo mais conhecido é o Portugol.• O Portugol é bastante simples e atende às necessidades de
rigidez sintática e semântica.
Estruturação de Algoritmos – Pseudocódigo
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 39/42
Lembrando: Por que Python?
Quem quer tentar resumir?
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 40/42
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 41/42
Finalizando
• Programa em Python para escolher o maior entre dois nú-meros inteiros distintos:
Num1 = int(raw_input('Primeiro:'))
Num2 = int(raw_input('Segundo:'))
if Num1 > Num2:
Maior = Num1
else:
Maior = Num2
print(Maior)
Vamos testar esse programa no Idle...
10/04/14 Informática Aplicada à Engenharia Florestal – Renato Dourado Maia 42/42
That's All Folks!