Formal Foundations of Computer Science
The basic objective of computer science is to model complex problems from business, science and society in an appropriate manner and to provide a computational solution. This is usually a multi-stage process that involves the following steps based on an informal description of the problem:
- Formal specification of a calculation problem,
- Design of a solving algorithm,
- Writing a corresponding computer program in a higher programming language,
- Computer-internal execution of the program, which involves compiling the program into a sequence of machine instructions and executing this sequence by an appropriate processor.
The content of this lecture is to comprehend these steps for a very simple formal computer model and thus to generate a fundamental understanding for the basic concepts of computer science such as computation problem, algorithm, program, circuit, processing of machine instructions by a processor. A formally correct but nevertheless easily understandable specification of these concepts is essential for this, for which the language of higher mathematics has proven its worth. The lecture begins with a compilation of the necessary mathematical basic concepts such as sets, relations, mappings, graphs and Boolean functions. Then the following topics are covered:
- Introduction to propositional logic and the realization of Boolean functions by logical circuits
- Finite state automats and their realization by logic control units
- Turing machines as a simple computer model
- Principle limits of computability
-
Lecture and Material
- Mondays, 12:00-13:30 in room B 6, A 0.01 (Matthias Hamann)
- Thursdays, 12:00-13:30 in room B 6, A 0.01 (Matthias Hamann)
Please note:
- 16.10.2019: The lecture that was cancelled on 05.09.2019 (Thursday) will be held on 24.10.2019 (Thursday), 17:15-18:45, in room SN 163 (Schloss Schneckenhof Nord).
- 02.09.2019: There will be no lecture on 05.09.2019 (Thursday). As already announced, this lecture will be postponed to a later date.
- 27.08.2019: In the first lecture week there will be no exercises.
Current Material for the Lecture
- 01. Einführung (Stand: 01.09.2019)
- 02. Aussagen (Stand: 01.09.2019)
- 03. Beweise (Stand: 11.09.2019)
- 04. Mengen und Relationen (Stand: 25.09.2019)
- 05. Abbildungen (Stand: 18.09.2019)
Old Material for the Lecture of the HWS 2018
- 01. Einführung (Folien HWS 2019 online)
- 02. Aussagen (Folien HWS 2019 online)
- 03. Beweise (Folien HWS 2019 online)
- 04. Mengen und Relationen(Folien HWS 2019 online)
- 05. Abbildungen(Folien HWS 2019 online)
- 06. Äquivalenzrelationen (Stand: 10.10.2018)
- 07. Halbordnungsrelationen (Stand: 10.10.2018)
- 08. Kombinatorik (Stand: 01.11.2018), „Zahlenbeispiele“ der Kombinatorik-Vorlesung (Stand: 07.12.2018)
- 09. Graphen (Stand: 01.11.2018)
- 10. Algebraische Strukturen (Stand: 15.11.2018)
- 11.-12. Endliche Automaten und Reguläre Ausdrücke (Stand: 07.12.2018)
- IMPORTANT: The lecture documents of the HWS 2018 are only intended as a supplementary offer to facilitate your preparation for the current lectures. However, only the documents of the current semester are authoritative for the upcoming examination!
Literature
Textbooks
- Christoph Meinel, Martin Mundhenk: Mathematische Grundlagen der Informatik, Teubner Verlag, 2002.
- Wegener, Ingo: Theoretische Informatik - eine algorithmenorientierte Einführung, Teubner Verlag, 2005. (insb. relevant für das Vorlesungskapitel Endliche Automaten)
Reference works and further literature
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg, 2010.
-
Practice
The practice is coordinated by Alexander Moch. For questions of a technical nature, the tutors are the first point of contact. If there is still some uncertainty, you can send your question(s) and at least three suggested dates by e-mail.
Registration for the tutorials is not necessary. However, it is advisable that you distribute yourself evenly among the offered dates.
Please note:
- 10.10.2019: The tutorial of Paul Huber on 14.10.2019 at 13:45 - 15:15 takes place once in the seminar room 405 in the new B 6 building B 6, 30-32.
- 28.09.2019: Due to a public holiday, the tutorial of Rebecca Armbruster will be moved once from Thursday, 03.10.2019, to Tuesday, 01.10.2019 from 10:15 - 11:45 in room B 6, A 3.01.
- 27.08.2019: There will be no exercises during the first week of lectures.
Dates of the Tutorials
- Mondays, 10:15-11:45 in room B 6, A 1.04 (Tutor: Teresa Kaufmann)
- Mondays, 13:45-15:15 in room B 6, A 2.04 (Tutor: Paul Huber)
- Mondays, 15:30-17:00 in room B 6, A 1.04 (Tutor: Paul Huber)
- Wednesdays, 08:30-10:00 in room B 6, A 3.01 (Tutor: Teresa Kaufmann)
- Wednesdays, 13:45-15:15 in room A 5, C 0.15 (Tutor: Rebecca Armbruster)
- Thursdays, 10:15-11:45 in room B 6, A 1.04 (Tutor: Rebecca Armbruster)
Exercise Sheets
- 01. Exercise Sheet (09.09.2019) -> Solution Draft
- 02. Exercise Sheet (17.09.2019)
- 03. Exercise Sheet (24.09.2019)
Please note:
- From the second week of the lecture a new exercise sheet will be published every week, which will be discussed in the following week. Subsequently, brief instructions for solutions will be made available on this page. These solution hints are only to be understood as a supplementary offer to the exercises and often contain only the essential steps of the solution.
-
Exam
- 27.08.2019: The written exam will take place on Saturday, 14.12.2019.
- 27.08.2019: There will be a 90-minute written exam. This will be 100% of the final score of the event.