Aula 21 de Métodos Computacionais em Economia - Interlúdio 2: Análise Numérica e Otimização

Essa aula não será formalmente discutida em sala de aula. De fato, precisaríamos de muitas aulas para fazer um apanhado das principais idéias. Usaremos esse espaço apenas para fazer alguns comentários e indicar possíveis referências que podem ser consultadas em tópicos específicos.

Na segunda parte do nosso curso sobre Machine Learning, alguns tópicos de Análise Numérica e Otimização Numérica serão mencionados e explicados informalmente quando aparecerem. Sem tentar ser exaustivo, entre eles estão:

1) Métodos que lidam com a solução de sistemas lineares. Particularmente a decomposição LU.
2) Métodos que lidam com a solução de sistemas não lineares. Particularmente o método de Newton.
3) Métodos que lidam com otimização numérica. Particularmente o método do gradiente e formas de restringir problemas de otimização.

Referências

Analysis of Numerical Methods - Eugene Isaacson and Herbert Bishop Keller

A First Look at Numerical Functional Analysis - W. W. Sawyer

Numerical methods in economics - Kenneth Rudd

Numerical methods in engineering with python - Jaan Kiusalaas

Aula 20 de Métodos Computacionais em Economia - Interlúdio 1: Métodos de Monte Carlo

Na nossa vigésima aula de métodos computacionais introduzimos técnicas de Monte Carlo. Esses são os slides usados em sala.

Abaixo temos os exemplos apresentados em sala de aula:

Relação entre as áreas do círculo e quadrado

Consistência do OLS

Album de figurinhas

Referências

Numerical methods in economics - Kenneth Judd [Capítulo 8]

Introdução aos métodos estatísticos para economia e finanças - Alexandre Carvalho, Daniel Cajueiro e Reinaldo Camargo.

Referências adicionais

Estatística sem Mistério

Soluções de Exercícios

Como são gerados os números aleatórios?

Aula Extra de Métodos Computacionais em Economia - Princípios de Programação Funcional

Nessa aula, o monitor do curso Cauê Melo gentilmente deu uma aula extra sobre Princípios de Programação Funcional em Python. Esses são os slides usados em sala.

Referências para essa aula:

John Backus: Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs

Programming in Scala - Martin Odersky, Lex Spoon, Bill Venners

Aula 19 de Métodos Computacionais em Economia - Compromisso entre eficiência temporal e espacial

Na nossa décima nona aula de métodos computacionais discutimos o compromisso entre eficiência temporal e espacial. Esses são os slides usados em sala.

Códigos usados em sala de aula

Ordenação por contagem

Referências para essa aula:

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

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

Aula 18: Quick sort

Na nossa décima oitava aula de métodos computacionais discutimos o algoritmo conhecido como Quick Sort e como aleatorização pode ser usada para melhorar a complexidade do algoritmo. Esses são os slides usados em sala.


Referências para essa aula:

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

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


Solução de exercícios

Cálculo da mediana com complexidade linear

Aula 17 de Métodos Computacionais em Economia - Melhoria Iterativa

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


Códigos usados em sala de aula

Marriage Stable Problem

Referências para essa aula:

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

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


Referências complementares

Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis - Alvin E. Roth e Marilda A. Oliveira Sotomayor

Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms - Donald Ervin Knuth

Soluções

College Problem Admission

Aula 16 de Métodos Computacionais em Economia - Estratégias Gananciosas

Na nossa décima sexta aula de métodos computacionais discutimos a estratégia conhecida como Gananciosa (ou Gulosa). Esses são os slides usados em sala.

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

Aula 15 de Métodos Computacionais em Economia - 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

Regressão linear segmentada

Multiplicação de cadeias de matrizes

Justificação de textos usando Programação Dinâmica

Maximizar a soma do produto dos elementos de uma pilha

Problema do troco

Aula Extra de Métodos Computacionais em Economia: Solução da prova de 2016

No dia 11 de abril, o monitor do curso Cauê Melo gentilmente deu uma aula extra para resolver a prova do curso de 2016 com a turma. Abaixo está a solução da prova que foi elaborada por ele e por Saulo Benchimol:

Encontrar o máximo usando recursões

Obtenção dos índices de uma sequencia de Fibonacci

Como testar se os números em um intervalo são números perfeitos?

Como testar se os números em um intervalo são números perfeitos?

Como encontrar o elemento que aparece na maioria?

Aula 14 de Métodos Computacionais em Economia - 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 - 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 - 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:

Cálculo da moda

Intersecção entre dois conjuntos

Eliminação gaussiana

Decomposição LU

Aula 11 de Métodos Computacionais em Economia - 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

Inversões

Quick sort

Conjunto de pontos mais próximos

Fecho convexo

Maior variação positiva