050057 VU Theoretische Informatik 2 (2006W)
Theoretische Informatik 2
Continuous assessment of course work
Labels
Di 12:30-15:00 HS7 UZA2,
Do 14:45-17:00 HS5 UZA2 (Nordbergstr. 15),
Beginn: Do, 5.10.2006
Do 14:45-17:00 HS5 UZA2 (Nordbergstr. 15),
Beginn: Do, 5.10.2006
Details
max. 50 participants
Language: German
Lecturers
Classes
Currently no class schedule is known.
Information
Aims, contents and method of the course
Assessment and permitted materials
Minimum requirements and assessment criteria
This class will present advanced concepts in Theoretical
Computer Science, based upon Theoretical Computer Science I.
The principal objectives include the study of the key
theoretical concepts underlying computer science,
and their application to a range of problems occurring in
real application contexts.Four topics will be discussed in detail:
computability and decidability, complexity theory,
predicate logic, and semantics of programming languages.The study of computability and decidability is motivated
by the fact that not every problem can be solved
algorithmically. We will discuss a number of diverse
formal approaches to computability all of which turn out to
be equivalent with respect to their expressivity.While the theory of computability addresses only the
principal possibility of solving a problem algorithmically,
without taking into account the actual effort required for
a practical solution, complexity theory deals with precisely
this issue. We will introduce complexity classes that
characterize the effort with respect to time and/or memory
required for the solution of a problem.Predicate logic provides a formal system that allows the
mechanical deduction of valid sentences based on a set of
axioms. This provides a framework that will be of use in the
subsequent discussion of program verification.The final part of the class deals with programming language
semantics and program verification and validation. We will
introduce basic concepts of operational semantics, Hoare
and wp-semantics, and denotational semantics.
Computer Science, based upon Theoretical Computer Science I.
The principal objectives include the study of the key
theoretical concepts underlying computer science,
and their application to a range of problems occurring in
real application contexts.Four topics will be discussed in detail:
computability and decidability, complexity theory,
predicate logic, and semantics of programming languages.The study of computability and decidability is motivated
by the fact that not every problem can be solved
algorithmically. We will discuss a number of diverse
formal approaches to computability all of which turn out to
be equivalent with respect to their expressivity.While the theory of computability addresses only the
principal possibility of solving a problem algorithmically,
without taking into account the actual effort required for
a practical solution, complexity theory deals with precisely
this issue. We will introduce complexity classes that
characterize the effort with respect to time and/or memory
required for the solution of a problem.Predicate logic provides a formal system that allows the
mechanical deduction of valid sentences based on a set of
axioms. This provides a framework that will be of use in the
subsequent discussion of program verification.The final part of the class deals with programming language
semantics and program verification and validation. We will
introduce basic concepts of operational semantics, Hoare
and wp-semantics, and denotational semantics.
Examination topics
Reading list
Association in the course directory
Last modified: Fr 31.08.2018 08:48
Computer Science, based upon Theoretical Computer Science I.
The following topics will be addressed in detail:- Computability and DecidabilityIntroduction to important formal models for computability;
recursive function theory; Turing Machines; Church's Thesis;
decidability; decidability issues in languages and automata
of the Chomsky Hierarchy- Complexity TheoryComplexity measures; the classes P and NP; languages
and problems; NP-completeness of the satisfiability problem;
additional NP-complete problems; overview of
additional complexity classes- Predicate LogicGeneral introduction to predicate logic; deduction.- Semantics of Programming LanguagesPredicate logic as a programming language; operational
semantics; Hoare-semantics
and wp-semantics; elements of denotational semantics;
program verification and validation.