72285-511284Aula1_-_IntroducIaIo-2

Prévia do material em texto

1
Programação para Engenharia
Prof. Armando Cardoso Ribas
2
Tópico 1 – Introdução aos sistemas computacionais
Algoritmos
3
Conteúdo
Algoritmos
Tópico 1
Introdução a Computação; 
História e evolução; 
Noções de arquitetura de computadores.
4
Objetivos
Algoritmos
Tópico 1
Introduzir os conceitos da computação;
Conhecer a história e evolução dos computadores; 
Ter noções de arquitetura de computadores;
Conhecer os passos para resolver problemas;
Entender como algoritmos descrevem a solução de problemas.
5
Algoritmos
Informalmente, um algoritmo é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores de saída.
Portanto, um algoritmo é uma sequência de passos computacionais que transforma a entrada na saída.
Cormen, Thomas H., et al. "Algoritmos: teoria e prática." 
Editora Campus, 2012.
6
>>
Tópico 1 – Introdução
Primeiro Computador ENIAC
Em 1943 durante a II guerra mundial foi desenvolvido o ENIAC, que pesava 30 toneladas e tinha 5,5 metros de altura, 25 metros de comprimento , 70 mil resistores e 17.468 válvulas de vácuo. Ao custo de US$ 500 mil.
 Electronic Numerical Integrator And Computer (Computador e Integrador Numérico Eletrônico)
