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

Schedule:            Wednesdays 2:00pm-2:45pm and Thursdays 10am-12am

                            starting 7.10.2015 in T01 see calendar


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


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


Office hours:       Wednesdays 11am-12am 


Tutorium:            Fridays 12am-1:30pm in T03

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: Test 1 on Friday December 11, at 3pm in T01. Test 2 on Tuesday February 2, at 2pm in T01.

                      Full exam on Friday February 26, at 2pm in T01.


Extra class (Q&A): Thursday, December 10, at 3:15pm in T02. Here is a set of example-test tasks.

                                Thursday, January 28, at 3:15pm in (room t.b.a.). Here is a set of example-test tasks.


Extra material: This year we did not manage to cover algebraic structures. However, this material is needed for other lectures.

                          Please read yourself in the following script, and contact me if you have any questions.

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 7.10.15 and Thursday 8.10.15: 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 -- Property 4, and Property 32).

  2. •Week 2, Wednesday 14.10.15 and Thursday 15.10.15: Logic, propositional logic, truth tables, equivalence of propositions -- everything with lots of examples and discussion. Please read until Section 4.4. (page 33) in the Logical Reasoning book. Slides for this week.

  3. •Week 3, Wednesday 21.10.15 and Thursday 22.10.15: Tautologies and contradictions, standard equivalences, calculating with propositions. As always, we showed many examples on the board (also of proofs by calculations). Please read Section 4.4., Chapter 5 and Chapter 6 in the Logical Reasoning book. Slides for this week.

  4. •Week 4, Wednesday 28.10.15 and Thursday 29.10.15. Further calculation proofs, strenghtening and weakening. Predicate logic. Please read Chapter 7 and Chapter 8 in the Logical reasoning book. Slides for this week.

  5. •Week 5, only Thursday 5.11.15 (no class on Wednesday). Equivalences with quantifiers and calculating with quantifiers. Please read Chapter 9 in the Logical reasoning book. Please also read Chapter 10 (which we do not explain in class). Slides for this week.

  6. •Week 6, Wednesday 11.11.15 and Thursday 12.11.15. Derivations -- implication elimination and intro, conjunction elimination and intro, examples. Derivations with other connectives, proofs by contradiction. Please read all of Chapter 11, Chapter 12, Chapter 13, and part of Chapter 14 -- until Section 14.5 in the Logical Reasoning book. Slides for this week.

  7. •Week 7, Wednesday 18.11.15 and Thursday 19.11.15. Derivations with other connectives (continued), derivations with quantifiers. Please read the rest of Chapter 14 (from Section 14.5) and Chapter 15 from the Logical Reasoning book. We will still discuss more examples (of derivation proofs with quantifiers) next week on Wednesday. Slides for this week.

  8. •Week 8, Wednesday 25.11.15 and Thursday 26.11.15. Some more examples of derivation proofs (with quantifiers). Relations, types of relations, many examples. From now on we deviate from the book, even though it is still very helpful if you read the corresponding chapters. Please read Chapter 16 (Sets) from the Logical Reasoning book, as well as Sections 17.1-17.4 from Chapter 17 (Relations). Slides for this week.

  9. •Week 9, Wednesday 2.12.15 and Thursday 3.12.15. Equivalence relations, equivalence classes, partitions. (We proved all properties mentioned on the slides and provided examples to all notions). You may read Chapter 17 (until the end) of the Logical Reasoning book or in any other source dealing with equivalences and partitions. Slides for this week. Note: The corrected slides for Week 8 are now also online -- replacing the ones from last week. The change is in slide nr.5, property 4.)

  10. •Week 10, Wednesday 9.12.15 and Thursday 10.12.15. Transitive closure (leftover from relations); Functions, injective, surjective, bijective functions --- characterizations, properties, and examples. We have proved some of the properties stated in class (will continue on Wednesday next week). You may read Chapter 18 in the Logical Reasoning book, or in any other source dealing with functions. Slides for this week.

  11. •Week 11, Wednesday 16.12.15 and Thursday 17.12.15. Functions (continued) and the structure of natural numbers, induction. Read Chapter 18 (if you have not read it yet) and Chapter 19 from the Logical Reasoning book until Section 19.5.  Slides for this week.

  12. •Week 12, Thursday 7.1.16. Strong induction, structural induction, cardinals. Read Section 19.5 - 19.8 from the Logical Reasoning book. When it comes to cardinals, we do a more detailed treatment -- you may follow the slides and read in any other source on cardinals. Slides for this week.

  13. •Week 13, Wednesday 13.1.16 and Thursday 14.1.15. We still briefly discussed cardinals on Wednesday, and continue with Finite Automata from Thursday on. Read the rest of Chapter 19 from the Logical Reasoning book, and Section 1.1. from the Sipser book. It is also very nice to read all of the introductiory chapter (Chapter 0) of the Sipser book. Slides for this week.

  14. •Week 14, Wednesday 20.1.16 and Thursday 21.1.16. Finite automata continued (NFA, equivalence of NFA and DFA). You may read Section 1.2. in the Sipser book. Slides for this week.

  15. •Week 15, Wednesday 27.1.16 and Thursday 28.1.16. Closure properties, regular expressions, Kleene’s theorem, nonregular languages. You may read the rest of Chapter 1 in the Sipser book, or any other source on finite automata. Slides for this week.

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