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

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

                            8.10.2014 in T01 see calendar


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


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


Office hours:       Wednesdays 11am-12am 


Tutorium:            Tuesdays 12am-1pm in T06 starting 14.10.14 including 11.11.14

                            Fridays  1pm - 3pm in T03 starting 14.11.14

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.


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 excersises 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 19, 2pm-5pm in T01. Here are two sets of example-test tasks: example-test-1 and example-test-2.The second partial exam will on February 12, 1pm-4pm in T01. Here is a set of example-test tasks: example-test2-1 and example-test2-2. The first full exam will be held on February 27, 1pm-4pm in T01. There will be one more full exam possibility in April and one in July. Exact dates are t.b.a.

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 2, Wednesday 8.10.14 and Thursday 9.10.14: Introduction and sets, first meeting. Slides for Week 2 (in class we also proved some of the properties at the end, and we will continue with them next week). You may read up to page 31 (Section 2.5.) in the Modelling book, even though we do not exactly follow it.

  2. •Week 3, Wednesday 15.10.14 (taught by Andreas Haas) and Thursday 16.10.14: More properties of sets, relations. Slides for Week 3 (in class we proved more of the properties of sets, gave many examples of relations, and discussed/proved their properties). You may read pages 31 to 35 in the Modelling book as well as Chapter 17 until Section 17.4. in the Logical Reasoning book or in any other source dealing with relations. We did not exactly follow the books in this class, but there you may find some nice examples and exercises.

  3. •Week 4, Wednesday 22.10.14 and Thursday 23.10.14: More properties of relations. Equivalences. Slides for Week 4 (in class we proved more properties, gave many examples of special relations, and discussed/proved their properties). You may read until the end of Chapter 17 in the Logical Reasoning book or in any other source dealing with relations. We did not exactly follow the book in this class, but there you may find some nice examples and exercises.

  4. •Week 5, Wednesday 29.10.14 and Thursday 30.10.14: Equivalences and partitions, functions. Slides for Week 5 (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 as well as Sections 18.1. and 18.2. of Chapter 18, or in any other source dealing with equivalences, partitions, and functions.

  5. •Week 6, Wednesday 5.11.14 and Thursday 6.11.14: Functions, injective, surjective, bijective functions --- characterizations, properties, and examples. We have proved many of the properties stated in class. You may read Chapter 18 in the Logical Reasoning book, or in any other source dealing with functions. Slides for Week 6.

  6. •Week 7, Wednesday 12.11.14 and Thursday 13.11.14: Propositions, truth tables, equivalence of propositions.. Slides for Week 7 (we provided examples for all notions). Read Chapter 1 to Chapter 4 of the Logical Reasoning book, until Section 4.4. (page 33). You may read any other source dealing with propositional logic.

  7. •Week 8, Wednesday 19.11.14 and Thursday 20.11.14: Tautologies and contradictions, standard equivalences, working with equivalent propositions, weakenings. Slides for Week 8 (we provided examples for all notions and example proofs by calculations). Read Chapter 5 and Chapter 6, as well as Sections 7.1 and 7.3 of Chapter 7 of the Logical Reasoning book (page 33-63 and 65). You may read any other source dealing with propositional logic.

  8. •Week 9, Wednesday 26.11.14 and Thursday 27.11.14: Calculating with weakenings, predicate logic, few standard equivalence. Slides for Week 9 (we provided examples for all notions). Read Section 7.4 of Chapter 7, Chapter 8, as well as Sections 9.1 to 9.3 of Chapter 9 of the Logical Reasoning book (pages 63-89). You may read any other source dealing with predicate logic.

  9. •Week 10, Extra class on 28.11.14, 2pm-5pm in T01 (catching up for December 10 and 11, when there will be no lecture). Standard equivalences with quantifiers, calculating with quantifiers (examples), derivations (implication elimination and intro, conjunction elimination and intro, examples). Slides for Week 10. Read Chapter 9 (from Section 9.4 till the end), Chapter 11, 12, and 13 from the Logical Reasoning book (pages 89-103 and 111-153). It also doesn’t harm to read Chapter 10 that we skipped.

  10. •Week 11, Wednesday 3.12.14 and Thursday 4.12.14: Derivations with other connectives, derivations with quantifiers, examples of proofs by derivation. Slides for Week 10. Read Chapter 14 and Chapter 15 (until Section 15.3) from the Logical Reasoning book (pages 153-190).

  11. •Q&A session - extra class on 16.12.14 at 5pm in T01. We will discuss the example test tasks, and any other questions related to the test.

  12. •Week 12, Wednesday 17.12.14 and Thursday 18.12.14: Alternative rules for exists-intro and exists-elimination. More examples on proofs by derivation. Slides for this. Read Section 15.3 from the Logical Reasoning book (pages 187-199). Then we learned about algebraic structures --- just a brief introduction so that you get familar with the basic notions and results. No slides for this part, but lecture notes. You may also read Wikipedia articles or any other source introducing basic notions of abstract algebra.

  13. •Week 13, Wednesday 7.1.15 and Thursday 8.1.15: The structure of natural numbers, induction, cardinals. Slides for Week 13. Read Chapter 19 from the Logical Reasoning book until Section 19.9. (pages 283-308).

  14. •Week 14, Wednesday 14.1.15 and Thursday 15.1.15: Infinite sets and cardinals, countable and uncountable sets. Deterministic finite automata. You may read the rest of Chapter 19 from the Logical Reasoning book (from Section 19.9 -- pages 306 - 320) even though the presentation in class had a somewhat different flow. You may also read in any source about DFA, for example, in the book by Sipser --- Chapter 0 (Introduction) and Section 1.1. of Chapter 1. Slides for Week 14.

  15. •Week 15, Wednesday 21.1.15 and Thursday 22.1.15: Regular languages and operations, neterministic finite automata, equivalnce of DFA and NFA (determinization). You may read in any source about regular languages and NFA, for example, in the book by Sipser --- Chapter 1, Section 1.2. Slides for Week 15.

  16. •Week 16, Wednesday 28.1.15 and Thursday 29.1.15: NFA continued, regular expressions, Kleene Theorem, nonregular languages, Pumping Lemma. You may read in any source about the mentioned topics, for example, in the book by Sipser --- Chapter 1, Sections 1.2 (continued), 1.3, and 1.4. Slides for Week 16. This is the end of the course.

  17. •Q&A session - extra class on 9.2.15 at 10am (room t.b.a). We will discuss the example test tasks, and any other questions related to the test.

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