7
Desenvolvido a pedido do exército dos EUA para seu laboratório de pesquisa balística, o ENIAC era um monstrengo de 30 toneladas de peso que ocupava uma área de 180 m² de área construída. Sua produção custou nada menos do que US$ 500 mil na época, o que hoje representaria aproximadamente US$ 6 milhões e a máquina contava com um hardware com 70 mil resístores e 18 mil válvulas de vácuo que em funcionamento consumiam vorazmente 200 mil watts de energia. Já seu “sistema operacional” eram cartões perfurados que eram operados por um time de funcionárias do exército – o que de quebra as classifica como as primeiras programadoras que se tem notícia. Sua construção de iniciou em plena guerra, em 1943, e apesar de ser mostrado em 46 só foi ser ligado pela primeira vez em julho de 47.
Apesar de ter uma capacidade de operação menor do que qualquer calculadora de mão moderna, durante seus 10 anos de operação o ENIAC “realizou mais contas do que toda humanidade já havia feito em sua história”. 
No final de sua carreira, um concorrente com o dobro da capacidade custava o equivalente a US$ 200 mil e tinha apenas 10% de seu tamanho.
Tópico 1 – Introdução
Primeiro Computador ENIAC
8
O "pai" da computação,
Artigo publicado em 1936, teorizou que uma máquina muito simples seria capaz de resolver qualquer problema matemático, desde que ele pudesse ser representado sob a forma de um algoritmo.
O trabalho de Turing foi publicado no artigo “On Computable Numbers, with an Application to the Entscheidungsproblem”, submetido em maio de 1936. 
O Entscheidungsproblem (termo alemão para "problema de decisão") é um problema da lógica simbólica que consiste em achar um algoritmo genérico para determinar se um dado enunciado da lógica de primeira ordem pode ser provado
Tópico 1 – Introdução
Alan Turing
9
Já assistiram o filme o Jogo da Imitação?
http://www.dcc.ufrj.br/~luisms/turing/
https://youtu.be/1VaZLn3_ADQ
Tópico 1 – Introdução
Porque Aprender a Programar
10
A arquitetura é frequentemente definida como o conjunto de atributos da máquina que um programador deve compreender para que consiga programar o computador específico com sucesso, ou seja, para que consiga compreender o que o programa irá fazer quando da sua execução.
Tópico 1 – Introdução
Arquitetura de um Computador
11
Trata do comportamento funcional de um sistema computacional, do ponto de vista do programador
Tópico 1 – Introdução
Arquitetura de um Computador
A diferença entre a arquitetura de Von Neumann e a Harvard é que a última separa o armazenamento e o comportamento das instruções do CPU e os dados, enquanto a anterior utiliza o mesmo espaço de memória para ambos.
12
A arquitetura de Von Neumann é composta por: Memória; CPU, que contém os registradores, Unidade aritmética e lógica, e Unidade de Controle (CU); E ainda os dispositivos de entrada e saída para comunicação com o meio externo.
Tópico 1 – Introdução
Arquitetura de um Computador
CISC = Complex Instruction Set Computer ou Computador com um Conjunto Complexo de Instruções
RISC = Reduced Instruction Set Computer ou Computador com um Conjunto Reduzido de Instruções
13
https://www.ime.usp.br/~adao/COMPUTADORESRISC2018.pdf
https://www.gruponetcampos.com.br/2011/03/17/arquitetura-cisc-e-risc-qual-diferenca/
Os circuitos que executam operações sobre dados são isolados em uma região chamada Unidade Central de Processamento UCP (CPU – Central Processing Unit), ou processador.
Os dados que estão armazenados na memória principal e são transferidos através de barramentos que interligam estes componentes.
A comunicação com o mundo externo, os usuários, se dá pelos dispositivos de Entrada e Saída (E/S). A comunicação entre o computador e estes dispositivos se dá através dos controladores de cada dispositivo de E/S. 
Tópico 1 – Introdução
Arquitetura de um Computador
14
Em computadores comuns, estes controladores correspondem placas de circuito encaixadas na placa principal do computador (placa mãe). 
Tópico 1 – Introdução
Arquitetura de um Computador
15
É composta por duas partes principais: a unidade lógica e aritmética (ULA), formada por circuitos que manipulam os dados através de operações binárias (dois operandos) e unárias (um operando). 
E a unidade de controle, cujos circuitos são responsáveis por coordenar as operações da UCP.
Tópico 1 – Introdução
Arquitetura de um Computador
16
Exemplos incluem a soma e operadores lógicos: and, or e not. 
http://producao.virtual.ufpb.br/books/camyle/introducao-a-computacao-livro/livro/livro.chunked/ch04s01.html
Tópico 1 – Introdução
Arquitetura de um Computador
17
Como resolver um problema?
Que abordagem para resolver o problema?
Que sequência lógica usar? Existe uma?
Por onde começar?
Tópico 1 – Introdução
Problema
18
Tópico 1 – Introdução
Elaboração de um Programa
19
Análise do problema:
–Ler atentamente o enunciado do problema até entendê-lo bem
–Identificar os dados de entrada
–O que o programa deve fazer (seu objetivo), isto é, como transformar as entradas em saídas(processamento)
–Identificar as saídas(resultados esperados)
–Identificar se existem valores ou dados intermediários, necessários para transformar entradas em saídas
Tópico 1 – Introdução
Processo de Geração de um Programa
20
Tópico 1 – Introdução
Processo de Geração de um Programa
Entrada
Processamento
Saída
21
A lógica é usada para guiar nossos pensamentos ou ações na busca da solução:
A lógica está correta se conseguirmos atingir o nosso objetivo;
É a habilidade fundamental para se resolver problemas de programação de computadores.
Temos que aprender a pensar de forma estruturada:
Desenvolver e aperfeiçoar a técnica de pensamento;
Seguir um raciocínio lógico e matemático.
Tópico 1 – Introdução
Lógica
22
A lógica trata da correção do pensamento;
Ensina-nos a usar corretamente as leis do pensamento:
É a arte de pensar corretamente;
A forma mais complexa do pensamento é o raciocínio;
Ordem da razão (nossa razão pode funcionar desordenadamente) ou ordem no pensamento.
Tópico 1 – Introdução
O que é Lógica
23
Exemplo:
 Todo mamífero é animal.
 Todo cavalo é mamífero.
 Portanto, todo cavalo é animal.
