Programação 1 UTFPR

Prévia do material em texto

CONCEITOS E 
DEFINIÇÕES 
FUNDAMENTAIS 
Profa. Simone Aires – Prof. Saulo Queiroz, UTFPR-PG 
1 
Primeiros passos 
 Você já parou para pensar no que há em comum na 
forma como resolvemos problemas do cotidiano 
tais como: 
 Solicitar parada a um ônibus? 
 Dar um troco ao receber uma nota alta? 
 Vamos descrever breves soluções para esses 
problemas? 
2 
Problema: Solicitando parada ao “80” 
1. Leia (e memorize) 
o número do 
próximo ônibus 
2. O número lido é 
igual a 80? 
a) Sim, solicite 
parada 
b) Não, não solicite 
3 
Problema: Troco para cédula “alta” 
1. Leia (e memorize) o 
valor da nota 
2. Subtraia o valor da 
nota pelo valor do preço 
do produto (memorize 
esse valor resultante) 
3. Apresente o troco 
conforme o valor 
resultante 
4 
Para resolver problemas costumamos: 
 Estabelecer uma sequência finita de “pequenas” ações 
 Sequência porque 
 não é qualquer ordem de ações que resolve o problema 
 Finita porque 
 uma solução que requer infinitos passos não nos interessa 
 Pequenas ações (ou mais formalmente, instruções) 
 Fácil execução pelo executor da solução 
 Essas características são a base para a definição de 
“algoritmos” 
5 
Algoritmo: uma primeira definição 
 Uma sequência finita de passos (instruções) 
visando resolver um problema 
 Mas como se define “problema”? 
6 
Problema (Computacional) 
 Enunciado que especifica de forma geral a relação entre uma 
condição inicial (“entrada”) e uma resposta (“saída”) 
 Ex.: Problema de Solicitar Parada ao Ônibus Nº 80 
 Entrada: Número do próximo ônibus 
 Saída: Solicitação/Não solicita 
 Ex.: Problema do troco 
 Entrada: Valor Pago (VP), Preço do Produto (PP) 
 Assumindo VP> PP 
 Saída: Valor do troco 
7 
Algoritmo: Definição Complementar 
 
 
 “Procedimento que produz uma saída correspondente 
a uma entrada” 
Cormen et al. Introduction to Algorithms. 
8 
Algoritmos: Ensino antes da universidade 
 Você consegue identificar algoritmos com (entradas 
e saída) que você aprendeu antes de entrar neste 
curso? 
9 
Algoritmos: Ensino antes da faculdade 
 Você consegue identificar algoritmos com (entradas 
e saída) que você aprendeu antes de entrar neste 
curso? 
Algoritmo/Solução Entrada Saída 
Equação de Bhaskara Equação do 2º grau Raízes da equação dada 
Teorema de pitágoras Catetos de um triângulo retângulo Valor da hipotenusa 
Análise sintática Frase Sujeito, predicado, ... 
 
10 
Algoritmos: Ensino antes da faculdade 
 Você consegue identificar algoritmos com (entradas 
e saída) que você aprendeu antes de entrar neste 
curso? 
Algoritmo/Solução Entrada Saída 
Equação de Bhaskara Equação do 2º grau Raízes da equação dada 
Teorema de pitágoras Catetos de um triângulo retângulo Valor da hipotenusa 
Análise sintática Frase Sujeito, predicado, ... 
 
11 
Algoritmos: Ensino antes da faculdade 
 Você consegue identificar algoritmos com (entradas 
e saída) que você aprendeu antes de entrar neste 
curso? 
Algoritmo/Solução Entrada Saída 
Equação de Bhaskara Equação do 2º grau Raízes da equação dada 
Teorema de pitágoras Catetos de um triângulo retângulo Valor da hipotenusa 
Análise sintática Frase Sujeito, predicado, ... 
 
12 
Algoritmos: Ensino antes da faculdade 
 Você consegue identificar algoritmos com (entradas 
e saída) que você aprendeu antes de entrar neste 
curso? 
Algoritmo/Solução Entrada Saída 
Equação de Bhaskara Equação do 2º grau Raízes da equação dada 
Teorema de pitágoras Catetos de um triângulo retângulo Valor da hipotenusa 
Análise sintática Frase Sujeito, predicado, ... 
 Conclusão? 
13 
Algoritmos: Ensino antes da faculdade 
 Você consegue identificar algoritmos com (entradas 
e saída) que você aprendeu antes de entrar neste 
curso? 
Algoritmo/Solução Entrada Saída 
Equação de Bhaskara Equação do 2º grau Raízes da equação dada 
Teorema de pitágoras Catetos de um triângulo retângulo Valor da hipotenusa 
Análise sintática Frase Sujeito, predicado, ... 
 Conclusão? A noção de algoritmo é tão antiga 
