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 2018/2019

Schedule:            Wednesdays 2pm-3pm and

                            Thursdays 10am-12am

                            starting 3.10.2018 in T01 see calendar


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


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


Office hours:       Wednesdays 11am-12am 


Tutorium:            Tuesdays 11am-1pm in T06

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 test will take place on Friday, December 7, at 3pm in HS01 and HS02.

                      Here is a set of example tasks, to be discussed during the Q&A session on Firday, November 30 (2pm in HS02).                     


                      The second partial test will take place on Monday, February 4, at 2pm in HS01 and HS02.

                      Here is a set of example tasks, to be discussed during the Q&A session on Firday, January 25 (12pm in T03).


                      The first full exam will take place on Friday, February 15, at 2pm in T01.

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 3.10.18 and Thursday 4.10.18: Introduction and puzzles, first meeting. This was an unusual class (on Thursday) in which we were solving puzzles in group of around 6 people. The puzzle sets are part of the slides, feel free to continue solving more. Note that there are 10 sets with 20 puzzles in total, but some puzzles repeat -- actually there are 10 different puzzles only. Still enough for a few days of fun :-). The point of this puzzles is that they illustrate sevral important concepts of theoretical computer science, and also show you the need of abstraction, formal reasoning, and the ability to communicate the solutions. At the end we briefly explained the solution to the first puzzle, and the concepts it relates too.
    Here are the slides.

  2. •Week 2, no class on Wednesday 10.10.18 due to “Brückenkurse”. Thursday 11.10.2018, we still discussed the MI -->> MU puzzle from Gödel, Escher, Bach, learned basic notions from naive set theory, and proved some properties. Here are the slides (already in advance). I emailed you the scanned lecture notes.

  3. •Week 3, starting from this week, we will learn Propositiona Logic. Here are the slides in advance (for more than a week), and here are the slides with each stage of builds. In class, on Wednesday 17.10.18 and Thursday 18.10.18, we covered abstract propositions (syntax) as well as truth tables and the boolean behavioral of propositions (semantics) -- shown as slides 1-23. Please read Chapter 2, Chapter 3, and Chapter 4 of [LR].

  4. •Week 4, Wednesday 24.10.18 and Thursday 25.10.18, we learned about calculating with propositions (standard equivalences and meta rules) -- summarized in slides 24-51 (from the Propositional Logic slides). Please read Chapter 5 and Chapter 6 of [LR].

  5. •Week 5, Wednesday 31.10.18 (this is a short week, no class on Thursday 1.11.18 due to public holiday), we did some examples of calculating with propositions, and learned about strengthening and weakening and calculating with weakenings  -- summarized in slides 52-61 (from the Propositional Logic slides). Please read Chapter 7 of [LR].

  6. •Week 6, Wednesday 7.11.18 and Thursday 8.11.18, we learned predicates and quantifiers and some standard equivalences with quantifiers. We will continue next week with calculating with predicate formulas. Here are the slides in advance (for more than a week, so far we covered slides 1-14) and here are the slides with each stage of builds. Please read Chapter 8 and Chapter 9 (up to, including, Section 9.4) of [LR].

  7. •Week 7, Wednesday 14.11.18 and Thursday 15.11.18, we continued calculating with predicates and quantifiers, and started derivations/reasoning.  We covered the material summarized in slides 14-20 from the PredicatesQuantifiers set of slides. Here are the slides on Derivations (for more than a week, so far we covered slides 1-10) and here are the slides with each stage of builds. Please read Chapter 9 (from Section 9.5) and Chapter 11 and 12 from [LR]. Please also read yourself Chapter 10 from [LR], although we did not discuss it in class.

  8. •Week 8, (no class on Wednesday 21.11 due to my travelling) Thursday 22.11.18, Derivations/reasoning with other connectives.  We covered the material summarized in slides 11-26 from the Derivations set of slides. Please read Chapter 13 and 14 from [LR].

  9. •Week 9, Wednesday 28.11.18 and Thursday 29.11.18, Derivations/reasoning with predicates and quantifiers. We covered the material in the Derivations slides from slide 27. Please read Chapter 15 from [LR].

  10. •Week 9, Wednesday 5.12.18 and Thursday 6.12.18, Relations. Here are the slides in advance (for more than a week, so far we covered slides 1-9) and here are the slides with each stage of builds. I will email you a copy of my lecture notes by Monday. Please read Chapter 17 (up to, including, Section 17.4) of [LR] as additional material. It is also good to read Chapter 16 of [LR] as a preparation, if you have not read it before.

  11. •Week 10, Wednesday 12.12.18 and Thursday 13.12.18: Equivalences, equivalence classes, partitions, transitive closure; we also started the topic of functions. We covered the material from slide 10 in the Relations set of slides.  I will email you a copy of my lecture notes by Monday. Please read the rest of Chapter 17 (from Section 17.5) of [LR] as additional material, as well as Section 18.1 and 18.2 from [LR].

  12. •Week 11, Wednesday 9.1.19 and Thursday 10.1.19: Functions, continued --- please check the Functions set of slides and here are the slides with each stage of builds.  I will email you a copy of my lecture notes by Monday. Please read the rest of Chapter 18 (from Section 18.3) of [LR] as additional material. We also discussed the structure of the natural numbers and induction -- please check these slides and here are the slides with each stage of builds. Please also read Section 19.1-19.4  from [LR].

  13. •Week 12, Monday 14.1.19, 3pm-5pm (extra class for lost Wednesday classes on 21.11. and 19.12), Wednesday 16.1.19 and Thursday 17.1.19. We finished the discussion on induction, with some examples, and learned further Cardinality, proved many properties and looked at examples, and finally moved to Finite Automata. For Cardinals, you can look at the following slides also slides with each stage of builds; for Automata --- until the end of the semester --- we will use the following set of slides and slides with each stage of builds. Today we discussed the material summarised in the first 7 slides. I already sent you detailed lecture notes regarding the parts on Naturals and Cardinals, and will send you the first part of the lecture notes on Automata this weekend. Please also read the rest of Chapter 19 from [LR] as well as Section 1.1 from [Comp]. I also highly recommend reading the nice introductory Chapter of [Comp] whenever you find some extra time.

  14. •Week 13, Wednesday 23.1.19 (with Sebastian Arming) and Thursday 24.1.19. We continued discussing finite automata (many examples on Wednesday), regular expressions, Kleene’s theorem, and nondeterministic finite automata. You can read Section 1.2 and 1.3 (although we did not yet discuss everything) from [Comp].

  15. •Week 14, Wednesday 30.1.19 and Thursday 31.1.19. We continued discussing nondeterministic finite automata and equivalence of NFA and DFA (determinisation), we proved the closure properties that motivated the study of nondeterminism, and briefly discussed nonregular languages and the pumping lemma. You can read the rest of Chapter 1 from [Comp].


IMPORTANT: We did not cover algebraic structures within the course, but basic knowledge of algebraic structures is expected in later courses. Please read the following brief lecture notes on algebraic structures on your own, and contact me if you need some help.


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