MC358 - Fundamentos matemáticos da programação
Changelog
2018-11-19: Exercicios dos capitulos 10.1/10.2/10.3/10.5/10.7
2018-11-15: Exercicios do capitulo 10.4
2018-10-27: Uma representação 2D do conjunto de Cantor.
2018-10-27: Adicionando um bom video sobre relações de recorrencia.
2018-10-04: Exercicio 16 do capitulo 5.1
2018-10-05: Exercicio 19 e 20 do capitulo 5.1
Aulas ministradas pelo Prof. Pedro J. de Rezende no segundo semestre de 2018.
Bons problemas, uma das partes mais interessante sobre a materia e a parte de alguns
problemas famosos que acabam aparencendo como referencia, segue uma lista dos mais bacanas:
-
Halting Problem, programas em geral podem ter loops infinitos, pode existir
algum algoritmo que consegue identificar se dado determinado input um programa qualquer
ira entrar em loop? (spoiler: nope).
Computerphile
Halting problem
-
Conjetura de Goldbach, todo número par maior que dois pode ser representado
pela soma de dois numeros primos.
-
Twin Prime, é todo numero primo cujo a soma ou subtração com dois resulta em
outro número primo.
-
Conjectura de Collatz, dada a função abaixo, é
possivel identificar se ela converge para todos os numeros naturais não nulos?
-
Four color theorem, dado um plano, dividindo-se em regiões arbitrarias,
quatro cores são suficiente para colori-lo de maneira que nenhuma região tem a mesma
cor que suas vizinhas. Existe uma versão mais fácil de ser provada onde o plano
é divido apenas por retas, nessa versão duas cores são o suficiente.
-
Continuum hypothesis, não existe conjunto cujo a cardialidade esteja exclusivamente,
entre a cardinalidade dos números naturais e os números reais.
-
O conjunto de Cantor, um conjunto bem interessante do qual mais informações podem ser encontradas aqui.
Boas referencias, entender é dificil, o mesmo conceito para ser explicado de diversas maneiras diferentes,
talvez uma das abaixo seja o que você esteja procurando para compreender algo que parece complexo:
-
Relações de Recorrencia, video sobre como resolver equações de recorrencia feito pelo John Bowers,
uma das minhas dificuldades com esse tipo de problema foi a organização da solução, eu acaba me confundindo e baguçando
as coisas, o John tem um metodo bem interessante de organização.
Video
Exercícios resolvidos, lembrando que o fato deles estarem resolvidos, não
é sinonimo deles estarem corretos, mas tudo leva a crer que eles estão. Caso voce encontre
algum erro ou tenha alguma sugestão, entre em contato comigo que eu atualizarei os documentos.
(do livro K. H. Rosen, Discrete Mathematics and its Applications 7ª Edição).
- 1.2 - Applications of Proposital Logic
- 1.5 - Nested Quantifiers
- 1.6 - Rules of Inference
- 1.7 - Introduction of Proves
- 1.8 - Proof Methods and Strategy
- 1 - Supplementary Exercises
- 2.1 - Sets
- 2.2 - Sets Operations
- 5.1 - Induction and Recursion, Indução é um assunto no qual eu tenho mais apego, por esse motivo, esses capítulos foram feitos com um pouco mais de amor;
- 10.1 - Graphs and Graph Model
- 10.2 - Graph Terminology and Special Types of Graphs
- 10.3 - Representing Graphs and Graph Isomorphism
- 10.4 - Graph: Connectivity
- 10.5 - Euler and Hamilton Paths
- 10.7 - Planar Graphs
Exercícios extras, alguns exercicios de referencias diversas que eu achei interessante e
que mereciam menção.
-
Prove que a soma dos primeiros n naturais números pode ser obtida atravez de
n(n+1)/2 .
-
Inducao Reversa: Exercicio interessante do Manber sobre Inducao reversa,
o Professor Rezende nao recomenda esse tipo de exercicio sem ter suficiente base em
inducao 'normal', porem eu acho que deixei todos os passos explicitos, dessa forma talvez,
ele esteja mais simples.
Prove que a media geometrica e sempre menor ou igual que a aritmetica
Parte 1/Parte 2
