The Nature of Computation - Detailseite

Was kann ein Computer prinzipiell leisten? Alan Turing hat diese Frage zu beantworten versucht, indem er das theoretische Modell einer universellen Maschine entwarf, das sich als gleichwertig mit allen anderen bislang bekannten Paradigmen erwies. Aber ist dieses Modell heute, im beginnenden Zeitalter von Quanten- und anderen Computern noch zeitgemäß? In diesem Seminar wollen wir gemeinsam das Buch "The Nature of Computation" von C. Moore und S. Mertens (Oxford Univ. Press, 2011) durcharbeiten, in dem es um die Grundlagen der Berechenbarkeit und Komplexitätstheorie geht, um das P-NP-Problem, randomisierte Algorithmen und Spiele, statistische Physik und Quantencomputer.

Von den Teilnehmerinnen und Teilnehmern wird erwartet, dass sie jeweils ein Referat über ein Kapitel des Buchs halten, und im Anschluss an das Semester eine Seminararbeit als Ausarbeitung des Vortrags verfassen.

Nach Vereinbarung kann das Seminar auch als Blockveranstaltung stattfinden.

Es sind maximal 15 Plätze zu vergeben.