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 2020/2021

Schedule:            Mondays 2pm-3pm  from 12.10.20

                            Thursdays 10am-12am

                            starting 8.10.2020 in T01 see calendar


Online meeting:   Mondays 9am-10am from 19.10.20, link tba in PlusOnline


First meeting:       Thursday, October 8 at 10am in T01


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


Office hours:       Tuesdays 11am-12am 


Tutorium:            tba

Literature:


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

  2. •Textbook: Language, Proof and Logic, by David Barker-Plummer, Jon Barwise, and John Etchemendy, CSLI Publications, Stanford (second edition) 2011. [LPL]


  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: 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]


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


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.


You pass via the partial tests (1) if you: 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, you pass if you have have at least 20 points on each test and a total sum of at least 110 points on both tests.


You pass via one of the exam possibilities if you have 55% of the maximal points available at the exam. That is, if the exam brings maximally 100 points, you pass with 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: Midterm I : Friday, 11.12.2020, 3:30pm. Midterm II : Thursday 4.2.2020 (11am-6pm).  Exam 18.2.2020 (1pm-4pm).

Here is an example set of tasks for Midterm I (from last year). On Friday 4.12.2020 at 4pm we have scheduled an extra Q&A session as preparation for the midterm test.

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.

Materials:  Whenever slides are used, they will be made available on this webpage and via Blackboard. 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. The videos will also be made available to you via Blackboard (or other means) and will give you a more complete picture. In addition, I will also provide you with my lecture notes.

Schedule: 


  1. •Week 1, Thursday 8.10.20: Introduction and discussion of the rules, first meeting. Here are the slides intro-slides, and here they are with all stages of build intro-slides-all-stages.

  2. •Week 2, Monday 12.10.20 and Thursday 15.10.20: Introduction to logic; Sets. Here are the slides: Logic-intro-slides, Logic-intro-slides-all-stages, Sets-slides, Sets-slides-all-stages, and the Sets-lecture-notes. There were typos in Proposition 5 and 6 in the lecture notes. The link now links to the corrected version. Thanks to David Hanny for pointing this out! The videos and board-notes are already in Blackboard.

