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

Schedule:            Thursdays 1pm-4pm starting 3.10.2013 in T01 see calendar


First meeting:       Thursday, October 3 at 1pm in T01


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


Office hours:       Wednesdays 11am-12am 


Tutorium:            Tuesdays 12am-2pm in T06  (starting 15.10.2013)

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 was held on Friday, 6.12.13 at 1:45pm in T01. Here is a an example set of tasks. We will have an extra class on Friday 10.1.14 at 11am in T02 to discuss the tasks from Test 1. You can see your exam notebooks on that day in my office from 10am to 11am (or after 3pm).


The second partial exam will be held on Friday, 7.2.14 at 11am in T01.


There will be one full exam possibility in February, one in April, one in July.

Schedule:


  1. •Week 1, Thursday 3.10.13, Introduction and sets, first meeting. Slides for Week 1 (in class we also proved some of the properties at the end, and we will continue with them next time). 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, Thursday 17.10.13, Sets properties and relations. Slides for Week 3 (we proved more of the sets properties and provided examples to all notions in class).  You may read pages 31 to 35 in the Modelling book as well as Chapter 17 until Section 17.5. in the Logical Reasoning book or in any other source dealing with relations. We do not exactly follow the books in class, but there you find nice examples and exercises.

  3. •Week 4, Thursday 24.10.13, Equivalences and partitions. Slides for Week 4 (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.

  4. •Week 5, Thursday 31.10.13, Functions. Slides for Week 5 (we proved some of the properties mentioned on the slides, the more important ones, and provided examples to all notions.. there was a nice discussion). You may read Chapter 18 of the Logical Reasoning book or any other source dealing with functions. Also, you may read pages 35 to 52 in the Modelling book (until end of Chapter 2).

  5. •Week 6, Thursday 7.11.13, Propositions, Truth tables, Equivalence of Propositions. Slides for Week 6 (we provided examples to all notions..). Read Chapter 1 to Chapter 4 of the Logical Reasoning book, until page 39. You may read any other source dealing with propositional logic.

  6. •Week 7, Thursday 14.11.13, Standard equivalences, calculating with equivalent propositions; Strenghtening and weakening, calculating with weakenings. Slides for Week 7 (we provided examples to all notions..). Read Chapter 5, 6, and 7 of the Logical Reasoning book, until page 69. You may read any other source dealing with propositional logic. The material for the first partial exam ends here.

  7. •Week 8, Thursday 21.11.13, Predicates and quantifiers, standard equivalences with quantifiers, calculating with equivalent propositions. Slides for Week 8 (we provided examples to all notions and some proofs..). Read Chapter 8, 9, and 10 of the Logical Reasoning book, until page 110. You may read any other source dealing with predicate logic (in particular a nice Wikipedia article).

  8. •Week 9, Thursday 28.11.13, Derivations / reasoning. Slides for Week 9 (we provided examples of flag proofs..). Read Chapter 11, 12, 13, and 14 of the Logical Reasoning book, until page 176. Also read about different types of proofs in the Modelling book and in the Automata-theory book. There are short summary chapters that are nice to read.

  9. •Week 10, Thursday 5.12.13, Derivations / reasoning with quantifiers. Examples and discussion. Slides for Week 10. Read Chapter 15 of the Logical Reasoning book, until page 199. Also read about different types of proofs in the Modelling book and in the Automata-theory book. There are short summary chapters that are nice to read. Also read this interesting text.

  10. •Week 11, Thursday 12.12.13, Algebraic structures, a crash course on the very basics of algebra. It is a nice application of what we know so far (predicate formulas, functions, sets) and needed for future courses. No slides for this week, all was done on the board. However, there are lecture notes. We also looked at some more examples (and did not cover all that is in these notes, plese read yourself). You may also read any introductory material dealing with algebras (for example a wikipedia article, also for the German terms).

  11. •Week 12, Thursday 19.12.13, The structure of natural numbers, induction. Cardinal numbers, finite sets (we did not manage to do all about infinite sets -- next time, after the break). We proved many example properties and also proved the properties mentioned on the slides. Read Chapter 19 of the Logical Reasoning book, at least until Section 19.9. Here are the slides (the slides after the video remain for after the break). Here is a link to the video shown in class. Happy holidays!

  12. •Week 13, Thursday 9.1.14, Infinite, countable and uncountable sets. We went  through the last two slides of last week (we proved all the statements there and several additional lemmas needed for them). We also started a bit with finite automata, more next week. Read the rest of Chapter 19 of the Logical Reasoning book (after Section 19.9) even though we gave more detailed proofs in class.

  13. •Extra class --- discussing the tasks from Test 1 on Friday 10.1.14, 11am-2pm (at most) in T02.

  14. •Week 14, Thursday, 16.1.14, Deterministic and Nondeterministic Finite Automata. Here are the slides. You may read in any textbook/source about finite automata (e.g. the Hopcroft book above).

  15. •Week 15, Thursday 23.1.14, Nondeterministic Automata (continued), determinization, closure properties, regular expressions, Theorem of Kleene (next time we will discuss nonregular languages). Here are the slides. You may read in any textbook/source about finite automata (e.g. the Hopcroft book above).

  16. •Week 16, Monday 3.2.14, 11am-2pm in T01 --- note the change in day and time. This is a replacement class for Thursday 30.1.14 --- no class on that day! We spent a lot of time discussing nonregular languages (proof of the pumping lemma and examples of applying it), also discussed the example test 2, and then quickly went through Hoare logic (pre and postconditions), here are some older slides.

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.

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