Berechenbarkeit und Komplexität (WS 2019/20)
Abschnittsübersicht
-
In dieser Lehrveranstaltung behandeln wir wesentliche Bereiche der Theoretischen Informatik, d.h., der "ewigen Wahrheiten" der Informatik, die auf der Grundlage der Mathematik/Logik ein für allemal bewiesen wurden und die unabhängig von weiteren technologischen Entwicklungen sind. Zentrale Fragestellungen sind dabei der Begriff der Berechenbarkeit (was ist berechenbar und was nicht?) und der Komplexität (wie groß ist der für eine Berechnung notwendige Aufwand?).
Um an der Lehrveranstaltung teilzunehmen, müssen Sie sich wie üblich im KUSSS System dafür (jeweils Vorlesung und Übung separat) anmelden. Wenn Sie sich auch im Moodle einloggen und als Kursteilnehmer eintragen, erhalten Sie per Email alle ins "Ankündigen"-Forum gestellte Nachrichten und können selbst Nachrichten ins "Fragen und Antworten"-Forum stellen.
-
A.Univ.Prof. DI Dr. Wolfgang Schreiner
Freitag, 12:00-13:30; HS 2 (13.12: HS 18); Beginn: 11. Oktober 2019Folien
Lehrbücher- Dirk W. Hoffmann: Theoretische Informatik
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation (deutsche Ausgabe: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit)
- Michael Sipser: Introduction to the Theory of Computation
- Thomas H. Cormen et al: Introduction to Algorithms
Das Buch von Hoffmann bietet eine sehr lesenswerte deutsche Einführung in das Thema.- 1. Klausur: Einsichtnahme ist im Raum S2 0327 (oder einem der beiden Nachbarräume) an den folgenden Terminen möglich:
- Dienstag, 3. März, 11:15-12:00
- Donnerstag, 5. März, 17:15-18:00
- Freitag, 6. März, 12:00-12:45
- 2. Klausur: Online-Klausur 26. Mai 2020 (siehe unten)
- Vor Jänner 2021 wird keine weitere Klausur stattfinden, aber Sie können mich jederzeit für eine individuelle (semi-schriftliche) (Zoom-)Prüfung kontaktieren.
-
Date: Tuesday, May 26, 16:00-18:30, Zoom/JKU Moodle
- To participate in the exam, you have to do until Tuesday, May 19 the following:
- You have to register in KUSSS for the exam and
- you have to upload in the course 326.023, VO Berechenbarkeit und Komplexität, Wolfgang Schreiner, 2019W of the JKU Moodle in the assignment "Exam May 26, 2020" a picture file "Ausweis.*" with a photo of your student id card.
- If you have not been registered in KUSSS for this course in the WS 2019/2020, you do not have yet access to this course. In this case, send me by Tuesday, May 12 an email with your id number such that I can register you in KUSSS.
- I will announce per email in KUSSS by Friday, May 22, who may participate in the exam.
- To take part in the exam, you need a computer with internet connection and Web-/Laptop-Cam (mandatory). You also need a device to convert handwritten DIN A4 pages into picture files of good quality (smartphone, tablet, scanner).
- The exam will proceed as follows:
- Login into the course 326.023, VO Berechenbarkeit und Komplexität, Wolfgang Schreiner, 2019W of the JKU Moodle.
- At 16:00 (not later) you enter the Zoom Meeting whose id and password is announced in the JKU Moodle course. Join the meeting with your full name and registration number (format: "FAMILYNAME GivenName (kXXXXXXX)"). Activate your webcam and position it such that it shows yourself and your work place. Make sure that no one else is in the room and that no one will enter the room during the exam.
- At 16:15 I will make the exam questions (a PDF file) visible in the Moodle course (you may print the file, but this is not necessary). From that time on, you may start your elaboration. You may use any materials (open book exam) but not perform any attempt at external communication.
- The exam is to be written manually with a dark pen on empty DIN A4 pages within the area well covered by your webcam. This area must not be left during the whole exam.
- You may ask questions (only) via the "Questions and Answers" forum in the JKU Moodle course (German or English, no audio questions).
- At 18:00 (not before) you stop your elaboration and start to photograph/scan and upload your results in the form indicated below.
- Until 18:15 latest the results of the exam have to be uploaded in the assignment "Exam May 26, 2020" of the JKU Moodle in the following form:
- One picture file "Foto.*" with a photo that shows your face, your student id card, and the first page of your manually written elaboration (Example).
- Picture files "Seite1.*", "Seite2.*", etc. with photos of every page of your manually written elaboration.
- At 18:15 (not before), position your camera such that it clearly shows (on your desk or in your hand) your student id card and the first page of your elaboration (as you have submitted it). Stay till 18:30 in the Zoom meeting.
- The meeting will not be recorded. If your Zoom connection is interrupted during the exam or above regulations are violated, I may not grade your exam.
- After the exam, preserve your written elaboration without changes. If the quality of your photos is not good enough for grading, I may ask for new ones.
- Please use the upload of the photo of your student id card to test your abilities to take photos and upload them in the Moodle course. Also test with some sample Zoom meetings your equipment (webcam).
-
Dr. Nikolaj Popov und Dr. Ralf Hemmecke
- 326.004 -- Do, 8:30-9:15 BA 9904
(Dr. Nikolaj Popov)
Beginn: 10. Oktober 2019 - 326.104 -- Do, 9:15-10:00 BA 9904
(Dr. Nikolaj Popov)
Beginn: 10. Oktober 2019 - 326.111 -- Do, 10:15-11:00 HS 11
(Dr. Nikolaj Popov)
- 326.016 -- Fr, 10:15-11:00 HS 11
(Dr. Ralf Hemmecke)
Beginn: 11. Oktober 2019 - 326.050 -- Fr, 11:00-11:45 HS 11
(Dr. Ralf Hemmecke)
Beginn: 11. Oktober 2019
Übungsklausuren (für alle Übungsgruppen):
(Unterlagen sind nicht zugelassen)
1. Klausur: 22.11.2019 11:00-11:45, H 10
2. Klausur: 10.01.2020 11:00-11:45, H 10
Die Übungsaufgaben sind ca. zwei Wochen vor Übungsbeginn hier verfügbar.
- 326.004 -- Do, 8:30-9:15 BA 9904
(Dr. Nikolaj Popov)