quanto a vontade humana de resolver problemas! 
14 
Computação 
 E onde entram os computadores nessa história? 
15 
Computação 
 Um computador nada mais é que um aparato capaz de executar 
um algoritmo 
 Ele não sabe criar algoritmos. Apenas executa instruções elementares 
sequencialmente tais como leia, apresente, subtraia 
 Em todos os exemplos de algoritmos, quem era o executor do 
algoritmo? 
 O ser humaninho! :D 
 Ao longo de anos, o homem cumpriu o papel do computador 
 Até que ele se deparou com problemas que exigiam algoritmos que 
a paciência humana não suporta executar 
16 
Computação 
 Um computador nada mais é que um mecanismo capaz de 
executar um algoritmo 
 Ele não sabe criar algoritmos. Apenas executa instruções elementares 
sequencialmente tais como leia, apresente, subtraia 
 Em todos os exemplos de algoritmos, quem era o executor do 
algoritmo? 
 O ser humaninho! :D 
 Ao longo de anos, o homem cumpriu o papel do computador 
 Até que ele se deparou com problemas que exigiam algoritmos que 
a paciência humana não suporta executar 
17 
Algoritmo para multiplicar duas matrizes 
18 
Entenderam o algoritmo 
queridos aluninhos? 
Sim! 
Sim! 
Exemplo em Sala de aula: Matrizes 2x2 
Que lindo! 
Sim! 
Nem preciso fazer 
exercícios 
Algoritmo para multiplicar duas matrizes 
19 
Questão de prova: matrizes 7x7 
2 0 9 1 9 4 8 
5 8 1 0 1 9 5 
2 0 9 1 9 4 8 
7 8 1 0 1 9 5 
9 0 9 1 9 4 8 
4 8 1 0 1 9 5 
3 0 9 1 9 4 8 
2 0 9 1 9 4 8 
5 8 1 0 1 9 5 
2 0 9 1 9 4 8 
7 8 1 0 1 9 5 
1 0 9 1 9 4 8 
4 8 1 0 1 9 5 
3 0 9 1 9 4 8 
Torre de Hanoi 
 Mover todos os discos do primeiro para o 
terceiro pino com auxílio do segundo 
 Disco maior não pode sobrepor-se a disco menor 
 Quantos instruções de “mover” são 
aproximadamente necessárias para n discos? 
 2T(n-1) + 1 = Θ(2n) 
 Gerações de tibetanos revesavam-se para 
mover n=64. Eles acreditavam que o mundo 
acabaria ao término do jogo. Porque? 
 264=18446744073709551616 instruçõesde 
mover 
 Movimentando 1 disco por segundo, a 
brincadeira terminaria em 500.000 anos! 
 
20 
Torre de Hanoi 
 Mover todos os discos (um por vez) do primeiro 
para o terceiro pino com auxílio do segundo 
 Disco maior não pode sobrepor-se a disco menor 
 Quantos instruções de “mover” são 
aproximadamente necessárias para n discos? 
 2T(n-1) + 1 = Θ(2n) 
 Gerações de tibetanos revesavam-se para 
mover n=64. Eles acreditavam que o mundo 
acabaria ao término do jogo. Porque? 
 264=18446744073709551616 instruçõesde 
mover 
 Movimentando 1 disco por segundo, a 
brincadeira terminaria em 500.000 anos! 
 
21 
Torre de Hanoi 
 Mover todos os discos (um por vez) do primeiro 
para o terceiro pino com auxílio do segundo 
 Disco maior não pode sobrepor-se a disco menor 
 Quantos instruções de “mover” são 
aproximadamente necessárias para n discos? 
 2T(n-1) + 1 = Θ(2n) (matemática discreta) 
 Diz a lenda que os tibetanos revesavam-se 
para mover n=64. Eles acreditavam que o 
mundo acabaria ao término do jogo. Porque? 
 264=18446744073709551616 instruções tipo 
de mover 
 Movimentando 1 disco por segundo, a 
brincadeira terminaria em 500.000 anos! 
 
22 
Torre de Hanoi 
 Mover todos os discos (um por vez) do primeiro 
para o terceiro pino com auxílio do segundo 
 Disco maior não pode sobrepor-se a disco menor 
 Quantos instruções de “mover” são 
aproximadamente necessárias para n discos? 2T(n-1) + 1 = Θ(2n) (matemática discreta) 
 Diz a lenda que os tibetanos revesavam-se 
