{"id":395,"date":"2002-07-02T07:01:55","date_gmt":"2002-07-02T05:01:55","guid":{"rendered":"http:\/\/schlu.de\/?p=395"},"modified":"2018-10-31T18:08:00","modified_gmt":"2018-10-31T17:08:00","slug":"logikseminar-an-der-eth","status":"publish","type":"post","link":"https:\/\/schlu.de\/?p=395","title":{"rendered":"Logikseminar an der ETH"},"content":{"rendered":"<p>In den Jahren 1998 bis 2002 durfte ich zusammen mit Professor Ernst Specker (1920 &#8211; 2011) das <strong>Seminar \u00fcber Algorithmik und Logik<\/strong> an der ETH veranstalten. Die Zusammenarbeit mit Ernst war \u00fcberaus freundlich, und das Logikseminar hat mir sehr viel Spa\u00df gemacht. Im Sommersemester 2002 f\u00fchrten wir das Logikseminar zuletzt durch, damit endete auch die lange Tradition dieses Seminars, das 1939 erstmalig von Paul Bernays (1888 &#8211; 1977) veranstaltet worden ist.\u00a0 Zum Abschluss gab es am 2. Juli 2002 einen Vortrag <i>Glanz und Elend der Logik.<\/i><\/p>\n<p>Weitere Informationen liefern die Artikel von George Szpiro vom 1.7.2002 in der NZZ und vom 28.7.2002 in der NZZ am Sonntag.<\/p>\n<p>Paul Bernays ist seit dem Jahre 1934, als er seine Lehrt\u00e4tigkeit an der Eidg. Technischen Hochschule aufnahm, <i><u>der<\/u> <\/i>Vertreter der mathematischen Logik und Grundlagenforschung in der Schweiz gewesen. Seit 1953 war Ernst Specker Mitveranstalter dieses Seminars.<\/p>\n<p>Informationen zu Paul Bernays liefert der folgende Artikel.<\/p>\n<p>Ernst Specker:<br \/>\nPaul Bernays<br \/>\nLOGIC COLLOQUIUM 78, 381-389<\/p>\n<h2>Themen der Jahre 1998 bis 2002<\/h2>\n<h3>Vier Logiken,\u00a0 Sommersemester 2002<\/h3>\n<p>Es sind die folgenden Themen vorgesehen:<\/p>\n<ul>\n<li><b>Mehrwertige Logik:<\/b> Nicht nur Wahrscheinlichkeitswerte wahr\/falsch.<\/li>\n<li><b>Intuitionistische Logik:<\/b> Logik der Mathematik, in der die Objekte als mentale Konstrukte aufgefasst werden.<\/li>\n<li><b>Quantenlogik:<\/b> Ber\u00fccksichtigt, dass zwei Gr\u00f6ssen nicht immer simultan messbar sind.<\/li>\n<li><b>Modale Logik:<\/b> Aussagen <i>A<\/i> werden durch Operatoren moduliert, wie: A ist beweisbar<\/li>\n<\/ul>\n<p>Die drei ersten Logiken sind Alternativen zur klassischen Logik; sie sollen unabh\u00e4ngig davon entwickelt werden. Modaloperatoren erweitern jede Logik.<b>Literatur:<\/b><\/p>\n<ul>\n<li>Alternatives to Classical Logic, Handbook of Philosophical Logic, Vol. III, Reidel Publishing Company, 1986<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Quantenalgorithmen, Wintersemester 2001\/2002<\/h3>\n<p>Die Beobachtung, dass sich gewisse Quanteneffekte klassisch nicht in Echtzeit simulieren lassen, hat zur Suche nach &#8222;Quantencomputern&#8220; gef\u00fchrt, d. h. Computern, die umgekehrt Berechnungen auf Grund von Quanteneffekten wesentlich schneller durchf\u00fchren als konventielle Computer (wie etwa Turing Maschinen). Ein wichtiger Schritt ist das Resultat von Peter Shor aus dem Jahre 1994. Er beschreibt einen Algorithmus, der auf einem solchen &#8222;idealen Quantencomputer&#8220; Zahlen in polynomialer Zeit in Primzahlen zerlegt.<\/p>\n<p><b>Literatur:<\/b><\/p>\n<ul>\n<li>E.G. Rieffel, W. Polak: An Introduction to Quantum Computing for Non-Physicists<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Kombinatorische Spiele, Sommersemester 2001<\/h3>\n<p>Kombinatorische Spiele sind Zweipersonenspiele, deren Ausgang (Gewinn\/Verlust\/Unentschieden) weder von der Geschicklichkeit (wie beim Tennis) noch vom Zufall (wie bei W\u00fcrfelspielen) noch von Hellsehkunst (wie bei Kartenspielen) abh\u00e4ngt.Der Prototyp eines kombinatorischen Spieles ist das Nim-Spiel: Gegeben sind einige Haufen von Spielmarken. Die beiden Spieler verringern abwechselnd einen der Haufen (was &#8222;ganz wegnehmen&#8220; einschliesst). Gewonnen hat, wer zuletzt ziehen kann.<br \/>\nFrage: Welche ersten Z\u00fcge f\u00fchren bei 4 Haufen mit 2, 3, 5, 7 Marken zum Gewinn?<\/p>\n<p>Die Theorie der kombinatorischen Spiele beschr\u00e4nkt sich nicht einfach darauf, f\u00fcr\u00a0 einzelne Spiele Ratschl\u00e4ge zu erteilen. Es werden vielmehr \u00c4quivalenzklassen von Spielen eingef\u00fchrt und auf diesen Klassen Operationen definiert. So kann dann etwa das obige Nimspiel (2, 3, 5, 7) aufgefasst werden als Summe der 4 Spiele (2), (3), (5), (7).<\/p>\n<p><a href=\"http:\/\/schlu.de\/wp-content\/uploads\/2018\/10\/AequiSpiele.gif\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-396 size-full\" src=\"http:\/\/schlu.de\/wp-content\/uploads\/2018\/10\/AequiSpiele.gif\" alt=\"\" width=\"537\" height=\"292\" \/><\/a><\/p>\n<p><b>Literatur:<\/b><\/p>\n<ul>\n<li style=\"list-style-type: none;\">\n<ul>\n<li>J.H. Conway: On Numbers and Games, Academic Press, 1976<\/li>\n<li>J.H. Convay: \u00dcber Zahlen und Spiele, Vieweg, 1983<\/li>\n<li>R.K. Guy: Combinatorial Games, Chapter 43 in Handbook of Combinatorics, Elsevier Science, 1995<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Descriptive Complexity, Wintersemester 2000\/2001<\/h3>\n<p>Die Darstellungskomplexit\u00e4t untersucht die Beziehung zwischen den beiden folgenden Fragen<\/p>\n<ol>\n<li>In welchen formalen Sprachen kann ein Problem formuliert werden?<\/li>\n<li>Wie aufwendig ist die L\u00f6sung des Problems?<\/li>\n<\/ol>\n<p>Beispiele von Sprachen, Problemen, Aufwand: Pr\u00e4dikatenlogik erster Stufe, &#8222;Ist ein vorgelegter Graph zusammenh\u00e4ngend?&#8220;, Platzbedarf zur L\u00f6sung des Problems.<b>Literatur:<\/b><\/p>\n<ul>\n<li>Neil Immerman: Descriptive Complexity, Graduate Texts in Computer Science, Springer-Verlag Telos; ISBN: 0387986006<\/li>\n<\/ul>\n<h3><\/h3>\n<h3>Quantenlogik, Sommersemester 2000<\/h3>\n<p>Die klassische Aussagenlogik setzt voraus, dass zwei Aussagen durch und\/oder verkn\u00fcpfbar sind. Dass dies nicht selbstverst\u00e4ndlich ist, zeigt die Quantentheorie.<\/p>\n<p>Entsprechend der klassischen Logik als einer Theorie der Boole&#8217;schen Verb\u00e4nde wird im ersten Teil des Seminars die Q-Logik als Theorie partieller Boole&#8217;scher Verb\u00e4nde entwickelt. Die Frage, ob sich in einem System verborgene Parameter einf\u00fchren lassen, kann dann interpretiert werden als Frage, ob eine partielle Boole&#8217;sche Algebra zu einer totalen erweitert werden kann.<\/p>\n<p><b>Literatur:<\/b><\/p>\n<ul>\n<li>Jeffrey Bub: Interpreting the quantum world, Cambridge University Press, 1997<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Modallogik, Wintersemester 1999\/2000<\/h3>\n<p>Modaloperatoren ordnen einem Satz \u03a6 einen anderen zu, etwa<br \/>\n1. \u03a6 ist beweisbar.<br \/>\n2. Ich weiss, dass \u03a6.<br \/>\n3. A weiss, dass B nicht weiss, ob \u03a6.<br \/>\n4. \u03a6 ist notwendig.<br \/>\nIm Seminar sollen Kapitel 1 (Klassische Aussagenlogik als Grundlage) und 3 (Einf\u00fchrung in die Modallogik) des nachfolgend genannten Buches behandelt werden. Zus\u00e4tzlich werden Anwendungen der Modallogik auf die Operatoren \u00bbbeweisbar\u00ab und \u00bbweiss, dass\u00ab betrachtet.<\/p>\n<p><b>Literatur:\u00a0 <\/b><\/p>\n<div>\n<ul>\n<li>Alexander Chagrov, Michael Zakharyaschev: Modal Logic, Clarendon Press, 1997<\/li>\n<\/ul>\n<\/div>\n<p>&nbsp;<\/p>\n<h3>Algebraische Komplexit\u00e4tstheorie, Sommersemester 1999<\/h3>\n<p>Ausgehend von einfachen Problemen (z.B. L\u00e4nge von Additionsketten) sollen einige Kapitel aus dem genannten Buch behandelt werden:<\/p>\n<ul>\n<li>Straight-Line Programs<\/li>\n<li>Computation Sequences<\/li>\n<li>Universality of the Determinant<\/li>\n<li>Completeness of the Permanent<\/li>\n<li>Branching and Connectivity<\/li>\n<\/ul>\n<p><strong>Literatur:<\/strong><\/p>\n<ul>\n<li>Peter B\u00fcrgisser, Michael Clausen, M. Amin Shokrollahi: Algebraic Complexity Theory, Springer Verlag, 1997<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Approximative Beweise, Wintersemester 1998\/99<\/h3>\n<p>Ziel des Seminars ist der Beweis des PCP-Theorems (<b>P<\/b>robabilistically <b>C<\/b>heckable <b>P<\/b>roofs). PCP0:=PCP(log(n),1) ist eine Klasse von Problemen, definiert auf Grund des Begriffs &#8222;stochastisch verifizierbar&#8220;. Das Theorem besagt PCP0=NP (Klasse der in polynomieller Zeit verifizierbaren Probleme).<br \/>\nAus der Definition von PCP folgt unmittelbar, dass NP eine Teilmenge von PCP0 ist. Die Umkehrung wird gef\u00fchrt mit Hilfe von Klassen PCPk (k=1,2), f\u00fcr welche entsprechende Inklusionen gezeigt werden. Diese Klassen sind auch f\u00fcr sich allein betrachtet bedeutsam, besonders auch auf Grund ihrer Anwendung in der Approximationstheorie.<\/p>\n<p><strong>Literatur:<\/strong><\/p>\n<ul>\n<li>Mayr, Pr\u00f6mel, Steger (Eds.): Lectures on Proof Verification and Approximation Algorithms, LNCS 1367, Springer, 1998<\/li>\n<\/ul>\n<h3><\/h3>\n<h3>Komplexit\u00e4tstheorie, Sommersemester 1998<\/h3>\n<p>Ziel des Seminars ist es, einige Aspekte der Komplexit\u00e4tstheorie zu erarbeiten; an dieser Schnittstelle zwischen Logik und Informatik sollen neben den klassischen Resultaten auch neuere Beweismethoden vorgestellt werden.<\/p>\n<p>Die Komplexit\u00e4tstheorie untersucht Fragen der folgenden Art: Sei <i>K<\/i> eine Klasse von Strukturen (z.B. Graphen) und <i>E<\/i> eine Eigenschaft (z.B. dreif\u00e4rbbar). Welchen Aufwand erfordern Algorithmen f\u00fcr die Entscheidung \/ Beweis (deterministische \/ nichtdeterministische Berechnung), dass eine Struktur aus <i>K<\/i> der Gr\u00f6sse <i>n<\/i> die Eigenschaft <i>E<\/i> besitzt. Masse f\u00fcr den Aufwand sind: Schrittzahl (Zeitkomplexit\u00e4t) und Speicherbedarf (Raumkomplexit\u00e4t). Zusammen mit der Alternative deterministisch \/ nicht-deterministisch ergibt dies die\u00a0 &#8222;klassischen&#8220; Klassen <i>TIME<\/i>, <i>NTIME<\/i>, <i>SPACE<\/i>, <i>NSPACE<\/i>.<br \/>\nHierzu sind auf Grund neuerer Beweismethoden weitere Klassen getreten: <i>IP<\/i> (&#8222;interactive proofs&#8220;) und\u00a0 <i>PCP<\/i> (&#8222;probabilistically checkable proofs&#8220;).<\/p>\n<h4>Literatur<\/h4>\n<ul>\n<li>D.P. Bovet, P. Crescenzi: Introduction to the Theory of Complexity, Prentice Hall, 1994<\/li>\n<li>S. Hougardy, H.J. Pr\u00f6mel, A. Steger: Probabilistically checkable proofs and their consequences for approximation algorithms, Discrete Mathematics 136 (1994), 175-223<\/li>\n<\/ul>\n<hr \/>\n<p><em>Konrad Schlude<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<div class=\"mh-excerpt\"><p>In den Jahren 1998 bis 2002 durfte ich zusammen mit Professor Ernst Specker (1920 &#8211; 2011) das Seminar \u00fcber Algorithmik und Logik an der ETH <a class=\"mh-excerpt-more\" href=\"https:\/\/schlu.de\/?p=395\" title=\"Logikseminar an der ETH\">[&#8230;]<\/a><\/p>\n<\/div>","protected":false},"author":1,"featured_media":396,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[15],"tags":[],"class_list":["post-395","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-mathematik"],"_links":{"self":[{"href":"https:\/\/schlu.de\/index.php?rest_route=\/wp\/v2\/posts\/395","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/schlu.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/schlu.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/schlu.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/schlu.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=395"}],"version-history":[{"count":5,"href":"https:\/\/schlu.de\/index.php?rest_route=\/wp\/v2\/posts\/395\/revisions"}],"predecessor-version":[{"id":402,"href":"https:\/\/schlu.de\/index.php?rest_route=\/wp\/v2\/posts\/395\/revisions\/402"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/schlu.de\/index.php?rest_route=\/wp\/v2\/media\/396"}],"wp:attachment":[{"href":"https:\/\/schlu.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=395"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/schlu.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=395"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/schlu.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=395"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}