Brasil é país do planeta Terra.
Todos os Brasileiros são do Brasil.
Portanto, todos os Brasileiros são terráqueos.
Tópico 1 – Introdução
Noções de Lógica
24
Sempre que pensamos.
Quando falamos, pois a palavra falada é a representação do pensamento.
Quando escrevemos, pois a palavra escrita é a representação da palavra falada ou mesmo do nosso pensamento.
Daí a importância da lógica em nossa vida, pois quando pensamos, escrevemos ou falamos corretamente precisamos colocar Ordem no Pensamento.
Tópico 1 – Introdução
Existe Lógica no Diaa Dia
25
Lógica de Programação é a técnica de encadear pensamentos para atingir determinado objetivo. 
Necessária para desenvolver programas e sistemas, pois permite definir a sequência lógica para a solução de um problema
Tópico 1 – Introdução
Lógica de Programação
26
>>
A lógica de programação é necessária para pessoas que desejam trabalhar com desenvolvimento de sistemas e programas. Ela permite definir a sequência lógica para o desenvolvimento.
Exercício 1
Um homem precisa atravessar um rio com um barco que possui capacidade de transportar apenas ele mesmo e mais uma de suas três cargas, que são: um lobo, um bode e uma caixa de alfafa. Indique as ações necessárias para que o homem consiga atravessar o rio sem perder suas cargas.
 O lobo não pode ficar sozinho com o bode, senão ele o come;
 O bode não pode ficar sozinho com a alfafa, senão a come.
Tópico 1 – Introdução
O Lobo o Bode e a Alfafa
27
informações:
 um barco
 um homem
 um lobo
 um bode
 um maço de alfafa
ação
 atravessar o rio sem perder as cargas
resultado
 todas as cargas na outra margem do rio.
Tópico 1 – Introdução
O Lobo o Bode e a Alfafa
Algoritmo:
 início
 atravessar homem e bode
 voltar homem
 atravessar homem e lobo
 voltar homem e bode
 atravessar homem e alfafa
 voltar homem
 atravessar homem e bode
 fim
28
Exercício 2
No problema dos canibais e missionários, três missionários e três canibais devem atravessar um rio com um barco que pode transportar no máximo duas pessoas, sob a restrição de que, para ambas as margens, se há missionários presentes naquela margem, eles não podem ser ultrapassados pelo número de canibais na mesma margem (se fossem, os canibais comeriam os missionários.) O barco não pode atravessar o rio por si só, sem pessoas a bordo.
Tópico 1 – Introdução
Problema dos Canibais e Missionários
29
Informações
 3 missionário
 3 canibais
 1 barco com capacidade para 2 pessoas
ações
 atravessar o rio com segurança
resultado
 3 missonário e 3 canibais na outra margem do rio
Tópico 1 – Introdução
O Problema dos Canibais e Missionários
Algoritmo:
 início
 atravessar dois canibais
 voltar um canibal
 atravessar dois canibais
 voltar um canibal
 atravessar dois missionário
 voltar um missionário e um canibal
 atravessar dois missionário
 voltar um canibal
 atravessar dois canibais
 voltar um canibal
 atravessar dois canibais
 fim
30
Exercício 3
Você tem dois baldes: um com capacidade para comportar 5 litros, e outro que comporta 3 litros. Você não possui outros recipientes e os baldes não possuem marcações de volume.
Problema 1: Você precisa retirar exatamente 7 litros de água de uma bica, com esses baldes. Como fazer isto?
Problema 2: Com os mesmos baldes, diga como fazer para retirar exatamente 4 litros de água da mesma bica.
Tópico 1 – Introdução
Problema dos Baldes
31
Informações
 1 baldes de 5 litros sem marcação
 1 baldes de 3 litros sem marcação
 1 bica
ações
Retirar uma determinada quantidade de agua
resultado
7 litros de agua retirada
Tópico 1 – Introdução
Problema dos Baldes
Algoritmo:
 início
 encher o balde de 5 lt
 esvaziar o balde de 5 lt no balde de 3 lt
 restam 2 lt no balde de 5 lt
 esvaziar o balde de 3 ltr
 mover os 2lt do balde de 5 lt no 
 balde de 3 lt
 encher o balde de 5 lt
fim
32
Sequência Lógica são passos executados até atingir um objetivo ou solução de um problema
Podem ser descritos como uma sequência de instruções, que devem ser seguidas para se cumprir uma determinada tarefa
Tópico 1 – Introdução
Sequência Lógica
33
Instruções são um conjunto de regras ou normas definidas para a realização ou emprego de algo. 
Cada um dos passos, cada uma das ações a tomar (obedecendo a sequência lógica) para ir resolvendo o problema, ou para ir executando a tarefa
Em computação, é a ordem/informação que indica a um computador uma operação elementar a ser executada
	Ex.: “somar”, “subtrair”, “comparar se é maior”, etc.
