Apresentação e Introdução
Prof. Dr. Leandro Balby Marinho
http//www.dsc.ufcg.edu.br/~lbmarinho
Análise e Técnicas de Algoritmos
(Slides adaptados de Jorge Figueiredo e Tiago Massoni)
Por que vocês estão aqui?

Curso obrigatório (Por que?)

Algoritmos são o coração do curso

Separa “homens” de “meninos”


Muitos outros cursos precisam de noções
de algoritmos
Ajuda o aluno a desenvolver a habilidade
de projetar algoritmos corretos e entender
sua eficiência
Relevância e motivação
Evitar reinventar a roda
Ajudar no desenvolvimento de seus
algoritmos
O conhecimento de algoritmos bem
estabelecidos é fonte de inspiração
Relevância e motivação
Ajudar a entender ferramentas que se baseiam
em algoritmos particulares
ferramentas de compressão de dados
mecanismos de busca na Web
bancos de dados
roteamento na internet
sequenciamento de DNA
Ex.: PageRank
Ex.: Menor Caminho
Ex.: Alinhamento de Sequencia
Por que ATAL é tão difícil?
Requer capacidade de abstração,
raciocínio, concentração e criatividade.
O que fazer?
participação em sala de aula
horário de
atendimento
pra valer exercícios
Não ao acúmulo de assunto
Não esperar nova chance (reposição)
Fazer
Algumas Dicas
• Participem em sala de aula. Façam perguntas
– Isso ajuda a conhecer o que a turma não está
entendendo
• Façam os exercícios
– resolvam, se possível, novos problemas.
– consolidam os algoritmos estudados em sala de
aula
• Leiam atentamente as questões das provas
– muita gente erra pelo fato de não entender o que
foi pedido
Algoritmos
Procedimentos computacionais que
tomam algum valor (ou conjunto)
como entrada e produz um valor
(ou conjunto) como saída
Problemas computacionais
Especificam a relação entre a entrada e a saída desejada
Ordenação
Entrada: Uma seqüência de n números ‹a1, a2, ..., an›.
Saída: Uma reordenação da seqûëncia de entrada ‹a'1, a'2, ...,
a'n›,
onde a'1 ≤ a'2 ≤ ... ≤ a'n.
Número Primo
Entrada: Uma número natural q.
Saída: sim ou não, dependendo se q é primo.
Instância do problema
• possível valor para a entrada
– ‹45, 7, 13, 23, 2› é uma instância para o
problema da ordenação
– 29 é uma instância para o problema dos
primos.
Corretude
Como afirmar que o algoritmo
é correto?
Insertion Sort
Em termos gerais, ele percorre um vetor de elementos
da esquerda para a direita e à medida que avança vai
deixando os elementos mais à esquerda ordenados
Insertion Sort
A:
j
1
ORDENADO
chave
n
Algoritmo: insertion sort
1
2
45
7
3
4
13 23
5
2
Como ler um
algoritmo?
Algoritmo: insertion sort
1
2
45
7
3
4
13 23
5
2
Algoritmo: insertion sort
1
2
3
4
5
45
7
13 23
2
7
45 13 23
2
Algoritmo: insertion sort
1
2
3
4
5
45
7
13 23
2
7
45 13 23
2
Algoritmo: insertion sort
1
2
3
4
5
45
7
13 23
2
7
45 13 23
2
7
13 45 23
2
Algoritmo: insertion sort
1
2
3
4
5
45
7
13 23
2
7
45 13 23
2
7
13 45 23
2
Algoritmo: insertion sort
1
2
3
4
5
45
7
13 23
2
7
45 13 23
2
7
13 45 23
2
7
13 23 45
2
Algoritmo: insertion sort
1
2
3
4
5
45
7
13 23
2
7
45 13 23
2
7
13 45 23
2
7
13 23 45
2
Algoritmo: insertion sort
1
2
3
4
5
45
7
13 23
2
7
45 13 23
2
7
13 45 23
2
7
13 23 45
2
2
7
13 23 45
Como descrever algoritmos?
Linguagem
Natural
Expressividade
Flexibilidade
Código
Controle
Concisão
Estrutura
Formal
Como descrever algoritmos?
Linguagem
Natural
Código
Expressividade
Flexibilidade
Controle
Concisão
Estrutura
Formal
Pseudo-Código
Reduzir ambiguidade
Abstrair detalhes não importantes
Fácil de ser assimilado por
humanos
Pré-requisitos
– Programação
– Estrutura de dados
– Matemática discreta
– Grafos
Horários e Atendimento
• Horário e Sala:
–
Segundas e Quintas, CD105
• Professor: sala 205 – DSC
–
Atendimento: hora marcada por
email
7
Página da Disciplina
http://www.dsc.ufcg.edu.br/~lbmarinho/atal_ap
res_2011.2.html
Conteúdo
Parte I – análise de algoritmos
Corretude de algoritmos
Análise de algoritmos
Recorrências
Análise de algoritmos de ordenação
Análise Amortizada
Conteúdo
Parte II – técnicas de projeto de
algoritmos
Projeto de algoritmos, força bruta
Backtracking
Branch and Bounds
Greedy
Método Húngaro
Divisão e conquista
Programação dinâmica
Conteúdo
Parte III – tópicos avançados
algoritmos para grafos
geometria computacional
problemas NP-completos, computabilidade
Bibliografia
Avaliações
Provas: 70%
Minitestes: 30%
Exercícios e Miniprojetos: Bônus na
Média