Métodos Computacionais 2021: Aula 18 - Exercícios resolvidos e Outros

 Referências para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Capítulo 9]

Combinatorial optimization: Algorithms and Complexity - Christos H Papadimitriou e Kenneth Steiglitz [Capítulo 12]

Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein [Capítulo 16]

Soluções da série de exercícios

Algoritmo de Prim para encontrar a MST de um grafo


Algoritmo de Kruskal para encontrar a MST de um grafo

4. Você pode resolver qualquer exercício dos Capítulos 13, 14 e 15 do livro
Tim Roughgarden - Algorithms Illuminated (Part 3): Greedy Algorithms and
Dynamic Programming. Enuncie o problema em português e apresente todos os
detalhes da sua solução. 

13.4 

Métodos Computacionais 2021: Aula 17 - Exercícios resolvidos e Outros

 

Códigos usados em sala de aula

Fibonacci com Memoization ou Bottom-Up

Programação dinâmica para resolver o problema da mochila

Programação dinâmica para encontrar os menores caminhos

Referências para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Capítulo 8]

Combinatorial optimization: Algorithms and Complexity - Christos H Papadimitriou e Kenneth Steiglitz [Capítulo 18]

Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein [Capítulo 15]

Soluções da série de exercícios

Problema do troco [Questão 1]

Justificação de textos usando Programação Dinâmica [Questão 2]

Regressão linear segmentada [Questão 3]

Maximizar a soma do produto dos elementos de uma pilha [Questão 4]

Multiplicação de cadeias de matrizes [Questão 6]

Capı́tulo 2 do livro Dynamic Programming: A computational tool – Art Lew e Holger Mauch.

Alocação ótima [Questão 7 (a)]

Busca binária [Questão 7 (e)]

Cobertura ótima [Questão 7 (f)]

7 g 

Questão 7 h  

7 i 

Questão 7 j

7 k 

Questão 7m

Investimento ótimo [Questão 7 (n)]

Investimento ótimo [Questão 7 (o)]

7 p

Questão 7q

7 r 

7s

Produção ótima [Questão 7 (y)]

Questão 7t

Questão 7v

Questão 7w 

Questão 7 ac

Métodos Computacionais 2021: Aula 16 - Exercícios resolvidos e Outros

 

Códigos usados em sala de aula

Branch and bound para resolver o problema da mochila


Referências para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Seção 12.2]

Combinatorial optimization: Algorithms and Complexity - Christos H Papadimitriou e Kenneth Steiglitz [Capítulo 18]

Referência complementar para estudar filas com prioridades

Data Structures and Algorithms in Python - Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser4. [Capítulo 9]

Soluçoes dos exercícios

1. Branch and bound para resolver o problema de alocação

2. Branch and bound para resolver encontrar os caminhos mais curtos de um grafo (Djkstra)

3. Branch and bound para resolver o problema do caixeiro viajante

4. Resolva qualquer problema do fim do capı́tulo 5 do livro Combinatorial Algorithms: Generation, Enumeration, and Search de Donald L. Kreher and
Douglas R. Stinson.

Capı́tulo 5 do livro Combinatorial Algorithms:
Generation, Enumeration, and Search de Donald L. Kreher and
Douglas R. Stinson.

5.4

5.9

Métodos Computacionais 2021: Aula 15 - Exercícios resolvidos e Outros

 
Códigos usados em sala de aula

Backtracking para gerar e resolver labirintos

Problema das N rainhas usando Backtracking

Subset sum usando backtracking

Longest integer subsequence usando backtracking

Referências para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Seção 12.1]

Lecture 3 do E-book Algorithms de Jeff Erickson.

Think recursively - Eric S. Roberts [Capítulo 8]

Referências complementares para essa aula:

Artificial intelligence: A modern approach - S. J. Russell and Peter Norvig [Capítulo 5]

Soluções de exercícios

3. Resta 1 usando backtracking
4. Slide Puzzle 15
5. Instant Insanity

6. Sudoku

7. Rota dos cavalos

8. M-coloring problem

9. Ciclos Hamiltonianos

10. Fim do capı́tulo 4 do livro
Combinatorial Algorithms: Generation, Enumeration, and Search
de Donald L. Kreher and Douglas R. Stinson. 

4.4 

4.7 

4.10 

4.13

Métodos Computacionais 2021: Aula 14 - Exercícios resolvidos e Outros

 Referências Adicionais para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Seções 6.1 e 6.2]

Solução de exercícios:

Unicidade de vetor [Questão 1]

Cálculo da moda [Questão 2]

Intersecção entre dois conjuntos [Questão 3]

Eliminação gaussiana [Questão 4]

Decomposição LU [Questão 5]

Métodos Computacionais 2021: Aula 13 - Exercícios resolvidos e Outros

 Abaixo temos os exemplos apresentados em sala de aula:

Merge sort

Referências Adicionais para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Capítulo 5]

Solução de exercícios:

Produto de matrizes [Questão 3]

Inversões [Questão 2]

Quick sort [Questão 1]

Conjunto de pontos mais próximos [Questão 4(a)

Fecho convexo[Questão 4(b)]

Fatorial [Questão 5]

Maior variação positiva [Questão 6]

Métodos Computacionais 2021: Aula 12 - Exercícios resolvidos e Outros

Abaixo temos os exemplos apresentados em sala de aula:

Torre de Hanoi

Busca binária

Insertion sort

Ordenação topológica

Permutações

Geração de todos os subconjuntos

Referências Adicionais para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Capítulo 4]

Soluções de exercícios


Gerar permutações lexicograficamente [Questão 3]

Movimentos da Torre de Hanoi para gerar todos os subconjuntos [Questão 4]

Knuth [Questão 5 (a)]

Knuth [Questão 5 (b)]

Knuth 5 (c) 

Knuth 5 (e)

Knuth 5 (h) 

Knuth 5 (i)

Knuth 6 c

Knuth 6 (e)

Knuth 6 f

Knuth 6 h