PDF for print
Find calendar
| Title |
Elective Course: Theoretical Computer Science
|
| Semester |
E2022
|
| Master programme in |
Computer Science * / Informatics * / Mathematical Computer Modelling * / Computer Science / Digital Transformation
|
| Type of activity |
Course |
| Teaching language |
English
|
| Study regulation |
Read about the Master Programme and find the Study Regulations at ruc.dk |
| REGISTRATION AND STUDY ADMINISTRATIVE | |
| Registration |
Sign up for study activities at STADS Online Student Service within the announced registration period, as you can see on the Study administration homepage. When signing up for study activities, please be aware of potential conflicts between study activities or exam dates. The planning of activities at Roskilde University is based on the recommended study programs which do not overlap. However, if you choose optional courses and/or study plans that goes beyond the recommended study programs, an overlap of lectures or exam dates may occur depending on which courses you choose. |
| Number of participants |
|
| ECTS |
5
|
| Responsible for the activity |
Mads Rosendahl (madsr@ruc.dk)
|
| Head of study |
Henrik Bulskov (bulskov@ruc.dk)
|
| Teachers |
|
| Study administration |
IMT Studyadministration (imt-studyadministration@ruc.dk)
|
| Exam code(s) |
U60464
|
| ACADEMIC CONTENT | |
| Overall objective |
With an elective course, the student has the opportunity to specialize in a specific subject area where the student acquires knowledge, skills and competences in order to translate theories, methods and solutions ideas into their own practice in relation to software development. Examples of elective courses: Robotics, AI, internet technologies, programming language, parallel calculation, mobile computers, etc. |
| Detailed description of content |
The aim of the course is cover central concepts in the foundation of computer science. These are topics which computer scientists are traditionally expected to be familiar with. • Hierarchy of languages: Different language classes and their relation to computational models. Formal languages, regular expressions, context-free grammars, the Chomsky hierarchy of languages. Parsing of formal lanuages and programming languages. • Computation: Finite state machines, pushdown automata, Turing machines, lambda calculus, universality of Turing machines. The Church-Turing thesis • Computability: What can and cannot be computed? The halting problem, complexity of algorithms, P≠NP conjecture. NP complete problems. Uncountable and recursively enumerable sets. The course assumes programming skills corresponding to a bachelor degree in computer science. |
| Course material and Reading list |
Recommended course textbook: Elements of the Theory of Computation, 2/E, Lewis & Papadimitriou, ISBN-10: 0132624788 | ISBN-13: 9780132624787. Slides and handouts. |
| Overall plan and expected work effort |
The course will have a total workload of 135 hours with 40 hours of lectures and exercises, 70 hours of preparation over an 11 week course period and 25 hours for the exam and preparation before the course. |
| Format |
|
| Evaluation and feedback |
Written course evaluation form and verbal feedback during final course lecture. Open forum on course website. |
| Programme |
Computer Science |
| ASSESSMENT | |
| Overall learning outcomes |
After completing this course, students will be able to:
|
| Form of examination |
Individual oral exam based on a written product
The character limit of the written product is maximum 48,000 characters, including spaces. The character limits include the cover, table of contents, bibliography, figures and other illustrations, but exclude any appendices. Time allowed for exam including time used for assessment: 20 minutes. The assessment is an overall assessment of the written product(s) and the subsequent oral examination. Permitted support and preparation materials for the oral exam: All. Assessment: 7-point grading scale. Moderation: Internal co-assessor. |
| Form of Re-examination |
Samme som ordinær eksamen / same form as ordinary exam
|
| Type of examination in special cases |
|
| Examination and assessment criteria |
The exam is based on an assignment consisting of a number of smaller exercises done during the coursse. At the exam we discuss some of the exercises and the assessment is based on the general understanding of the central concepts in the course as listed in the detailed description of the course. |
| Exam code(s) | |
| Last changed | 29/09/2022 |
Find calendar (1)
PDF for print (1)