Search This Blog

Saturday, July 17, 2021

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

 



Códigos usados em sala de aula

Implementação do problema da locadora usando programação dinâmica

Referências

Numerical Methods in Economics - Keneth Judd

Reinforcement Learning [Capítulos 1 a 4]

Markov Decision Processes - Martin Puterman [Capítulo 6]

Referências Complementares

O site Quantitative Economics tem muito material legal.

Soluções de Exercícios

Value iteration usando discretização [Questão 1(a)]

Value iteration usando discretização [Questão 4(a)]

Método de Newton Raphson [Questão 8]

Gerando fractais: Fractal de Vicsek [Questão 11]

Gerando fractais: Carpete de Sierpinski [Questão 11]

Gerando fractais: Triângulo de Sierpinski [Questão 11]

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

 Referências

Modern multivariate statistical techniques - Alan Julian Izenman [Capítulo 5]

Statistical Learning with Sparsity: The Lasso and Generalizations - Trevor Hastie and Robert Tibshirani

Referências Complementares

High-Dimensional Methods and Inference on Treatment and Structural Effects in Economics - Victor Chernozhukov, A. Belloni and C. Hansen

Soluções de Exercícios

Double Selection via lasso [Questão 1(b)]

Double Selection via lasso [Questão 1(b)]

Diferença entre os modelos regularizados usando Monte Carlo [Questão 2]

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

 



Códigos usados em sala de aula

OLS para classificação

Implementação do Perceptron

Implementação de um modelo de resposta binária

Referências

Pattern Recognition and Machine Learning - Christopher Bishop [Seções 4.1, 4.2 e 4.3]

A. Carvalho, D. Cajueiro e R. Camargo - Introdução aos Métodos Estatísticos para Economia e Finanças [Capítulo 9]

Modern multivariate statistical techniques - Alan Julian Izenman [Seções 8.1 a 8.4]

The elements of statistical learning - Hastie, Tibshirani e Friedman [Capítulo 4]

Neural networks - Haykin [Capítulos 3 e 5]

Bases de dados usadas para responder os exercícios

PRorum: Sites com bases de dados interessantes

Soluções de Exercícios

Linear Discriminant Analysis

Probabilistic Generative Models

Stepwise logistic regression

Xor

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

 



Códigos usados em sala de aula


Decomposição Viés-Variância

Referências

Pattern Recognition and Machine Learning - Christopher Bishop [Seções 3.1, 3.2 e 3.6]

Modern multivariate statistical techniques - Alan Julian Izenman [Capítulo 5]

The elements of statistical learning - Hastie, Tibshirani e Friedman [Capítulo 3]

Neural networks - Haykin [Capítulo 7]



Referências Complementares para otimização numérica

Numerical methods in economics - Kenneth Rudd

Numerical methods in engineering with python - Jaan Kiusalaas

Bases de dados usadas para responder os exercícios

PRorum: Sites com bases de dados interessantes

Soluções de Exercícios


Rede Neural de Bases radiais [Questão 1]

