ALGORITMOS E PROGRAMAÇÃO 1 P01

Prévia do material em texto

ALGORITMOS E PROGRAMAÇÃO 1 
P01 
Prof. Glauder Guimarães Ghinozzi 
glauderguimaraes@gmail.com 
 
 
Baseado em material do Prof. 
Rafael Robson Negrão 
PLANO DE ENSINO 
Horário de Aula: 
 
 2ª feira das 9:25 as 11:25h (teórica), sala M16 
 4ª feira das 9:25 as 11:25h (pratica), sala L1 
 6ª feira das 9:25 as 11:25h (teórica), sala M16 
 
PLANO DE ENSINO 
Ementa: 
Variáveis e Tipos de Dados; 
Estrutura Sequencial; 
Estrutura Condicional; 
Estruturas de Repetição; 
Variáveis Compostas Homogêneas e Heterogêneas; 
Modularização. 
PLANO DE ENSINO 
 - B. A. Forouzan e R. F. Gilbert, Computer Science - A Structured 
Programming Approach Using C (3rd ed), Thomson Course 
Technology, 2007.** 
 - H. Farrer et al., Algoritmos Estruturados (3a ed), LTC, 1999. 
 - R. Sedgewick e K. Wayne, Introduction to Programming in Java - An 
Interdisciplinary Approach, Addison Wesley, 2008. 
 - A. B. Tucker et al., Fundamentals of Computing I: Logic, Problem 
Solving, Programs, and Computers (C++ Edition), McGraw-Hill, 1995. 
 - Notas de aulas disponíveis em http://ava.ufms.br 
PLANO DE ENSINO 
 MA: Média Aproveitamento 
 MA = (P1 * 0,30) + (P2 * 0,30) + (T * 0,25) + (EA * 0,10) + (CA *0,05) 
 EA: Exercícios Avaliativos 
- Serão exercícios realizados durante as aulas práticas. 
- Os exercícios realizados nas atividades EAD serão avaliados como 
exercícios avaliativos. 
 CA: Conceito do aluno 
- Nota por assiduidade e participação. 
 P1 = Prova 25/09/2019 
 P2 = Prova 27/11/2019 
 T = Trabalho 27/11/2019 
 PO = Prova Optativa 04/12/2019 
- Conteúdo: Todo conteúdo do semestre. 
- A PO substitui a menor nota entre as provas P1 ou P2. 
- As datas das provas são as datas planejadas, porém podem ser alteradas 
ao longo do semestre. 
 
 
 
 O que é computação 
 
 O que é informática 
 
 Componentes de um sistema de computação 
 
 Histórico e evolução 
 
 Classificação de computadores 
 
6 
ALGORITMOS E PROGRAMAÇÃO 
 
 O que é computação 
 
 O que é informática 
 
 Componentes de um sistema de computação 
 
 Histórico e evolução 
 
 Classificação de computadores 
 
7 
ALGORITMOS E PROGRAMAÇÃO 
O QUE É COMPUTAÇÃO? 
 A computação pode ser definida como a busca de 
uma solução para um problema a partir de 
entradas (inputs) e tem seus resultados (outputs) 
depois de trabalhada através de um algoritmo. 
9 
DADOS PROCESSAMENTO INFORMAÇÃO 
O QUE É COMPUTAÇÃO? 
 
 O que é computação 
 
 O que é informática 
 
 Componentes de um sistema de computação 
 
 Histórico e evolução 
 
 Classificação de computadores 
 
10 
INTRODUÇÃO A COMPUTAÇÃO 
11 
 
mação auto
O QUE É INFORMÁTICA? 
 
 O que é computação 
 
 O que é informática 
 
 Componentes de um sistema de computação 
 
 Histórico e evolução 
 
 Classificação de computadores 
 
12 
INTRODUÇÃO A COMPUTAÇÃO 
13 
PEOPLEWARE 
SOFTWARE HARDWARE 
COMPONENTES DE UM SISTEMA DE 
COMPUTAÇÃO 
 
 O que é computação 
 
 O que é informática 
 
 Componentes de um sistema de computação 
 
 Histórico e evolução 
 
 Classificação de computadores 
 
