Skip to main content
MyCourses MyCourses
  • Schools
    School of Arts, Design, and Architecture (ARTS) School of Business (BIZ) School of Chemical Engineering (CHEM) –sGuides for students (CHEM) – Instructions for report writing (CHEM) School of Electrical Engineering (ELEC) School of Engineering (ENG) School of Science (SCI) Language Centre Open University Library Aalto university pedagogical training program UNI (exams) Sandbox
  • Service Links
    MyCourses - MyCourses instructions for Teachers - MyCourses instructions for Students - Teacher book your online session with a specialist - Digital tools for teaching - Personal data protection instructions for teachers - Workspace for thesis supervision Sisu Student guide Courses.aalto.fi Library Services - Resourcesguides - Imagoa / Open science and images IT Services Campus maps - Search spaces and see opening hours Restaurants in Otaniemi ASU Aalto Student Union Aalto Marketplace
  • ALLWELL?
    Study Skills Guidance and support for students Starting Point of Wellbeing About AllWell? study well-being questionnaire
  •   ‎(en)‎
      ‎(en)‎   ‎(fi)‎   ‎(sv)‎
  • Toggle Search menu
  • Hi guest! (Log in)

close

Can not find the course?
try also:

  • Sisu
  • Courses.aalto.fi

CS-C2150 - Theoretical Computer Science, 07.01.2020-08.04.2020

This course space end date is set to 08.04.2020 Search Courses: CS-C2150

  1. Home
  2. Courses
  3. School of Science
  4. department of...
  5. cs-c2150 - th...
  6. Sections
  7. Lectures
 
Syllabus
 

Lectures

  • Lectures

    Lectures

    Because of the coronavirus situation, all teaching on the course has moved to the Zoom remote meeting platform. For further information, see Forums -> Announcements.

    • icon for activity
      FileIntroduction and practical arrangements File
      PDF document
    • icon for activity
      FileIntroduction handout File
      PDF document
    • icon for activity
      FileLecture 1. Mathematical preliminaries, formal languages File
      PDF document

      What is theoretical computer science? Sets. Relations and functions. Equivalence relations. Proof by induction. Automata, alphabets, strings, languages.

    • icon for activity
      FileLecture 1 handout File
      PDF document
    • icon for activity
      FileLecture 2. Finite automata File
      PDF document

      State diagrams and transition tables. Programming with finite automata. Formal definition of finite automata. Excursion: Extensions of finite automata.

    • icon for activity
      FileLecture 2 handout File
      PDF document
    • icon for activity
      FileLecture 3. Finite automata: minimisation and nondeterminism File
      PDF document

      Minimisation of finite automata. Nondeterministic finite automata. Equivalence of deterministic and nondeterministic finite automata.

    • icon for activity
      FileLecture 3 handout File
      PDF document
    • icon for activity
      FileLecture 4. Regular expressions File
      PDF document

      Syntax and semantics of regular expressions. Regular expressions and finite automata. Excursion: Regular expressions in programming languages.

    • icon for activity
      FileLecture 4 handout File
      PDF document
    • icon for activity
      FileLecture 5. Limitations of regular languages; context-free grammars and languages File
      PDF document

      The pumping lemma. Generating strings with grammars. Context-free grammars. Some useful constructions. Right- and left-linear grammars.

    • icon for activity
      FileLecture 5 handout File
      PDF document
    • icon for activity
      FileLecture 6. The parsing problem, parse trees and recursive-descent parsing File
      PDF document

      The parsing problem and parse trees. Recursive-descent parsing. LL(1) grammars. Excursion: Attribute grammars. Excursion: Parsing tools in the Scala language. Supplement: General definition of LL(1) grammars.

    • icon for activity
      FileLecture 6 handout File
      PDF document
    • icon for activity
      FileLecture 7. The CYK parsing algorithm and Chomsky normal form, pushdown automata, limitations of context-free languages File
      PDF document

      Parsing context-free grammars. The Chomsky normal form for CFGs. The CYK parsing algorithm. Pushdown automata. Pushdown automata and context-free languages. A pumping lemma for context-free languages.

    • icon for activity
      FileLecture 7 handout File
      PDF document
    • icon for activity
      FileLecture 8. Turing machines File
      PDF document

      Turing machines. Extensions of Turing machines: multitrack machines, multitape machines, nondeterministic machines. Some computability theory: Turing-recognisable and Turing-decidable languages. Excursion: The halting problem, first encounter.

    • icon for activity
      FileLecture 8 handout File
      PDF document
    • icon for activity
      FileLecture 9. Decidability and undecidability File
      PDF document

      Decidable and semi-decidable languages and problems. Background: countable and uncountable sets. Universal Turing machines and undecidable problems.

    • icon for activity
      FileLecture 9 handout File
      PDF document
    • icon for activity
      FileLecture 10. More on undecidability File
      PDF document

      Undecidability of some Turing machine properties: the halting and non-emptiness problems. Other undecidability results: logic and algebra, Post's correspondence problem, the Chomsky hierarchy. Computable functions and reductions. Excursion: Post's correspondence problem.

    • icon for activity
      FileLecture 10 handout File
      PDF document
    • icon for activity
      FileLecture 11. Rice's theorem, general grammars File
      PDF document

      Rice's theorem. Unrestricted grammars and their relation to Turing machines. Context-sensitive grammars. A glimpse beyond: Computational complexity.

    • icon for activity
      FileLecture 11 handout File
      PDF document
    • icon for activity
      FileLecture 12. Elements of program verification File
      PDF document

      Programs as state transformers. Specification and correctness of programs: weak and strong correctness, proving weak correctness viar loop invariants. Establishing strong correctness.

    • icon for activity
      FileLecture 12 handout File
      PDF document

