Theory of Computation
Course Contents (Syllabus):
Finite automata and regular expressions. Pushdown automata and context-free grammars. Turing machines and Church's thesis. Undecidability. Computational complexity.
Required course, 3rd year
Prerequisites and/or related courses:
Discrete Mathematics, Algorithms and Complexity, Graph Theory
Objectives:
- Automata and formal grammars
- Turing Machines- Determinism vs non-determinism
- Unsolvability
- Polynomial hierarchy
- P vs NP
Teaching Methods:
Theory lectures (5h/week).
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes
Recommended reading:
- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).
- H. R. Lewis & Ch. Papadimitriou, ‘’ Elements of Computation’’, Kritiki, 2005 (in Greek).
Bibliography:
- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).
- H. R. Lewis & Ch. Papadimitriou, ‘’ Elements of Computation’’, Kritiki, 2005 (in Greek).
Discrete Mathematics I
Course Contents (Syllabus):
Propositional Logic, logical reasoning methods (mathematical induction, reductio ad absurdum, proof by contradiction, etc), sets, relations and functions, combinatorics, introduction to discrete probability.
Required course, 1st year
Prerequisites and/or related courses:
Objectives:
Learn how to
- use propositional logic
- use reasoning methods for constructing proofs
- use sets, relations and functions
- count combinations
- compute discrete probability
Teaching Methods:
Theory lectures (5h/week).
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes
Recommended reading:
- S. Epp, ‘’Discrete Mathematics with Applications’’.
- K. Rosen, ‘’Discrete Mathematics and its Applications”.
- D. Hunter, “Essentials of Discrete Mathematics”
Graph Theory
Course Contents (Syllabus):
Basic Graph Parameters. Directed Graphs, Cliques, Bipartite and Planar Graphs. Euler and Hamilton Cycles. Minimum Spanning Trees, Depth First Search, Breadth First Search, Shortest Paths. Maximum Flows. The Matching problem. NP-complete problems: Vertex Cover, Vertex Coloring, Maximum Clique.
Elective course, >= 3rd year
Prerequisites and/or related courses:
Discrete Mathematics, Data Structures, Algorithms and Complexity.
Objectives:
- Modeling algorithmic problems in graphs
- Analyzing and proving graph properties
- Graph Algorithms
Teaching Methods:
Theory lectures (4h/week) and additionally seminars (2h/ 3 weeks) solving exercises.
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes
Recommended reading:
- Graph Theory and Algorithms, I. Manolopoulos, A. Papadopoulos, K. Tsichlas, Ekdosis Neon Technologion Mon. EPE, 2013 (in Greek).
- Introduction to Graphs, L. Kirousis, X. Mpouras, P. Spirakis, Y, Stamatiou, Ekdosis G. Dardanos - K. Dardanos O.E., 1999 (in Greek).
Distributed Computing
Course Contents (Syllabus):
Distributed algorithms by autonomous agents. Examples in geometric environments, communication networks, distributed databases, internet. Models of computation. Basic algorithms for message-passing systems. Algorithms and models of computation for robots in 2D/3D space. Algorithms for mobile agents in networks. Implementation and visualization of distributed algorithms. The Look-Compute-Move model. Synchronous and asynchronous systems. The Rendezvous (Gathering) problem. The Pattern problem. The Exploration problem. Faulty networks with hostile nodes. Algorithms for discovering hostile nodes. Fault tolerant algorithms. The Graph Searching problem. Reliable communication in faulty environments.
Post-graduate course.
Prerequisites and/or related courses:
Discrete Mathematics, Design and Analysis of Algorithms, Graph Theory, Theory of Computation, Distributed Systems
Bibliography:
- Algorithmic Theory of Distributed Computing (in greek), Markou, E., Kranakis, E., Pagourtzis, A., & Krizanc, D. (2015). Kallipos, Open Academic Editions. https://dx.doi.org/10.57713/kallipos-476