PDF for print    Find calendar

Elective course: Theoretical Computer Science

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
  • Knowledge

  • Knowledge and understanding of a specific Informatics subject area.

  • A comprehensive overview and understanding of the general principles behind the subject area’s theory, methods and technological solutions.

  • Skills:

  • Selecting and applying appropriate methods and techniques from the subject area.

  • Kompetencer:

  • Being able to work with IT issues, both independently and in teams.

  • Being able to critically and systematically learn new approaches to the subject area and thereby independently take responsibility for one’s own professional development.

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)
Exam code(s) : U41141
Last changed 15/03/2021

lecture list:

Show lessons for Subclass: 1 Find calendar (1) PDF for print (1)

Friday 10-09-2021 12:15 - 10-09-2021 16:00 in week 36
Theoretical Computer Science (INF)

Friday 17-09-2021 12:15 - 17-09-2021 16:00 in week 37
Theoretical Computer Science (INF)

Friday 24-09-2021 12:15 - 24-09-2021 16:00 in week 38
Theoretical Computer Science (INF)

Friday 01-10-2021 12:15 - 01-10-2021 16:00 in week 39
Theoretical Computer Science (INF)

Friday 08-10-2021 12:15 - 08-10-2021 16:00 in week 40
Theoretical Computer Science (INF)

Friday 15-10-2021 12:15 - 15-10-2021 16:00 in week 41
Theoretical Computer Science (INF)

Friday 22-10-2021 12:15 - 22-10-2021 16:00 in week 42
Theoretical Computer Science (INF)

Friday 29-10-2021 12:15 - 29-10-2021 16:00 in week 43
Theoretical Computer Science (INF)

Friday 05-11-2021 12:15 - 05-11-2021 16:00 in week 44
Theoretical Computer Science (INF)

Friday 12-11-2021 12:15 - 12-11-2021 16:00 in week 45
Theoretical Computer Science (INF)

Friday 19-11-2021 10:00 - 19-11-2021 10:00 in week 46
Theoretical Computer Science - Hand-in (INF)

Thursday 06-01-2022 08:15 - Friday 07-01-2022 18:00 in week 01
Theoretical Computer Science - Oral examination (INF)

Thursday 17-02-2022 10:00 - 17-02-2022 10:00 in week 07
Theoretical Computer Science - Reexam - Hand-in (INF)

Friday 25-02-2022 08:15 - 25-02-2022 18:00 in week 08
Theoretical Computer Science - Oral reexamination (INF)