14 
ALGORITMOS E PROGRAMAÇÃO 
 
 
 
Primeiro ser humano a CALCULAR foi um pastor, que se 
utilizou de uma técnica de empilhamento de pedras para 
controlar a quantidade de ovelhas de seu rebanho. 
Calculus = pedra, em latim 
15 
HISTÓRICO E EVOLUÇÃO 
 
 
 
Primeira maneira que os seres humanos encontraram para 
identificar uma determinada quantidade foi através dos 
dedos da mão. 
 
Digitus = dedo, em latim 
16 
HISTÓRICO E EVOLUÇÃO 
 
 
A primeira tentativa bem-sucedida de criar uma máquina de 
contar foi o ÁBACO. 
17 
HISTÓRICO E EVOLUÇÃO 
 
O primeiro instrumento moderno de 
calcular – na verdade, uma somadora – 
foi construído pelo físico, matemático e 
filósofo francês Blaise PASCAL, em 
1642. 
18 
HISTÓRICO E EVOLUÇÃO 
 
 JACQUARD 
desenvolveu os cartões perfurados para 
entrada de dados. 
 
19 
HISTÓRICO E EVOLUÇÃO 
 
 
MÁQUINA de BABBAGE 
Base do funcionamento de 
um computador: 
 Alimentação de dados, através de cartões 
perfurados. 
 Uma unidade de memória, onde os 
números podiam ser armazenados e 
reutilizados. 
 Programação seqüencial de operações. 
 20 
HISTÓRICO E EVOLUÇÃO 
 
Herman HOLLERITH 
 
- Juntou os cartões de Jacquard e o 
conceito de impulsos elétricos para 
transmissão de dados. 
- Reconhecimento no censo americano de 
1890. 
- Tempo muito menor gerando economia. 21 
HISTÓRICO E EVOLUÇÃO 
 
 
Guerra e Computação: o que tem a ver? 
 
- As guerras trouxeram para a computação 
um enorme desenvolvimento. 
 
- Os governos incentivaram o 
desenvolvimento de equipamentos que 
pudessem calcular trajetórias precisas, 
construir mísseis, e etc... 
22 
HISTÓRICO E EVOLUÇÃO 
 
 
Alan TURING cria o 
Colossus, máquina que, 
uma vez plugada, 
programada e alimentada, 
resolvia problemas de 
criptografia em poucos 
minutos. 
23 
HISTÓRICO E EVOLUÇÃO 
 
ENIAC (Eletronic Numerical Integrator And Computer) 
O computador mais famoso desta época. 
Foi o primeiro computador digital eletrônico de 
grande escala, construído em 1946. 
 17.840 válvulas 
 Pesava 4 toneladas 
 30 metros de comprimento e 3 metros de 
altura 
 Ocupava área de 180 m2 
 Capacidade de 5.000 somas por segundo 
24 
HISTÓRICO E EVOLUÇÃO 
 
ENIAC 
25 
HISTÓRICO E EVOLUÇÃO 
 
MARK I 
 
 O Mark também reivindica o 
título de primeiro computador. 
 
26 
HISTÓRICO E EVOLUÇÃO 
HISTÓRICO E EVOLUÇÃO 
1950 - UNIVAC 
Primeiro sucesso comercial. 
HISTÓRICO E EVOLUÇÃO 
 1960’s, 1970s......- Uso de circuitos integrados com milhares de 
transistores em um único chip 
 Circuitos digitais complexos 
 Calculadoras, Computadores digitais, mainframes, PCs, 
telecomunicações, etc. 
 
Intel 
 
 1971 - 4004 
 Primeiro micropocessador comercial 
 Todos os componentes da CPU em um chip 
 4 bit 
 Seguido em 1972 pelo 8008 
 8 bit 
 Ambos para aplicações especificas 
 1974 - 8080 
 Primeiro de uso geral. 
HISTÓRICO E EVOLUÇÃO 
 
