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 

Marvel Network 

 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)

7.5 (3ª Edição, 2008)

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.

Create a function clist (for create list) that takes an arbitrary number of arguments and creates a list of the arguments given. clist is useful for giving as an argument to other functions. If you use a Lisp, it already exists in the form of list, and you can skip this exercise.

Create a function drop that takes a number n and a sequence seq, and returns a list with the first n elements of seq dropped.

Create a function frequencies that takes a sequence and counts how many times the elements appear in the sequence, returns a map.

Create a function partition that takes the arguments n, step, and seq (number, number, seqence). It should take n elements from seq, wrap that in a list, and step forward in seq step steps, then take another n elements, and so on.

Create a function every_pred that takes an arbitrary number of predicates (functions that return a truth value) and returns a function that returns true if and only if all predicates were truthy for the argument.

Create two functions postwalk and prewalk, that both take a function f and a tree t. (A tree in this case is a list where the elements can be trees themselves), e.g. [1, [2, 3, [1, 2]], [4, 5, 6]]. In this case 1, [2, 3, [1, 2] and 6 are all elements of the tree (but not the only ones).) The functions should apply f to each element in the tree to create a new tree with the results, like map but for trees instead of lists. The difference between prewalk and postwalk is that prewalk does the replacement on the way “down” and postwalk on the way “up”, so that prewalk can continue down into the new value that was “just” created.

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.

 6 - Você pode resolver qualquer exercício apresentado no Capítulo 2 ”Information
structures“ do Volume 1 The Art of Computer Programming que tenha score maior ou
igual que 25.

Exercício 5, cap 2 

Exercício 14 (2.2.1), cap. 2

Exercício 16, cap 2

 

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 - item b (1ª Edição, 2018) 

3.18 (d)

3.18 (f) 

3.18 (h) (1ª Edição, 2018)

5. Você pode resolver qualquer problema apresentado no Capítulo 8 do livro
”Combinatorial Optimization: Algorithms and Complexity“ de Christos H. Papadimitriou e Kenneth Steiglitz.

 8.1 (2ª Edição, 1998)

 8.3 (2ª Edição, 1998)

 

 

 

 

 

 

 

 

 

 

 

 

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 (5ª Edição, 2016) 

7.1 

7.2

7.3

7.4 

7.5

7.5 (5ª Edição, 2016) 

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.28 ( 5ª Edição, 2016)

7.29 

7.30

7.31 (5ª Edição, 2016)  

7.32 (5ª Edição, 2016)

7.33 (5ª Edição, 2016) 

7.34 

7.35

Exercícios 9: Você pode resolver qualquer problema apresentado no Capítulo 6 ”Abstraction“ do ”Java Gently for Engineers and Scientists - Judith Bishop e Nigel Bishop.

6.2 (1ª Edição, 2000)

Exercícios 10: Você pode resolver em Python qualquer ”Programming Exercise“ dos capítulos 5, 7, 8 e 9 apresentado no livro ” Object Oriented Programming with C++ - E
BALAGURUSAMY (5a edição). Esses problemas podem ser resolvidos em C++, mas
preferencialmente em Python ou em outra linguagem de sua escolha.

5.1 ( 4ª Edição)