Uma única instrução não resolve problemas reais
Executar um conjunto de instruções
Executar em uma sequencia lógica
Tópico 1 – Introdução
Instrução
34
Instruções: “quebrar ovos”, “bater ovos”, “pôr sal”, “ligar fogão”, “pôr óleo na frigideira”, “pôr frigideira no fogo”, “fritar ovos batidos”, etc...
Quanto às instruções isoladas:
	Só “quebrar ovos”, ou só “pôr óleo na frigideira”, não é suficiente para cumprir a tarefa “fazer omelete”
Quanto à sequência lógica:
	Se executarmos “fritar ovos batidos” antes de “bater ovos”, ou pior, antes de “quebrar ovos”, não iremos cumprir a tarefa “fazer omelete”
Tópico 1 – Introdução
Exemplo Fazer Omelete
35
– Um Algoritmo é formalmente uma sequência definida e finita de passos que levam à execução de uma tarefa.
–Claro e preciso. Ex. “somar dois números”:
 •Escrever primeiro número no retângulo A
 •Escrever segundo número no retângulo B
 •Somar o número do retângulo A com o número do retângulo B e escrever o resultado no retângulo C
Tópico 1 – Introdução
Algoritmo
36
- Um Algoritmo deve ser claro e preciso 
	- Deve indicar a ordem de realização de cada passo.
- Um Algoritmo deve estar definido. 
	- Seguindo um algoritmo duas vezes, devemos obter o mesmo resultado toda vez.
- Um Algoritmo deve ser finito. 
	- Seguindo um algoritmo, devemos terminar em algum momento, ou seja deve ter um número finito de passos.
