Address

Jakob-Haringer-Str. 2

5020 Salzburg, Austria


Room 2.17


Phone

+43 (0)662 8044 6417

+43 (0)662 8044 611 (fax)


Skype ana_sokolova

Home

Papers

Talks

Teaching

Personal

Many thanks to Silviu Craciunas for the photo (RTAS 2010 in Stockholm) and his help with iWeb!

Formale Systeme 511.001 (lectures), Winter semester 2017/2018

Schedule:            Wednesdays 2pm-3pm and

                            Thursdays 10am-12am

                            starting 4.10.2017 in T01 see calendar


First meeting:       Wednesday, October 4 at 2pm in T01


Language:           Teaching in German, course material (mainly) in English


Office hours:       Wednesdays 11am-12am 


Tutorium:            Tuesdays 4pm-5:30pm in HS02 (lab building - material sciences)

Literature:


  1. •Textbook: Logical Reasoning: A First Course, by Rob Nederpelt and Fairouz Kameraddine, King’s College London Publications, 2007. [LR]


  1. •Textbook: How to Think Like a Mathematician, by Kevin Houston, Cambridge University Press, 2009. [Think]

  2. •Lecture Notes on Math Basics by Harald Woracek, TU Vienna, 2017 [LN]


  1. •Textbook: Modellierung: Grundlagen und formale Methoden by Uwe Kastens and Hans Kleine Buening, Hanser, 2005. [Mod]


  1. •Textbook: Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Pearson/Addison-Wesley, 2007. [Aut]

  2. •Textbook: Introduction to the Theory of Computation, by Michael Sipser, Cengage, 2005. [Comp]


The books can be ordered via Amazon.de . Some copies are available at the department library.

Prerequisites:  None, the course material is self-contained, as are the textbooks.

Exam:   The exam is written. In case a student wants to improve his/her grade, an additional oral exam can be scheduled. One can pass the exam by either (1) passing the two partial tests within the semester, or (2) passing one of the possible full exams that will be scheduled after the semester ends. The tests/exam consist of several exercises from the material covered during the course.


In order to pass via the partial tests (1) one needs to: have in sum a total of 55% of the maximal points available at both tests and no less than 20% of the maximal number of points at each one test. That is, if partial test 1 brings maximally 100 points and partial test 2 also 100 points, in order to pass one needs to have at least 20 points on each test and a total sum of at least 110 points on both tests.


In order to pass via one of the exam possibilities one needs to have 55% of the maximal points available at the exam. That is, if the exam brings maximally 100 points, in order to pass one needs to have at least 55 points.


Note that the exams cover the full course material, whereas each partial test covers one half of the material.


Exam dates: The first partial exam will be held on December 15, 2:30-5:30pm, in HS01 and HS02.

                      Here is a set of example tasks, to be discussed during the Q&A session on Tuesday, December 12, at 5pm in HS02.


                      The second partial exam will be held on February 5, 2018, 2pm-5pm, in T01 and T03.

                      Here is a set of example tasks, to be discussed during the Q&A session on Friday, February 2, at 3pm in T01.

                     

                      The full exam (first possibility) will be held on February 12, 2018, 2pm-5pm, in T01 and T03.

Course description:  This is a first-semester obligatory course on basics of theoretical computer science: logic and sets.

In this course we will learn the basics of formal methods, the alphabet :-) necessary to read and write basic theoretical computer science. In particular we will learn logic and logical reasoning (propositional and predicate logic, basic proof methods) and apply it to learn and understand sets, relations, functions, orderings, algebra, finite automata, labelled transition systems, and Hoare triples for reasoning about programs.

Slides:  Whenever slides are used, they will be made available on this webpage. The slides are by no means complete and only serve as help for better presentation. More material is covered during the class (on the blackboard) than visible on the slides.

Schedule: 


  1. •Week 1, Wednesday 4.10.17 and Thursday 5.10.17: Introduction and sets, first meeting. Slides for this week (in class we looked at many examples of all notions and proved some of the set properties listed at the end). Please read the introducory chapter in [LR] as well as Chapter 1 (Einleitung) from [LN].

  2. •Week 2, no class on Wednesday 11.10.17 due to “Brückenkurse”. There will be a class on Thursday morning as normal.  Slides for this week. We first still proved an interesting property of sets, and then started with basics of propositional logic: propositions (syntax) and truth tables (semantics). Please read Chapter 2 and Chapter 3 of [LR].

  3. •Week 3, Wednesday 18.10.17 and Thursday 19.10.17: Equivalence of propositions, standard equivalences, calculating with equivalent propositions. Slides for this week. Please read Chapter 4, 5, and 6 of [LR].

  4. •Week 4, only Wednesday 25.10.17: Strengthening and weakening. This class was given by Markus Flatz. slides for week 4. Please read Chapter 7 of [LR].

  5. •No class in week 5, due to public holidays.

  6. •Week 6, predicate logic, quantifiers, equivalences with quantifiers.  Slides for week 6. Please read Chapter 8 and 9 until Section 9.6 of [LR].

  7. •Week 7, predicate logic continued, derivations / reasoning. These classes were given by Sebastian Arming. Slides for week 7. Please read the rest of Chapter 9, also Chapter 10 that was not discussed in class but is significant as infortmation -- as well as Chapter 11-14 including Section 14.4 from [LR].

  8. •Week 8, Derivations / reasoning continued, derivations with quantifiers. Slides for week 8. Please read the rest of Chapter 14 and Chapter 15 from [LR]. We will still do more examples next Wednesday.

  9. •Week 9, examples of derivation proofs with quantifiers, and back to (naive) set theory - relations. Slides for week 9. Please read through Chapter 16 and Chapter 17 (until Section 17.5) from [LR] and read Section 2.1 and 2.2 from [LN].

  10. •Week 10, relations continued, equivalences, equivalence classes, partitions, correspondence of equivalences and partitions. Slides for week 10. Please read the rest of Chapter 17 from [LR] and I strongly encourage you to read Section 2.2 and Section 2.3 from [LN].

  11. •Week 11, functions, image and inverse image, injections, surjections, bijections. We proved some of the properties in class and looked at many examples. We will prove few more properties next week.  Slides for week 11. Please read Chapter 18 from [LR] and Section 2.4 and 2.5 from [LN].

  12. •Week 12, still a bit more properties of functions, (natural) numbers and structures, cardinality. Slides for week 12. Please read Chapter 19 until Section 19.9 from [LR] and Section 3.1 and 3.2 from [LN]. Moreover, please read yourself during the Christmas break the following lecture notes on basics of algebra, and Section 3.3 from [LN]. You will be expected in other courses to have basic knowledge of algebra.

  13. •Week 13, Cardinality (we proved many of the properties mentioned last time), discussed examples, and we started with finite automata, deterministic ones. Slides for week 13. Please read the rest of Chapter 19 from [LR] and in any source where FA are discussed, e.g. in the book by Sipser.

  14. •Week 14, DFA, continued: examples, an extensive proof of regularity of a simple language, regular operations, closure properties, regular expressions.  Slides for week 14. Please read in any source where FA are discussed, e.g. in the book by Sipser.

  15. •Week 15, FA, continued: NFA, closure properties, Kleene’s theorem, determinisation, nonregular languages. We gave proof sketches of most results (but had no time to prove the pumping lemma). Slides for week 15. Please read in any source where FA are discussed, e.g. in the book by Sipser.

Ana Sokolova

Dr. TU Eindhoven, The Netherlands, 2005



Associate Professor


Computational Systems Group

Department of Computer Sciences

University of Salzburg

Austria


anas@cs.uni-salzburg.at