para mover n=64. Eles acreditavam que o 
mundo acabaria ao término do jogo. Porque? 
 264=18.446.744.073.709.551.616 instruções 
do tipo “mover” 
 Movimentando 1 disco por segundo, a 
brincadeira terminaria em 500.000 anos! 
 
23 
Outros exemplos 
 Calcular determinante de grandes matrizes 
 Desembaralhar uma grande mensagem pelo sistema de criptografia 
zenit/polar 
 Cálcular trajetória de projéteis 
 Para executar algoritmos de forma rápida, novos computadores 
não-humanos foram sendo propostos pelo homem 
 NOTA: O homem continua sendo o principal responsável pela invenção 
dos algoritmos e projeto de computadores 
 Os computadores só executam algoritmos 
 
24 
Ábaco 
 Origem: Mesopotâmia, 
2700 aC (?) 
 Só trabalha com soma e 
subtração 
 Não consegue computar o 
algoritmo da parada de 
ônibus, por exemplo 
 
25 
Máquina de Turing 
 Poderoso modelo teórico de um computador genérico 
apresentado pelo matemático Alan Turing em 1936 
 Turing também criou aparato mecânico de sua máquina para 
decifrar mensagens dos nazistas durante a 2ª grande guerra 
 Filme: O Jogo da imitação 
 Acredita-se que um algoritmo só pode ser computável se a 
máquina de Turing consegue computá-lo (tese de Church-
Turing) 
 Linguagens formais e autômatos 
26 
 
ENIAC, 1943 
 Electronic Numerical Integrator 
and Computer 
 Execução de 5000 instruções 
por segundo 
 Como os computadores atuais, 
obedece modelo teórico de 
Turing 
 é mais rápido que o aparato 
mecânico de Turing 
27 
Computadores hoje em dia 
 Há muitos outros computadores mecânicos na 
história. Hoje predominam os eletrônicos! 
28 
Relação Algoritmo x Computador 
 O conjunto de instruções que um computador reconhece 
é chamado de linguagem de máquina 
 Em “Arquitetura de computadores” estudamos a linguagem de 
máquina dos computadores modernos 
 Um programa é uma forma de apresentar um 
algoritmo numa dada linguagem de máquina 
 Computadores executam algoritmos por meio de programas 
29 
Tentando relacionar tudo 
Computador 
Criador e 
programador 
do algoritmo 
1. Linguagem 
da Máquina 
3. Execução do 
programa 
Programa 
2. Programação 
30 
Tentando relacionar tudo 
Computador 
Criador e 
programador 
do algoritmo 
1. Linguagem 
da Máquina 
3. Execução do 
programa 
Programa 
2. Programação 
 Programar em linguagem de máquina é tarefa tediosa (o que queríamos 
evitar) 
 Ex.: Programar no ENIAC exigia conhecimentos de níveis de tensão e voltagem pois 
as instruções eram representadas por variáveis da física/eletrônica 
31 
Abstração 
 Técnica para remover a complexidade de um 
objeto de estudo: sistema, cenário, programa 
 Representa o objeto de estudo da forma mais 
simplificada possível porém preservando 
informações relevantes a um dado contexto 
 Diferentes contextos podem requerer diferentes 
níveis de abstração 
32 
Exemplo: Mapa Metro de Lisboa 
 Nível de abstração 
do usuário 
 Contexto: facilitar 
o deslocamento 
entre estações 
É irrelevante saber 
se há curvas 
entre “Odivelas” e 
“Ameixoeira”! 
33 
Exemplo: Mapa Metro de Lisboa 
 Nível de abstração 
do usuário 
Contexto: facilitar o 
deslocamento 
entre estações 
É irrelevante saber 
se há curvas 
entre “Odivelas” e 
“Ameixoeira”! 
 É irrelevante 
saber se há 
curvas entre 
“Odivelas” e 
“Ameixoeira”! 
34 
 Nível de 
abstração do 
engenheiro 
 Contexto: 
facilitar o 
projeto de 
expansão da 
malha! 
Exemplo: Mapa Metro de Lisboa 
35 
Linguagens de programação 
 Apresentam ao programador instruções mais parecidas com o 
vocabulário humano 
 Escondem (abstraem) a complexidade da linguagem de máquina. Por 
isso são chamadas de linguagem de “alto-nível” 
 Um compilador é um programa especial que faz a tradução entre 
linguagem de alto nível e linguagem de máquina 
 Em “compiladores” aprenderemos a construir um compilador 
 Um algoritmo pode ser visto em diferentes níveis de abstração 
 Considere um algoritmo para adicionar um amigo no Facebook 
36 
Exemplo: Adicionar amigo no Facebook 
 Como aceitar um amigo no 
