# 185.278 Theoretical Computer Science and Logics This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_20",{id:"j_id_20",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_22",{id:"j_id_22",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2021W 2020W 2019W 2018W 2017W 2017S 2016S 2015S 2014S 2013S 2012S 2011S 2010S 2009S 2008S 2007S

2021W, VU, 4.0h, 6.0EC, to be held in blocked form

## Properties

• Semester hours: 4.0
• Credits: 6.0
• Type: VU Lecture and Exercise
• Format: Hybrid

## Learning outcomes

After successful completion of the course, students are able to classify formal languages relative to the Chomsky hierarchy, develop and adequately manipulate formal grammars, as well as recognize limits of computability. Moreover successful participants have a deeper understanding of basic concepts of classical logic and formal specification, in particular with respect to the syntax/semantics division. They can formalize relatively complex sentences in classical first order logic and can use the tableau calculus to find formal proofs. Finally, they can judge the partial and/or total correctness of simple programs and evaluate the correctness of rules for correctness proofs.

## Subject of course

Specification of of formal languages: regular and context free languages (deepening), Chomsky hierarchy, finite automata (deepening), push-down auomata, Turing machines, computability, problem reduction, elements of complexity theory: P, NP; syntax/semantics division, model structures, terms and boolean expressions, syntax and semantics of a simple programming language, classical propositional and first order logic: logical consequence and implication, concep of a logical calculus, semantic tableaux with and without identity, basic properties of first order logic (undecidability, completeness etc.); reasoning about programs: Hoare calculus

## Teaching methods

• formal specification
• mathematical proofs
• derivations in calculi
• formalization in classical first order logic

## Mode of examination

Immanent

The following information is for the (regular) German track of the course only. If you have to get credits for this course to be admitted for a master program in English, please contact Prof. Agata Ciabatoni <agata@logic.at>.

ECTS-Breakdown:

• 40 hours: lecture time
• 60 hours: exercises (homework - 4 blocks)
• 20 hours: four online tests (incl. preparation)
• 30 written examination (incl. preparation)

Total: 150 hours

## Course dates

DayTimeDateLocationDescription
Mon14:00 - 16:0004.10.2021 - 24.01.2022Informatikhörsaal - ARCH-INF Lecture
Wed14:00 - 16:0006.10.2021 - 26.01.2022Informatikhörsaal - ARCH-INF Lecture
Theoretical Computer Science and Logics - Single appointments
DayDateTimeLocationDescription
Mon04.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed06.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon11.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed13.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon18.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed20.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon25.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed27.10.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed03.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon08.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed10.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon15.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed17.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon22.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed24.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon29.11.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed01.12.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon06.12.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Mon13.12.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Wed15.12.202114:00 - 16:00Informatikhörsaal - ARCH-INF Lecture
Course is held blocked

## Examination modalities

If you have to get credits for this course to be admitted for a master program in English, please contact Prof. Agata Ciabatoni <agata@logic.at>. (Otherwise switch to the German version.)

## Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Fri14:00 - 16:0003.02.2023 online [ZOOM link in TUWEL]assessed16.01.2023 12:00 - 31.01.2023 23:59TISS1. Prüfung WS2022
Mon14:00 - 16:0020.03.2023 online [ZOOM link in TUWEL]written28.02.2023 12:00 - 18.03.2023 23:59TISS2. Prüfung WS22
Wed15:00 - 17:0010.05.2023FH Hörsaal 1 - MWB assessed19.04.2023 10:00 - 09.05.2023 12:00TISS3. Prüfung WS 2022
Wed15:00 - 17:0021.06.2023GM 1 Audi. Max.- ARCH-INF assessed31.05.2023 10:00 - 20.06.2023 12:00TISS4. Prüfung WS 2022
Wed15:00 - 17:0021.06.2023FH Hörsaal 1 - MWB assessed31.05.2023 10:00 - 20.06.2023 12:00TISS4. Prüfung WS 2022

## Course registration

Begin End Deregistration end
01.10.2021 10:00 17.10.2021 23:59

## Curricula

Study CodeSemesterPrecon.Info
033 531 Data Engineering & Statistics 2. Semester
033 533 Medical Informatics 3. Semester
Course requires the completion of the introductory and orientation phase
033 534 Software & Information Engineering 3. Semester
Course requires the completion of the introductory and orientation phase
033 535 Computer Engineering 3. Semester
Course requires the completion of the introductory and orientation phase
066 939 Business Engineering and Computer Science

## Literature

All lecture material is available at the TUWEL site for this course..

## Previous knowledge

• Gundkonzepte formaler Sprachen: reguläre Sprachen, endliche Automaten, formale Grammatiken
• Syntax und Semantik der klassischen Logik

Beides wie in 185.A06 Formale Modellierung vermittelt.

German