From 19.10.2020 all teaching will be online - the Webex links are accessible from Blackboard!


  1. •Week 3, Monday 19.10.20 (online Webex meeting to discuss the material of Week 2) and Thursday 22.10.20: Propositional Logic: Propositions, truth tables, equivalence of propositions. Here are the slides: Propositional-logic-slides, Propositional-logic-slides-all-stages (also for future weeks). The videos and board-notes are already in Blackboard. Please read Chapter 1,2,3, and 4 from [LR].

  2. •Week 4, Thursday 29.10.20: Standard equivalences and calculating with propositions. We are still using the propositional-logic-slides. The videos and board-notes are in Blackboard. Please read Chapter 5 and 6 from [LR].

  3. •Week 5, Thursday 5.11.20: Standard equivalences and calculating with propositions - continued / Weakening and strengthening. We are still using the propositional-logic-slides. The videos and board-notes are in Blackboard. Please read Chapter 7 from [LR].

  4. •Week 6, Monday 9.11.20 and Thursday 12.11.20: Predicate logic: Syntax, semantics, and calculating with predicate logic formulas. Here are the slides: Predicates-and-Quantifiers-slides, Predicates-and-Quantifiers-slides-all-stages. The videos and board-notes are already in Blackboard. Please read Chapter 8 and 9 from [LR].

  5. •Week 7, Monday 16.11.20 and Thursday 19.11.20: Derivations. Here are the slides: Derivations-slides, Derivations-slides-all-stages. The videos and board-notes are already in Blackboard. Please read Chapters 11 - 14 from [LR].

  6. •Week 8, Monday 23.11.20 and Thursday 26.11.20: Derivations with quantifiers. We still used the slides from last week. The videos and board-notes are already in Blackboard. Please read Chapters 15 from [LR]. Please also read Chapter 16 from [LR] as a connection to what we learned about sets.

  7. •Week 9, Monday 30.11.20 and Thursday 3.12.20: Relations. The videos and board-notes are already in Blackboard. Please read Chapter 17 from [LR] until Section 17.5. Here are my Relations-lecture-notes. Here are the slides: Relations-Equivalences-slides, Relations-Equivalences-slides-all-stages.

  8. •Week 10, (no class on Monday 30.11.20 due to a holiday) Thursday 10.12.20: Equivalences, equivalence classes, partitions. The videos and board-notes are already in Blackboard. Please read the rest of Chapter 17 from [LR] and (more importantly) my Equivalences-lecture-notes. We still use the slides from last week.

  9. •Week 11, Monday 14.12.20 and Thursday 17.12.20: Functions (definitions, examples, image and inverse image, injections, surjections, bijections, operations on functions). The videos and board-notes are already in Blackboard. Please read Chapter 18 from [LR] and (more importantly) my Functions-lecture-notes. Here are the slides: Functions-slides, Functions-slides-all-stages.

  10. •Week 12, Thursday 7.1.21: Happy New Year ! The structure of natural numbers, induction, and cardinals. The videos and board-notes are already in Blackboard. Please read Chapter 19 from [LR], and my lecture notes: Naturals-lecture-notes and Cardinals-lecture-notes. Here are the slides: Naturals-and-Cardinals-slides, Naturals-and-Cardinals-slides-all-stages.

  11. •Week 13, Monday 11.1.21 and Thursday 14.1.21: Finite Automata (deterministic finite automata, regular languages and expressions, Kleene’s theorem). The videos and board-notes are already in Blackboard. Here are the slides: Automata-slides, Automata-slides-all-stages. You may read on deterministic finite automata from any source, e.g., the books by Sipser [Comp], or Hopcroft et al [Aut]. I strongly recommend reading the very nice introduction (Chapter 0) in [Comp], or the introductory Chapter 1 of [Aut], in particular Section 1.5. In addition, my lecture notes will be available at the end of the semester.

  12. •Week 14, Monday 18.1.21 and Thursday 21.1.21: Nondeterministic finite automata, determinisation, closure properties, nonregular languages. The videos and board-notes are already in Blackboard. This is more material than for one week, but I decided to upload all now, so that we can discuss it next week. We will also have an extra class with Q&A next week (preparation for the midterm and exam). The slides are already online since last week (slightly modified now). You may read on automata from any source, e.g., the books by Sipser [Comp], or Hopcroft et al [Aut]. My lecture notes should be available by the end of the semester.






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

Corona adjustments:  We can only admit up to 28 people in the lecture room for our regular classes. Therefore, the first class on October 8, will be taught in 5 groups. You will receive information via PlusOnline (Email) and Blackboard in which of the 5 groups you should come to this class. The intention is that all students can join the first class (“Vorbesprächung”).


From October 12, we will work as follows: Each week 28 people will be admitted to the lecture in the lecture room. For all others, I will

provide videos (latest on Thursday morning) covering the material of the course for that week. Moreover, we will schedule an online-meeting class for 1 hour every week, which is to be used for questions and discussions on anything related to the material of that week (for those who could not be present in class).


We will have a registration system in order to schedule who is allowed to come to the lecture-room class each week. This will be done with a group in Blackboard to which a group of people will be invited to register from Thursday evening until Saturday of a given week. If not all of these students register, the remaining places will be open for registration to all remaining students.

Plan B:  If there are any corona-related problems throughout the semester and we are no longer allowed to use the lecture room, we can all fall back to fully online teaching, by simply skipping the lecture-room classes -- everyone can then watch the videos, and take part in the online-meeting hour.


However, for the feedback tests it is essential that they happen in presence, in a lecture room. It might happen, if we can not use the lecture rooms, that these have to be cancelled.