Facebook? 
 Algoritmo para o nível de 
abstração do usuário 
37 
Exemplo: Adicionar amigo no Facebook 
 Como aceitar um amigo no 
Facebook? 
 Exemplo de solução para o nível de 
abstração do analista de banco de 
dados 
 Aprenderemos isso nas disciplinas de 
banco de dados 
Ami-
za-
de 
Usuário 
Nome Email Aniversário Sexo Senha 
Data 
38 
Exemplo: Adicionar amigo no Facebook 
 Como aceitar um amigo no 
Facebook? 
 Exemplo de solução para o nível 
de abstração do programador 
do sistema gerenciador de 
banco de dados 
 Aprenderemos nas disciplinas de 
algoritmos e estruturas de dados 
typedef struct TUsuario 
{ 
 char nome[500], email[50], 
senha[50]; 
 int dia, mes, ano; //data 
 char sexo; 
} TUsuario; 
typedef struct TAmizade 
{ 
 char nome[500], email[50], 
senha[50]; 
 int dia, mes, ano; //data 
} TAmizade; void main(){ ... } 
39 
Exemplo: Adicionar amigo no Facebook 
 Como aceitar um amigo no 
Facebook? 
 Trecho de solução para o 
nível de abstração do 
programador de baixo nível 
(linguagem de montagem) 
.LFB0: 
 .cfi_startproc 
 pushl %ebp 
 .cfi_def_cfa_offset 8 
 .cfi_offset 5, -8 
 movl %esp, %ebp 
 .cfi_def_cfa_register 5 
 nop 
 popl %ebp 
 .cfi_restore 5 
 .cfi_def_cfa 4, 4 
 ret 
 .cfi_endproc 
40 
Exemplo: Adicionar amigo no Facebook 
 Como aceitar um amigo no 
Facebook? 
 Trecho de solução para o 
nível de abstração do 
programador de baixo nível 
(linguagem de montagem) 
.LFB0: 
 .cfi_startproc 
 pushl %ebp 
 .cfi_def_cfa_offset 8 
 .cfi_offset 5, -8 
 movl %esp, %ebp 
 .cfi_def_cfa_register 5 
 nop 
 popl %ebp 
 .cfi_restore 5 
 .cfi_def_cfa 4, 4 
 ret 
 .cfi_endproc 
41 
Linguagem de Programação próxima aos códigos binários, 
de forma que um processador conseguiria decodificar 
imediatamente sem recorrer a um compilador. 
Exemplo: Adicionar amigo no Facebook 
 Como aceitar um amigo no 
Facebook? 
 Exemplo de solução para o 
nível de abstração do 
projetista de 
processador/arquitetura de 
computadores (linguagem 
de máquina) 
42 
Exemplo: Adicionar amigo no Facebook 
 Como aceitar um amigo no 
Facebook? 
 Exemplo de solução para o 
nível de abstração do 
programador de 
drivers/engenheiro de 
hardware (placa WiFi) 
 Solução para enviar o 
pedido de amizade via Wi-
Fi: Modulação QAM 
43 
O código-fonte 
Linguagem de 
Programação 
Criador e 
programador 
do algoritmo 
1. Instruções de 
alto-nível 
5. Execução do 
programa 
Código-Fonte 
2. Programação 
44 
Compilador 
Programa 
(Linguagem de 
Máquina) 
3. Compilação 
(Entrada) 
4. Compilação 
(Saída) 
Computador 
Síntese 
 Ser humano cria algoritmos e computadores (cientista da computação) 
 Um ser humano pode exercer papel de computador 
 Podemos criar algoritmos sem ter em mente o computador que o executará 
 Para executar nosso algoritmo em um dado computador, precisamos 
programá-lo na linguagem de máquina do computador 
 Linguagem de máquina é algo muito complexo, exige muito tempo e 
atenção 
 Linguagens de programação têm comandos mais próximos do vocabulário 
humano 
 Compiladores traduzem o código-fonte feitoem uma linguagem de 
programação para um programa em linguagem de máquina 
45 
Conceitos-chave 
 Algoritmo 
 Problema 
 Computador; Computar; Computação 
 Ciência da Computação 
 Abstração 
 Linguagem de Máquina 
 Linguagem de Programação 
 Programa e Código Fonte 
 Compilador 
46 
O que é ciência da computação? 
 "Ciência da computação tem tanto a ver com o 
computador como a Astronomia com o telescópio, a 
Biologia com o microscópio, ou a Química com os 
tubos de ensaio. A Ciência não estuda ferramentas, 
mas o que fazemos e o que descobrimos com elas.“ 
Edsger Dijkstra 
47