Geração de Computadores: 
 Valvulas- 1946-1957 
 Transistor - 1958-1964 
 Low scale integration (LSI) 1965 
 Até 100 componentes em um chip 
 Medium scale integration – (MSI) 1971 
 100-3,000 componentes em um chip 
 Large scale integration (LSI) - 1971-1977 
 3,000 - 100,000 componentes em um chip 
 Very large scale integration (VLSI) - 1978 to date 
 100,000 - 100,000,000 componentes em um chip 
 Ultra large scale integration (ULSI) 
 Mais de 100,000,000 componentes em um chip 
HISTÓRICO E EVOLUÇÃO 
 BUG 
É a palavra em inglês que significa inseto. 
Ela é usada em computação como significado 
de erro, falha, problema, pois uma mariposa 
conseguiu entrar num Mark II e travou todo o 
sistema. 
31 
CURIOSIDADE 
 Um bit pode representar apenas 2 símbolos (0 e 1) 
 
 Necessidade - unidade maior, formada por um conjunto de 
bits, para representar números e outros símbolos, como os 
caracteres e os sinais de pontuação que usamos nas 
linguagens escritas. 
 
 Unidade maior (grupo de bits) - precisa ter bits suficientes 
para representar todos os símbolos que possam ser usados: 
 dígitos numéricos, 
 letras maiúsculas e minúsculas do alfabeto, 
 sinais de pontuação, símbolos matemáticos e assim por diante. 
A INFORMAÇÃO E SUA REPRESENTAÇÃO 
Caracteres alfabéticos maiúsculos 26 
Caracteres alfabéticos minúsculos 26 
Algarismos 10 
Sinais de pontuação e outros símbolos 32 
Caracteres de controle 24 
Total 118 
Necessidade: 
A INFORMAÇÃO E SUA REPRESENTAÇÃO 
 Capacidade de representação: 
Bits Símbolos 
2 4 
3 8 
4 16 
5 32 
6 64 
7 128 
8 256 
9 512 
10 1024 
A INFORMAÇÃO E SUA REPRESENTAÇÃO 
 Pode ser calculado usando o inteiro superior do log 
do número de simbolos. 
 Log2118 = 6.882643, o inteiro superior é 7. 
 
 Pode ser feito utilizando o logaritmo neperiano 
 ln118/ln2 = 6.882643, o inteiro superior é 7. 
A INFORMAÇÃO E SUA REPRESENTAÇÃO 
 EBCDIC 
 Código de 8 bits (256 símbolos). 
 Usado em mainframe IBM em sistemas de médio porte, raramente 
encontrado em microcomputadores. 
 
 
 ASCII 
 Padrão definido pela organização ANSI. 
 Código de 7 bits (128 combinações de caracteres). 
 Nos computadores é utilizado o ASCII Estendido (utiliza outros 128 
códigos para símbolos gráficos, e línguas diferentes do inglês). 
 
 
 UNICODE 
 Novo padrão para representação de dados, oferece 2 bytes para a 
representação de símbolos (mais de 65.000 símbolos) 
A INFORMAÇÃO E SUA REPRESENTAÇÃO 
 1 byte = 8 bits = 1 caractere (letra, número ou 
símbolo) 
 Podemos definir palavra como um conjunto de bits 
que representa uma informação útil para os 
computadores. A palavra nos computadores é um 
valor fixo e constante para um dado processador : 
 ex.: 32 bits, 64 bits 
 
A INFORMAÇÃO E SUA REPRESENTAÇÃO 
 Partes do conjunto de caracteres ASCII 
38 
Como os principais códigos de representação de caracteres utilizam grupos de 8 
bits por caractere, os conceitos byte e caractere tornam-se semelhantes, e as, 
palavras, quase sinônimas 
Binário Caractere 
0100 0001 A 
0100 0010 B 
0110 0001 a 
0110 0010 b 
0011 1100 < 
0011 1101 = 
0001 1011 ESC 
0111 1111 DEL 
A Informação e sua 
Representação 
 Indicações numéricas dos computadores: 
 Bit - 2 estados: 0 e 1 
