Mathematics BSc
Course description
2013.
Course description
2013.
Computer science
| Hours lect+pc |
Credits lect+pc |
Assessment | Specialization | Course code lect/pc |
Semester | Status |
|---|---|---|---|---|---|---|
| 2 + 2 | 2 + 3 | exam + term grade |
pure math. | mm1c1cs6m mm1c2cs6m |
6 | compulsory |
| applied math. | mm1c1cs6a mm1c2cs6a |
6 | compulsory |
Course coordinator
| Strong | Weak | Prerequisites | |
|---|---|---|---|
| Practice class | |||
|
Strong:
Algebra1L
(mm1c1al1)
| |||
|
Strong:
Discrete mathematics2L
(mm1c1vm2)
| |||
|
Strong:
| |||
| Lecture | |||
|
Weak:
practice class
| |||
Syllabus
- Fundamental sorting, search- and graph-algorithms. Dynamic programming.
- An abstract model of computers: the Turing machine. Examples; Church-thesis. Palindromes, Turing machines with one and two tapes accepting palindromes. The definition and existence of universal Turing machines.
- The k-tape Turing machine can be simulated by a one-tape Turing machine. Recursive and recursively enumerable languages; their basic properties. The halting problem. Time complexity classes. The class P. Arthur-Merling game, the definition of the NP class. co-NP. Examples for languages in NP.
- The PRIME language. Polynomial reduction. NP-completeness. Boole formulae. The SAT language.
- Cook's theorem: SAT is NP-complete. Other NP-complete languages.