Tópico 1 – Introdução
Algoritmo
37
O nome Algoritmo vem de um matemático Persa do século IX -
Al Khowarizmi - Saiba mais:
https://pt.wikipedia.org/wiki/Al-Khw%C4%81rizm%C4%AB 
Tópico 1 – Introdução
Algoritmo
38
>>
Mais famoso (talvez o primeiro): Euclides de Alexandria foi um professor, matemático platónico e escritor possivelmente grego, muitas vezes referido como o "Pai da Geometria".
Desenvolveu um algoritmo para o cálculo do máximo divisor comum entre dois números MDC.
Existem diversas formas de representação de algoritmos, mas não há um consenso com relação à melhor delas. Para SALIBA (1992), o critério usado para classificar hierarquicamente estas formas está diretamente ligado ao nível de detalhe ou, inversamente, ao grau de abstração oferecido. 
O processo de abstração é uma abordagem dada à solução do problema onde se consideram apenas os aspectos que são importantes para sua solução.
Tópico 1 – Introdução
Representação de Algoritmos
39
Dentre as formas de representação de algoritmos mais conhecidas se destacam:
Descrição Narrativa;
Abordagem Gráfica;
Pseudocódigo, também conhecido como Linguagem Estruturada ou Portugol.
Tópico 1 – Introdução
Representação de Algoritmos
40
Descrição Narrativa
Nesta forma de representação os algoritmos são expressos diretamente em linguagem natural
Tópico 1 – Introdução
Representação de Algoritmos
41
Descrição Narrativa
Quando uma dona de casa prepara um bolo, segue uma receita, que nada mais é do que um algoritmo em que cada instrução é um passo a ser seguido para que o prato fique pronto com sucesso:
1.Bata 4 claras em neve
2.Adicione 2 xícaras de açúcar
3.Adicione 2 colheres de farinha de trigo, 4 gemas, uma colher de fermento e duas colheres de chocolate
4.Bata por 3 minutos
5.Unte uma assadeira com margarina
6.Coloque o bolo para assar por 20 minutos a 200 graus C
Tópico 1 – Introdução
Exemplo Algoritmo Fazer Bolo
42
Algoritmo para trocar pneu de um carro
Níveis de detalhes:
Versão 1
Versão 2
Versão 3
Versão 4
Tópico 1 – Introdução
Exemplo Algoritmo Trocar Pneu
43
>>Osmar
Vamos ver este algoritmo em 4 versões diferentes com níveis diferentes de detalhes.
Trocar pneu
Versão 1
Tópico 1 – Introdução
Exemplo Algoritmo Trocar Pneu
44
>>Osmar
Neste caso temos 0 detalhamento dos passos.
Para pessoas experientes é suficiente, mas para quem nunca trocou um pneu?
Abra o porta mala;
Verifique o estado do estepe;
Se estepe estiver furado chame o borracheiro;
Caso contrário faça a troca do pneu.
Versão 2
Tópico 1 – Introdução
Exemplo Algoritmo Trocar Pneu
45
>>Osmar
Mascomo faço a troca?
Abra o porta malas;
Verifique o estado do estepe;
Se estepe estiver furado chame o borracheiro;
Caso contrário tire o pneu reserva do porta malas; 
Tire o macaco hidráulico e a chave de roda do porta malas;
Coloque o macaco hidráulico embaixo do carro para levantar a roda que está com o pneu furado;
Utilize o macaco hidráulico para levantar o carro;
Retire o pneu furado;
Coloque o pneu reserva;
Abaixe o carro utilizando o macaco hidráulico;
Versão 3
Tópico 1 – Introdução
Exemplo Algoritmo Trocar Pneu
46
Gostaria de saber como tirar o pneu furado do carro. Não se detalhou a retirada dos parafusos.
Posso apertar os parafusos do pneu com o carro no macaco?
Abra o porta malas;
Verifique o estado do estepe;
Se estepe estiver furado chame o borracheiro;
Caso contrário retire o triângulo de sinalização;
Coloque o triângulo de sinalização a no mínimo 30 metros do veículo
Tire o pneu reserva do porta malas; 
Tire o macaco hidráulico e a chave de roda do porta malas;
Identifique o pneu furado;
Pegue a chave de roda;Afrouxe os parafusos da roda que está com o pneu furado usando a chave de roda;
Coloque o macaco hidráulico embaixo do carro para levantar a roda que está com o pneu furado;
Utilize o macaco hidráulico para levantar o carro;
Retire os parafusos da roda;
Retire o pneu furado;
Coloque o pneu reserva;
Coloque os parafusos no pneu reserva;
Aperte os parafusos do pneu reserva;
Abaixe o carro utilizando o macaco hidráulico;
Aperte mais os parafusos do pneu reserva;
Guarde o triângulo de sinalização, o macaco hidráulico, a chave de roda e o pneu furado no porta malas.
Versão 4
Tópico 1 – Introdução
Exemplo Algoritmo Trocar Pneu
47
>>Osmar
Já possui mais detalhes, mas ainda poderia ser mais refinado.
Mas em todos os casos a ordem dos passos é fundamental.
Lista de Exercício 1
Tópico 1 – Introdução
48
Há diversas formas de representação de algoritmos que diferem entre si pela quantidade de detalhes de implementação que fornecem ou, inversamente, pelo grau de abstração que possibilitam com relação à implementação do algoritmo em termos de uma linguagem de programação específica.
Dentre as principais formas de representação de algoritmos destacam-se: a descrição narrativa, o fluxograma convencional e o pseudocódigo (ou linguagem estruturada).
Tópico 1 – Introdução
Conclusão
49
DEITEL, P.; DEITEL, H. C: como programar. 6. ed. São Paulo: Pearson Prentice Hall, 2011. Disponível em:
<https://aplicacoes.unisul.br/pergamum/biblioteca_s/php/login_usu.php?flag=index.php>. Acesso em: 11 fev. 2015. Acesso restrito via Biblioteca Virtual 3.0 (Pearson).
PUGA, Sandra; RISSETTI, Gerson. Lógica de programação e estrutura de dados: com aplicação em Java. 2. ed. São Paulo: Pearson Prentice Hall, 2009. Disponível em: <https://aplicacoes.unisul.br/pergamum/biblioteca_s/php/login_usu.php?flag=index.php>. Acesso em: 11 fev. 2015. Acesso restrito via Biblioteca Virtual 3.0 (Pearson).
TOSCANI, Laira Vieira; VELOSO, Paulo A. S. INSTITUTO DE INFORMÁTICA DA UFRGS. Complexidade de
algoritmos : Laira Vieira Toscani, Paulo A. S. Veloso. Porto Alegre: Bookman, 2008. 261 p. (Livros didáticos ; n. 13) ISBN 9788577803507.
Bibliografia
50
Fim
Algoritmos
51