Course home

Course home

Next section

Tutorials►
Skip Upcoming events
Upcoming events
Loading
Site event MyCourses maintenance, service out of use
Monday, 12 June, 10:00 » 17:00

Go to calendar...
  • CS-C2150 - Theoretical Computer Science, 07.01.2020-08.04.2020
  • Sections
  • Course home page
  • Lectures
  • Tutorials
  • Computerised assignments
  • Additional materials
  • Exams
  • Results
  • Home
  • Calendar
  • Learner Metrics

Aalto logo

Tuki / Support
Opiskelijoille / Students
  • MyCourses instructions for students
  • email: mycourses(at)aalto.fi
Opettajille / Teachers
  • MyCourses help
  • MyTeaching Support form
Palvelusta
  • MyCourses rekisteriseloste
  • Tietosuojailmoitus
  • Palvelukuvaus
  • Saavutettavuusseloste
About service
  • MyCourses protection of privacy
  • Privacy notice
  • Service description
  • Accessibility summary
Service
  • MyCourses registerbeskrivining
  • Dataskyddsmeddelande
  • Beskrivining av tjänsten
  • Sammanfattning av tillgängligheten

Hi guest! (Log in)
  • Schools
    • School of Arts, Design, and Architecture (ARTS)
    • School of Business (BIZ)
    • School of Chemical Engineering (CHEM)
    • –sGuides for students (CHEM)
    • – Instructions for report writing (CHEM)
    • School of Electrical Engineering (ELEC)
    • School of Engineering (ENG)
    • School of Science (SCI)
    • Language Centre
    • Open University
    • Library
    • Aalto university pedagogical training program
    • UNI (exams)
    • Sandbox
  • Service Links
    • MyCourses
    • - MyCourses instructions for Teachers
    • - MyCourses instructions for Students
    • - Teacher book your online session with a specialist
    • - Digital tools for teaching
    • - Personal data protection instructions for teachers
    • - Workspace for thesis supervision
    • Sisu
    • Student guide
    • Courses.aalto.fi
    • Library Services
    • - Resourcesguides
    • - Imagoa / Open science and images
    • IT Services
    • Campus maps
    • - Search spaces and see opening hours
    • Restaurants in Otaniemi
    • ASU Aalto Student Union
    • Aalto Marketplace
  • ALLWELL?
    • Study Skills
    • Guidance and support for students
    • Starting Point of Wellbeing
    • About AllWell? study well-being questionnaire
  •   ‎(en)‎
    •   ‎(en)‎
    •   ‎(fi)‎
    •   ‎(sv)‎