Homepage zu der Vorlesung
|
Komplexität von Algorithmen |
Sommersemester 2011
V. Strehl
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Die Vorlesung findet statt
Mittwochs 8:30--10:00 im H4 (RRZE)
Freitags, 10:15--11:45 im H14 (= 0.61 WW)
Beginn der Vorlesung: 4. Mai 2011
Eintragung für die Übungen ab sofort bis 6. Mai in meinCampus
letztes update dieser Seite: 5. August 2011
Hinweis auf Veranstaltungen in den kommenden Semestern
|
Studierende der Informatik, aber auch für Studierende aus anderen Fächern (Mathematik, Physik, E-Technik...), die Interesse und Gefallen an den Themen dieser Komplexitäts-Vorlesung gefunden haben, möchte ich an dieser Stelle auf zwei Veranstaltungen hinweisen, die ich in den beiden kommenden Semestern durchführen werde. Sie sind für das Informatik-Master (bzw. Hauptstudium Diplom) vorgesehen, können aber auch als Vertiefung im Informatik-Bachelor gewählt werden.
Aufbauend auf einer Einführung in das Reich der Fouriertransformation wird der Formalismus der Wavelettransformationen in Theorie und Praxis behandelt. Die Anwendungsbeispiele stammen aus dem Bereich der Bildverarbeitung, deshalb wird diese Vorlesung durch Übungen ergänzt, die vom Lehrstuhl für Mustererkennung betreut werden. Diese Veranstaltung eignet sich daher für eine Vertiefung in “Theoretischer Informatik” und ebenso wie in “Mustererkennung”. Nähere Informationen dazu im UnivIS früherer Semester (z.B. WS 2010/11) und unter diesem Link Quantencomputing und Quanteninformation (SS2012) Diese Veranstaltung hat zum Ziel, die Teilnehmer mit den grundlegenden Konzepten, Techniken und Resultaten des Quantencomputing und der Quanteninformation vertraut zu machen. Nach einer Diskussion grundlegender Phänomene wie Superposition und Verschränkung und einer Behandlung des mathematischen Formalismus werden insbesondere solche Themen behandelt, die aus der Sicht der Informatik interessant sind: Deutsch-Josza-Problem und Verwandtes; Phasenschätzung, Fouriertransformation und Shors Faktorisierungsalgorithmus; Grovers Suchalgorithmus; kryptografische Protokolle wie BB84; Verwendung fehlerkorrigierender Codes. Diese ist eine Vertiefungs-Veranstaltung für “Theoretische Informatik" Nähere Informationen dazu im UnivIS früherer Semester (z.B. SS2010) und unter diesem Link. |
Die Übungen werden in mehreren Gruppen durchgeführt, die zu den in der Tabelle aufgeführten Terminen stattfinden. Aktueller Stand:
|
Bezeichnung |
Tag/Uhrzeit |
Ort |
Übungsleiter |
|
Montag-A |
Montag 12:15-13:45 |
00.151 |
Manuel Schmitt |
|
Montag-B |
Montag 16:15-17:45 |
E 1.12 (EEI) |
Ulrich Dorsch |
|
Montag-C |
Montag 16:15-17:45 |
0.85 (WW) |
Manuel Schmitt |
|
Dienstag-D |
Dienstag 10:15-11:45 |
00.152 |
Ulrich Dorsch |
|
Dienstag-E |
Dienstag 16:15-17:45 |
E 1.11 (EEI) |
Christoph Rauch |
|
Mittwoch-F |
Mittwoch 10:15-11:45 |
0.85 (WW) |
Christoph Rauch |
Beginn der Übungen ab 9. Mai
Inhalt: Zentraler Gegenstand der Vorlesung ist der Begriff der Komplexität von Algorithmen und von Problemen. Dabei stehen "alltägliche" Aufgaben wie: Sortieren, Suchen, elementare Arithmetik, ... im Vordergrund. Der Analyse konkreter Algorithmen wird besondere Beachtung geschenkt. Die wesentlichen Kapitel der Vorlesung betreffen die Themen: Rekursion und Komplexität, Information und Komplexität, Arithmetik und Komplexität. Begleitend werden die benötigten mathematischen Techniken behandelt.
Literatur: Literaturempfehlungen werden zu Beginn und im Verlauf der Vorlesung gegeben.Die homepages der entsprechenden Vorlesung in früheren Semestern
Kontakt:Ich bin per email erreichbar unter: strehl@cs.fau.de
oder telefonisch unter +49-9131-8528712.
Mein Büro befindet sich in der Haberstrasse 2, Raum 3.004.Sprechstunden nach Vereinbarung.see you in my office ...-->![]()