39 
Byte B 8 bits 
Quilobyte 
(ou Kilobyte) 
KB 1.024 bytes 210=1.024 
Megabyte MB 1.024 KB 220=1.048.576 
Gigabyte GB 1.024 MB 230=1.073.741.824 
Terabyte TB 1.024 GB 240=1.099.511.627.77
6 
Os valores utilizados em computação para indicar capacidade de memória são 
normalmente compostos de um número (entre 0 e 999) e uma das abreviaturas 
citadas (ex.: 256K, 64M, etc.). 
A Informação e sua 
Representação 
EVOLUÇÃO DOS COMPUTADORES 
 Atualmente, os computadores processam 
dados a partir de conjuntos de instruções 
denominadas programas. 
 
 É uma máquina eletrônica capaz de 
receber informações, submetê-las a um 
conjunto especificado/pré-determinado de 
operações lógicas/aritméticas e fornecer o 
resultado destas operações. 
LINGUAGENS E ALFABETOS 
Hello World 
 
Olá Mundo 
 
Bonjour Monde 
 
Halo welt 
1ª GERAÇÃO – LINGUAGEM DE MÁQUINA 
 1ª geração – Linguagem máquina 
 Conjunto de dígitos binários do “instruction set” do 
processador 
 Os programas rodam apenas no computador para o qual foram 
projetados. 
 
0100 1010100 
0100 1010110 
0110 1001100 
0101 1010101 
1100 1001100 
2ª GERAÇÃO – ASSEMBLER 
 2ª geração – Assembler 
 Mnemônicas do “instruction 
set” do processador 
 Assembler – Programa que 
traduz o código assembly 
para linguagem de máquina 
 Os Programas funcionam 
apenas em um tipo de 
processador 
 Mov –> 00001100 
 int -> 10001101 
 
 Desenvolvimento de 
programas muito difícil e 
demorado 
dosseg 
.model small 
.stack 100h 
 
.data 
hello_message db 'Hello, World!','$' 
 
.code 
main proc 
 mov ax,@data 
 mov ds,ax 
 
 mov ah,9 
 mov dx,offset hello_message 
 int 21h 
 
 mov ax,4C00h 
 int 21h 
main endp 
end main 
2ª GERAÇÃO – ASSEMBLER 
Desvantagens 
 Pequeno número de instruções 
Programas longos 
Pouco legíveis 
Difíceis de modificar 
 Utiliza diretamente os recursos da máquina 
Os programas não são portáteis entre computadores 
Vantagens 
 Código otimizado 
Velocidade de processamento elevado 
 Controle total do hardware 
3ª GERAÇÃO – LINGUAGENS DE ALTO NÍVEL 
 3ª geração – Linguagens de alto nível 
 Uma instrução pode corresponder a um grande número de 
instruções em assembly 
 Instruções em linguagem natural 
 write, read, print, . . . 
 Ler, escrever, repetir 
 Linguagens de propósito geral 
 Cálculo matemático 
 Gestão de documentos 
 Controle 
 Exemplos 
 Basic 
 Pascal 
 C 
 Cobol 
 Fortran 
10 print"Hello World!" 
20 goto 10 
3ª GERAÇÃO – LINGUAGENS DE ALTO 
NÍVEL 
#include <stdio.h> 
main() 
{ 
 for(;;) 
 printf ("Hello World!\n"); 
} 
C 
 PROGRAM HELLO 
 DO 10, I=1,10 
 PRINT *,'Hello World' 
 10 CONTINUE 
 STOP 
 END 
Fortran 
program Hello_World; 
Begin 
 repeat 
 writeln('Hello World!') 
 until 1=2; 
End. 
Pascal 
100200 MAIN-LOGIC SECTION. 
100300 BEGIN. 
100400 DISPLAY " " LINE 1 POSITION 1 ERASE EOS. 
100500 DISPLAY "HELLO, WORLD." LINE 15 POSITION 10. 
100600 STOP RUN. 
100700 MAIN-LOGIC-EXIT. 
100800 EXIT. 
Cobol 
4ª GERAÇÃO DE LINGUAGENS DE APLICAÇÃO 
4ª geração – Linguagens de alto nível com 
aplicações a áreas concretas 
 Funções muito específicas 
