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 2016/2017

Schedule:            Wednesdays 2:00pm-2:45pm (change in schedule)

                            and Thursdays 10am-12am

                            starting 5.10.2016 in T01 see calendar


First meeting:       Wednesday, October 5 at 1pm in T01


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


Office hours:       Wednesdays 11am-12am 


Tutorium:            Tuesdays 5pm-6:30pm in T02

Literature:


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


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


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

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


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: 1st partial test on December 16, 2016 (Friday), 2pm-5pm in T01.

                      Here is an example set of tasks.

                     Q&A sesstion on November 25, 2016 (Friday), 11am-1pm in T03.


                      2nd partial test on February 7, 2017 (Tuesday), 1pm-4pm in T01.

                      Here is an example set of tasks.

                      Q&A sesstion on February 3, 2017 (Friday), 1pm-3pm, room t.b.a.

                      1st full exam on February 28, 2017 (Tuesday), 2pm-5pm 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 5.10.16 and Thursday 6.10.16: Introduction and sets, first meeting. Slides for this week (in class we will look at many examples of all notions and proved some of the set properties listed at the end).

  2. •Week 2, Wednesday 12.10.16 and Thursday 13.10.16: More example proofs of set properties; propositional logic (truth tables, equivalence of propositions). Slides for this week. Please read Chapter 1, 2, and 3, as well as Section 4.1 and 4.3 from the Logical Reasoning book.

  3. •Week 3, Wednesday 19.10.16 and Thursday 20.10.16: Equivalence of propositions, tautologies and contradictions, standard equivalences, and calculating with equivalent propositions. Slides for this week. Please read Sections 4.3 and 4.4, Chapter 5, and Chapter 6 from the Logical Reasoning book.

  4. •Week 4, Thursday 27.10.16 (no class on Wednesday 26.10.16 due to public holiday). Calculating with equivalent propositions (continued), strengthening and weakening, calculating with weakenings, standard weakenings. Slides for this week. Please read Chapter 7 from the Logical Reasoning book.

  5. •Week 5, Thursday 3.11.16 (no class on Wednesday 2.11.16 due to public holiday). Predicate logic, equivalences with quantifiers (just started). Slides for this week. Please read Chapter 8 and Section 9.1 and 9.2 from the Logical Reasoning book.

  6. •Week 6, Wednesday 9.11.16 and Thursday 10.11.16. Predicate logic, equivalences with quantifiers, calculating with equivalent propositions, derivation (implication and conjunction intro and elimination). Slides for this week. Please read Chapter 9 starting from Section 9.3, Chapter 10 (for your information), and Chapter 11 and 12 from the Logical Reasoning book.

  7. •Week 7, Wednesday 16.11.16 and Thursday 17.11.16. Derivations (continued) - reasoning with other connectives, different kinds of proofs, derivations with quantifiers. Slides for this week. Please read Chapter 13, 14, and 15 up to (including) Section 15.2. from the Logical Reasoning book.

  8. •Week 8, Wednesday 23.11.16 and Thursday 24.11.16. Alternative intro and elimination rules for existential quantification, more examples of  proofs by derivation; Back to naive set theory - relations. Slides for this week.  Please read Chapter 15 from the Logical Reasoning book, as well as Chapter 16 and 17  up to (including) Section 17.4. Note that from now on we will deviate from the book, but it is still of great help to read the corresponding chapters. It is also of great help to come to the lectures.

  9. •Week 9, Wednesday 30.11.16 and Thursday 1.12.16. More on relations, equivalences, partitions. Slides for this week. Please read Chapter 17 from the Logical Reasoning book.

  10. •Week 10, Wednesday 7.12.16 (this is a short week as Thursday 8.12.16 is a holiday). Functions - just started with basic definitions and examples. Slides for this week. Please note that next week Wednesday the class will be again from 1:15pm to 2pm (only next week!).

  11. •Week 11, Wednesday 14.12.16 and Thursday 15.12.16. Functions (special functions, composition of functions, properties). Slides for this week. Please read Chapter 18 in the Logical Reasoning book, or any other source dealing with functions (definitions and basic properties).

  12. •Week 12, Wednesday 21.12.16 and Thursday 22.12.16. The structure of natural numbers, induction, and cardinals. Slides for this week. Please read Chapter 19 in the Logical Reasoning book. In class we went quickly through many properties (regarding cardinals) -- we will return to their proofs after the Christmas break.

  13. •Week 13, no classes due to my traveling -- double classes next week.

  14. •Week 14, Wednesday 18.1.17, Thursday 19.1.17, as well as Friday (2pm-5pm in T02) 20.1.17. Cardinals -- we proved all properties that we briefly discussed before the Christmas break; Finite Automata -- DFA, regular languages, regular expressions, closure properties of regular languages, Kleene’s theorem -- as usual, proofs and examples on the board. Slides for this week. Please read in any source where FA are discussed, e.g. in the book by Sipser.

  15. •Week 15, Wednesday 25.1.17 and Thursday 26.1.17. Nondeterministic Automata, equivalence of NFA and DFA, more closure properties of regular languages, lumping lemma, nonregular languages. Slides for this week. Please read in any source where FA are discussed, e.g. in the book by Sipser.

Extra material: This year we did not manage to cover algebraic structures. However, this material may be needed for other   lectures. Please read yourself in the following lecture notes, and contact me if you have any questions.

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