Aula 15 de Métodos Computacionais em Economia (2018) - Programação Dinâmica

Na nossa décima quinta aula de métodos computacionais discutimos a estratégia conhecida como Programação Dinâmica. Esses são os slides usados em sala.

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]


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

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

Aula 14 de Métodos Computacionais em Economia (2018) - Branch and Bound

Na nossa décima quarta aula de métodos computacionais discutimos a estratégia conhecida como Branch e Bound. Esses são os slides usados em sala.


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. Goldwasser [Capítulo 9]

Soluçoes dos exercícios

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

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

Branch and bound para resolver o problema do caixeiro viajante

Aula 13 de Métodos Computacionais em Economia (2018) - Backtracking

Na nossa décima terceira aula de métodos computacionais discutimos a estratégia conhecida como Backtracking. Esses são os slides usados em sala.

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

Resta 1 usando backtracking

Slide Puzzle 15

Instant Insanity

Sudoku

Rota dos cavalos

M-coloring problem

Aula 12 de Métodos Computacionais em Economia (2018) - Transformação e Conquista

Na nossa décima segunda aula de métodos computacionais discutimos a estratégia conhecida como Transformação e Conquista. Esses são os slides usados em sala.


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]

Aula 11 de Métodos Computacionais em Economia (2018) - Divisão e Conquista

Na nossa décima primeira aula de métodos computacionais discutimos a estratégia conhecida como Divisão e Conquista. Esses são os slides usados em sala.

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]

Aula 10 de Métodos Computacionais em Economia (2018) - Redução e Conquista

Na nossa décima aula de métodos computacionais discutimos a estratégia conhecida como Redução e Conquista. Esses são os slides usados em sala.

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]

Aula 9 de Métodos Computacionais em Economia (2018) - Força Bruta III - Busca Exaustiva em Grafos

Na nossa nona aula de métodos computacionais discutimos os algoritmos BFS e DFS que promovem busca exaustiva em grafos e várias de suas aplicações. Esses são os slides usados em sala.

Abaixo temos os exemplos apresentados em sala de aula:

Análise empírica de redes

Como implementar o algoritmo de busca exaustiva em grafos conhecido como breadth first search - BFS (busca em largura)?

Como implementar o algoritmo de busca exaustiva em grafos conhecido como depth first search - DFS (Busca em profundidade)?

Referências Adicionais para essa aula:

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

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

Referências complementares para essa aula:

Networks: An Introduction - Mark Newman

Soluções de exercícios:

Como implementar BFS e DFS em Python e extrair informações úteis de um grafo, como conectividade, aciclicidade, etc?

Problema das jarras

Aula 8 de Métodos Computacionais em Economia (2018) - Força Bruta II - Busca Exaustiva

Na nossa oitava aula de métodos computacionais discutimos vários problemas clássicos usando o método de busca exaustiva. Nessa aula, vimos nosso primeiro problema com sabor de teoria econômico - o chamado problema Marriage-Matching. A solução apresentada foi uma baseada em busca exaustiva. Obviamente, nas próximas aulas iremos aprender estratégias que produzam algoritmos menos custosos. Esses são os slides usados em sala.

Abaixo temos os exemplos apresentados em sala de aula:

Existem bibliotecas prontas em python para gerar permutações e combinações?

Como implementar uma solução computacional para o problema do caixeiro viajante?

Como implementar uma solução computacional para o problema da mochila?

Como implementar uma solução computacional para o problema do casamento (marriage-matching)?

Referências Adicionais para essa aula:

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

Referências Complementares:

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation -
William J. Cook

The Art of Computer Programming, Volume 4A: Combinatorial Algorithms - Donald E. Knuth

Aula 7 de Métodos Computacionais em Economia (2018) - Força Bruta

Na nossa sétima aula de métodos computacionais discutimos vários problemas clássicos usando o método de força bruta (usando a definição do problema). Obviamente, nas próximas aulas iremos aprender estratégias que produzam algoritmos menos custosos. Esses são os slides usados em sala.

Abaixo temos os exemplos apresentados em sala de aula:

Algoritmos de ordenação com complexidade quadrática

Cálculo de máximo e mínimo de uma sequência

Busca linear em uma lista

Cálculo de determinantes usando cofatores

Produto de matrizes em Python

Par mais próximo em python

Substring matching

Fecho convexo

Referências Adicionais para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Seções 3.1, 3.2 e 3.3]

Referências Complementares:

Computational Geometry: Algorithms and Applications - Mark de Berg and Otfried Cheong

Soluções de exercícios

Tetrominoes [Questão 2]

Josephus [Questão 8]


Locomoção de robôs [Questão 9 (f)]

Aula 6 de Métodos Computacionais em Economia (2018) - Filas e Pilhas

Na nossa sexta aula de métodos computacionais discutimos duas coleções importantes de dados: pilhas e filas. Esses são os slides usados em sala.

Abaixo temos os exemplos apresentados em sala de aula:

Como implementar uma pilha em python?

Como implementar uma fila em python?

Como python aloca memória dinamicamente para uma lista?


Referências Adicionais para essa aula:

Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein [Seções 10.1, 17.2 and 17.4]

Data Structures and Algorithms in Python - Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser [Seções 5.3, 6.1, 6.2]

Fundamentals of Python: Data Structures - Kenneth Lambert [Capítulos 7 e 8]

Data Structures and Algorithms Using Python - Rance D. Necaise [Capítulos 7 e 8]

Solução da série de exercícios

Você pode dar um exemplo de um algoritmo que verifica se um número é um palíndromo usando pilha?

Como usar uma pilha para gerar todas as permutações de um conjunto?

Algoritmo não recursivo para gerar todos os subconjuntos de um dado conjunto

Chamadas recursivas da torre de Hanoii