Gestão de bases de dados 
Elaboração de relatórios 
Geração de Gráficos 
Exemplos 
DBASE 
SQL 
CLIPPER 
CREATE TABLE HELLO (HELLO CHAR(12)) 
UPDATE HELLO 
 SET HELLO = 'HELLO WORLD!' 
SELECT * FROM HELLO 
SQL 
5ª GERAÇÃO – LINGUAGENS DE MUITO ALTO 
NÍVEL 
 5ª geração – Linguagens de muito alto nível 
 Programação declarativa 
 Declaração dos problemas 
 Métodos específicos de resolução dos problemas 
 Linguagens de Inteligência Artificial 
 Prolog 
hello :- 
printstring("HELLO WORLD!!!!"). 
 
printstring([]). 
printstring([H|T]) :- put(H), printstring(T). 
 
ALGORITMO 
 Origem da palavra 
 al-Khwarizmi - Matemático árabe 
 Algoritmo 
 Algarismo 
 Definição 
 É uma sequência finita de passos ou instruções, 
ordenadas de forma lógica, que levam a execução de 
uma tarefa ou solução de um problema. 
EXEMPLO DE UM ALGORITMO 
•250g de farinha 
•150g de margarina 
•5 ovos 
•2 colheres de fermento 
•200 gramas de acucar 
1. Misturar os ingredintes 
2. cozinhar o bolo. 
Receita 
ABORDAGEM TOP DOWN 
Receita: 
1 - Misturar os ingredintes 
 1.1 – juntar a margarina e a farinha e bater até obter um creme 
 1.2 – Juntar os ovos e mexer 
 1.3 – juntar o fermento 
2 –Cozinhar o bolo 
 2.1 Aquecer o forno a 180ºc 
 2.2 Cozinhar o bolo durante 45 min 
•Refinamento: 
•Obter o creme 
•Juntar ovos 
•Ligar e regular o forno 
•Desligar o forno 
Pode um computador fazer um bolo ? 
ALGORITMOS 
 Algoritmo não computational 
 Exemplos 
 Receita 
 Manual de instruções 
 Depende da perícia do utilizador! 
 Algoritmo computational 
 Manipular informação 
 Receber dados 
 Guardar dados 
 Devolver informação 
 Executar instruções 
 Fazer operações aritméticas 
 Fazer operações lógicas 
 Escolha entre várias instruções. 
 Repetir um conjunto de instruções 
 
Um algoritmo 
computacional é uma 
sequencia de passo tão 
bem definida que até 
um computador o é 
capazde a executar 
ALGORITMOS: EXEMPLO 
 A seguir os passos necessários para trocar uma 
lâmpada 
 Veremos quatro possíveis soluções 
 E os problemas de cada solução 
A formulação de um problema é frequentemente mais 
essencial do que a sua solução, a qual pode ser meramente 
uma questão de habilidade matemática ou experimental 
 
Einstein 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 1 
 Pegue uma escada 
 Posicione-a embaixo da lâmpada 
 Busque uma lâmpada nova 
 Suba na escada 
 Retire a lâmpada velha 
 Coloque a lâmpada nova 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 1 
 Problema 
 Mesmo que a lâmpada não esteja queimada, o algoritmo faz 
com que ela seja trocada!! 
 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 2 
 Pegue uma escada 
 Posicione-a embaixo da lâmpada 
 Busque uma lâmpada nova 
 Ligue o interruptor 
 Se a lâmpada não acender, então: 
 Suba na escada 
 Retire a lâmpada velha 
 Coloque a lâmpada nova 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 2 
 Problemas 
 A ordem das ações!! 
 A escada é posicionada abaixo mesmo que a lâmpada não 