PCR - Principal Components Regression [Questão 2(a)

PLS - Implementação do Partial Least Squares [Questão 2(b)

PLS - Implementação do Ridge [Questão 2(c)

Modern multivariate statistical techniques - Alan Julian Izenman que versa sobre o uso da base de dados ”Boston housing data”

Forwards Stepwise em python [Questão 3(a)

Implementação do Lasso [Questão 3(b)

Implementação do LARS [Questão 3(c)

Forwards Stagewise em python [Questão 3(d)

Replicar os resultados empı́ricos do livro “Introduction to
Econometrics - Stock e Watson”


Questão 4a 

Questão 4b

Questão 4c 

Questão 4d

 

 

 

 

 

 

 

 

 

 

 

 

 

 


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

 



Soluções de Exercícios

1. Problema de machine learning

Data: Adult Salary predictor do Kaggle 

Data: Restaurant Revenue Prediction" do Kaggle 

Data: SF salaries

Data: Titanic - ML for Disaster

Data: Forest Cover Type Prediction

Data: Brazilian Cities

Data: Bike Sharing Demand

Data:
Otto Group Product


Data:
Prudentials 1


Data:
Prudentials 2

Restaurant Revenue Prediction   

Credit Card Fraud Detection   

Brazilian yield curve   
 

TMDB Box Office Prediction   
 

Rossman Store Sales   
 

House Prices   
 

Liberty Mutual Group: Property Inspection Prediction    http://prorum.com/?qa=5331/exercicio-machine-learning-property-inspection-prediction  

Kaggle: House Rent Prediction Datase

Kaggle: Medical Cost Personal Dataset 
.
 Kaggle: Diamonds - Analyze diamonds by their cut, color, clarity, price, and other attributes

Kaggle Restaurant Revenue Prediction 

kaggle Titanic

Kaggle: Credit Score Classification Dataset 

Worldwide deaths by country/risk factors" do Kaggle

Referências

The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World - Pedro Domingos

Pattern Recognition and Machine Learning - Christopher Bishop

Deep learning - Ian Goodfellow, Yoshua Bengio and Aaron Courville

The elements of statistical learning - Hastie, Tibshirani e Friedman

Modern multivariate statistical techniques - Alan Julian Izenman

The discipline of machine learning - T. M. Mitchel

A few useful things to know about machine learning - P. Domingos

Learning deep architectures for AI - Y. Bengio

In defence of forensic social science - Amir Goldberg [Big data and Society, 2015]

Sociology in the era of big data: the ascent of forensic social science - D. A. McFarland e
K. Lewis [American Sociology, 2015]

Economic reason and artificial intelligence - D. C. Parkes and M. P. Wellman [Sience 349,
p.267, 2015]

Big Data: New Tricks for Econometrics - H. R. Varian

The Impact of Machine Learning on Economics - Susan Athey

The State of Applied Econometrics: Causality and Policy Evaluation
Susan Athey e Guido W. Imbens.

Beyond Prediction: Using Big Data for Policy Problems -
Susan Athey

High-Dimensional Methods and Inference on Treatment and Structural Effects in Economics - Victor Chernozhukov, A. Belloni and C. Hansen

Prediction Policy Problems -
Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ziad Obermeyer

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

 Abaixo temos os exemplos apresentados em sala de aula:

Jogo da Minoria

Modelo de Simulação Bancária


Referências

Arthur, W. B. Inductive reasoning and bounded rationality. American Economic Review, v. 84, n. 2, p. 406--411, 1994.

Barroso, R. V. et al., Interbank network and regulation policies: an analysis through agent-based simulations with adaptive learning, published in the Journal Of Network Theory In Finance, v. 2, n. 4, p. 53–86, 2016. [A versão preliminar está aqui: https://mpra.ub.uni-muenchen.de/73308/]

Challet, D. and Zhang, Y. C. Emergence of cooperation and organization on an evolutionary game. Physica A 246, p. 407--418, 1997

Agent-Based and Individual-Based Modeling: A Practical Introduction
by Steven F. Railsback and Volker Grimm

An Introduction to Agent-Based Modeling: Modeling Natural, Social, and Engineered Complex Systems with NetLogo -- Wilensky, Uri, Rand, William (2015)

Complex Adaptive Systems: An Introduction to Computational Models of Social Life -- John H. Miller and Scott Page


Agent-Based Modeling: The Santa Fe Institute Artificial Stock Market Model Revisited -- Norman Ehrentreich

Soluções de Exercícios

Questão 1 An Introduction to Agent-Based Modeling: Modeling Natural,
Social, and Engineered Complex Systems with NetLogo – Wilensky, Uri,
Rand, William (2015)


Questão 1 (a): Fire model
Questão 1 (b): Diffusion limited aggregation 

Questão 1 c) Segregation model
Questão 1 (d): El Farol

Questão 2 Agent-Based Modeling: The Santa Fe Institute
Artificial Stock Market Model Revisited – Norman Ehrentreich

 a) Capitulo 6

Questão 3 “Complex Adaptive Systems: An Introduction to
Computational Models of Social Life – John H. Miller and Scott Page”

 3 a

 

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

 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

 

Scientific Computing: An Introductory Survey, 2018 - Michael T. Heath.

Questão 1a  

Questão 1b

1c 

1d 

Questão 1e

1f 

1g

1h  

1 i

1 j 

Questão 1l

1 m

1.o 

1 p 

1 r 

Questão 1v

Questão 1x

1 x

1 w

1 y 

 1.z

 

 

 

 

 

 

 

 

 

 

 

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

 


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

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

Questão 3 (a): Monte Carlo

Questão 3 (c): Monte Carlo

Questão (d): Monte Carlo

Questão (e): Monte Carlo

Questão 4 Knuth

Vol2, Seção 3.1 ex 8

 Vol2, Seção 3.6 ex 3

 Vol 2 - 3ed, pág 190 Cap. 3 - Seção 3.6 - Questão 3

Vol. 2 - 3ª edição p. 141 Cap. 3 seção 3.4.1  exercício 30.

Questão 5: Capı́tulo 2 ou 3 do livro Monte Carlo Statistical Methods by Christian Robert and George Casella .

 2.1

2.1 

2.2 

2.3 

2.3 

2.5 

2.10

2.12 

2.19 

2.20 

3.3 

 3.4

 

 

 

 

 

 

 

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


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]

Solução de exercícios

Questão 4 (a): Pigeonhole sort

Questão 4 (b): Bucket sort

Questão 4 c Radix Sort

Questão 4 d Spread Sort

Questão 4 (f): Flashsort

Questão 4 g Postman Sort

Questão 5: Capı́tulo 5 ”Sorting“ do Volume 3 The Art of Computer Programming

Vol. 3 - 2ª edição Cap. 5 Seçõ "Sorting"Questão 9 pag 5

Vol3 - 2ed, pag.7 - Cap.5 - Seção 0 - Questão 7

Vol3 - 2ed, pag.7 - Cap.5 - Seção 0 - Questão 13 

Vol3 - 2ed, pag.6 - Cap.5 - Seção 0 - Questão 12

Vol3 - 2ed, pag. 152 - Cap.3 - Questão 3.11

2ed, pag.134 - Cap.5 - Seção 5.2.2 - Questão 7 

2ed, pag.19 - Cap.5 - Seção 5.1.1 - Questão 19



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

 
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

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


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

Questão 1: College Problem Admission

Questão 2: Stable roomates

Questão 3

Questão 4 

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

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


 

 

 

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

 


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

Exercício 5 (Análise empírica de redes)

 Rede de livros

Dados de aprisionamento 

Collective dynamics of small-world network (Strogatz e Watts)

Star Wars

 Exercício 6 (Complex Networks: Principles, Methods and Applications)

1.3

1.6 

2.1 

2.4 

2.5 a

2.5 b

4.2  

10.5

Exercício 7 - capı́tulo 11 do livro Combinatorics: Topics, Techniques, Algorithms by Peter J.
Cameron.

Exercício 2

Exercício 6

Exercício 8















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

 


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

Solução de exercícios

Questão 5 (a)

Questão 5 (b)

Questão 5 (c)

 Questão 5 (d)

Questão 5 (e) 

Questão 5 (f)

 Questão 5 (g)

Questão 5 (h) 

Questão 5 (i) 

Questão 5 (j)

Questão 5 (l)

Questão 5 (m)

Questão 5 (n) 

Questão 5 (o)

Questão 5 (q) 



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

 


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 7]

Josephus [Questão 8]

Questão 9

Contagem da intersecção de segmentos (Pag 20, Seção 2.1)

Triangularização de polı́gonos (Pag 46, Seção 3.1) 

Diagramas de Voronoi (Pag. 147, Seção 7.1)

Locomoção de robôs sem tamanho (Robôs em forma de pontos) (Pag. 286, Seção 8.2)






Thursday, July 15, 2021

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

 Exercícios resolvidos:

Questão 1 

Questão 2

Questão 3 

Questão 4 

Questão 4


Exercícios de programação funcional do GitHub: https://gist.github.com/oskarkv/3168ea3f8d7530ccd94c97c19aafe266

Crie uma partição de função que receba os argumentos n, step e seq (número, número, sequência). Ele deve pegar n elementos de seq, agrupar isso em uma lista e avançar nas etapas de conforme o valor de step, depois pegar outros n elementos e assim por diante

Pede-se que seja criada uma função chamada "update" que recebe um mapa "m", uma chave "k", uma função "f" e um número arbitrário de argumentos adicionais "args". Ele especifica que a função deve retornar um novo mapa que seja semelhante a "m", mas com o valor para a chave "k" substituído pelo resultado da aplicação de "f" ao valor anterior e aos argumentos fornecidos.

Crie uma função zipwith que receba uma função f e um número arbitrário de sequências e retorne uma lista de f aplicada aos primeiros elementos das sequências fornecidas, seguida por f aplicada aos segundos elementos das sequências e assim por diante.

Crie uma função zip que pegue um número arbitrário de sequências e as compacte, ou seja, crie uma lista de listas, onde as listas internas consistem nos primeiros elementos das sequências fornecidas, depois nos segundos elementos das sequências fornecidas e assim por diante.

Crie uma função zipmap que receba duas sequências e forme um dicionário dos elementos da primeira sequência com os elementos da segunda sequência.

O objetivo desse exercício é criar uma função flatten que possa achatar uma árvore 

Crie uma função 'take' que receba um número 'n' e uma sequência 'seq' e retorne uma lista dos primeiros 'n' elementos de 'seq'.

Crie uma função "interleave" que pegue um número arbitrário de sequências e as intercale.

Crie uma função compose que receba 2 funções e faça a composição da função, ou seja, compose(double, negate) deve retornar uma função que primeiro chama negate e depois double em seu argumento.

Nesse exercício devemos criar uma função chamada "balanced" que recebe uma string "s" e retorna True se ela contiver apenas parênteses, colchetes e chaves balanceados ((), [], {}), caso contrário retorna False.










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

 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

Exercício 1:

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

Exercício 3:

Chamadas recursivas da torre de Hanoii

Exercício 5 (a):

Pilha com três números distintos

Exercício 5 (b):

Pilha com capacidade limitada.

Exercício 5 (c):

Inversão de elementos usando pilhas

Exercício 5 d

Exercício 5 (e):

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

Exercício 5 (f):

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

Exercício 5 g


Exercício 5 (h):

Manipulação de elementos usando pilhas.

 Exercício 5 i

Exercício 5 j

Exercicio 5 k 


Exercício 5 (l):

Encontrando elemento em uma pilha

Exercício 5 m

Exercício 5 n 

Exercício 5 o

Exercício 5 (p):

Travessia de vacas.

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

 



Abaixo temos os exemplos apresentados em sala de aula:

Medição empírica da complexidade computacional

Referências Adicionais para essa aula:

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

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

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

1. Como calcular a complexidade computacional das implementações recursivas da série de fibonacci?

2. Qual a complexidade computacional de um algoritmo recursivo que satisfaz a relação de recorrência?

3. Qual a complexidade computacional dessas relações de recorrência de acordo com o Teorema Mestre (master theorem)?

4. Capı́tulo 3 ”Runtime analysis of recursive algorithms“ do livro ”Introduction to
Recursive Programming“

3.1 

3.1 

3.2 

3.3 

3.4

3.5 

3.6 

3.7 

3.8 

3.10

3.11 

3.12 

3.13 

3.14

3.17 

3.18 (a)

3.18 (d)

3.18 (f)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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



Abaixo temos os exemplos apresentados em sala de aula:

Exemplo de Classes

Exemplo de encapsulamento

Exemplo de sobrecarga de operadores

Exemplo de polimorfismo

Exemplos de iteradores

Exemplos de geradores

Exemplo de herança

Exemplo de classe abstrata

Referências Adicionais para essa aula:

1. Usuários de Python podem ter interesse em olhar:

Think Python - Allen Downey

2. Usuários de C++ podem ter interesse em olhar:

Think C++

3. Usuários de Java podem ter interesse em olhar:

Intro to Java Programming

Soluções de exercícios

Exercício 5 (a):
M sets

Exercício 5 (b):
Julia sets

Exercício 6:
Alocação de carteiras

Criação de classes
 

Exercício 7:
a) Círculos

b) Cell

c) Superposição de polígonos

Exercício 8: A Primer on Scientific Programming

7.1

7.1 

7.2

7.3

7.4 

7.5

7.6 

7.7

7.8 

7.10

7.11

7.12

7.13

7.13 

7.14 

7.15 

7.16 

7.16

7.17

7.18 

7.19 

7.20

7.21 

7.23 

7.24

7.25

7.26

7.28 

7.29 

7.30

7.34 

7.35















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




Abaixo temos os exemplos apresentados em sala de aula:

Implementações da sequencia de Fibonacci

Implementações do fatorial de um número

Solução da Torre de Hanoi

Referências:

Think recursively - Eric S. Roberts

Persian Recursion Anne M. Burns Mathematics Magazine Vol. 70, No. 3 (Jun., 1997), pp. 196-199

The Algorithmic Beauty of Plants - Przemyslaw Prusinkiewicz and Aristid Lindenmayer (1991)

Introduction to recursive programming - Manuel Rubio Sanchez

Mathematical puzzles and diversions (Volume 2) - Martin Gardner

Referências Adicionais para essa aula:

1. Usuários de Python podem ter interesse em olhar:

Think Python - Allen Downey: Capítulo 5.

2. Usuários de C++ podem ter interesse em olhar:

Think C++: Capítulo 4.


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


Observação: Vários dos exercícios abaixo usam a idéia de Turtle Graphics discutida aqui.

Algoritmo de Euclides [Questão 5 dos slides]

Árvores usando recursão [Questão 6 dos slides]



Pinturas de Mondrian usando recursão [Questão 7 dos slides]


Sierpinski Gasket [Questão 8]

Questões do livro The Algorithmic Beauty of Plants - Przemyslaw Prusinkiewicz

Ilhas de Koch [Questão 9(a)]

Ilhas de Koch 2 [Questão 9(b)]

Gosper Hexagonal Curve [Questão 9(c)]

L-systems [Questão 9(d)]

Tree OL Systems 2 [Questão 9(e)]

Tree OL Systems [Questão 9(f)]

Tree OL Systems [Questão 9(g)]

Tree OL Systems [Questão 9(g) - solução 2]

Tree OL Systems [Questão 9(i)]

Questão 9 j

Questão 9 k 

Questão 9 l 

 
Tree OL Systems [Questão 9(m)]

Questão 9 (n)

Tree OL Systems [Questão 9(o)]

Tree OL Systems [Questão 9(r)]

Tree OL Systems [Questão 9(s)]

Questão 9 t

Questão 9 x


Persian Recursions que estão presentes no artigo Persian
Recursion Anne M. Burns Mathematics Magazine Vol. 70, No. 3
(Jun., 1997), pp. 196-199

Como implementar persian recursions [Questão 10(a) e 10(b)]

 Questões selecionadas dos capítulos 7, 8 e 9 do livro “Introduction
to recursive programming - Manuel Rubio Sanchez”

Triangulo de Sierpinski [Questão 11(a)]

Curva de Hilbert [Questão 11(b)]

Árvore binária [Questão 11(c)]

Tabuleiro [Questão 11(d)]

Combinações no jogo de basquete [Questão 11(e)]

Soma de bits [Questão 11(f)]

Números de Catalan [Questão 11(g)]

Números de Catalan [Questão 11(g)]

Árvore binária [Questão 11(h)]

Pirâmides [Questão 11(i)]

John-Mary [Questão 11(j)]

Questão 11 k

Questões do Capı́tulo 4 ou 5  ”Introduction to Recursive Programming“ by Manuel Rubio-Sanchez.

Questão 12 4.1 

Questão 12 4.2 

 Questão 12 4.3

Questão 12 4.4

Questão 12 4.5

Questão 12 4.6 

Questão 12 4.7

Questão 12 4.8

Questão 12 4.8

Questão 12 4.9 

Questão 12 4.10 

Questão 12 4.12

Questão 12 4.13 

Questão 12 4.15

4.15

4.16 

 Questão 12 4.17

 Questão 12 5.1

5.2

5.4 

 Questão 12 5.5

5.6

5.7 

5.8

 Questão 12 5.9


Questões do livro “Recursion via Pascal - Rohl”

1.1

1.4

1.11

 

 

 

 

 

 

 

 






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

Na nossa segunda aula de métodos computacionais discutimos coleções básicas de dados. Esses são os slides usados em sala.

Abaixo temos os exemplos apresentados em sala de aula:

Como usar sequências de dados ou arrays em programação estruturada?

Como usar conjuntos ou sets em programação computacional?

Como usar mapas (maps) ou dicionários em programação computacional?

Soluções de exercícios

Como implementar o produto de matrizes? [Considere apenas a solução convencional nessa resposta. As outras serão discutidas mais para frente no curso]

Como fatorar um número inteiro? 

Questões do Capı́tulo 6 (Files, strings and Dictionaries) do A Primer on Scientific Programming with Python por Hans Petter Langtangen.

6.1

6.2

6.3

6.5

6.6

6.8 

6.9

6.10

6.11

6.17










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


Referências Adicionais para essa aula:

1. Usuários de Python podem ter interesse em olhar:

Think Python - Allen Downey

2. Usuários de C++ podem ter interesse em olhar:

Think C++

Alguns links externos relacionados com essa aula:

Qual o propósito de incluir "if __name__ == '__main__':" em python?

Computação Humana

Page Rank

Melhores livros de Python


Soluções das séries de exercício:

Questão 1

Questão 2

Questão 3

Questão 4

Questão 5

Questão 6

Questão 7

Questão 8 

Questão 9

Questão 10 

Questão 11 (a)

Questão 11 (b)

Questão 11 (c)

Questão 11 (d)  

Questão 11 (e)

Questão 11 (f) 

Questão 12

Questão 13

 Exercício 14 Pag 228

Questão 14

a) Chapter 1 Figura 4

f) Chapter 1 Figura 10

s) Chapter 8 Figura 1