Algoritmos e Ciência da
Computação
Nivio Ziviani
Professor Titular do DCC/UFMG
Introdução à Ciência da Computação
DCC/UFMG, 19 de Outubro de 2007
LATIN – Laboratório para Tratamento da Informação
1
O que é um algoritmo?

Pode ser visto como uma seqüência de ações executáveis
para a obtenção de uma solução para um determinado tipo
de problema

É um procedimento (um conjunto finito de instruções bem
definidas) para executar alguma tarefa, a qual, dado um
estado inicial, termina em um estado final (Wikipedia)

Corresponde a uma descrição de um padrão de
comportamento, expresso em termos de um conjunto finito
de ações (Dijkstra, 1971)
LATIN – Laboratório para Tratamento da Informação
2
Por que estudar algoritmos?

Algoritmos e estruturas de dados formam o núcleo da
ciência da computação

Formam os componentes básicos de qualquer software

Aprender como programar está intimamente ligado a
algoritmos

Um algoritmo é a abstração de um programa

Logo, aprender algoritmos é crucial para quem deseja
desenvolver software de qualidade
LATIN – Laboratório para Tratamento da Informação
3
Qual a origem da palavra algoritmo?

Muhammad ibn Musa abu Djafar Al-Khorezmi

Algoritmo: vem de Al-Khorezmi
Al-Khorezmi: originário de Khorezmi (hoje Khiva, Uzbekistan)
Nascido por volta do ano 780, escreveu vários livros
Criou o conceito de zero
Aritmetica: introduz sistema numérico da India
Kitab al-jabr wa’l-muqabala: deu origem a palavra álgebra
Grande poder de abstração, se preocupava em reduzir o
número de operações necessárias em cada cálculo
Não foi o inventor do primeiro algoritmo, mas merece que o
conceito de algoritmo seja ligado ao seu nome
Foi sem dúvida o primeiro pensador algoritmico!








LATIN – Laboratório para Tratamento da Informação
4
Maneiras de ensinar algoritmos

Por tópicos ou tipos de problemas


Estruturas de dados básicas; ordenação;
pesquisa em memória principal; pesquisa em
memória secundária; grafos; processamento de
cadeias de caracteres; problemas NP-completo;
algoritmos aproximados
Paradigmas ou técnicas de projeto

Indução; recursividade; tentativa e erro; divisão e
conquista; balanceamento; programação
dinâmica; algoritmos gulosos; algoritmos
aproximados
LATIN – Laboratório para Tratamento da Informação
5
Algoritmos: eficiência
Buscar um registro:

Registros não ordenados

Registros ordenados
Registros ordenados com
info sobre a distribuição

LATIN – Laboratório para Tratamento da Informação
6
Algoritmos: eficiência
Descobrir quais cheques
foram descontados a partir do
saldo
Problema do caixeiro viajante
LATIN – Laboratório para Tratamento da Informação
7
Problema dos cheques
No primeiro dia de cada mês o Sr. Joaquim recebe o saldo bancário
de sua conta corrente. Baseado apenas no saldo bancário o Sr.
Joaquim quer descobrir quais os cheques dados por ele foram
descontados até a data de emissão do saldo. O Sr. Joaquim sabe
que o valor dos n cheques dados por ele são todos diferentes.
1
Cheques: 20
bits: 0
2
3
60 30
1
0
4
10
1
Total = 120
Saldo = 50
Descontados = 70 (quais cheques?)
Solução: tentar todas as combinações (24 = 16 para o exemplo)
Quantas são: 2n possibilidades
20 cheques: 220 ?
30 cheques: 230 ?
2n
LATIN – Laboratório para Tratamento da Informação
8
Problema do Caixeiro Viajante
<C1,C3,C4,C2,C1> = 24
Como encontrar a menor rota?
Resp.: tentar todas as rotas!
Quantas são? (n-1)!
20! = 2432902008176640000
40! = 815915283247897734345611269596115894272000000000
LATIN – Laboratório para Tratamento da Informação
9
P vs NP: prêmio de 1 milhão de dólares

Clay Mathematics Institute (CMI), Cambridge,
Massachusetts

Comitê do CMI selecionou sete problemas (prêmio de US$1
milhão para cada um)

Foco em problemas clássicos importantes sem solução por
muitos anos

P vs NP é um deles

Teoria fornece um mecanismo que permite descobrir se um
problema é “fácil” ou “difícil”

Existem milhares de problemas na natureza que são “difíceis”

Se alguém encontrar um algoritmo eficiente para qualquer um deles
estará resolvendo todos os outros

Ninguém conseguiu provar que tal algoritmo não existe
LATIN – Laboratório para Tratamento da Informação
10
Engenharia de software?
Programação: coração da Ciência da Computação

Algoritmos e estruturas de dados + paradigmas de programação

Mais arte do que ciência ou engenharia (trilogia sobre algoritmos e
estruturas de dados de Knuth se chama The Art of Computer Programming)


A tarefa de programar é nobre?
Importante distinguir:


Pessoas capazes de tornar uma solução em um programa
Pessoas capazes de projetar a solução de um problema e então
transformá-la em um programa



Um programador completo, chamado de engenheiro, é capaz de
conduzir todo o processo, da análise à implementação
Programar deveria trazer satisfação pessoal
Nós engenheiros produzimos os melhores programas
LATIN – Laboratório para Tratamento da Informação
11
A Computação como Ciência
Que problemas podemos resolver?
Modelos e complexidade dos problemas
Como podemos resolver um problema?
Projeto de algoritmos
Com que rapidez podemos resolvê-lo?
Análise de algoritmos
LATIN – Laboratório para Tratamento da Informação
12
Computação: Ciência e Engenharia
Matemática
Computação
Biologia
Engenharia
Eletrônica
Física
LATIN – Laboratório para Tratamento da Informação
13
Algoritmos
Matemática
Análise
Projeto de
Algoritmos
Realidade
Abstração
Implementação
Software
Aplicação
Recuperação
de Informação
LATIN – Laboratório para Tratamento da Informação
14
Exemplo
Análise
Software
Projeto
Abstração
Busca em texto
Aplicação
Recuperação
de Informação
LATIN – Laboratório para Tratamento da Informação
15
Algoritmos e Ciência da Computação
Para aprender algoritmos é necessário ter a
combinação correta de conhecimentos matemáticos e
bom senso
O balanceamento entre teoria e prática é sempre uma
tarefa difícil
A melhor teoria é inspirada na prática e a
melhor prática é inspirada na teoria.
Donald Knuth, 1989
LATIN – Laboratório para Tratamento da Informação
16
?
LATIN – Laboratório para Tratamento da Informação
17