Items list

Subject Code: IC233
ECTS: 6
Study Program: Undergraduate Degree Program
Teaching Semester: Semester 6
Type
 Επιλογής
Κατεύθυνση ΓΝΜ: Βασικό
Κατεύθυνση ΘΡΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΕΦΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΠΛΗ: Υποχρεωτικό Κατεύθυνσης
Κατεύθυνση ΣΠΕ: Ελεύθερης Επιλογής
Teaching Hours (Theory / Tutorial / Laboratory): 2-2-0
Teachers: Raggos Omiros
Erasmus Students: No
Description
of Computation Theory Part One: Logic and Proof. Repetition in Propositional Logic: Alphabet, syntax and semantics. Repetition in Categorical Logic: Alphabet, syntax and semantics, Basic proof methods: Direct proof, Proof by contrainversion, Proof of existence (with construction and without construction), Non-direct proof, Proof by mathematical induction (weak and strong form of induction). Formal inference systems: Hilbert-style systems, Important tables. Recursion and induction. Verification of programs using Hoare Logic: Partial code correctness, Total code correctness. Relations-Relational databases (elementary presentation of Prolog). Part Two. Automata and formal languages. Alphabets and languages. Regular expressions and regular languages. Deterministic and non-deterministic finite automata. Extraction lemma for regular languages. Grammars and context-free languages. Regular grammars. Simplification and reduction of grammars. Extraction lemma for context-free languages. Stack automata. Syntactic analysis. Turing machines. Computations with Turing machines. Unconstrained grammars. Computability. Undecidable languages. Recursively enumerable languages. The limits of computability. Rice's theorem.