ALGORITMOS E APLICAÇÕES
FATEC – IPIRANGA – ADS Noturno – 1º semestre de 2012
Prof. Luiz Carlos de Jesus Junior
BREVE HISTÓRIA DOS COMPUTADORES
Ábaco (5500 a.C.): Utilizado para o cálculo em áreas de comércio de mercadorias e construção
civil. (Usado principalmente para soma e subtração).
BREVE HISTÓRIA DOS COMPUTADORES
Régua de Cálculo (1638): Permite o cálculo de valores ‘grandes’ porém com
alguma imprecisão.
Exemplo: 1345 x 3442 = 4.629.490, valor da régua: 4.650.000
BREVE HISTÓRIA DOS COMPUTADORES
Máquina de Pascal (1642): Primeira calculadora mecânica da história.
Idéia era fazer os cálculos das quatro operações básicas, porém só fazia adição e subtração.
BREVE HISTÓRIA DOS COMPUTADORES
Tear Programável (1801): Revolucionou as máquinas, pois aceitava personalizar
sua programação.
BREVE HISTÓRIA DOS COMPUTADORES
Máquina de diferenças (1822): Calculava diversas ‘naturezas’ (trigonometria,
Logaritmos entre outros) de maneira muito simples.
BREVE HISTÓRIA DOS COMPUTADORES
Máquina Analítica (1837): Usava como ‘base’ as idéias do Tear Programável.
Aceitava instruções e comandos que poderiam ser informados pelos cartões.
BREVE HISTÓRIA DOS COMPUTADORES
Teoria de Boole
Boole desenvolveu, em 1847, um sistema lógico que reduzia a representação de
valores através de dois algarismos: 0 ou 1.
Em sua teoria, o número “1” tem significados como: ativo, ligado, existente,
verdadeiro. Por outro lado, o “O” representava o inverso: não ativo, desligado, não
existente, falso.
Para representar valores intermediários, como “mais ou menos” ativo, é possível usar
dois ou mais algarismos(bits) para a representação.
Por exemplo:
00 – desligado
01 – carga baixa
10 – carga moderada
11 – carga alta
BREVE HISTÓRIA DOS COMPUTADORES
Máquina de Hollerith (1890): Usado na computação do censo dos Estados Unidos.
(Empresa foi a precursora da IBM (1916))
BREVE HISTÓRIA DOS COMPUTADORES
Computadores Pré-Modernos
Mark I (1944): Primeiro computador digital em larga escala produzido.
BREVE HISTÓRIA DOS COMPUTADORES
Computadores Modernos (primeira geração 1946 – 1959)
ENIAC (1946): 1000x mais rápida. A maioria das operações eram realizadas sem a necessidade
de movimentar peças de forma manual . Peso total: 30 toneladas.
BREVE HISTÓRIA DOS COMPUTADORES
Computadores Modernos (segunda geração 1959 – 1964)
IBM 7030 (1961) e PDP-8 (1964): Cálculos na casa dos milesegundos. Diversas linguagens foram
desenvolvidas para essas máquinas: Fortran, Cobol e Algol.
BREVE HISTÓRIA DOS COMPUTADORES
Computadores Modernos (terceira geração 1964 – 1970)
IBM 360/91 (1967): Usava circuitos integrados. Dispositivos de entrada de saída
como discos e fitas de armazenamento além da possibilidade de imprimir os resultados
em papel.
BREVE HISTÓRIA DOS COMPUTADORES
Computadores Modernos (quarta geração 1970 – HOJE)
ALTAIR 8800 (1975): Usava processador da INTEL (8080). Cabia facilmente em uma mesa.
Liguagem Altair Basic (criada por Bill Gates)
BREVE HISTÓRIA DOS COMPUTADORES
Computadores Modernos (quarta geração 1970 – HOJE)
Machintosh, Apple II e LISA: Primeiros computadores a usarem mouse e possuírem
interface gráfica como conhecemos hoje.
COMPUTADORES E ALGORITMOS
- PARA QUE SERVEM OS COMPUTADORES ?
RESOLVER PROBLEMAS QUE ENVOLVAM UMA GRANDE QUANTIDADE
DE DADOS E/OU EXIGEM A EXECUÇÃO DE UM GRANDE NÚMERO DE PASSOS.
- O QUE É UM PROBLEMA ?
SITUAÇÃO QUE, A PRINCÍPIO, NÃO SABEMOS A RESPOSTA
E PRECISAMOS ENCONTRÁ-LA.
COMPUTADORES E ALGORITMOS
- ETAPAS PARA SOLUÇÃO DE UM PROBLEMA:
1. DEFINIR E ENTENDER (O PROBLEMA);
2. CRIAR UMA SEQUÊNCIA DE OPERAÇÕES, QUE QUANDO EXECUTADA,
PRODUZIRÁ (EM TESE) A RESOLUÇÃO DO PROBLEMA;
3. EXECUTAR A SEQUÊNCIA DE OPERAÇÕES;
4. VERIFICAR A REPOSTA.
Como o cliente
explicou
Como o líder do
projeto entendeu
Como o analista
projetou
Como o programador
construiu
Como o consultor de
negócios descreveu
Como o projeto foi
documentado
Quais as
funcionalidades que
foram
implementadas
Como o cliente foi
cobrado
Como foi mantido
O que o cliente
realmente queria
COMPUTADORES E ALGORITMOS
DESTA FORMA, ALGORITMO É...
um conjunto finito de regras que fornece
uma sequência de operações para resolver um problema específico.
- CARACTERÍSTICAS IMPORTANTES:
1. FINITUDE: DEVE TERMINAR SEMPRE APÓS UM NUMERO FINITO DE PASSOS.
2. DEFINIÇÃO: AÇÕES BEM DEFINIDAS EM CADA PASSO SEM AMBIGUIDADE.
3. ENTRADAS: DEVE CONTER DE 0 A VÁRIAS ENTRADAS. INFORMAÇÕES PARA O
ALGORITMO INICIAR.
4. SAÍDAS: DEVE TER 1 OU MAIS SAÍDAS.
5. EFETIVIDADE: NÚMERO MÍNIMO DE PASSOS COM MÁXIMA PRECISÃO E
EXECUTADO EM UM TEMPO FINITO.
COMPUTADORES E ALGORITMOS
EXEMPLOS
Troca de pneu do carro
1: desligar o carro.
2: pegar as ferramentas (chave e macaco).
3: pegar o estepe.
4: suspender o carro com o macaco.
5: desenroscar os 4 parafusos do pneu furado.
6: colocar o estepe.
7: enroscar os 4 parafusos.
8: baixar o carro com o macaco.
9: guardar as ferramentas.
Pegar um onibus.
1: ir até a parada
2: enquanto ônibus não chega faça
3:
esperar ônibus
4: fim-enquanto
5: subir no ônibus
6: pegar passagem
7: se não há passagem então
8:
pegar dinheiro
9: fim-se
10: pagar o cobrador
11: troco <= dinheiro - passagem
12: enquanto banco não está vazio faça
13:
ir para o próximo
14: fim-enquanto
15: sentar
PROBLEMA DA RÃ
Quatro rãs estão posicionadas em cinco casas da seguinte maneira:
rã 1 rã 2 rã 3 rã 4
As rãs foram treinadas para trocar de casas, mas sempre obedecendo as seguintes regras:
- elas podem pular para a casa vizinha (frente ou trás), se ela estiver vazia;
- elas podem pular sobre a rã vizinha para uma casa livre (frente ou trás).
Mostre como as rãs podem chegar a seguinte posição final:
rã 4 rã 3 rã 2 rã 1
PROBLEMA DA RÃ
(SOLUÇÃO)
rã 1
rã 2
rã 2
rã 1
rã 2
rã 1
rã 2
rã 3
rã 2
rã 3
rã 2
rã 3
rã 4
rã 2
rã 3
rã 4
rã 2
rã 3
rã 3
rã 3
rã 3
rã 4
rã 3
rã 4
rã 4
rã 3
rã 4
rã 3
rã 4
rã 3
rã 4
rã 1
rã 4
rã 1
rã 4
rã 1
rã 1
rã 4
rã 1
rã 2
rã 4
rã 1
rã 2
rã 4
rã 1
rã 2
rã 3
rã 1
rã 2
rã 1
rã 2
rã 1