| Language of instruction : English |
|
Sequentiality
|
| |
|
No sequentiality
|
| Degree programme | | Study hours | Credits | P2 SBU | P2 SP | 2nd Chance Exam1 | Tolerance2 | Final grade3 | |
 | Master of Computer Science choice | 2-yearly optional (current academic year) | 162 | 6,0 | 162 | 6,0 | Yes | Yes | Numerical |  |
|
| | | Learning outcomes |
- EC
| EC 2: A graduate of the Master of Computer Science programme is able to keep up with the evolution in the field of computer science (and related fields), to evaluate and to acquire new technologies. | - EC
| EC 3: A graduate of the Master of Computer Science programme has the necessary knowledge and insights in at least one subdiscipline which allow to contribute to the development and the application of innovative ideas in a certain area of computer science (by deepening basic knowledge at bachelor level, including that of mathematical and other scientific foundations). | - EC
| EC 4: A graduate of the Master of Computer Science programme takes account of the limitations of computer science, such as the existence of undecidedness and the existence of important unresolved problems in computer science such as the P=NP problem. | - EC
| EC 6: A graduate of the Master of Computer Science programme is able to independently situate a scientific problem, analyse and evaluate it, to formulate a research question and propose a solution for this in a scientifically substantiated manner. | - EC
| EC 7: A graduate of the Master of Computer Science programme is able to analyse and evaluate information in a critical manner and to process this information efficiently. | - EC
| EC 12: A graduate of the Master of Computer Science programme is able to critically reflect his or her own approach, to account for this and to adjust his/her behaviour accordingly. |
|
| | EC = learning outcomes DC = partial outcomes BC = evaluation criteria |
|
|
Knowledge of complexity analysis from algorithms and knowledge of theoretical computer science are recommended.
|
|
|
|
In the course Theoretical Computer Science it is shown that there are problems that cannot be solved by a computer: problems that are not "decidable".
In this course we are only interested in decidable problems, but we wonder how much time and how much memory, the computer needs to solve them.
Many known problems can be solved very efficiently by the computer: in the course Algorithms and Data Structures we have learned a whole series of
important efficient algorithms. On the other hand, we will see that there are also problems that are indeed decidable, but not efficiently, both in terms of time and memory.
Somewhere in between these two (efficiently solvable, not efficiently solvable) there appears to be a whole class of major problems
(the so-called NP-complete problems) for which we only know non-efficient, brute-force algorithms.
The surprising observation is that if you find an efficient algorithm for one such problem, you immediately have efficient algorithms for the whole class of NP-complete problems.
The problem of whether NP-complete problems can be solved efficiently is the most famous open problem in computer science.
A lot of important practical computer problems are (unfortunately) NP-complete, for example: problems from artificial intelligence; the planning of business processeses; optimizing solutions.
Yet not everything is unknown in terms of complexity! For example, we can make nice connections between the amount of memory needed to solve a problem and the necessary time.
For example, we will see that problems that can be solved with very little memory usage can also be solved in a reasonable time.
Apart from time and space complexity, this course also looks at space and time hierarchy theorems, Turing Machines equipped with oracles and Boolean circuit complexity,
among other topics.
The general goals of this course are:
1. The student acquires insight into the possibilities and limitations of computer science to solve problems in an efficient manner.
2. The student realizes that a number of fundamental issues about complexity are still unresolved.
|
|
|
|
|
|
|
|
|
Lecture ✔
|
|
|
|
Small group session ✔
|
|
|
|
Period 2 Credits 6,00
|
| Additional information | There is a written exam on theory and exercises. |
|
Second examination period
| Evaluation second examination opportunity different from first examination opprt | |
|
|
|
| Previously purchased compulsory textbooks |
| |
Introduction to the Theory of Computation,M. Sipser,3rd edition, (2nd edition is also fine),PWS Publishing Co |
|
|
| Compulsory course material |
| |
Extra study materials will be made available on Blackboard. |
|
|
|
|
|
| Bachelor of Mathematics year 2 - pakket fundamentele wiskunde | 2-yearly optional (current academic year) | 162 | 6,0 | 162 | 6,0 | Yes | Yes | Numerical | |
| Bachelor of Mathematics year 3 - pakket fundamentele wiskunde | 2-yearly optional (current academic year) | 162 | 6,0 | 162 | 6,0 | Yes | Yes | Numerical | |
|
| | | Learning outcomes |
- EC
| EC 1: A graduate of the Bachelor of Mathematics programme has a thorough basic knowledge and insight in various disciplines of Mathematics including algebra, geometry, analysis, numerical mathematics, probability theory, statistics, aspects of discrete mathematics and logic. | - EC
| EC 2: A graduate of the Bachelor of Mathematics programme has an advanced knowledge and insight into the main branches of Mathematics (pure mathematics, applied mathematics,...). | - EC
| EC 3: A graduate of the Bachelor of Mathematics programme has mastered the formal mathematical language and methodology. He/she is able to work at a sufficiently high level of abstraction. | - EC
| EC 4: A graduate of the Bachelor of Mathematics programme is able to understand a mathematical proof, he/she is able to judge whether an argument is correct and is able to understand which properties are used (in the context of the acquired knowledge). He/she can identify a gap or a redundant step in a proof or a calculation. | - EC
| EC 5: A graduate of the Bachelor of Mathematics programme can apply the theories and methods to relatively simple mathematical problems (theoretical as well as computational). He/she can make and write down a mathematical line of reasoning by him/herself. | - EC
| EC 7: A graduate of the Bachelor of Mathematics programme is able to autonomously comprehend new mathematical basic texts.
| - EC
| EC 11: A graduate of the Bachelor of Mathematics programme has acquired basic knowledge in another scientific discipline. | - EC
| EC 12: A graduate of the Bachelor of Mathematics programme has a basic knowledge of programming and is able to use common mathematical software (e.g.. Maple, Matlab). | - EC
| EC 13: A graduate of the Bachelor of Mathematics programme is familiar with English professional literature.
|
|
| | EC = learning outcomes DC = partial outcomes BC = evaluation criteria |
|
|
Knowledge of complexity analysis from algorithms and knowledge of theoretical computer science are recommended.
|
|
|
|
In the course Theoretical Computer Science it is shown that there are problems that cannot be solved by a computer: problems that are not "decidable".
In this course we are only interested in decidable problems, but we wonder how much time and how much memory, the computer needs to solve them.
Many known problems can be solved very efficiently by the computer: in the course Algorithms and Data Structures we have learned a whole series of
important efficient algorithms. On the other hand, we will see that there are also problems that are indeed decidable, but not efficiently, both in terms of time and memory.
Somewhere in between these two (efficiently solvable, not efficiently solvable) there appears to be a whole class of major problems
(the so-called NP-complete problems) for which we only know non-efficient, brute-force algorithms.
The surprising observation is that if you find an efficient algorithm for one such problem, you immediately have efficient algorithms for the whole class of NP-complete problems.
The problem of whether NP-complete problems can be solved efficiently is the most famous open problem in computer science.
A lot of important practical computer problems are (unfortunately) NP-complete, for example: problems from artificial intelligence; the planning of business processeses; optimizing solutions.
Yet not everything is unknown in terms of complexity! For example, we can make nice connections between the amount of memory needed to solve a problem and the necessary time.
For example, we will see that problems that can be solved with very little memory usage can also be solved in a reasonable time.
Apart from time and space complexity, this course also looks at space and time hierarchy theorems, Turing Machines equipped with oracles and Boolean circuit complexity,
among other topics.
The general goals of this course are:
1. The student acquires insight into the possibilities and limitations of computer science to solve problems in an efficient manner.
2. The student realizes that a number of fundamental issues about complexity are still unresolved.
|
|
|
|
|
|
|
|
|
Lecture ✔
|
|
|
|
Small group session ✔
|
|
|
|
Period 2 Credits 6,00
|
| Additional information | There is a written exam on theory and exercises. |
|
Second examination period
| Evaluation second examination opportunity different from first examination opprt | |
|
|
|
| Previously purchased compulsory textbooks |
| |
Introduction to the Theory of Computation,M. Sipser,3rd edition, (2nd edition is also fine),PWS Publishing Co |
|
|
| Compulsory course material |
| |
Extra study materials will be made available on Blackboard. |
|
|
|
|
|
| Exchange Programme Computer Science | 2-yearly optional (current academic year) | 162 | 6,0 | 162 | 6,0 | Yes | Yes | Numerical | |
|
| |
|
|
Knowledge of complexity analysis from algorithms and knowledge of theoretical computer science are recommended.
|
|
|
|
In the course Theoretical Computer Science it is shown that there are problems that cannot be solved by a computer: problems that are not "decidable".
In this course we are only interested in decidable problems, but we wonder how much time and how much memory, the computer needs to solve them.
Many known problems can be solved very efficiently by the computer: in the course Algorithms and Data Structures we have learned a whole series of
important efficient algorithms. On the other hand, we will see that there are also problems that are indeed decidable, but not efficiently, both in terms of time and memory.
Somewhere in between these two (efficiently solvable, not efficiently solvable) there appears to be a whole class of major problems
(the so-called NP-complete problems) for which we only know non-efficient, brute-force algorithms.
The surprising observation is that if you find an efficient algorithm for one such problem, you immediately have efficient algorithms for the whole class of NP-complete problems.
The problem of whether NP-complete problems can be solved efficiently is the most famous open problem in computer science.
A lot of important practical computer problems are (unfortunately) NP-complete, for example: problems from artificial intelligence; the planning of business processeses; optimizing solutions.
Yet not everything is unknown in terms of complexity! For example, we can make nice connections between the amount of memory needed to solve a problem and the necessary time.
For example, we will see that problems that can be solved with very little memory usage can also be solved in a reasonable time.
Apart from time and space complexity, this course also looks at space and time hierarchy theorems, Turing Machines equipped with oracles and Boolean circuit complexity,
among other topics.
The general goals of this course are:
1. The student acquires insight into the possibilities and limitations of computer science to solve problems in an efficient manner.
2. The student realizes that a number of fundamental issues about complexity are still unresolved.
|
|
|
|
|
|
|
|
|
Lecture ✔
|
|
|
|
Small group session ✔
|
|
|
|
Period 2 Credits 6,00
|
| Additional information | There is a written exam on theory and exercises. |
|
Second examination period
| Evaluation second examination opportunity different from first examination opprt | |
|
|
|
| Previously purchased compulsory textbooks |
| |
Introduction to the Theory of Computation,M. Sipser,3rd edition, (2nd edition is also fine),PWS Publishing Co |
|
|
| Compulsory course material |
| |
Extra study materials will be made available on Blackboard. |
|
|
|
|
|
| Master of Teaching in Sciences and Technology - Engineering and Technology choice for subject didactics math | 2-yearly optional (current academic year) | 162 | 6,0 | 162 | 6,0 | Yes | Yes | Numerical | |
|
| | | Learning outcomes |
- EC
| WET 1. The newly graduated student has advanced knowledge, insight, skills and attitudes in the disciplines relevant to his/her specific subject didactics and is able to communicate these appropriately to his/her stakeholders. | - EC
| WET 2. The newly graduated student can independently set up and conduct research relevant to his field, consisting of a critical literature study, formulating a research question and hypothesis, selecting and optimizing suitable methods and techniques, critically analyzing and interpreting the results, formulating conclusions and reporting of the findings. |
|
| | EC = learning outcomes DC = partial outcomes BC = evaluation criteria |
|
|
Knowledge of complexity analysis from algorithms and knowledge of theoretical computer science are recommended.
|
|
|
|
In the course Theoretical Computer Science it is shown that there are problems that cannot be solved by a computer: problems that are not "decidable".
In this course we are only interested in decidable problems, but we wonder how much time and how much memory, the computer needs to solve them.
Many known problems can be solved very efficiently by the computer: in the course Algorithms and Data Structures we have learned a whole series of
important efficient algorithms. On the other hand, we will see that there are also problems that are indeed decidable, but not efficiently, both in terms of time and memory.
Somewhere in between these two (efficiently solvable, not efficiently solvable) there appears to be a whole class of major problems
(the so-called NP-complete problems) for which we only know non-efficient, brute-force algorithms.
The surprising observation is that if you find an efficient algorithm for one such problem, you immediately have efficient algorithms for the whole class of NP-complete problems.
The problem of whether NP-complete problems can be solved efficiently is the most famous open problem in computer science.
A lot of important practical computer problems are (unfortunately) NP-complete, for example: problems from artificial intelligence; the planning of business processeses; optimizing solutions.
Yet not everything is unknown in terms of complexity! For example, we can make nice connections between the amount of memory needed to solve a problem and the necessary time.
For example, we will see that problems that can be solved with very little memory usage can also be solved in a reasonable time.
Apart from time and space complexity, this course also looks at space and time hierarchy theorems, Turing Machines equipped with oracles and Boolean circuit complexity,
among other topics.
The general goals of this course are:
1. The student acquires insight into the possibilities and limitations of computer science to solve problems in an efficient manner.
2. The student realizes that a number of fundamental issues about complexity are still unresolved.
|
|
|
|
|
|
|
|
|
Lecture ✔
|
|
|
|
Small group session ✔
|
|
|
|
Period 2 Credits 6,00
|
| Additional information | There is a written exam on theory and exercises. |
|
Second examination period
| Evaluation second examination opportunity different from first examination opprt | |
|
|
|
| Previously purchased compulsory textbooks |
| |
Introduction to the Theory of Computation,M. Sipser,3rd edition, (2nd edition is also fine),PWS Publishing Co |
|
|
| Compulsory course material |
| |
Extra study materials will be made available on Blackboard. |
|
|
|
|
|
1 Education, Examination and Legal Position Regulations art.12.2, section 2. |
| 2 Education, Examination and Legal Position Regulations art.16.9, section 2. |
3 Education, Examination and Legal Position Regulations art.15.1, section 3.
|
| Legend |
| SBU : course load | SP : ECTS | N : Dutch | E : English |
|