Curso completo de algorítimos

Prévia do material em texto

Introdução
Alison Zille Lopes
Aula 0
Conceitos Iniciais
2
HardwareSoftware
A presença dos programas
3
Entrada e Saída
Dispositivos de entrada Dispositivos de saída
4
Arquitetura Básica
5
Introdução
• Lentos
• Pouco confiáveis
Década de 40 e início da década de 50
• Caros
•Memória pequena
• Difícil programação
ENIAC (Electronic Numerical Integrator Analyzer and Computer)
Contituído por 17.468 válvulas 
Programado por 6000 chaves manuais
6
Introdução
Complexidade Complexidade
Custo
Custo
7
Introdução
Hardware
Linguagem de máquina
Programação
Programação e leitura difíceis
Linguagens de nível mais elevado 
Solução?
8
Introdução
• Linguagem: Qualquer meio que sirva para 
exprimir sensações ou idéias.
Linguagens 
de 
Programação
9
Linguagem de Programação
Linguagens de alto nível
Linguagem de máquina
10
Linguagem de Programação
• Algoritmo: conjunto finito de instruções, 
numa determinada seqüência, que quando é 
executado leva à solução de um problema.
• Em geral, algoritmos trabalham sobre 
Estruturas de Dados
– Conjunto de dados que representa uma situação 
real
– Abstração da realidade
11
Tradução
• Um programa é uma formulação concreta de 
um algoritmo abstrato, baseado em 
representações de dados específicas
Linguagem de 
Programação
Algoritmo Tradução
Linguagem de 
Máquina
12
Tradução
• Compilação: A tradução ocorre pela conversão em 
linguagem de máquina, que pode ser executada no 
computador.
• Interpretação: Um programa chamado interpretador 
é responsável pela tradução e execução, mas sem a 
conversão.
• Sistema de implementação Híbrido: 
Compilação/Interpretação
13
Compilação
Código fonte
Analisador 
léxico
Analisador 
sintático
Otimização (opcional)
sintático
Gerador de 
código 
intermediário
Gerador de 
código
Computador
Tabela de 
símbolos
Resultados
Dados de entrada
14
Interpretação
Código fonte
Interpretador
Dados de entrada
Computador
Resultados
15
Sistema de Implementação Híbrido
Código fonte
Analisador 
léxico
Analisador 
sintático
Otimização (opcional)
sintático
Gerador de 
código 
intermediário
Tabela de 
símbolos
Resultados
Dados de entrada
Computador
Interpretador
16
Pseudocódigo
• Assemblers e linguagens de montagem
– Short code: interpretada, codificação de difícil 
compreensão, utilizado no UNIVAC I, códigos de 
12 bits em palavras de 72 bits.12 bits em palavras de 72 bits.
– Speed coding: interpretada, incluía pseudo-
instruções para as 4 operações aritméticas, além 
de raiz, seno, arco-tangente, exponenciação e 
logaritmo.
– Assembly: mnemônicos representavam instruções 
de máquina, uso de assemblers.
17
Linguagens imperativas
• As primeiras linguagens de programação 
surgiram no final da década de 50 e 60 para 
facilitar o trabalho de programação
• Por conta da cultura de programação e 
limitações dos recursos computacionais à 
época, as linguagens foram fortemente 
influenciadas pela linguagem de máquina e 
pela arquitetura dos computadores.
18
Linguagens imperativas
• FORTRAN (1957):
– Primeira linguagem imperativa
– Desenvolvida inicialmente para o IBM 704
– Enfatizava a eficiência Computacional– Enfatizava a eficiência Computacional
– Não enfocava eficiência do programador (uso da 
estrutura de controle GOTO)
– Sua ultima versão FORTRAN 90, incorpora avanços 
de outras LPs
19
Linguagens imperativas
• COBOL (1960)
– Primeira linguagem encomendada pelo 
Departamento de defesa americano
– Destinada a aplicações comerciais (muitos dados e – Destinada a aplicações comerciais (muitos dados e 
pouca computação)
– Tentou enfatizar a legibilidade e acabou 
comprometendo a redigibilidade
20
Linguagens imperativas
• ALGOL (1960)
– Criada por um comitê especialista
– Grande importância teórica
– Influenciou fortemente as linguagens imperativas – Influenciou fortemente as linguagens imperativas 
subsequentes
– Não foi uma linguagem muito utilizada
21
Linguagens imperativas
(Instruções + Dados)
Memória
Arquitetura de Von Neumann
Unidade lógica e 
aritmética
Unidade de 
controle
CPU
Entrada e Saída
22
Linguagens imperativas
• Variáveis modelam as posições de memória
• Instruções de atribuição são baseadas na 
operação de canalizaçãooperação de canalização
• Forma iterativa de repetição, sendo o método 
mais eficiente na arquitetura de Von 
Neumann
23
Variáveis
• Variáveis são abstrações de posições de 
memória. Podem armazenar tipos de dados 
tais como inteiro, real, caractere...
• Variáveis, em linguagens de programação, são 
representadas por nomes chamados 
identificadores.
24
Atribuição
• Considerando, por exemplo, as variáveis 
inteiras nomeadas como soma e parcela:
– soma = soma + parcela;
– soma e parcela são canalizados da memória para a – soma e parcela são canalizados da memória para a 
CPU
– Então, o resultado é canalizado para a memória 
(posição ocupada pela variável soma)
soma e 
parcela
CPU soma
25
Iteração
Memória
Programa
26
Linguagens imperativas
• O uso indiscriminado do comando de controle 
GOTO trouxe sérios problemas a legibilidade 
dos códigos fonte.
• No final dos anos 60, as LPs passaram a 
enfocar a eficiência na produtividade dos 
programadores.
27
Linguagens imperativas
• Surgimento da programação estruturada.
• Linguagens que surgiram nessa época:
– Pacal (1971): projetada para o ensino de – Pacal (1971): projetada para o ensino de 
programação estruturada.
– C (1972): projetada para ser utilizada no 
desenvolvimento de sistemas de programação 
(em particular o sistema operacional UNIX)
28
Programação estruturada
• A programação estruturada preconiza que 
todos os programas possíveis podem ser 
reduzidos a apenas três estruturas:
– Sequência: execução sequencial de instruções
– Seleção: escolha efetuada de acordo com a 
avaliação de um dada condição
– Repetição: repetição de instruções até a 
ocorrência de um determinado evento
29
Programação estruturada
• A programação estruturada orienta os 
programadores para a criação de estruturas 
simples em seus programas, através do uso de 
sub-rotinas.sub-rotinas.
• Sub-rotinas são conjuntos de instruções com 
função bem definida. Muitas vezes 
mencionadas como sub-programas.
30
Programação estruturada
• As subrotinas podem ser de dois tipos:
– Procedimentos: não retornam valor.
• Ex: Exibir um valor na tela, mover cursor, ...• Ex: Exibir um valor na tela, mover cursor, ...
– Funções: retornam valor.
• Ex: somar, enviar uma carta com aviso de recebimento.
31