Aula 01 intro comp

Prévia do material em texto

Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Introduc¸a˜o a` Computac¸a˜o
Prof. Vale´rio Rosset
Baseado no Material do Prof. Ota´vio Lemos
March 3, 2015
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 1/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
O que e´ isso?
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 2/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
E isso?
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 3/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
E isso?
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 4/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
O Computador
Inventado: ± 1943
ENIAC (Electrical Numerical Integrator and Computer):
17m x 9m – 2h ' 100 engenheiros em um ano
Entretanto: 1 PlayStation 3 ' 1.000.000 ENIACs
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 5/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
O Computador
Inicialmente: calculadora enorme / ra´pida – Para queˆ?
Ex.: Previsa˜o do tempo para um dia no Brasil:
155.520.000.000.000.000 operac¸o˜es
Com 100 contas por segundo, 3 bilho˜es de anos para
calcular
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 6/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
O Computador
Hoje: processador essencialmente realiza operac¸o˜es
fundamentais
Sobre isso → programas sofisticados (MP3, Jogos, Orkut,
etc.)
Lembre-se do Lego
→
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 7/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Origens
Aparelhos mecaˆnicos – usados pela humanidade por
mileˆnios
Exemplo: abaco; provavelmente 3000 A.C.; Babiloˆnia
(Iraque)
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 8/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Aristo´teles (384 a.C. - 322 a.C.) - primeiro Lo´gico Formal
Filo´sofo grego: cieˆncias naturais,
lo´gica, f´ısica, poe´tica, astronomia,
e´tica, pol´ıtica, reto´rica, psicologia,
entre outras.
Lo´gica Matema´tica: ca´lculos
simbo´licos, silogismo e o me´todo
axioma´tico.
pensamento dedutivo e
matema´tico, problemas da
mecanizac¸a˜o do pensamento
quantitativo, bases da teoria da
computabilidade.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 9/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Al-Khwarizmi (≈780, ≈850)
Abu Ja’far Mohammed ibn Muˆsa
al-Khwarizmi – matema´tico persa,
se´c. IX
Livro “al-Kitab al-mukhtasar fi
hisab al-jabr wa’l-muqabala” –
livro de a´lgebra, para resolver
equaco˜es lineares e quadra´ticas.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 10/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Antes de 1900
Gottfried Wilhelm Leibniz (1646 - 1716) – precursor da
Lo´gica Matema´tica moderna
Blaise Pascal (1623-1662) – primeira calculadora
mecaˆnica.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 11/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Antes de 1900
Charles Babbage (1791-1871) – Ma´quina Diferencial
(func¸o˜es polinomiais) e Ma´quina Anal´ıtica (precursora do
computador digital) – nenhum funcionou
satisfatoriamente. Ada Byron foi a primeira programadora
da histo´ria trabalhando com a ma´quina de Babbage.
George Boole (1815 - 1864): considerado o fundador da
Lo´gica Simbo´lica, consequentemente deu origem a`
A´lgebra Booleana e os estados de quantificac¸a˜o lo´gica ’0’
e ’1’.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 12/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
David Hilbert (1862-1943)
1928, Congresso Internacional de
Matema´ticos:
1 A matema´tica e´ completa?
2 A matema´tica e´ consistente?
3 A matema´tica e´ decid´ıvel?
Problema da decisa˜o.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 13/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Kurt Go¨del (1906-1978)
Amigo de Einstein em Princeton
1931 – respondeu as duas
primeiras perguntas:
1 Mostrou que todo sistema
formal suficientemente forte e´
ou inconsistente ou
incompleto;
2 Mostrou que se um sistema
axioma´tico e´ consistente, a
consisteˆncia na˜o pode ser
provada pelo pro´prio sistema
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 14/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Alan Turing (1912-1954)
1936 – soluc¸a˜o para o problema da
decisa˜o;
Ma´quina de Turin – modelo formal
de um computador; mostrou que
alguns problemas na˜o poderiam ser
resolvidos pela ma´quina
Exemplo: problema da parada;
dado um programa, saber se da´
resposta para todas as poss´ıveis
entradas
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 15/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
John von Neumann (1903-1957)
1944 – muitas das ideias ainda
utilizadas em computadores
digitais modernos
Arquitetura de von Neumann
Unidade central de processamento
(CPU) + memo´ria (instruc¸o˜es e
dados)
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 16/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
John von Neumann (1903-1957)
Memória
Entrada Saída
Accumulador
Unidade
Controle
de
Unidade
Lógica
Aritmética
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 17/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Primeiro microprocessador – Intel (1970)
Depois disso: acelerac¸a˜o fenomenal
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 18/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Curiosidade
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 19/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Breve histo´rico
Curiosidade
Termo bug : 1945, Grace Murray Hopper (Harvard) –
contas na˜o batiam
Ao verificar o hardware: mariposa em uma das va´lvulas –
a impedia de fechar
Relato´rio de operac¸o˜es: mariposa na folha
Maior desgosto de um profissional da computac¸a˜o
Faz parte, aprender a conviver e a utilizar os inseticidas
apropriados
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 20/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Cieˆncia da computac¸a˜o?
Por que na˜o Cieˆncia da Programac¸a˜o?
Cieˆncia/estudo da resoluc¸a˜o de problemas com me´todos
computacionais (n˜ necessariamente computadores)
Como resolver um problema; qua˜o eficiente e´ uma
soluc¸a˜o; como otimizar uma soluc¸a˜o; etc.
Programac¸a˜o e´ um dos artefatos... parte do processo
Programac¸a˜o ↔ Computac¸a˜o; Construc¸a˜o de telesco´pios
↔ Astronomia
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 21/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Para que serve a computac¸a˜o?
Me´dico → problema de sau´de; Engenheiro → construir
uma ponte, etc.
Problema central da computac¸a˜o: encontrar algoritmos
para solucionar problemas da melhor forma poss´ıvel
Tal como Medicina, ramificac¸o˜es:
1 Banco de Dados: algoritmos para gerar e manipular grandes quantidades
de dados
2 Computac¸a˜o Gra´fica: algoritmos para projetar imagens em uma tela
plana (iluminac¸a˜o, sombras, reflexos,etc.)
3 Inteligeˆncia Artificial: algoritmos para simular ou planejar
comportamentos
4 Otimizac¸a˜o: algoritmos mais eficientes do que os conhecidos
5 Entretenimento: algoritmos para dar raza˜o ao PlayStation, Xbox, etc.
6 Etc.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 22/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Hardware VS Software
Hardware: o equipamento propriamente dito –
inclui perife´ricos de entrada e de sa´ıda, a
ma´quina e seus elementos f´ısicos: carcac¸as,
placas, fios, componentes em geral.
Software: constitu´ıdo pelos programas que
permitem atender a`s necessidades do usua´rio.
Programar, lidar com software → arte
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 23/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Modelo Hipote´tico
Funcionamento do Computador
Componentes
Calculadora;
ma´quina de escrever;
estante com 30 escaninhos
numerados(1-30);
carto˜es externos contendo
um valor nume´rico (pilha de
entrada);
carto˜es em branco;
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 24/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Modelo Hipote´tico
Funcionamento do Computador
Nomenclatura
Esc1, Esc2,..., Escn: significam os nu´meros de
cada escaninho.
(Esc1), (Esc2),..., (Escn): significam os valores
nos carto˜es de cada escaninho.
Funcionamento
O operador comec¸a o trabalho lendo e
executando sequencialmente as instruc¸o˜es
contidas nos carto˜es amazenados no escaninho,
comec¸ando por Esc1.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 25/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Modelo Hipote´tico
Funcionamento do Computador
Funcionamento
Algumas instruc¸o˜es podem fazer com que
operador salte ou retorne a escaninhos ja´ lidos
e, desse modo, rompendo a sequeˆncia inicial
mas na˜o a maneira como ele trabalha.
O operador sempre efetuara´ a leitura do
pro´ximo escaninho na sequeˆncia.
O Hardware sa˜o o operador e os dispositivos
que ele gerencia e o software e´ o conjunto de
instruc¸o˜es dos carto˜es. O conjunto de
instruc¸o˜es e´ o seu PROGRAMA.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 26/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Modelo Hipote´tico
Funcionamento do Computador
Instruc¸o˜es Poss´ıveis
Leitura de dados;
Carregamento de constantes (coloca um novo
carta˜o no escaninho);
Co´pia de dados (copia valor existente de um
escaninho para um outro escaninho);
Operac¸a˜o aritme´tica;
Impressa˜o de resultados;
Quebra de sequeˆncia (Condicional/
Incondicional) e te´rmino.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 27/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Modelo Hipote´tico
Calculando a Me´dia Aritme´tica: o Programa
1 Carregar valor 0 em Esc21;
2 Carregar valor 0 em Esc22;
3 Carregar valor 1 em Esc23;
4 Se na˜o ha´ carto˜es de entrada, va´ para Esc9;
5 Ler o valor do carta˜o de entrada para Esc24;
6 Somar (Esc24) com (Esc21), carregando o resultado em Esc21;
7 Somar (Esc23) com (Esc22), carregando o resultado em Esc22;
8 Va´ para Esc4;
9 Se (Esc21) =0, va´ para Esc12;
10 Divida (Esc21) por (Esc22), carregando o resultado em Esc25;
11 Imprima (Esc25);
12 Terminar.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 28/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Modelo Hipote´tico
Calculando a Me´dia Aritme´tica: o Programa
Entrada: Carto˜es com os valres 5, 8 e 14,
respectivamente.
Esc Valor
21 0
22 0
23 1
24 ?
25 ?
Partindo deste estado inicial,o resultado final armazenado em
Esc25 e impresso sera´ ”9”.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 29/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
UCP
UCP: Unidade Central de Processamento (CPU).
1 UC: Unidade de Controle;
2 UF: Unidade Funcional;
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 30/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
UCP – Unidade Central de Processamento:
UCP – Unidade Central de Processamento:
Recentemente denominado processador, e´ o
conjunto formado por sua UC, suas UF´s e por
um pequeno mo´dulo de memo´ria chamado de
conjunto de registradores de propo´sitos gerais
(Acesso mais ra´pido que o acesso a memo´ria
principal).
Supercomputadores atuais contam com dezenas,
centenas e ate´ milhares de processadores.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 31/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
UF – Unidade Funcional:
UF – Unidade Funcional:
Parte do computador que confere a capacidade
de realizar operac¸o˜es matema´ticas, c operandos
armazenados localmente (sistema de memo´ria
pro´prio).
Operac¸o˜es Aritme´ticas com nu´meros inteiros e
reais ou Lo´gicas com 0 ou 1;
Alguns mais modernos fazem operac¸o˜es mais
complexas (Trigonome´tricas, logaritmicas,
exponenciais, etc.)
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 32/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
UC – Unidade de Controle:
UC – Unidade de Controle:
Responsa´vel pela leitura e interpretac¸a˜o de cada
instruc¸a˜o do programa em execuc¸a˜o;
Responsa´vel pelo acionamento da unidade que
executara´ a instruc¸a˜o e obtenc¸a˜o de eventuais
operandos.
Responsa´vel pela escolha correta da sequ¨eˆncia
das instruc¸o˜es a serem executadas (sequencial
ou com desvio condicional/incondicional).
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 33/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
Memo´rias
Memo´ria Prima´ria (ou Principal);
Memo´ria secunda´ria.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 34/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
Memo´rias
Memo´ria Prima´ria
armazena os programas em processamento pela
UCP em um dado instante. Exemplo: RAM
(Random Access Memory)
Memo´ria Secunda´ria
tem a finalidade de armazenar todos os
programas e toda a diversidade de informac¸o˜es
residentes no computador, devendo permanecer
ali guardados mesmo com ele desligado.
Exemplo: HD (Hard Disk), PenDrive, CD/DVD
etc.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 35/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
Entrada e Sa´ıda
UE: Unidades de Entrada.
UE: Unidades de Sa´ıda.
Barramentos.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 36/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
Unidades de Entrada e Sa´ıda
UE: Unidades de Entrada.
Interface com equipamentos do mundo externo.
Recebem dados externos. Exemplos: Mouse;
Teclado; alternativamente arquivos armazenadas
em dispositivos de memo´ria secunda´ria.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 37/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
Unidades de Entrada e Sa´ıda
US: Unidades de Sa´ıda.
Interface com equipamentos do mundo externo.
Envia dados para o mundo externo. Exemplos:
Impressoras; Alto Falantes; alternativamente
arquivos armazenadas em dispositivos de
memo´ria secunda´ria.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 38/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do ComputadorAlgoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
Barramentos
Barramentos.
Barramento de dados: transporta dados de e
para o armazenamento principal.
Barramento de enderec¸os: transporta os sinais
usados para localizar um determinado enderec¸o
do armazenamento principal.
Barramento de Controle: transporta sinais
indicando se dados devem ser lidos ou escritos
no enderec¸o especificado do armazenamento
principal e de ou para dispositivos de sa´ıda.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 39/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Unidades Ba´sicas do Computador
Correspondencia entre o modelo hipote´tico e o Computador
Comparando:
Modelo Hipote´tico Computador Simples
Operador Unidade de Controle
Calculadora Unidade Funcional
Escaninhos Memo´ria
Pilha de Entrada Unidade de Entrada
Ma´quina de Escrever Unidade de Sa´ıda
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 40/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Idioma do Computador
Alfabeto e Sistema de Numerac¸a˜o
No´s: Portugueˆs! Nosso alfabeto, 26 letras;
Computador: Bits. Alfabeto do computador:
Sistema de numerac¸a˜o;
Sistema Base Alfabeto
Decimal 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Bina´rio 2 0, 1
Terna´rio 3 0, 1, 2
Quaterna´rio 4 0, 1, 2, 3
Octal 8 0, 1, 2, 3, 4, 5, 6, 7
Hexadecimal 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 41/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Idioma do Computador
Alfabeto e Sistema de Numerac¸a˜o
Sistema Bina´rio
O bit e´ a menor unidade de armazenamento do
computador, 1 byte (palavra) equivale a 8 bits
(Ex: 1010 1110).
Toda informac¸a˜o e´ baseada em sequ¨eˆncias de 0
e 1, na˜o se sabe a priori se o conteu´do de um
determinado trecho e´ um nu´mero decimal,
texto, imagem ou som digitalizado. E´ necessa´rio
que o programa que utiliza o conteu´do
interprete o conteu´do de maneira correta.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 42/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Idioma do Computador
Alfabeto e Sistema de Numerac¸a˜o
Prefixos
Prefixos Poteˆncia de 2 Decimal Pro´ximo de
Kilo 210 1.024 103
Mega 220 1.048.576 106
Giga 230 1.073.741.824 109
Tera 240 1.099.511.627.776 1012
Peta 250 1.125.899.906.842.624 1015
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 43/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Idioma do computador
Muitas LPs. Exemplos:
1 C/C++: BCPL → 1970, melhoras por
Martin Richards: ‘B’ → 1972, melhoras por
Ritchie e Thopmson: ‘C’ → de´cada de
1980, com POO, Bjarne Stroustrup: ‘C++’
(C e C++ – populares; Pascal semelhante a
C, pore´m mais fa´cil – acadeˆmica)
2 C#: Microsoft; conceitos de C, C++ e Java
3 ASP e PHP: para Web (PHP similar a C)
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 44/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Compilac¸a˜o
resolução de 
um problema
programa em 
linguagem
de alto nível
compilação 01001010
01001111
01101001
11010011
01011011
programa em 
linguagem
de máquina
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 45/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Algoritmos
Um dos algoritmos mais antigos – Euclides
(Gre´cia, 300 a.C.) – MDC
Exemplo: MDC(3654, 1365) – algoritmo:
1 Divida um dos nu´meros pelo outro e pegue
o resto da divisa˜o;
2 Substitua o primeiro nu´mero pelo segundo,
e o segundo pelo resto;
3 Repita ate´ que o resto seja 0
Repare no cara´ter imperativo
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 46/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Algoritmos
Exemplo de MDC (Ma´ximo Divisor Comum)
Executando:
1 3654 ÷ 1365 → resto 924
2 1365 ÷ 924 → resto 441
3 924 ÷ 441 → resto 42
4 441 ÷ 42 → resto 21
5 42 ÷ 21 → resto 0
o resultado de MDC(3654,1365) e´ 21.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 47/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Algoritmos
Lo´gica de programac¸a˜o – te´cnica de
encadear pensamentos para atingir
determinado objetivo
Algoritmo – sequeˆncia de ac¸o˜es
necessa´ria para solucionar um problema
Receita de bolo:
1 ingredientes (ENTRADA);
2 modo de preparo (PROCESSAMENTO);
3 alimento pronto (SA´IDA)
Partitura musical, manual de instruc¸o˜es,
instruc¸o˜es de caminho, etc.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 48/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Algoritmos
Problema de uma receita: linguagem vaga
Formalizac¸a˜o de algoritmos, linguagens:
1 Formato livre
2 Fluxograma
3 Pseudoco´digo
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 49/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Algoritmos
Formato livre
Passos necessa´rios numerados item a item
Exemplo:
Inı´cio do Algoritmo
1. pegue o primeiro nu´mero
2. pegue o segundo nu´mero
3. some o primeiro nu´mero com
o segundo
4. mostre o resultado da soma
Fim do Algoritmo.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 50/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Algoritmos
Fluxograma
Representac¸a˜o gra´fica do formato livre
Exemplo:
Tocou o alarme
Pronto 
para
acordar?
Não
Sim
Aperte o soneca
Levante
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 51/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Algoritmos
Pseudoco´digo
Linguagem mais pro´xima de uma linguagem de
programac¸a˜o de alto n´ıvel
Evita-se regras de construc¸a˜o gramatical muito r´ıgidas
inı´cio
inteiro: A, B
A ← 1;
B ← 2;
se A > B
ent~ao A ← 5;
sen~ao A ← 10;
fimse;
fim.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 52/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Exerc´ıcio
Algoritmo para levar um lea˜o, uma cabra
e um pedac¸o de grama de um lado para
outro de um rio, atravessando com um
bote. Sabe-se que o bote so´ tem dois
lugares e nunca o lea˜o pode ficar sozinho
com a cabra e nem a cabra sozinha com a
grama. (Use o Formato Livre)
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 53/54
Introduc¸a˜o Breve histo´rico Conceitos Estrutura do Computador Algoritmos Exerc´ıcio
Exerc´ıcio
Soluc¸a˜o
Inı´cio do Algoritmo
1. leve a cabra;
2. volte;
3. leve o le~ao e volte com a cabra;
4. leve a grama;
5. volte;
6. leve a cabra
Fim do Algoritmo.
DCT–UNIFESP — Introduc¸a˜o a` Computac¸a˜o 54/54
	Introdução
	Breve histórico
	Conceitos
	Estrutura do Computador
	Algoritmos
	Exercício