Proseminar SS2022

Zertifizierende Algorithmen

Zertifizierend banner

Inhalt

Algorithmen sind überall. Aber wo viel programmiert wird, gibt es auch Bugs. Während Bugs mit vielen Tests oft erkannt werden können, sind diese keine Garantie für Richtigkeit. Deshalb gibt es das Konzept der zertifizierenden Algorithmen:
Neben dem Resultat geben sie einen kurzen und simplen Beweis (Zertifikat) an, dass das Ergebnis richtig ist. Die Stärke dieses Verfahrens ist, dass der Benutzer selber überprüfen kann, ob die Ausgabe korrekt ist – und das schneller als dieses oder ein anderes Programm nochmal auszuführen oder gar das ganze Programm formal zu verifizieren. So ist kein Vertrauen in die Richtigkeit des Programmes nötig.

Um kurze Zertifikate zu ermöglichen, muss man oft hilfreiche Strukturen des Problems ausnutzen. Deshalb ist das Feld der Zertifizierenden Algorithmen so interessant, nicht nur weil sie nützlich sind, sondern auch tiefe Einblicke in ein Problem födern.

Es gibt für zertifizierende Algorithmen viele Beispiele: Um den größten gemeinsamen Nenner zu bestimmten, nutzt man den Euklidischen Algorithmus. Um zu überprüfen, ob das Ergebnis wirklich der größte gemeinsame Nenner ist, müsste man die Rechnung wiederholen. Ein zertifizerender Algorithmus ist der erweiterte Euklidische Algorithmus (bekannt aus DS).

Auch in der Graphentheorie gibt es viele Beispiele: von relativ einfach bis hin zu ganz ausgefuchst. Relativ simpel sind hier, die Zusammenhangskomponenten eines Graphen herauszufinden oder zu überprüfen, ob ein Graph bipartit ist. Ausgeklügelter ist da schon der zertifizierende Algorithmus für den Planaritätscheck, also zu überprüfen, ob ein Graph auf der Ebene ohne Kantenüberkreuzungen einbettbar ist.

Ort und Zeit

Das Proseminar findet semesterbegleitend wöchentlich statt.

Wir erwarten, dass die Teilnehmenden sich aktiv am Proseminar beteiligen, d.h. Fragen stellen und mit aktivierter Kamera teilnehmen, falls das Proseminar digital stattfindet. Die genauen Zeiten und weitere Details werden beim Kickofftreffen bekanntgegeben. Dieses findet vor Semesterbeginn statt und wird den Teilnehmenden per Mail angekündigt.

Die Teilnahme an diesem Proseminar ist nur nach einer Anmeldung im Supra moeglich!

Material

Inhalt

Wird in Kürze ergänzt.

Termine und Themen

Datum Thema StudentIn
??? Themenvergabe usw Alle