Construção de Algoritmos
e Programação
Prof. Dr. Ednaldo Pizzolato
DC - UFSCar
Apresentação
Disciplina
que
fornecerá
instrumentos para que o aluno
aprenda a desenvolver soluções
computacionais para problemas bem
determinados.
Fazem parte do escopo da disciplina
o aprendizado de fluxogramas,
algoritmo e linguagem C.
Apresentação
Avaliação:
Existem atividades práticas (AP) que
auxiliam o aprendizado. A média das
avaliações práticas terá peso correspondente a 20% das avaliações na
média final.
Apresentação
Avaliação:
Existem também as avaliações
teóricas cuja média corresponderá a
80% da média final.
Assim, a média final (MF) será:
MF = 20% MAP + 80% MAT
Apresentação
Avaliação:
Se o aluno não obtiver média igual
ou superior a 6, tal aluno deverá
fazer uma prova extra chamada de
prova substitutiva que substituirá
(em benefício do aluno) sua pior
nota.
Apresentação
Avaliação:
A SUB não poderá ser feita para
aumentar a nota final.
Caso o aluno tenha feito a SUB, sua
média nunca será superior a 7.
Apresentação
Avaliação:
Caso o aluno mesmo com a sub não tenha
conseguido obter média de aprovação (igual ou
superior a 6), e caso o mesmo aluno tenha obtido
média igual ou superior a 5, poderá realizar uma
prova de recuperação no início do próximo
semestre. Tal prova versará sobre todo o conteúdo e
a média final será a média aritmética entre a média
final obtida com a sub e a nota da prova de
recuperação. Quem fizer a recuperação e conseguir
aprovação terá média final 6.
Apresentação
Aulas:
As aulas acontecerão no laboratório
(com computadores). Assim, será
possível testar as informações
imediatamente (bem como tirar
dúvidas e fazer experimentos
diferentes).
Apresentação
Aulas:
As provas práticas acontecerão também
no laboratório. Elas serão questões
relativas às atividades práticas que os
alunos deverão fazer em casa. Ou seja,
as atividades práticas terão suas notas
através das provas práticas.
Apresentação
Aulas:
As provas teóricas acontecerão na
sala oficial divulgada pela UFSCar.
Elas terão questões relativas ao
conteúdo ministrado durante o
período.
Apresentação
Datas:
Serão 3 provas e uma substitutiva.
Acontecerão nos seguintes dias:
P1 – 14/04
P2 – 12/05
P3 – 23/06
Sub – 30/06
Apresentação
Material de Apoio:
Haverá uma área de apoio no
MOODLE que permitirá que o
aluno faça downloads de slides.
Essa área, na verdade, servirá de
apoio para a disciplina.
www.moodle.ufscar.br
Apresentação
Bibliografia:
Senne, E.L.F. – Primeiro curso de programação
em C, Visual Books, 2003.
Kernighan, B.W. & Ritch, D.M. – C: A
linguagem de Programação, Rio de Janeiro,
Campus, 1986.
Mizrahi, V. – Treinamento em Liguagem C –
Módulo 1 e 2, São Paulo, McGraw-Hill, 1990.
Apresentação
Bibliografia:
Medina, M. & Fertig, C. - Algoritmos e
Programação – Teoria e Prática, Novatec, 2005.
Tremblay, J-P. & Bunt, R. - Ciência dos
Computadores – Uma Abordagem Algoritmica,
McGraw-Hill, 1981.
INTRODUÇÃO
Área que estuda os computadores
e o que eles podem fazer.
COMPUTAÇÃO
INTRODUÇÃO
Programação
software
Equipamento
hardware
INTRODUÇÃO
• Hardware
É a parte que você chuta
– São os equipamentos e
dispositivos eletrônicos, elétricos
e mecânicos que compõem o
computador
• Software
É a parte que você xinga
– São os programas e aplicativos
que contêm instruções para
comandar o hardware
INTRODUÇÃO
Programação
software
hardware
INTRODUÇÃO
Entrada
processamento
Saída
INTRODUÇÃO
Exemplo: Cálculo da média entre 3 números
Entradas: ???
Saídas: ???
10 20 30
20
INTRODUÇÃO
Teclado
Mouse
Modem
MODELO DE COMPUTADOR
Entrada
Saída
Monitor
Impressora
Modem
Unidade de
processamento
Memória
Primária
Secundária
Pentium
Athlon
Motorola
+
Co-processador
Modelo de computador
• Memória
•Endereçamento
Identificação de onde as
informações estão
•Capacidade
Quantidade de
informação que pode ser
armazenada
– Armazenamento de dados e
programas
•Volatilidade
Exigência de eletricidade
Entrada
Saída
Unidade de
processamento
Memória
•Velocidade
Taxa de transferência dos
dados para
processamento
Tipos básicos
• Memória
Nunca conte
com isso!!!
– Não existem posições vazias
– Há sempre bits em posições de
memória
• Pode-se não saber o que está lá
• Em posições com conteúdo
desconhecido, diz-se que existe “lixo”
– Alguns compiladores mais modernos, mas
não todos, tendem a ter bits zero nas áreas de
dados
INTRODUÇÃO
• Hardware e periféricos executam operações
sob controle da UCP (unidade central de
processamento)
• UCP segue os comandos armazenados na
memória primária
• O sistema operacional é o conjunto básico de
comandos que gerenciam o computador
– Gerencia também o uso de outros
programas
•
•
•
•
Editores de texto
Planilhas de cálculo
Jogos
Programas em geral... feitos pelo usuário
INTRODUÇÃO
Aplicativos
S.O.
Hardware
Periféricos
Sistemas operacionais
• Exemplos de S.O.
(principais)
–
–
–
–
–
–
–
–
–
–
–
–
–
–
1961 – CTSS
1966 – DOS/360 (IBM)
1969 – Unix
1970 – DOS/Batch 11
(PDP-11)
1976 – CP/M
1978 – VMS
1981 – MS/DOS
(Microsoft)
1981 – SunOS
1984 – MacOS (McIntosh)
1985 – AmigaOS
1985 – Windows 1.0
1987 – Minix
1987 – IRIX (SGI)
1987 – OS/2 (IBM)
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
1987 – Windows 2.0
1989 – SCO Unix
1991 – Linux
1992 – Windows 3.1
1993 – FreeBSD
1993 – Windows NT
3.1
1995 – Windows 95
1997 – MacOS 7.6
1998 – Windows 98
1999 – MacOS 8
2000 – Windows 2000
2000 – Windows ME
2001 – Windows XP
2001 – MacOS X
2003 – Windows 2003
Server
2005 – Windows Vista
Aplicativos
Aplicativos
Algoritmo
Linguagem de Programação
Tradutor ou Compilador
Instruções em 0s e 1s
SOLUÇÃO
ALGORITMICA
• Algoritmo:
– Definição informal
Conjunto finito de instruções que, em
um tempo também finito, transforma
um conjunto de dados em um
conjunto de dados processados, com o
intuito de resolver um problema. Uma
linguagem de programação permite
que um algoritmo seja “convertido”
em programa.
Algoritmos
• Algoritmos envolvem
– Linguagem algorítmica
• Formalização dos comandos
• Formalização de estruturas de controle
– Ferramental de representação de dados
• Tipos de dados variados
• Composições de tipos de dados
– Metodologia de desenvolvimento
• Abordagem de problemas e proposição de solução
– Objetivo final
• Algoritmos têm como objetivo ser a base para programas
SOLUÇÃO
ALGORITMICA
• Lógica de interpretação
– Sequencia linear
• Remoção de ambiguidade
• Abstração da execução
– Velocidade arbitrária
– Memória infinita
– Sem limitação para a representação de
informação
SOLUÇÃO
ALGORITMICA
• Ciclo de desenvolvimento
– Entendimento do problema
– Entendimento da solução nãoalgorítmica
– Proposição da solução algorítmica
– Depuração da solução: testes,
correções, reavaliação da solução
– Avaliação da solução quanto a
melhorias e desempenho
SOLUÇÃO
ALGORITMICA
• Entendimento do problema
– Avaliação de qual o problema
– Determinação com clareza de quais são os dados de
que se dispõe
– Determinação com clareza de qual a resposta à qual
se precisa chegar
SOLUÇÃO
ALGORITMICA
• Entendimento da solução não-algorítmica
– Aquisição de conhecimento (ou consulta a alguém
que o tenha) para que se tenha uma solução para o
problema
• Proposição da solução algorítmica
– Desenvolvimento do algoritmo
• Estruturação organizada
• Abordagem com enfoque do panorama mais geral para
o mais específico
SOLUÇÃO
ALGORITMICA
• Depuração da solução: testes, correções, reavaliação da
solução
– Avaliação do algoritmo para certificar que as respostas
produzidas são as esperadas
• Checagem para diferentes entradas das saídas produzidas
– Correção e adequação do algoritmo frente às deficiências
encontradas
• Avaliação da solução quanto a melhorias e desempenho
– Reavaliar a solução proposta
• Busca de melhores opções para a solução proposta
• Avaliação das partes do algoritmo para torná-lo mais rápido
(usando um menor número do comandos/operações)
Aplicativos
Algoritmo
Aplicativos
Linguagem de Programação
Tradutor ou Compilador
Instruções em 0s e 1s
Programação
• Máquina programável
– Capacidade de executar instruções a
partir de uma lista de comandos
especificada por um programador
• Cartões perfurados
• Fitas de papel perfurado
• HD, CD, DVD etc.
Programação
• No começo:
– Os programas eram feitos através da mudança física
dos circuitos (chaves).
• Depois:
– Evoluiu para programas armazenados;
– A máquina é capaz de obter a lista de comandos e
armazená-la internamente, em um dispositivo
chamado memória.
• Trabalhos:
–
–
–
–
História dos computadores até 1900
História dos computadores de 1901 a 1960
História dos computadores de 1961 a 2009
História da programação
Trabalho
Trabalhos (em powerpoint):
Título
Número do Trabalho
Nome de cada membro do grupo
Data da Entrega
Conteúdo
Bibliografia
Trabalho
• Perguntas a serem respondidas
–
–
–
–
–
–
O que é um ábaco?
O que é uma régua de cálculo?
O que são os bastões de Napier?
O que são válvulas, relés e transístores?
O que são bugs e por que esta denominação?
Qual foi a participação de Da Vinci, Pascal,
Babbage, Ada Augusta, Hollerith, Von
Neumann entre outros na história dos
computadores e da programação?
Trabalho
• Bibliografia
– Ciência dos Computadores (Livro)
–
–
–
–
–
–
http://www.hitmill.com/computers/history/index.html
http://lecture.eingang.org/toc.html
http://www.islandnet.com/~kpolsson/comphist/
http://www.maxmon.com/history.htm
http://inventors.about.com/library/weekly/aa051599.htm
Outros sites na internet
Programação
• Voltando ao assunto de programação...
Programação
• Como era no início...
– Instruções do processador
• Exigia conhecimento das instruções (em
binário?!?)
• Exigia paciência para identificar e
corrigir erros
• A chance de erros era grande
10001010 11000100
8AC416
Programação
• Linguagem montadora
– Mnemônicos para as instruções do
processador
8AC416
MOV
ADD
SUB
JMP
...
Programação
• Linguagem montadora
– Um programa específico
• Interpreta os mnemônicos
• Gera a instrução adequada para o
processador
– Nome do programa
• Programa montador
• Em inglês: assembler
– Nome da “linguagem” dos
mnemônicos
• Assembly
Programação
• Linguagem montadora
– Dificuldades
• Ainda sujeita a erros
• Ainda exigia atenção do programador
• O assembly era específico para cada processador
– Vantagens
• Documentação
– O texto assembly admitia comentários escritos
pelo programador
– Os comentários eram simplesmente ignorados
pelo programa montador
Programação
• Linguagem de nível alto
– Substitui o assembly por instruções
independentes do processador
– O programador não escreve
diretamente as instruções do
processador, mas um conjunto de
comandos mais abstrato
Copia o conteúdo da
B=A
posição de memória
chamada A para B
Programação
• Linguagem de nível alto
– Um programa interpreta o código escrito na
linguagem
• Equipamentos distintos interpretam o mesmo
código para gerar instruções para seus próprios
processadores
– Vantagens
• Um mesmo código de nível alto pode ser usado
em várias máquinas diferentes
– Desvantagens
• Máquinas diferentes exigem programas
específicos para interpretar a linguagem
• Nem sempre estes programas interpretam
exatamente a mesma linguagem
– Dialetos!!!
Programação
C=A+B
A fica no endereço A0FF0216
B fica no endereço A0FF0616
C fica no endereço A0FF0A16
Carrega o conteúdo de A0FF0216
Carrega o conteúdo de A0FF0616
Soma os valores carregados
Armazena o resultado em A0FF0A16
10010100
00110101
11001101
11001001
00111101
00001101
11101010
00101001
11001010
00111101
00001101
11101010
00101001
11001010
01010101
10101010
00101001
...
Compiladores e Interpretadores
Algoritmo
Linguagem de Programação
Aplicativos
Tradutor ou Compilador
Instruções em 0s e 1s
Compiladores e Interpretadores
• Compilador
– Interpreta o código de nível alto inteiro e gera
todo o conjunto de instruções
– Se houver erro, nenhuma instrução é gerada
- Somente executa se não houver erros
(sintáticos) no programa
• Interpretador
– Interpreta o código de nível alto comando por
comando e o executa na hora
– Se houver erro, o programa executa até o ponto
do erro, então pára
- Resultados parciais podem ser obtidos
antes do erro
Compiladores e Interpretadores
• Um compilador converte um programa
(escrito em uma linguagem de
programação)
em
um
código
compreendido pelo computador.
• Um interpretador também executa tarefa
semelhante à de um compilador, mas a
diferença está no fato de que o
interpretador terá que executar a mesma
tarefa de “tradução” a cada vez que o
usuário executar o programa.
Compiladores e Interpretadores
Bla...
• O interpretador tem
que ouvir “pouco a
pouco” o que o
locutor está falando
e traduzir para todos
os ouvintes. Se o
locutor
for
apresentar
10
palestras iguais, o
intérprete terá que
traduzir 10 vezes...
Compiladores e Interpretadores
Bla...
• O compilador ouve
tudo uma única vez e
cria um “livro” traduzido com o conteúdo
da palestra do locutor.
Assim, o trabalho do
compilador ocorre somente uma vez e as
coisas ficam bem mais
rápidas...
Compiladores e Interpretadores
Programa
em
uma
linguagem
Algoritmo
Tradução
Lisp
C#
Java
C
C++
Pascal
Cobol
PL/I
Executável
Aplicativos
Algoritmo
Linguagem de Programação
Tradutor ou Compilador
Aplicativos
Instruções em 0s e 1s
Bases
• Sistema de base decimal
– Composto de 10 algarismos (0 a 9)
– Algarismo é o termo usado para denominar
os símbolos de zero a nove e é em
homenagem a um matemático chamado alKhowarizmi.
– 5.326 = 5 x 1000 + 3 x 100 + 2 x 10 + 6 x 1
–
= 5 x 103 + 3 x 102 + 2 x 101 + 6 x 100
Bases
• Sistema binário
– Composto de 0s e 1s
– Nro = bn x 2n + bn-1 x 2n-1 + .... + b0 x 20
– Exemplo:
•
•
•
•
01000010
00001101
00001010
01101001
– Bits  0s e 1s
– Byte  agrupamento de 8 bits
– Palavra  agrupamento de 4 bytes
Bases
• Conversão de bases
• 61  base 2 ??
• 61 2
•
1 30 2
•
0 15 2
•
1 7 2
•
1 3 2
•
1 1 2
•
1 0
111101
Bases
•
•
•
•
•
•
•
•
•
•
•
•
111101
1 x 25 = 32
+
1 x 24 = 16
+
1 x 23 = 08
+
1 x 22 = 04
+
0 x 21 = 00
+
1 x 20 = 01
32 + 16 + 08 + 04 + 01 = 61
Bases
• Mudar da base 10 para a base 8
(octal)
– 61
– 120
– 56
Bases
• Base Hexadecimal
– Valores entre 0 e F, onde
•
•
•
•
•
•
A = 10
B = 11
C = 12
D = 13
E = 14
F = 15
Portanto, 4A3F16 = 1900710
16.384 + 2.560 + 48 + 15
Bases
• Operações
– Soma de binários
1 1
1 1 1 0
•
•
•
•
0+0=0
0+1=1
1+0=1
1 + 1 = 0 (e vai 1)
0011
1011
Bases
• Operações
– Subtração de binários
•
•
•
•
0-0=0
1-1=0
1-0=1
0 - 1 = 1 (e empresta 1)
Bases
•
Operações
–
Adição de Hexadecimais
1
1
B C 7
3 4 B
F 1 2
7 + 11 = 18 – 16 = 2 (e vai 1)
1 + 12 + 4 = 17 – 16 = 1 (e vai 1)
Representação
• Código ASCII
– Representação interna (computador)
de símbolos em binário
•
•
•
•
A = 0100 0001
B = 0100 0010
C = 0100 0011
...
Motivação - programação
• Vamos brincar um pouco de programar!
PROBLEMA SIMPLES
• COMANDOS
–
–
–
–
F (FRENTE)
T (TRAS)
D (DIREITA)
E (ESQUERDA)
PROBLEMA SIMPLES
• SOLUÇÃO 1
–
–
–
–
–
–
–
–
–
DD
FFF
EE
FF
DDDD
TT
EEEE
FFF
DDDDD
PROBLEMA SIMPLES
• SOLUÇÃO 2
–
–
–
–
D2
F3
D3
F3
PERGUNTA: Pode-se trocar a ordem dos
comandos?
PROBLEMA SIMPLES 2
Siga em frente
até a prefeitura.
Depois vire à
direita e siga em
frente por um
quarteirão
e
meio.
PROBLEMA SIMPLES 2
Siga em frente
significa que
os sinais de
trânsito devem
ser respeitados.
PROBLEMA SIMPLES 3
Um professor de física
necessita de uma solução
computacional
que
resolva o problema de
cálculo da velocidade
final de um objeto, solto
do repouso na direção
vertical a partir de uma
dada altura, quando este
atinge o solo. Este
problema é parte de um
outro problema maior em
que o professor está
trabalhando, em cinética.
v0 = 0
v=?
PROBLEMA SIMPLES 3
v0 = 0
Entendimento do problema
• É um caso de queda livre
Entendimento da solução
não-algorítmica
• Consultando o material do
cursinho
• Fazendo as manipulações
algébricas adequadas
• Solução:
v  2hg
v  4,43 h
h – altura
g – aceleração gravitacional
v  2hg
PROBLEMA SIMPLES 3
– Desenvolvimento do algoritmo
algoritmo quedaLivre
início
Obtenha o valor da altura
Calcule a velocidade
Devolva como resposta a velocidade calculada
fim
Esboço inicial
PROBLEMA SIMPLES 3
– Desenvolvimento do algoritmo
algoritmo quedaLivre
início
Obtenha o valor para “altura”
Calcule “velocidade” pela fórmula “
Devolva o valor de “velocidade”
fim
Esboço mais refinado
velocidade 4,43 altura
”
PROBLEMA SIMPLES 3
• Exemplo
– Desenvolvimento do algoritmo
algoritmo quedaLivre
{ Calcula a velocidade de uma partícula ao atingir o solo
após ser largada do repouso a uma dada altura }
declare altura, velocidade: real
início
leia(altura)
velocidade  4,43 * raiz(altura)
escreva(velocidade)
fim
Versão final
PROBLEMA SIMPLES 3
• Exemplo
– Observações
• O problema proposto foi bastante específico
– A altura deve ser dada em metros e o valor deve
ser positivo
– A velocidade resultante é em m/s
• O algoritmo não é geral
–
–
–
–
–
O valor da gravidade foi estimado em 9,8m/s2
Não se admite outro valor para g
Não se admite velocidade inicial diferente de zero
Não se considera resistência do ar
Etc. etc. etc.
PROBLEMA SIMPLES 3
– Teste do algoritmo
• Acompanhamento dos cálculos
realizados
Valor para h
8,00
9,50
13,73
Valor
esperado
12,52
13,65
16,40
Valor
calculado
12,50
13,62
16,38
PROBLEMA SIMPLES 3
• Exemplo
– Melhorias
• Verificou-se que o cálculo intermediário
da velocidade podia ser omitido
Algoritmo QuedaLivre
{ Calcula a velocidade de uma partícula ao atingir o solo
após ser largada do repouso a uma dada altura }
Declare Altura, Velocidade: real
Início
Leia (Altura)
Velocidade  4,43 * Raiz(Altura)
Escreva (Velocidade)
Fim
Versão final
PROBLEMA SIMPLES 3
• Exemplo
– Melhorias
algoritmo quedaLivre
Algoritmo
QuedaLivre
{ Calcula a velocidade de uma partícula ao atingir o solo
após ser largada do repouso a uma dada altura }
Declare Altura:
declare
Altura, Velocidade:
real
real
Início
início
Leia (altura)
leia
(Altura)
Velocidade
 4,43
* Raiz(Altura)
escreva
(4,43
* raiz(altura))
fim
Escreva (Velocidade)
Fim
Versão final