185 lines
7.7 KiB
Markdown
185 lines
7.7 KiB
Markdown
|
|
# MA0301 - Spring 2021 - Diskret Matematikk
|
|
|
|
Using styling files from [oysteikt/texmf](https://gitlab.stud.idi.ntnu.no/oysteikt/texmf)
|
|
|
|
## Exercises
|
|
|
|
| Num | Exercise PDF | Answer PDF | Solutions PDF |
|
|
| --- | ------------------------- | ---------------- | ------------------------- |
|
|
| 1 | [wiki.math.ntnu.no][ex1] | [ex1.pdf][as1] | [wiki.math.ntnu.no][so1] |
|
|
| 2 | [wiki.math.ntnu.no][ex2] | [ex2.pdf][as2] | [wiki.math.ntnu.no][so2] |
|
|
| 3 | [wiki.math.ntnu.no][ex3] | [ex3.pdf][as3] | [wiki.math.ntnu.no][so3] |
|
|
| 4 | [wiki.math.ntnu.no][ex4] | [ex4.pdf][as4] | [wiki.math.ntnu.no][so4] |
|
|
| 5 | [wiki.math.ntnu.no][ex5] | [ex5.pdf][as5] | [wiki.math.ntnu.no][so5] |
|
|
| 6 | [wiki.math.ntnu.no][ex6] | [ex6.pdf][as6] | [wiki.math.ntnu.no][so6] |
|
|
| 7 | [wiki.math.ntnu.no][ex7] | [ex7.pdf][as7] | [wiki.math.ntnu.no][so7] |
|
|
| 8 | [wiki.math.ntnu.no][ex8] | [ex8.pdf][as8] | [wiki.math.ntnu.no][so8] |
|
|
| 9 | [wiki.math.ntnu.no][ex9] | [ex9.pdf][as9] | [wiki.math.ntnu.no][so9] |
|
|
| 10 | [wiki.math.ntnu.no][ex10] | [ex10.pdf][as10] | [wiki.math.ntnu.no][so10] |
|
|
| 11 | [wiki.math.ntnu.no][ex11] | [ex11.pdf][as11] | [wiki.math.ntnu.no][so11] |
|
|
| 12 | [wiki.math.ntnu.no][ex12] | [ex12.pdf][as12] | [wiki.math.ntnu.no][so12] |
|
|
|
|
[ex1]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-1-2021-new.pdf "Exercise 1 Questions"
|
|
[ex2]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-2-2021-new.pdf "Exercise 2 Questions"
|
|
[ex3]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-3-2021.pdf "Exercise 3 Questions"
|
|
[ex4]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-4-2021.pdf "Exercise 4 Questions"
|
|
[ex5]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-5-2021.pdf "Exercise 5 Questions"
|
|
[ex6]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-6-2021.pdf "Exercise 6 Questions"
|
|
[ex7]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-7-2021.pdf "Exercise 7 Questions"
|
|
[ex8]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-8-2021.pdf "Exercise 8 Questions"
|
|
[ex9]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-9-2021.pdf "Exercise 9 Questions"
|
|
[ex10]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-10-2021.pdf "Exercise 10 Questions"
|
|
[ex11]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-11-2021.pdf "Exercise 11 Questions"
|
|
[ex12]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-12-2021.pdf "Exercise 12 Questions"
|
|
|
|
[as1]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise1.pdf "Exercise 1 Answers"
|
|
[as2]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise2.pdf "Exercise 2 Answers"
|
|
[as3]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise3.pdf "Exercise 3 Answers"
|
|
[as4]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise4.pdf "Exercise 4 Answers"
|
|
[as5]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise5.pdf "Exercise 5 Answers"
|
|
[as6]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise6.pdf "Exercise 6 Answers"
|
|
[as7]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise7.pdf "Exercise 7 Answers"
|
|
[as8]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise8.pdf "Exercise 8 Answers"
|
|
[as9]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise9.pdf "Exercise 9 Answers"
|
|
[as10]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise10.pdf "Exercise 10 Answers"
|
|
[as11]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise11.pdf "Exercise 11 Answers"
|
|
[as12]: http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exercise12.pdf "Exercise 12 Answers"
|
|
|
|
[so1]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-1-2021-solutions.pdf "Exercise 1 Solutions"
|
|
[so2]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-2-2021-solutions.pdf "Exercise 2 Solutions"
|
|
[so3]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-3-2021-solutions.pdf "Exercise 3 Solutions"
|
|
[so4]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-4-2021-solutions.pdf "Exercise 4 Solutions"
|
|
[so5]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-5-2021-solutions.pdf "Exercise 5 Solutions"
|
|
[so6]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-6-2021-solutions.pdf "Exercise 6 Solutions"
|
|
[so7]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-7-2021-solutions.pdf "Exercise 7 Solutions"
|
|
[so8]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-8-2021-solutions.pdf "Exercise 8 Solutions"
|
|
[so9]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-9-2021-solutions.pdf "Exercise 9 Solutions"
|
|
[so10]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-10-2021-solutions.pdf "Exercise 10 Solutions"
|
|
[so11]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-11-2021-solutions.pdf "Exercise 11 Solutions"
|
|
[so12]: https://wiki.math.ntnu.no/_media/ma0301/2021v/set-12-2021-solutions.pdf "Exercise 12 Solutions"
|
|
|
|
---
|
|
|
|
## Automation
|
|
|
|
---
|
|
|
|
### VSCode snippets
|
|
|
|
[See snippets for LaTeX](https://gitlab.stud.idi.ntnu.no/oysteikt/v21-ma0301/-/blob/master/exam_template/.vscode/latex.code-snippets)
|
|
|
|
[See snippets for Makefile](https://gitlab.stud.idi.ntnu.no/oysteikt/v21-ma0301/-/blob/master/exam_template/.vscode/makefile.code-snippets)
|
|
|
|
---
|
|
|
|
### Chrome plugin
|
|
|
|
#### Chapter 1. 2. 3. Boolean calculator
|
|
|
|
![Boolean Calculator](.gitlab/graphics/chrome-extension/booleanalgebra.png)
|
|
|
|
Automates calculating boolean expression step by step by running the input through https://boolean-algebra.com/
|
|
|
|
Outputs the resulting set of expressions to either propositional logic, boolean algebra or set operations.
|
|
|
|
Converts output to LaTeX
|
|
|
|
- [X] Finished
|
|
|
|
**NOTE: there are some bugs when converting boolean algebra AND operations to PL/S**
|
|
|
|
#### Chapter 4. Induction
|
|
|
|
Automates proof by induction by running the input through https://wolframalpha.com/
|
|
|
|
Converts output to LaTeX
|
|
|
|
- [ ] Finished
|
|
|
|
#### Chapter 6. Combinatorics
|
|
|
|
![Permutation/Combination Calculator](.gitlab/graphics/chrome-extension/permscombs.png)
|
|
|
|
Permutations / Combinations Calculator
|
|
|
|
Computes permutations and combinations
|
|
|
|
Outputs to LaTeX
|
|
|
|
- [X] Finished
|
|
|
|
---
|
|
|
|
### Python framework
|
|
|
|
See examples of what the engine for the exam template can do here: [exam_template_graphics.pdf](http://oysteikt.pages.stud.idi.ntnu.no/v21-ma0301/exam_template_graphics.pdf)
|
|
|
|
#### Chapter 1. Truthtables (propositional logic)
|
|
|
|
**Capabilities:**
|
|
|
|
- [X] Calculate and render truthtable for propositional logic expressions
|
|
|
|
#### Chapter 3. Sets
|
|
|
|
**Capabilities:**
|
|
|
|
- [ ] Calculate and output powersets
|
|
|
|
#### Chapter 5. Relations
|
|
|
|
**Capabilities:**
|
|
|
|
Proofs:
|
|
|
|
- [X] Check whether relation is reflexive
|
|
- [X] Check whether relation is symmetric
|
|
- [X] Check whether relation is antisymmetric
|
|
- [X] Check whether relation is transitive
|
|
- [X] Check whether relation is an equivalence relation
|
|
- [X] Check whether relation is a partial order
|
|
|
|
Graphs:
|
|
|
|
- [X] Draw a hasse diagram from a partial order
|
|
- [X] Draw an graph from any relation
|
|
|
|
Note: Checking whether a relation has a property in this context means that it goes over every pair of related elements and looks for contradictions. **This program can not prove relation properties algebraically**
|
|
|
|
#### Chapter 6. Combinatorics
|
|
|
|
**Capabilities:**
|
|
|
|
- [X] Make an inclusion exclusion expression from list of conditions
|
|
|
|
#### Chapter 7. Graph theory
|
|
|
|
**Capabilities:**
|
|
|
|
Inputs:
|
|
|
|
- [X] Input a graph from a matrix
|
|
- [X] Input a graph from a node/edge list
|
|
- [X] Input a complete graph from a node number
|
|
|
|
Outputs:
|
|
|
|
- [X] Output a graph to a matrix
|
|
- [X] Draw an undirected graph
|
|
- [X] Draw a directed graph
|
|
- [X] Find a minimal spanning tree with Kruskals algorithm
|
|
|
|
#### Chapter 8. Finite state automata
|
|
|
|
**Capabilities:**
|
|
|
|
- [X] Draw a finite state machine
|
|
- [ ] Output a finite state machine table
|
|
- [ ] Calculate input based on a finite state machine
|
|
|
|
#### Python
|
|
|
|
**Capabilities:**
|
|
|
|
- [X] Include a raw python program, and capture its output into a listing |