Semester |
E2021
|
Subject |
Computer Science * / Informatics * / Mathematical Computer Modelling *
|
Activitytype |
master course
|
Teaching language |
English
|
Registration |
Tilmelding sker via STADS-Selvbetjening indenfor annonceret tilmeldingsperiode, som du kan se på Studieadministrationens hjemmeside Når du tilmelder dig kurset, skal du være opmærksom på, om der er sammenfald i tidspunktet for kursusafholdelse og eksamen med andre kurser, du har valgt. Uddannelsesplanlægningen tager udgangspunkt i, at det er muligt at gennemføre et anbefalet studieforløb uden overlap. Men omkring valgfrie elementer og studieplaner som går ud over de anbefalede studieforløb, kan der forekomme overlap, alt efter hvilke kurser du vælger. Registration through STADS-Selvbetjeningwithin the announced registration period, as you can see on the Studyadministration homepage. When registering for courses, please be aware of the potential conflicts between courses or exam dates on courses. The planning of course 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. |
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. Automata theory. What can and cannot be computed? • Finite state machines, pushdown automata, Turing machines, lambda calculus • Universality of Turing machines. The Church-Turing thesis • Uncomputable functions; the Halting problem Formal languages • Different language classes and their relation to automata. Context-free grammars, The Chomsky Hierarchy of languages. Complexity of algorithms • Main complexity classes. P≠NP conjecture. NP complete problems. From theory to practice. Important applications of theoretical computer science, such as compiler implementation and program verification and analysis. |
Expected work effort (ECTS-declaration) |
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. |
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. |
Evaluation- and feedback forms |
Written course evaluation form and verbal feedback during final course lecture. Open forum on course website. |
Administration of exams |
IMT Studieadministration (imt-studieadministration@ruc.dk)
|
Responsible for the activity |
Mads Rosendahl (madsr@ruc.dk)
|
ECTS |
5
|
Learning outcomes and assessment criteria |
|
Overall content |
With the topic of their own choosing, the student has the opportunity to specialise 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 the design and implementation of IT applications. Subjects can include: IT strategy, IT project management, sourcing of IT projects, IT and enterprise architecture, design and innovation in IT organisations |
Teaching and working methods |
Normal class instruction, i.e. a mix of lecturer presentations, student presentations and practical work on specific tasks. Lectures with exercises. |
Type of activity |
Elective course |
Form of examination |
Individual oral exam based on an assignment.
The exam is conducted as a dialogue. There may be posed questions in any part of the curriculum. 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
|
Exam code(s) | |
Last changed | 15/03/2021 |