esteja queimada. 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 3 
 Ligue o interruptor 
 Se a lâmpada não acender, então: 
 Pegue uma escada 
 Posicione-a embaixo da lâmpada 
 Busque uma lâmpada nova 
 Suba na escada 
 Retire a lâmpada velha 
 Coloque a lâmpada nova 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 3 
 Problemas 
 E se a lâmpada nova não funcionar?? 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 4 
 Ligue o interruptor 
 Se a lâmpada não acender, então: 
 Peque uma escada 
 Posicione-a embaixo da lâmpada 
 Busque uma lâmpada nova 
 Suba na escada 
 Retire a lâmpada velha cont... => 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 4 
 Coloque a lâmpada nova 
 Se a lâmpada não acender, então: 
 Retire a lâmpada 
 Coloque outra lâmpada 
 Se a lâmpada não acender, então: 
 Retire a lâmpada 
 ... ... ... 
 ... ... ... 
ALGORITMOS: EXEMPLO 
 Trocar uma Lâmpada - Solução 4 
 Problemas 
 Se nenhuma lâmpada funcionar?? 
 Se a mesma pessoa não agüentar testar várias lâmpadas?? 
 Até quando isto será feito?? 
CONCLUSÃO 
 O algoritmo não é a solução de um 
problema 
 É uma forma de chegar á solução 
 Não se aprende 
 A copiar algoritmos 
 Ler algoritmos prontos 
 A decorar algoritmos 
 Aprende-se 
 Construindo algoritmos 
 Testando algoritmos 
 
CONCLUSÃO - CONSTRUIR 
ALGORITMOS 
 Qual é o problema. 
 O que pretendemos do algoritmo 
 Definir quais são os dados que entram 
 Qual a situação inicial 
 O que é necessário para resolver o 
problema 
 Definir quais são os dados que saem 
 Qual a situação final 
 Que resultados devem ser apresentados 
CONCLUSÃO - CONSTRUIR 
ALGORITMOS 
 Definir o Algoritmo 
 Definir quais as instruções 
disponíveis/necessárias 
 Organizar as instruções de forma a 
resolver o problema 
 transformar as entradas na saída 
 Testar o algoritmo 
 Verificar se resolve o problema 
 Verificar se resolve todos os casos 
 Optimizar o algoritmos 
 Verificar se não utiliza recursos supérfluos 
ALGORITMOS: EXERCÍCIOS 
 Exercício 1 
 Elabore um algoritmo que mostre os passos 
necessários para trocar um pneu furado. 
ALGORITMOS: EXERCÍCIOS 
 Exercício 1 - Solução Possível 
 Pegue a chave de roda 
 Folgue os parafusos 
 Levante o carro com o macaco 
 Retire os parafusos 
 Coloque o pneu 
 Arroxe os parafusos 
 Baixe o macaco 
 Dê o arroxo final 
ALGORITMOS - EXERCÍCIOS 
 Liste os passos necessários para a solução do seguinte 
problema: 
 Um homem precisa atravessar um rio com um barco que 
possui capacidade de carregar apenas ele mesmo e 
mais uma de suas três cargas, que são: um leão, um 
bode e um fardo de capim. O que o homem deve fazer 
para conseguir atravessar o rio sem perder suas 
cargas? Sabendo que: o homem não pode deixar o 
bode e o capim juntos, se não o bode come o capim, e 
não pode deixar o leão e o bode juntos, se não o leão 
come o bode. 
 
ALGORITMOS - EXERCÍCIOS 
 Algoritmo – Possível Solução 
 
 Levar o bode 
 Voltar 
 Levar o capim 
 Trazer o bode 
 Levar o leão 
 Voltar 
 Levar o bode 
 
DESENVOLVENDO.. 
Algoritmos 
PSEUDO-CÓDIGO 
 Os algoritmos são descritos em uma linguagem 
chamada pseudocódigo 
 Algoritmos são independentes das linguagens de 
programação 
 Não existe um formalismo rígido de como deve 
ser escrito o algoritmo. 
 O algoritmo deve ser fácil de se interpretar e fácil 
de codificar 
REGRAS PARA CONSTRUÇÃO DO ALGORITMO 
 Para escrever um algoritmo precisamos 
descrever a seqüência de instruções, de 
maneira simples e objetiva 
 
 Usar somente um verbo por frase 
 Usar frases curtas e simples 
 Ser objetivo 
 Procurar usar palavras que não tenham 
sentido dúbio 
FASES DO ALGORITMO