WEBVTT 00:06.960 --> 00:11.300 Ok, lassen Sie mich beginnen mit ein paar organisatorischen Dingen. 00:12.440 --> 00:14.040 Zunächst nochmal mein Name. 00:14.640 --> 00:19.560 Ich bin wissenschaftlicher Assistent am Institut für angewandte 00:19.560 --> 00:21.540 Informatik und formale Beschreibungsverfahren. 00:23.060 --> 00:28.380 Wenn Sie mich suchen, dann finden Sie mich in meinem Büro in Raum 223. 00:38.590 --> 00:42.090 Manche Leute finden es relativ schwer, sich oben bei uns am Institut 00:42.090 --> 00:46.110 zurechtzufinden, weil die Nummerierung der Räume relativ schwer 00:46.110 --> 00:46.850 durchschaubar ist. 00:46.970 --> 00:51.630 Also mein Büro liegt in Richtung Westen. 00:51.870 --> 00:53.850 Wenn Sie runtergucken, sehen Sie genau den Ballermann. 00:54.530 --> 00:56.190 Das gibt Ihnen vielleicht eine Orientierung. 00:57.870 --> 01:00.370 Meine Sprechstunde ist mittwochs 11 bis 12 Uhr. 01:01.310 --> 01:03.310 Sie können sich auch per E-Mail an mich wenden. 01:03.310 --> 01:05.930 E-Mail-Adresse ist wie üblich bei uns. 01:14.980 --> 01:19.500 Es gibt eine ganze Reihe Informationsquellen, wenn Sie irgendwelche 01:19.500 --> 01:21.320 Fragen haben oder Unterlagen suchen. 01:22.120 --> 01:26.320 Die wichtigste Informationsquelle ist sicherlich das World Wide Web. 01:27.440 --> 01:29.600 Wir haben eine Webseite. 01:31.400 --> 01:34.900 Den Link finden Sie entweder, wenn Sie über die Institut-Webseite 01:34.900 --> 01:40.280 gehen und dann über Lehrangebot Wintersemester 2003-2004 und dann auf 01:40.280 --> 01:41.240 unsere Vorlesung. 01:42.780 --> 01:45.740 Oder Sie merken sich einfach die komplette Adresse, so wie sie 01:45.740 --> 01:46.320 dasteht. 01:47.420 --> 01:51.640 Auf der Webseite finden Sie Links zu relevanten Themen. 01:53.600 --> 01:58.120 Sie finden die ganzen Folien. 01:59.680 --> 02:05.440 Und Sie finden auch einen Link auf die Aufzeichnung der Folien, der 02:05.440 --> 02:05.980 Vorlesung. 02:06.420 --> 02:09.940 Wenn Sie sich vielleicht wundern, warum ich hier so ein Mikrofon trage 02:09.940 --> 02:12.720 und was wir hier vorne alles aufgebaut haben. 02:13.640 --> 02:18.360 Wir bieten Ihnen als zusätzlichen Service an, dass die Vorlesung 02:18.360 --> 02:19.360 aufgezeichnet wird. 02:20.140 --> 02:24.940 Und Sie haben die Möglichkeit, sich die komplette Vorlesung, das heißt 02:24.940 --> 02:29.180 die Folien, so wie wir sie hier durchgehen, alles was ich hier auf die 02:29.180 --> 02:34.200 Folien schreibe, sowie meine Stimme runterzuladen und sich dann als 02:34.200 --> 02:35.200 Video anzuschauen. 02:37.360 --> 02:38.380 Ohne mein Bild. 02:39.380 --> 02:41.660 Das heißt, wenn Sie mich persönlich sehen wollen, dann müssen Sie 02:41.660 --> 02:42.820 immer noch in die Vorlesung kommen. 02:46.800 --> 02:50.800 Sie können sich das runterladen, entweder als AVI-File. 02:51.120 --> 02:54.100 Das können Sie sich dann mit irgendeinem Player anschauen. 02:55.380 --> 02:58.320 Empfehlen würden wir, wenn Sie irgendwelche Probleme haben, den 02:58.320 --> 02:59.300 Camtasia -Player. 02:59.380 --> 03:01.440 Wir zeichnen das auf mit Camtasia. 03:02.540 --> 03:04.980 Aber Sie finden auch die Anleitung dann, denke ich, im Web. 03:06.020 --> 03:09.600 Oder Sie können es sich runterladen in Streaming-Format. 03:10.900 --> 03:14.220 Falls Sie kein Windows benutzen und sich nicht die komplette Vorlesung 03:14.220 --> 03:16.780 runterladen wollen, können Sie eben auch über Streaming gehen. 03:22.560 --> 03:26.620 Die Daten werden von der Universitätsbibliothek bereitgestellt. 03:27.800 --> 03:29.900 Die sind, glaube ich, noch nicht ganz so weit. 03:29.900 --> 03:33.720 Das heißt, wenn Sie die Vorlesung als Aufzeichnung suchen, dann kann 03:33.720 --> 03:35.840 es sein, dass das bis Mittwoch oder Donnerstag kommt. 03:36.180 --> 03:38.460 Aber wir zeichnen jetzt schon auf und Sie können dann alles 03:38.460 --> 03:39.220 nachschauen. 03:40.980 --> 03:43.380 Termine für die Vorlesung sind Montag 11.30 Uhr. 03:43.720 --> 03:45.680 Das ist Ihnen offensichtlich alles bekannt. 03:45.840 --> 03:46.600 Sonst wären Sie nicht hier. 03:47.780 --> 03:49.920 Und Mittwoch 8.00 Uhr bis 9.30 Uhr. 03:51.160 --> 03:53.160 Die Vorlesung ist dreistündig. 03:53.540 --> 03:54.760 Drei Semesterwochenstunden. 03:54.760 --> 03:58.860 Das heißt, der Mittwochstermin findet normalerweise nur alle zwei 03:58.860 --> 03:59.480 Wochen statt. 04:00.700 --> 04:03.280 Wir haben uns gedacht, dass es praktischer wäre, wenn wir diese 04:03.280 --> 04:08.540 zweiwöchigen Veranstaltungen vorziehen und erst einmal Anfang des 04:08.540 --> 04:10.640 Semesters jeden Mittwoch eine Vorlesung machen. 04:11.560 --> 04:14.760 Dann haben Sie am Ende des Semesters mehr Zeit, sich auf Klausuren 04:14.760 --> 04:15.600 vorzubereiten. 04:16.540 --> 04:20.120 Und wir haben auch am Anfang des Semesters schon mehr Stoff für die 04:20.120 --> 04:20.700 Übungsblätter. 04:20.700 --> 04:26.360 Das heißt, zunächst einmal jeden Mittwoch 8.00 Uhr bis 9.30 Uhr hier 04:26.360 --> 04:29.400 im Hörsaal Vorlesung, voraussichtlich bis 3. 04:29.480 --> 04:30.000 Dezember. 04:31.000 --> 04:33.820 Und dann haben wir diese Mittwochstermine abgearbeitet und es findet 04:33.820 --> 04:35.400 nur noch Montagsvorlesung statt. 04:38.580 --> 04:41.040 Klausur findet statt am Montag, den 16. 04:41.540 --> 04:42.180 Februar. 04:43.080 --> 04:48.940 Das ist der erste Montag nach Semesterende oder nach Vorlesungsende. 04:49.940 --> 04:54.020 Und wir haben zusätzlich dieses Semester eine Bonusprüfung. 04:54.660 --> 04:56.520 Das sage ich gleich nachher noch was dazu. 04:57.080 --> 04:58.400 Die findet am 24. 04:58.620 --> 04:59.340 Januar statt. 05:02.160 --> 05:04.020 Ja, wie gesagt, da kommt noch was dazu. 05:04.820 --> 05:08.260 Das Skript stellen wir Ihnen zur Verfügung in Postscript und PDF 05:08.260 --> 05:14.060 -Format, sowohl einzelne Dateien als auch mehrere Folien auf einer 05:14.060 --> 05:14.440 Seite. 05:15.660 --> 05:19.220 Zusätzlich bieten wir Ihnen noch eine Newsgroup, wo Sie Ideen 05:19.220 --> 05:23.200 austauschen können, Fragen stellen können, die wir dann hoffentlich 05:23.200 --> 05:24.540 relativ schnell beantworten. 05:26.540 --> 05:28.920 Übungen gibt es auch zu der Vorlesung. 05:29.760 --> 05:35.020 Wir haben zwei wissenschaftliche Mitarbeiter, die diese Übungen 05:35.020 --> 05:35.460 leiten. 05:35.460 --> 05:38.960 Das ist einmal der Herr Stein und einmal der Herr Gunsch. 05:39.080 --> 05:40.560 Ich glaube, Fotos habe ich auch noch hier. 05:45.360 --> 05:49.080 Herr Stein sitzt in Raum 234, das ist die Nordseite. 05:50.000 --> 05:53.460 Und Herr Gunsch sitzt nicht in Raum 234, sondern... 05:55.000 --> 05:57.560 Okay, 250. 05:58.220 --> 05:59.400 Gut, 250. 06:09.240 --> 06:12.040 Sprechstunde ist jeweils angegeben, bzw. 06:12.500 --> 06:15.280 Sie können sich auch per E-Mail an die Mitarbeiter wenden. 06:16.160 --> 06:20.240 Wir haben außerdem 15 Tutorinnen und Tutoren, die Sie über das 06:20.240 --> 06:21.960 Semester in den Tutorien begleiten. 06:22.660 --> 06:25.680 Die Tutorien finden jeweils 14-tägig statt. 06:26.380 --> 06:28.380 Es gibt aber zwei Gruppen pro Tutor. 06:29.080 --> 06:32.700 Das heißt, zwei Wochen hintereinander findet genau das gleiche 06:32.700 --> 06:35.980 Tutorium statt, vom gleichen Tutor zur gleichen Zeit im gleichen Raum. 06:36.440 --> 06:39.840 Aber Sie besuchen natürlich nur jede zweite Woche das Tutorium. 06:39.840 --> 06:42.980 Das heißt, entweder Sie sind in der ersten Gruppe, dann haben Sie in 06:42.980 --> 06:45.080 Wochen 1, 3, 5 usw. 06:45.280 --> 06:45.780 ein Tutorium. 06:45.880 --> 06:48.920 Oder Sie sind in der zweiten Gruppe, dann haben Sie das gleiche 06:48.920 --> 06:52.560 Tutorium in den Wochen 2, 4, 6 usw. 06:54.000 --> 06:56.640 Beginn der Tutorien ist am 27.10. 06:57.960 --> 07:01.440 Eine Woche vorher werden wir entsprechende Übungsblätter austeilen. 07:03.260 --> 07:07.120 Für die Tutorien würde ich Sie bitten, sich anzumelden im Internet ab 07:07.120 --> 07:07.980 Donnerstag. 07:09.600 --> 07:12.800 Einfach auf unseren Webseiten schauen und da finden Sie dann ein 07:12.800 --> 07:15.960 Anmeldungsprogramm, wo Sie sich über Internet anmelden können. 07:16.720 --> 07:19.460 Wir haben auch eine Tutoren-Sprechstunde. 07:19.620 --> 07:22.240 Das heißt, wenn Sie Fragen zum Stoff haben, wenn Sie Fragen zu den 07:22.240 --> 07:26.140 Übungsblättern haben, wenn Sie nicht verstehen, wieso Ihre 07:26.140 --> 07:30.720 Übungsblätter so oder anders korrigiert wurden und das vielleicht ein 07:30.720 --> 07:33.900 bisschen umfangreicher wird, dazu, dass die Zeit nicht reicht, es 07:33.900 --> 07:37.980 direkt nach dem Tutorium mit Ihrem Tutor zu besprechen, dann können 07:37.980 --> 07:40.080 Sie in die Tutoren-Sprechstunde gehen. 07:40.920 --> 07:43.800 Die ist jeweils... 07:46.970 --> 07:50.030 Okay, jetzt funktioniert mein schönes Werkzeug hier nicht mehr. 07:51.770 --> 07:57.630 Freitag 9.15 Uhr bis 11.15 Uhr in Raum Minus 117. 07:57.630 --> 08:01.470 Minus heißt Untergeschoss oder Sockelgeschoss, wie es manchmal 08:01.470 --> 08:02.690 netterweise genannt wird. 08:04.610 --> 08:10.250 Und das ist in der südwestlichen Ecke der Raum bei uns im 08:10.250 --> 08:11.630 Kollegiengebäude am Ehrenhof. 08:14.030 --> 08:17.730 Okay, zum Übungskonzept muss ich, glaube ich, ein paar Worte 08:17.730 --> 08:18.270 verlieren. 08:19.630 --> 08:22.190 Wir haben uns lange Gedanken gemacht, weil wir mit unserem 08:22.190 --> 08:24.930 Übungskonzept nicht hundertprozentig glücklich waren und deswegen 08:24.930 --> 08:27.910 haben wir dieses Semester ein paar Änderungen eingeführt. 08:28.870 --> 08:31.570 Die Ziele von diesen Übungen sind vielfältig. 08:33.810 --> 08:37.590 Zum einen ist uns wichtig, dass Sie sich schon während des Semesters 08:37.590 --> 08:40.710 mit dem Stoff auseinandersetzen und nicht erst auf die Klausur lernen. 08:41.770 --> 08:42.670 Das hat zwei Gründe. 08:42.830 --> 08:47.350 Der eine Grund ist, dass Sie sonst eigentlich keine Chance haben, in 08:47.350 --> 08:49.410 der Vorlesung mitzukommen mit dem, was ich erzähle. 08:49.410 --> 08:52.310 Wenn Sie sich nicht zu Hause damit beschäftigt haben und es einfach 08:52.310 --> 08:55.870 nochmal darüber nachgedacht haben und rekapituliert haben, dann hänge 08:55.870 --> 08:57.770 ich Sie zwangsläufig hier in der Vorlesung ab. 08:58.830 --> 09:07.230 Der andere Grund ist, dass die Vorlesung oder die Klausur sehr nah bei 09:07.230 --> 09:09.650 der Klausur über Statistik 2 liegt. 09:10.290 --> 09:14.390 Ich glaube, die Statistik 2 Klausur ist zwei Tage vor der Klausur 09:14.390 --> 09:17.590 Angewandte Informatik 2. 09:20.130 --> 09:24.110 Das bedeutet, es funktioniert einfach nicht, nur die Woche vorher zu 09:24.110 --> 09:28.830 lernen, weil Sie zwei große Klausuren haben, die im gleichen Zeitraum 09:28.830 --> 09:29.430 stattfinden. 09:33.190 --> 09:36.510 Um Ihnen das nochmal zu verdeutlichen, nicht um Ihnen Angst zu machen, 09:36.970 --> 09:40.970 wir hatten letztes Jahr bei dieser Klausur ungefähr 30% 09:40.970 --> 09:41.710 Durchfallquote. 09:42.950 --> 09:46.690 Das liegt meines Erachtens nicht daran, dass die Klausur schwerer war 09:46.690 --> 09:47.210 als sonst. 09:47.210 --> 09:52.970 Das liegt daran, dass wir umgestellt haben den Zyklus, ich sage 09:52.970 --> 09:56.110 nachher auch noch ein paar Worte dazu, von Informatik A, B, C auf 09:56.110 --> 09:59.130 Grundlagen der Informatik 1 und 2. 10:00.270 --> 10:03.830 Dadurch ist einmal der Stoffumfang pro Prüfung natürlich größer 10:03.830 --> 10:07.910 geworden, also insbesondere der Stoffumfang für die Grundlagen der 10:07.910 --> 10:09.190 Informatik 2 Prüfung. 10:10.250 --> 10:13.510 Und Sie haben eben jetzt das Problem, dass Sie im Grundstudium diese 10:13.510 --> 10:16.990 Statistik Klausur und die Informatik Klausur so dicht hintereinander 10:16.990 --> 10:17.350 haben. 10:18.430 --> 10:20.770 Wir versuchen diese Klausuren zu entzerren. 10:22.050 --> 10:24.910 Das ist aber nicht möglich und wahrscheinlich die nächsten zwei Jahre 10:24.910 --> 10:28.690 auch noch nicht möglich, weil die Hörsäle für die Klausuren, 10:28.850 --> 10:33.610 insbesondere für so große Klausuren, schon zwei, drei Jahre im Voraus 10:33.610 --> 10:36.770 geplant werden und man da jetzt die nächsten zwei Jahre nichts mehr 10:36.770 --> 10:37.450 dran ändern kann. 10:39.710 --> 10:42.930 Gut, aber deswegen einfach nochmal zur Verdeutlichung, es ist wichtig 10:42.930 --> 10:46.450 bei dieser Vorlesung, dass Sie auch schon während des Semesters 10:46.450 --> 10:47.110 arbeiten. 10:48.510 --> 10:51.870 Wir möchten selbstständiges Lernen fördern, also Ihnen nicht nur 10:51.870 --> 10:59.670 bestimmte Aufgabentypen vorkauen, sondern auch Sie anregen, selber 10:59.670 --> 11:02.870 über den Stoff nachzudenken, vielleicht mal in dem einen oder anderen 11:02.870 --> 11:06.050 Buch zu blättern, das Ganze mal aus einer anderen Perspektive zu 11:06.050 --> 11:06.350 sehen. 11:07.290 --> 11:11.190 Wir möchten Ihnen beibringen, wie man komplexe Aufgaben löst und an 11:11.190 --> 11:12.430 solche Aufgaben rangeht. 11:13.210 --> 11:19.730 Es ist leider im Rahmen einer 90-minütigen Klausur nicht möglich, 11:20.250 --> 11:24.110 Ihnen praxisrelevante Prüfungsaufgaben zu geben. 11:25.310 --> 11:29.850 Keine der Aufgaben, die Ihnen in der Industrie begegnen werden, lassen 11:29.850 --> 11:31.790 sich in 10 oder 15 Minuten lösen. 11:31.790 --> 11:36.030 Und das ist aber eigentlich das Maximum, was wir pro Aufgabe für eine 11:36.030 --> 11:37.170 Klausur vorsehen können. 11:38.490 --> 11:42.870 Das heißt, wir müssen diesen Teil, wie geht man an komplexe 11:42.870 --> 11:46.890 Fragestellungen ran, irgendwie in den Übungen behandeln. 11:48.770 --> 11:51.890 Die Übungen haben außerdem das Ziel, Ihnen ein Feedback zu geben, 11:52.170 --> 11:55.010 schon während dem Semester, dass Sie also mitbekommen, okay, ich habe 11:55.010 --> 11:57.450 den Stoff verstanden oder ich habe den Stoff nicht verstanden, ich 11:57.450 --> 11:59.510 muss vielleicht ein bisschen mehr lernen. 12:01.810 --> 12:08.870 Und wir haben auch das Ziel der Fairness und das ist das Problem, das 12:08.870 --> 12:11.470 wir bisher eigentlich mit dem Übungskonzept hatten. 12:12.610 --> 12:18.130 Bisher hatten wir benotete, abgegebene Übungsblätter, das heißt, wir 12:18.130 --> 12:21.110 haben die Übungsblätter ausgegeben, Sie haben die bearbeitet, Sie 12:21.110 --> 12:24.230 haben die in der Vorlesung abgegeben, die wurden korrigiert und wenn 12:24.230 --> 12:28.030 Sie über eine bestimmte Anzahl von Punkten erreicht haben, dann haben 12:28.030 --> 12:29.850 Sie einen Bonus auf die Klausur bekommen. 12:33.170 --> 12:35.050 Das hat zwei Nachteile. 12:35.930 --> 12:39.470 Zum einen hat es immer mehr Studenten gegeben, die einfach nur 12:39.470 --> 12:42.910 abgeschrieben haben, ihre Übungsblätter, die gar nicht bearbeitet 12:42.910 --> 12:45.330 haben und letztendlich den Bonus bekommen haben. 12:46.630 --> 12:49.990 Zum anderen hatten wir einen relativ großen zeitlichen Versatz zur 12:49.990 --> 12:50.510 Vorlesung. 12:50.510 --> 12:53.030 Der Stoff wurde in der Vorlesung behandelt, wir haben die 12:53.030 --> 12:56.350 Übungsblätter ausgeteilt, Sie hatten genug Zeit, diese Übungsblätter 12:56.350 --> 12:59.830 zu bearbeiten, die Übungsblätter mussten dann wieder abgegeben werden, 12:59.910 --> 13:02.510 dann mussten die Übungsblätter korrigiert werden, dann wurden sie in 13:02.510 --> 13:07.430 der ersten Gruppe diskutiert und dann wurden sie erst in der zweiten 13:07.430 --> 13:10.830 Gruppe diskutiert, sodass zwischen dem Stoff der Vorlesung und dem, 13:10.930 --> 13:14.710 was in den Tutorien tatsächlich passiert ist, eine Lücke von vier bis 13:14.710 --> 13:15.710 sechs Wochen klaffte. 13:17.170 --> 13:20.650 Deswegen haben wir uns überlegt, was kann man an dem Übungskonzept 13:20.650 --> 13:25.870 ändern und wir sind bereit, dieses Übungskonzept auch in Zukunft 13:25.870 --> 13:28.570 nochmal zu modifizieren, aber wir wollten einfach mal was Neues 13:28.570 --> 13:28.890 ausprobieren. 13:30.790 --> 13:34.430 Das neue Übungskonzept für dieses Semester sieht folgendermaßen aus. 13:35.470 --> 13:40.590 Wir haben wieder Übungsblätter mit relativ komplexen Aufgaben, um eben 13:40.590 --> 13:45.350 Ihnen auch schwierigere Aufgaben als in der Klausur mal zum Bearbeiten 13:45.350 --> 13:45.830 zu geben. 13:46.710 --> 13:48.650 Die Bearbeitung ist jedoch freiwillig. 13:49.110 --> 13:53.910 Das heißt, wir passen nicht mehr so gut auf wie vorher, zwingen Sie 13:53.910 --> 13:57.970 nicht mehr zur Abgabe, denn der Zwang hat eben dazu geführt, dass 13:57.970 --> 14:00.950 viele Leute nur abgeschrieben haben und dann hat es auch keinen 14:00.950 --> 14:01.290 Effekt. 14:01.910 --> 14:07.090 Wir bauen jetzt darauf, dass Sie motiviert genug sind, diese 14:07.090 --> 14:11.850 Übungsblätter selbst zu bearbeiten, dass Sie einsehen, dass diese 14:11.850 --> 14:17.410 Ziele, die ich hier oben definiert habe, dass die sinnvoll sind, dass 14:17.410 --> 14:20.910 Sie eben lernen müssen, auch komplexe Aufgaben zu bearbeiten. 14:22.610 --> 14:27.130 Und wir machen deswegen die Bearbeitung dieses Semester freiwillig. 14:29.270 --> 14:32.250 Wir wollen Ihnen aber natürlich ein Feedback geben. 14:32.350 --> 14:36.550 Die Musterlösung wird vor den Tutorien im www veröffentlicht. 14:36.550 --> 14:39.970 Das heißt, Sie können selber schauen, haben Sie die Übungen korrekt 14:39.970 --> 14:40.890 gelöst oder nicht. 14:43.290 --> 14:49.010 Deswegen ist es nur noch teilweise notwendig, auf die Übungsblätter im 14:49.010 --> 14:50.230 Tutorium einzugehen. 14:50.670 --> 14:53.710 Das heißt, der Tutor wird nur noch gezielt bestimmte Punkte 14:53.710 --> 15:00.170 herausgreifen, wird dann Fragen dazu beantworten und die Übungsblätter 15:00.170 --> 15:02.950 werden nicht mehr komplett vorgerechnet, sondern mehr oder weniger 15:02.950 --> 15:03.670 diskutiert. 15:05.350 --> 15:09.970 Okay, wir bieten Ihnen außerdem noch die Möglichkeit, wenn Sie jetzt 15:09.970 --> 15:14.130 feststellen, Ihre Lösung, die Sie sich ausgedacht haben, 15:14.670 --> 15:18.330 korrespondiert nicht genau mit der Musterlösung, dann wollen wir Ihnen 15:18.330 --> 15:21.830 gerne Feedback geben, was an dieser Lösung korrekt ist oder ob Ihr 15:21.830 --> 15:25.270 Lösungsweg vielleicht auch korrekt ist, nur ein anderer Lösungsweg ist 15:25.270 --> 15:25.920 als in der Musterlösung. 15:25.920 --> 15:32.180 Das heißt, wir haben eine freiwillige Abgabe. 15:41.950 --> 15:46.310 Sie können das, was Sie zu Hause gerechnet haben, Ihre Lösung beim 15:46.310 --> 15:47.250 Tutor abgeben. 15:47.650 --> 15:51.630 Der Tutor wird sich hoffentlich viel Mühe geben, das detailliert zu 15:51.630 --> 15:55.010 korrigieren und Ihnen ein Feedback zu geben, was jetzt korrekt war, 15:55.130 --> 15:59.370 was nicht korrekt war, wie viele Punkte sowas vielleicht noch gegeben 15:59.370 --> 15:59.770 hätte. 16:01.750 --> 16:07.030 Im Tutorium selber, wie gesagt, die Diskussion der Übungsblätter, das 16:07.030 --> 16:10.990 sollte dann aber nicht mehr allzu viel Zeit in Anspruch nehmen. 16:12.070 --> 16:16.630 Und ansonsten Gruppenarbeit zur Lösung kleinerer Probleme. 16:17.230 --> 16:21.370 Das heißt, wir geben Ihnen typische Klausuraufgaben im Tutorium und 16:21.370 --> 16:23.970 Sie setzen sich in Kleingruppen zusammen und arbeiten daran. 16:24.570 --> 16:28.310 Die Idee ist, dass Ihnen das vielleicht ein relativ gutes Feedback 16:28.310 --> 16:31.810 dazu gibt, wie Ihr Wissensstand ist im Vergleich zu dem mit Kollegen, 16:32.410 --> 16:40.230 dass Sie ein bisschen Teamarbeit praktizieren und dass der Tutor Ihnen 16:40.230 --> 16:43.370 beim Lösen der Aufgaben behilflich sein kann. 16:43.510 --> 16:47.150 Das heißt, er wird von Gruppe zu Gruppe gehen, wird sich anhören, was 16:47.150 --> 16:50.890 Sie da diskutieren und wird versuchen, Ihnen die Herangehensweise an 16:50.890 --> 16:55.180 das Problem zu verdeutlichen. 16:56.170 --> 16:59.010 Denn es kommt letztendlich nicht nur darauf an, dass Sie einen 16:59.010 --> 17:02.830 bestimmten Lösungsweg letztendlich können, sondern es kommt darauf an, 17:03.230 --> 17:06.890 dass Sie eine neue Aufgabe gestellt bekommen und dass Sie wissen, was 17:06.890 --> 17:10.730 für Gedanken müssen gemacht werden, um diese Aufgabe lösen zu können. 17:11.470 --> 17:14.870 Und sowas ist, denke ich, in Gruppenarbeit ganz gut möglich. 17:15.550 --> 17:17.830 Das ist also der neue Sinn der Tutorien. 17:19.630 --> 17:21.450 Außerdem, hatte ich schon erwähnt, haben wir diese 17:21.450 --> 17:25.450 Tutorensprechstunde, die auch ein freiwilliges Angebot ist, das heißt, 17:25.550 --> 17:28.010 da können Sie hingehen, können sich nochmal alles erklären lassen, 17:28.130 --> 17:29.470 wenn Sie was nicht verstanden haben. 17:30.810 --> 17:33.090 Und das waren jetzt alles freiwillige Angebote. 17:35.130 --> 17:38.030 Und wie gesagt, meine Hoffnung ist, dass Sie motiviert genug sind, 17:38.130 --> 17:40.730 diese freiwilligen Angebote auch tatsächlich anzunehmen. 17:41.610 --> 17:47.730 Falls das für Ihre Motivation nicht ausreicht, haben wir zusätzlich 17:47.730 --> 17:49.130 noch eine Bonusprüfung. 17:50.810 --> 17:53.590 Das heißt, am 24. 17:53.870 --> 17:58.090 Januar machen wir eine relativ kurze Prüfung. 17:59.930 --> 18:02.670 Dreiviertelstunde, eine Stunde vielleicht maximal. 18:04.470 --> 18:13.660 Und da geben wir Ihnen Aufgaben, von diesen komplexen Aufgaben, von 18:13.660 --> 18:14.500 den Übungsblättern. 18:17.520 --> 18:21.640 Das sind Aufgabentypen, die Sie kennen, die werden Sie vielleicht 18:21.640 --> 18:25.040 leicht modifizieren, aber im Prinzip, wenn Sie die Übungsblätter 18:25.040 --> 18:29.580 gemacht haben und verstanden haben, sollte es überhaupt kein Problem 18:29.580 --> 18:34.720 sein, dieses Wissen nochmal hervorzuholen in der Bonusprüfung. 18:35.540 --> 18:38.800 Die Bonusprüfung ist freiwillig, Sie müssen nicht daran teilnehmen. 18:40.120 --> 18:43.960 Sie können auch volle Punktzahl in der Klausur, also eine 1-0 mit 18:43.960 --> 18:47.180 voller Punktzahl, in der Klausur erreichen, ohne an der Bonusprüfung 18:47.180 --> 18:48.240 teilgenommen zu haben. 18:48.820 --> 18:53.140 Aber, wenn Sie sowieso die Übungsblätter gemacht haben, dann sollten 18:53.140 --> 18:55.700 Sie das Wissen haben, auch schon für die Bonusprüfung. 18:55.700 --> 18:59.280 Dann können Sie daran teilnehmen, Sie können Ihr Wissen unter Beweis 18:59.280 --> 19:03.180 stellen, können zeigen, dass Sie die Übungsaufgaben gemacht haben und 19:03.180 --> 19:07.240 können dann einen Bonus für die bestandene Klausur bekommen. 19:08.200 --> 19:10.800 Das heißt, wenn Sie die Klausur bestehen, kriegen Sie nochmal eine 19:10.800 --> 19:14.340 Drittelnote besser, wenn Sie die Bonusprüfung auch bestanden haben. 19:16.460 --> 19:22.380 Okay, das sind unsere grundlegenden Ideen gewesen und das neue 19:22.380 --> 19:24.360 Übungskonzept, das daraus resultiert ist. 19:24.840 --> 19:27.180 Gibt es dazu konkret irgendwelche Fragen? 19:32.200 --> 19:35.600 Wenn das nicht der Fall ist, dann werden wir das einfach mal so 19:35.600 --> 19:36.280 ausprobieren. 19:37.600 --> 19:40.320 Da das das erste Mal ist, dass wir dieses Konzept in dieser Art und 19:40.320 --> 19:42.400 Weise durchführen, sind wir auch dankbar für Feedback. 19:42.920 --> 19:46.560 Wenn also was gut klappt oder nicht gut klappt, schicken Sie uns eine 19:46.560 --> 19:48.000 E -Mail und lassen Sie es uns wissen. 19:48.440 --> 19:51.300 Das wird sich auswirken auf die Art und Weise, wie wir in den 19:51.300 --> 19:54.260 zukünftigen Jahren unser Übungskonzept gestalten. 20:01.280 --> 20:03.860 Okay, noch Grundsätzliches. 20:05.640 --> 20:10.200 Sie haben wahrscheinlich mitbekommen, dass wir den Studienplan 20:10.200 --> 20:14.300 umgestellt haben, was früher Informatik A, B, C waren, also drei 20:14.300 --> 20:16.230 Vorlesungen, sind jetzt nur noch zwei Vorlesungen. 20:17.200 --> 20:21.560 Was früher die meisten Studenten im Hauptstudium gehört haben, findet 20:21.560 --> 20:23.080 jetzt im Grundstudium statt. 20:23.080 --> 20:28.760 Und weil wir gerade in dieser Periode sind, wo wir von einem 20:28.760 --> 20:32.480 Studienplan auf den anderen umstellen, haben wir im Wesentlichen jetzt 20:32.480 --> 20:36.920 wahrscheinlich zwei Jahrgänge hier in der Vorlesung sitzen, nämlich 20:36.920 --> 20:41.620 die, die noch nach der alten Studienordnung studieren und eben das im 20:41.620 --> 20:45.380 Hauptstudium machen und diejenigen, die neu dazugekommen sind und das 20:45.380 --> 20:46.380 im Grundstudium machen. 20:46.860 --> 20:48.300 Deswegen haben wir auch so viele Studenten. 20:50.560 --> 20:53.600 Vielleicht darf ich gerade mal fragen, wer macht denn die Vorlesungen 20:53.600 --> 20:54.500 im Hauptstudium? 20:57.600 --> 20:59.760 Okay, es sind gar nicht so viele. 21:03.360 --> 21:05.760 Jetzt kann es natürlich sein, dass die Leute zu faul waren, die Hand 21:05.760 --> 21:05.940 zu heben. 21:05.980 --> 21:07.180 Wer macht es denn im Grundstudium? 21:08.660 --> 21:09.720 Okay, doch fast alle. 21:11.200 --> 21:13.820 Also wir hatten letztes Jahr schon diese Überlappung, dass wir Leute 21:13.820 --> 21:16.160 hatten aus dem Hauptstudium und aus dem Grundstudium. 21:16.160 --> 21:21.820 Das zeigt, dass dieser Prozess jetzt langsam zu Ende geht und dass wir 21:21.820 --> 21:24.580 im nächsten Jahr wahrscheinlich nur noch Grundstudium rechnen können 21:24.580 --> 21:26.640 und deswegen auch weniger Studenten haben werden. 21:31.520 --> 21:35.560 Okay, für diejenigen, die irgendwie schon angefangen haben A, B und C 21:35.560 --> 21:38.780 zu hören und die das jetzt ergänzen wollen, für die gilt im 21:38.780 --> 21:46.760 Wesentlichen die Regel hier, Informatik 1 und Informatik A werden als 21:46.760 --> 21:47.840 Äquivalent betrachtet. 21:48.900 --> 21:52.000 Wenn Ihnen also nur noch Informatik A fehlt und Sie haben B und C 21:52.000 --> 21:55.220 schon gehört, dann können Sie jetzt einfach nur noch Informatik 1 21:55.220 --> 22:00.620 hören und Informatik 2 und Informatik B und C werden übergangsweise 22:00.620 --> 22:01.860 als Äquivalent betrachtet. 22:01.860 --> 22:07.520 Das heißt, wenn Ihnen noch B und C fehlt, dann können Sie jetzt 22:07.520 --> 22:11.020 einfach Informatik 2 hören und das deckt die beiden Bereiche B und C 22:11.020 --> 22:11.280 ab. 22:12.460 --> 22:15.480 Das ist vom Stoffumfang auch fast identisch. 22:17.720 --> 22:22.860 Bisher waren das zwei Semesterwochenstundenvorlesungen, jetzt haben 22:22.860 --> 22:25.460 wir eine Dreisemesterwochenstundenvorlesung, aber sie ist ein 22:25.460 --> 22:30.140 Wintersemester und das Wintersemester hat deutlich mehr Wochen, sodass 22:30.140 --> 22:32.100 der Stoffumfang fast identisch ist. 22:33.760 --> 22:36.840 Wenn Sie B schon gehört haben und es fehlt Ihnen nur noch C oder Sie 22:36.840 --> 22:40.360 haben C gehört und es fehlt Ihnen nur noch B, dann müssten Sie 22:40.360 --> 22:43.880 nachfragen, was man da konkret macht, aber da findet sich dann ein 22:43.880 --> 22:45.480 Weg, zum Beispiel über mündliche Prüfungen. 22:52.120 --> 22:59.580 Okay, die Informatikausbildung, die wir am Institut anbieten, gliedert 22:59.580 --> 23:01.060 sich jetzt in vier Teile. 23:01.180 --> 23:04.960 Das Ganze fängt an mit Programmieren I, Einführung in die 23:04.960 --> 23:08.520 Programmierung, dann Grundlagen der Informatik I, was Sie 23:08.520 --> 23:10.680 wahrscheinlich letztes Semester gehört haben. 23:11.960 --> 23:15.000 Jetzt im Augenblick, hier diese Vorlesung ist Grundlagen der 23:15.000 --> 23:19.380 Informatik II und im Hauptstudium kommt dann noch die Programmierung 23:19.380 --> 23:22.120 kommerzieller Systeme, für die Wirtschaftsingenieure zumindest. 23:23.760 --> 23:31.080 Ich gehe auf Informatik I und II, auf die Inhalte nochmal ein bisschen 23:31.080 --> 23:31.840 genauer ein. 23:32.680 --> 23:35.400 Zunächst ein kurzer Rückblick auf Informatik I. 23:37.060 --> 23:42.240 Da stand im Mittelpunkt die Frage, wie realisiert man 23:42.240 --> 23:48.760 Problemlösungsverfahren, indem man einen Computer programmiert und 23:48.760 --> 23:50.280 zwar einen Universalrechner. 23:54.120 --> 23:57.720 Universalrechner heißt, dass ich ein Stück Hardware habe, aber ganz 23:57.720 --> 23:59.620 verschiedene Programme daraus ausführen kann. 24:00.310 --> 24:04.500 Und wie beurteilt man die Qualität und die Kosten dieser Programme? 24:06.500 --> 24:11.700 Sie haben kennengelernt die Unified Modeling Language, um Systeme und 24:11.700 --> 24:15.120 Abläufe zu modellieren, was sehr hilfreich ist, wenn Sie ein Programm 24:15.120 --> 24:17.580 entwickeln, wenn Sie ein Programm spezifizieren. 24:22.470 --> 24:26.410 Sie haben Aussagenlogik, Prädikatenlogik in der Vorlesung 24:26.410 --> 24:33.570 kennengelernt, bursche Algebren, wobei Aussagenlogik und bursche 24:33.570 --> 24:36.230 Algebren auch für diese Vorlesung vorausgesetzt werden. 24:39.980 --> 24:43.140 Darf ich Sie nochmal bitten, ein bisschen ruhiger zu sein? 24:43.920 --> 24:46.880 Meine Stimme ist heute nicht ganz so fit wie normalerweise. 24:46.940 --> 24:47.180 Danke. 24:47.920 --> 24:51.680 Wenn Sie also Informatik 1 noch nicht gehört haben, dann würde ich Sie 24:51.680 --> 24:55.620 bitten, speziell diese Kapitel Aussagenlogik und bursche Algebren 24:55.620 --> 24:59.500 vielleicht aus dem Netz zu laden und nochmal durchzuschauen. 24:59.800 --> 25:01.900 Die Kapitel setze ich voraus in der Vorlesung. 25:04.060 --> 25:08.640 Wir haben uns angeschaut, welche Eigenschaften haben Algorithmen, wie 25:08.640 --> 25:13.440 Endlichkeit, Determiniertheit, wie spezifiziert man Algorithmen in 25:13.440 --> 25:16.720 Programmiersprachen, wie beurteilt man die Qualität. 25:17.240 --> 25:19.880 Ich bin mir nicht sicher, ob Sie auch über Korrektheit geredet haben. 25:20.240 --> 25:25.120 Ein ganz wichtiger Aspekt im Prinzip, der aber leider sehr schwer 25:25.120 --> 25:25.920 handhabbar ist. 25:26.200 --> 25:29.380 Nicht umsonst haben wir ständig fehlerhafte Programme, Abstürze. 25:30.400 --> 25:35.040 Ich habe jetzt erst wieder gelesen, dass der häufigste Fehler, warum 25:35.040 --> 25:38.080 die modernen Autos liegen bleiben, Softwarefehler sind. 25:38.080 --> 25:41.920 Also Korrektheit von Programmen ist ein sehr schwieriges Thema. 25:43.660 --> 25:46.380 Ein anderes wichtiges Thema ist die Komplexität. 25:47.060 --> 25:48.820 Wie lange läuft denn so ein Programm? 25:49.860 --> 25:52.720 Im besten Fall, im schlechtesten Fall, im mittleren Fall. 25:53.880 --> 25:56.880 Und der Punkt ist auch ein Punkt, auf den wir in der Vorlesung 25:56.880 --> 26:01.500 Informatik 2 zurückgreifen, den Sie also nacharbeiten müssten, wenn 26:01.500 --> 26:03.380 Sie Informatik 1 noch nicht gehört haben. 26:03.380 --> 26:07.120 Komplexität, die Groß-O-Notation im Wesentlichen. 26:09.000 --> 26:13.080 Sie haben Entwurfsprinzipien kennengelernt, wie geht man überhaupt 26:13.080 --> 26:17.220 vor, was gibt es für verschiedene Techniken der Programmierung, 26:17.360 --> 26:20.680 Backtracking, Divide & Conquer, Branch & Bound, dynamisches 26:20.680 --> 26:21.420 Programmieren. 26:24.940 --> 26:28.800 Und Sie haben verschiedene Datenstrukturen kennengelernt, die eben 26:28.800 --> 26:33.400 wichtig sind, um effizient programmieren zu können, wie Listen und 26:33.400 --> 26:35.740 Baumstrukturen, Schlange oder Heap. 26:36.200 --> 26:38.680 Heapsort sagt Ihnen wahrscheinlich was, Quicksort. 26:39.460 --> 26:43.140 Also es kommt durchaus darauf an, wie man programmiert, ob das 26:43.140 --> 26:45.500 Programm letztendlich effizient läuft oder nicht. 26:47.580 --> 26:48.420 Okay. 26:49.320 --> 26:51.920 Kommen wir zur Informatik 2. 26:53.000 --> 26:56.280 Der Stoff der Vorlesung gliedert sich in zwei Teile. 26:57.020 --> 27:01.080 Im ersten Teil werden wir formale Modelle der Informatik uns 27:01.080 --> 27:01.600 anschauen. 27:03.460 --> 27:07.320 Das heißt, es ist mehr ein Grundlagenteil, ein Theorie-Teil. 27:07.320 --> 27:12.800 Da geht es dann um endliche Automaten und reguläre Sprachen oder 27:12.800 --> 27:15.120 Kellerautomaten und kontextfreie Sprachen. 27:15.380 --> 27:20.440 Also verschiedene komplexe Automaten und verschiedene komplexe 27:20.440 --> 27:22.320 Sprachsysteme. 27:23.020 --> 27:26.360 Und schließlich noch um Berechenbarkeit und Komplexität. 27:27.300 --> 27:30.980 In Teil 2 geht es dann mehr um die Architektur von Rechnersystemen. 27:31.600 --> 27:33.940 Es geht um Schaltnetze und Schaltwerke. 27:34.500 --> 27:39.780 Also da schauen wir uns tatsächlich die Hardware-Implementierung an, 27:40.320 --> 27:44.740 die Gatter-Ebene bis hinunter zur Transistorebene. 27:44.880 --> 27:46.540 Wie funktioniert eigentlich so ein Rechner? 27:49.280 --> 27:53.360 Wir schauen uns so Dinge an wie Codierung, Zahlendarstellung, 27:53.500 --> 27:54.500 Rechnerarithmetik. 27:54.920 --> 27:59.160 Wie Sie sicher wissen, können Computer nur mit zwei Zuständen rechnen. 27:59.300 --> 28:02.300 Entweder auf der Leitung ist Strom oder es ist kein Strom, also 0 oder 28:02.300 --> 28:02.800 1. 28:04.000 --> 28:07.260 Und wenn man nun alles übersetzen muss in Nullen und Einsen, muss man 28:07.260 --> 28:11.300 sich überlegen, wie stellt man eine bestimmte Zahl dar, wie rechnet 28:11.300 --> 28:13.840 man mit Nullen und Einsen all diese Dinge. 28:14.920 --> 28:17.680 Wir schauen uns die typische Rechner-Architektur an. 28:18.240 --> 28:21.380 Das heißt, was macht die CPU, was für verschiedene Speicher 28:21.380 --> 28:22.500 -Hierarchien gibt es. 28:23.240 --> 28:25.760 Wir schauen uns verschiedene Ebenen der Programmierung an. 28:27.760 --> 28:29.720 Wir schauen uns an, was ein Betriebssystem macht. 28:30.680 --> 28:34.880 Und wir schauen uns auch an, wie man Dateien effizient organisieren 28:34.880 --> 28:35.160 kann. 28:38.410 --> 28:43.390 Literatur gibt es eine ganze Menge und ich empfehle Ihnen sehr, 28:43.630 --> 28:46.710 einfach mal in bestimmte Bücher reinzuschauen. 28:49.490 --> 28:53.390 Als ich studiert habe, war es für mich immer sehr hilfreich, einfach 28:53.390 --> 28:56.230 nicht nur die Sicht des Dozenten zu sehen, sondern im Prinzip den 28:56.230 --> 28:58.610 gleichen Stoff nochmal anders erklärt zu bekommen. 28:59.790 --> 29:02.590 Da entwickelt man ein sehr viel tieferes Verständnis und deswegen 29:02.590 --> 29:05.950 würde ich Ihnen empfehlen, auch mal in die Literatur reinzuschauen. 29:07.910 --> 29:12.130 Für den ersten Teil, für den theoretischen Teil, kann ich Ihnen 29:12.130 --> 29:14.850 insbesondere zwei Bücher ans Herz legen. 29:15.910 --> 29:22.050 Das eine ist dieses hier von Hopcroft, Motwani und Ullmann. 29:22.150 --> 29:26.690 Das ist so im Prinzip das Standardwerk im Bereich theoretische 29:26.690 --> 29:28.790 Informatik, Sprachen- und Komplexitätstheorie. 29:30.430 --> 29:33.510 Und auch noch ein Buch, das mir sehr gut gefällt, ist von Ingo 29:33.510 --> 29:37.090 Wegener, der eine ganz andere Sichtweise hat. 29:37.610 --> 29:40.630 Der zäumt das Pferd im Prinzip von hinten auf. 29:42.270 --> 29:45.350 Also es ist vielleicht gut, wenn Sie... dieses Buch eignet sich 29:45.350 --> 29:48.470 vielleicht irgendwie zur Klausurvorbereitung, wenn Sie den Stoff schon 29:48.470 --> 29:52.710 komplett mal erfasst haben, weil wir anfangen hier in der Vorlesung 29:52.710 --> 29:55.450 mit ganz einfachen Automaten und dann immer komplexer werden. 29:55.450 --> 29:58.750 Und er fängt gleich mit den kompliziertesten Automaten an und zeigt 29:58.750 --> 30:01.170 dann auch, dass es einfacher geht an manchen Dingen. 30:01.630 --> 30:04.670 Also er geht einer ganz anderen Art und Weise vor, deswegen ist das 30:04.670 --> 30:07.870 vielleicht interessant als Komplementär oder als Ergänzung zur 30:07.870 --> 30:08.370 Vorlesung. 30:12.630 --> 30:17.990 Außerdem bieten wir Ihnen verschiedene elektronische Spielereien. 30:18.750 --> 30:21.990 Die Aufzeichnung, darauf habe ich ja schon hingewiesen, die Sie sich 30:21.990 --> 30:23.090 aus dem Netz ziehen können. 30:24.010 --> 30:30.530 Wir haben einige Lernmodule zum Selbststudium, also Java-Applets im 30:30.530 --> 30:33.950 Wesentlichen, wo bestimmte Sachverhalte erklärt werden. 30:35.410 --> 30:38.330 Wir sind beteiligt an so einem Verbundprojekt Wissenswerkstatt 30:38.330 --> 30:41.570 Rechensysteme und da sind die eben entstanden und die stellen wir 30:41.570 --> 30:42.610 Ihnen jetzt auch zur Verfügung. 30:42.610 --> 30:47.370 Dann können Sie das einfach selber nochmal ausprobieren, verschiedene 30:47.370 --> 30:48.530 Dinge mit rumspielen. 30:49.790 --> 30:55.790 Teilweise sind diese Module hier am Institut in einem Seminar 30:55.790 --> 30:59.990 entstanden, also von Ihren Kommilitonen und es ist schon ganz 30:59.990 --> 31:02.730 interessant, was dabei rausgekommen ist. 31:02.830 --> 31:08.130 Teilweise sehr ansprechende Applets, um bestimmte Sachverhalte zu 31:08.130 --> 31:08.470 erklären. 31:09.670 --> 31:13.330 Wenn solche Module für unsere Vorlesung speziell relevant werden, dann 31:13.330 --> 31:16.010 werde ich hier darauf hinweisen und Sie finden außerdem einen Link 31:16.010 --> 31:18.050 dann im Netz, wo Sie diese Module finden. 31:19.530 --> 31:24.390 Wir haben ein paar praktische Übungen im Bereich Schaltkreisentwurf. 31:24.910 --> 31:27.810 Das heißt, wir stellen Ihnen hier ein Werkzeug zur Verfügung, mit dem 31:27.810 --> 31:32.410 Sie Schaltkreise zusammen bauen können, zusammen klicken können am 31:32.410 --> 31:35.690 Computer, also da ein Und-Gatter und da ein Ohr-Gatter und die 31:35.690 --> 31:39.290 irgendwie miteinander verbinden und auch dann ausprobieren können, was 31:39.290 --> 31:43.210 das für ein Verhalten hat, wenn bestimmte Eingänge anliegen, was dann 31:43.210 --> 31:47.170 am Ausgang anliegt usw., wo Sie das also simulieren können. 31:48.800 --> 31:51.430 Das wird wahrscheinlich so Anfang Dezember interessant. 31:52.030 --> 31:54.290 Ich werde hier in der Vorlesung darauf hinweisen und Sie finden das 31:54.290 --> 31:54.910 auch im Netz. 31:56.750 --> 32:07.030 Und schließlich haben wir im Rahmen eines anderen Projekts Feedback 32:07.030 --> 32:09.390 -Werkzeuge für große Vorlesungen entwickelt. 32:09.390 --> 32:14.830 So große Vorlesungen sind sehr anonym, es sind sehr viele Studenten, 32:14.890 --> 32:21.310 es ist immer ein gewisser Geräuschpegel und die Idee dieser Feedback 32:21.310 --> 32:28.590 -Werkzeuge ist, dass wenn Sie ein Laptop haben mit WLAN-Zugang oder 32:28.590 --> 32:34.450 ein Palm-Pilot oder ähnliches mit einem Funkzugang, dass Sie sich so 32:34.450 --> 32:37.410 ein Werkzeug runterladen können und dann mir hier Feedback geben 32:37.410 --> 32:37.710 können. 32:37.710 --> 32:43.610 Ist noch nicht ausprobiert worden, aber die große Vorlesung ist sehr 32:43.610 --> 32:46.070 groß und ist daher geeignet, sowas mal auszuprobieren. 32:46.970 --> 32:50.890 Und Feedback wäre beispielsweise, es ist zu schnell oder es ist zu 32:50.890 --> 32:51.370 langsam. 32:51.550 --> 32:55.630 Können Sie dann anklicken und wenn genügend von Ihnen anklicken, dass 32:55.630 --> 33:01.310 es zu schnell ist, dann leuchtet bei mir hier so ein kleines Fenster 33:01.310 --> 33:04.110 auf, dass ich zu schnell bin oder zu langsam und dann kann ich das 33:04.110 --> 33:05.030 entsprechend anpassen. 33:09.190 --> 33:09.710 Okay, 33:13.910 --> 33:17.350 das stelle ich Ihnen in zwei, drei Wochen vor, wenn wir das mal 33:17.350 --> 33:18.550 ausprobieren und einführen. 33:19.570 --> 33:20.950 Ein Versuch ist es wert. 34:01.430 --> 34:06.770 Okay, wenn ich es mir so recht überlege, werde ich meinen Kollegen 34:06.770 --> 34:09.770 bitten, vielleicht da auch noch ein Button einzubauen, das ist zu laut 34:09.770 --> 34:13.150 und dann kann ich vielleicht hier oben draufklicken und dann erscheint 34:13.150 --> 34:15.450 für Sie auf dem Bildschirm, es ist zu laut. 34:17.930 --> 34:22.650 Oder vielleicht könnten Sie das ja selber machen, ein Button für Sie 34:22.650 --> 34:25.590 selber einführen, sodass wenn es einigen von Ihnen zu laut ist, dass 34:25.590 --> 34:29.310 Sie draufklicken können und dann für die anderen erscheint oder darum 34:29.310 --> 34:30.990 gebeten wird, dass es ein bisschen leiser ist. 34:32.010 --> 34:35.910 Okay, wir sind ein Informatikinstitut, deswegen versuchen wir eben 34:35.910 --> 34:41.090 solche innovativen Informatiklösungen auch tatsächlich umzusetzen und 34:41.090 --> 34:43.330 die Lehre vielleicht ein bisschen zu verbessern. 34:44.270 --> 34:48.150 Dann können wir jetzt mit dem ersten Teil der Vorlesung anfangen, 34:48.290 --> 34:50.330 formale Modelle der Informatik. 34:58.390 --> 35:05.450 Ziel dieses Theorieteils ist es, Ihnen abstrakte Modelle für 35:05.450 --> 35:09.130 informationsverarbeitende Systeme ganz allgemein, eben Computer im 35:09.130 --> 35:14.770 Speziellen vorzustellen und auch abstrakte Modelle für 35:14.770 --> 35:15.790 Programmiersprachen. 35:16.710 --> 35:21.010 Und das Ganze hat das Ziel, eben die prinzipiellen Möglichkeiten der 35:21.010 --> 35:24.970 Informationsverarbeitung mithilfe von Computern zu untersuchen. 35:25.670 --> 35:27.770 Also was für Aufgaben kann man überhaupt lösen? 35:27.910 --> 35:28.730 Ich glaube, genau. 35:29.130 --> 35:33.950 Typische Fragestellungen wären dann, mit was für Modellen lässt sich 35:33.950 --> 35:34.950 ein Rechner beschreiben? 35:37.010 --> 35:39.650 Oder welche Eigenschaften haben sinnvolle Programmiersprachen? 35:39.650 --> 35:42.210 Ist Java eine sinnvolle Programmiersprache? 35:42.370 --> 35:46.590 Was für Befehle braucht man in der Programmiersprache, um komplexe 35:46.590 --> 35:47.690 Probleme lösen zu können? 35:48.430 --> 35:52.930 Wie lässt sich ein Programm auf syntaktische Korrektheit überprüfen? 35:57.970 --> 36:02.710 Das wäre der Teil Automatentheorie und Grammatiken und formale 36:02.710 --> 36:03.230 Sprachen. 36:04.810 --> 36:09.070 Und dann geht es noch darum, was ist überhaupt ein Algorithmus? 36:10.710 --> 36:14.170 Welchen Aufwand verursacht eine bestimmte Berechnung? 36:15.730 --> 36:19.510 Haben Sie schon ein bisschen in Informatik 1 die Komplexität von 36:19.510 --> 36:20.500 Programmen kennengelernt? 36:21.950 --> 36:27.630 Was wir uns hier anschauen, ist nicht die Komplexität von Programmen, 36:28.530 --> 36:33.430 das haben Sie eben in Informatik 1 gemacht, sondern die Komplexität 36:33.430 --> 36:35.130 von Problemen. 36:35.430 --> 36:40.250 Wenn ich ein bestimmtes Problem habe, gibt es überhaupt ein Programm, 36:40.470 --> 36:41.910 das dieses Problem berechnen kann? 36:42.470 --> 36:44.290 Das die Lösung zu diesem Problem berechnen kann? 36:46.130 --> 36:50.310 Das schnellste Programm, was ich möglicherweise entwickeln könnte, wie 36:50.310 --> 36:53.730 viel Zeit wird es vermutlich brauchen, um dieses Problem zu lösen? 36:55.630 --> 37:00.030 Also nicht, dass man sich ein bestimmtes Programm anschaut und sagt, 37:00.130 --> 37:03.810 dieses Programm hat Laufzeit, lineare Laufzeit oder quadratische 37:03.810 --> 37:06.970 Laufzeit oder exponentielle Laufzeit, sondern dass man sich das 37:06.970 --> 37:11.470 Problem anschaut und versucht zu beweisen, egal wie clever der 37:11.470 --> 37:15.350 Programmierer ist, er kann kein Programm schreiben, das schneller als 37:15.350 --> 37:17.090 quadratische Laufzeit ist zum Beispiel. 37:18.530 --> 37:20.730 Und eben auch, wo liegen die Grenzen der Berechenbarkeit? 37:20.730 --> 37:24.210 Gibt es Probleme, die überhaupt nicht berechenbar sind? 37:26.290 --> 37:27.730 Das ist dann der Teil Komplexitätstheorie. 37:29.290 --> 37:33.650 Und um das eben alles beantworten zu können, brauchen wir zunächst mal 37:33.650 --> 37:36.470 die Grundlagen Automatentheorie, Grammatiken und so weiter. 37:39.190 --> 37:41.410 Okay, ein paar einfache Beispiele. 37:43.290 --> 37:46.510 Wir schauen uns Automaten an und wir schauen uns Sprachen an. 37:46.510 --> 37:50.530 Zunächst mal, Automate sind sehr allgemeiner Begriff. 37:50.710 --> 37:53.130 Sie alle haben täglich mit Automaten zu tun. 37:54.010 --> 37:58.350 Sei es die Waschmaschine oder sei es ein Geldautomat oder sei es eben 37:58.350 --> 37:59.210 ein Computer. 38:04.920 --> 38:07.280 Sie alle haben auch mit Sprachen zu tun. 38:07.920 --> 38:12.640 Natürliche Sprachen wie Deutsch, Englisch, Französisch oder formale 38:12.640 --> 38:18.040 Sprachen wie Programmiersprachen, C, C++, Java, was immer Sie kennen, 38:19.420 --> 38:24.460 Spezifikationssprachen, UML aus Informatik 1, Anfragesprachen, also 38:24.460 --> 38:27.660 wie stellt man eine Anfrage an die Datenbank. 38:27.800 --> 38:31.020 Da gibt es bestimmte Sprachen, die Ihnen sagen, die Anfrage muss die 38:31.020 --> 38:33.460 und die Syntax haben, damit sie verarbeitet werden kann. 38:34.200 --> 38:40.980 Markup-Sprachen, HTML, also um zu beschreiben, wie das Format im 38:40.980 --> 38:42.140 Internet aussehen soll. 38:46.600 --> 38:49.400 Und wir schauen uns im Prinzip zwei Sachen an. 38:49.500 --> 38:52.440 Das eine ist, wie spezifiziert man solche Sprachen? 38:55.000 --> 38:57.320 Wie spezifiziert man genau eine Syntax? 38:57.600 --> 38:58.840 Wann ist eine Sprache korrekt? 38:58.960 --> 39:00.920 Was darf alles vorkommen in dieser Sprache? 39:02.580 --> 39:06.100 Und das andere ist, wie überprüft man die Korrektheit? 39:06.520 --> 39:08.180 Und das macht man über Automaten. 39:08.180 --> 39:11.160 Also es gibt einmal ein formales System, eine Beschreibung der 39:11.160 --> 39:14.100 Sprache, die sagt, die Sprache ist so und so aufgebaut und das und 39:14.100 --> 39:15.440 das, so sieht die Syntax aus. 39:15.980 --> 39:20.240 Und dann gibt es Automaten, die überprüfen können zu einem bestimmten 39:20.240 --> 39:25.800 Wort oder einem Satz oder was auch immer, ob dieser Wort oder Satz 39:25.800 --> 39:28.400 Teil der Sprache ist und syntaktisch korrekt ist. 39:28.660 --> 39:29.700 Das machen die Automaten. 39:33.310 --> 39:37.930 Das hat zahlreiche Anwendungen, diese Automaten und formalen Sprachen. 39:38.990 --> 39:43.670 Im Software- und Systems Engineering, wenn Sie versuchen, Systeme zu 39:43.670 --> 39:46.570 beschreiben, wenn Sie versuchen zu beschreiben, was macht ein Automat? 39:46.970 --> 39:48.490 Was soll das Software-System machen? 39:48.570 --> 39:51.010 Bei welchen Eingaben muss was rauskommen und so weiter? 39:52.010 --> 39:58.790 Vielleicht auch als noch eine noch genauere und detailliertere, 39:59.030 --> 40:02.030 exaktere Spezifikation, als es in UML gemacht wird. 40:03.190 --> 40:05.870 Schaltwerk-Synthese, das heißt, wenn Sie versuchen wollen, 40:06.050 --> 40:09.790 systematisch digitale Schaltwerke zu erzeugen. 40:09.790 --> 40:14.010 Bei Programmiersprachen ganz naheliegend spielen Sprachen natürlich 40:14.010 --> 40:17.870 eine große Rolle, wenn Sie einen Compiler bauen, der eine Sprache auf 40:17.870 --> 40:21.110 Syntax überprüfen soll, der Ihnen also die Fehler anzeigt. 40:22.010 --> 40:26.270 Bei der Textverarbeitung beispielsweise, wenn Sie auf einer Webseite 40:26.270 --> 40:30.310 oder in einem Text nach einem bestimmten Wort suchen, dann sind die 40:30.310 --> 40:33.250 dahinterstehenden Algorithmen genau solche endlichen Automaten, die 40:33.250 --> 40:35.010 das übernehmen, das werden wir auch noch kennenlernen. 40:35.010 --> 40:40.630 Also es gibt sehr viele praktische Anwendungen auch für diese eher 40:40.630 --> 40:42.290 formalen Dinge, die wir uns hier anschauen. 40:44.150 --> 40:47.230 Okay, was braucht man überhaupt, um eine Sprache zu beschreiben? 40:48.410 --> 40:50.610 Das Grundlegende ist erst einmal die Syntax. 40:50.830 --> 40:56.110 Das sind einfach Regeln, die Ihnen sagen, in welcher Art und Weise Sie 40:56.110 --> 40:59.550 Wörter und Sätze zusammenfügen dürfen und aufbauen können. 41:00.390 --> 41:08.730 Es gibt außerdem die Semantik, die die Bedeutung eines Satzes 41:08.730 --> 41:16.550 bezeichnet und es gibt die Pragmatik, also subjektive Aspekte des 41:16.550 --> 41:21.410 Sprechers oder des Benutzers, wie die Umgebung oder die Zeit, wo je 41:21.410 --> 41:25.830 nachdem, in welcher Umgebung ich bin, derselbe Satz eine andere 41:25.830 --> 41:26.810 Bedeutung haben kann. 41:28.750 --> 41:32.150 Wir beschränken uns in der Vorlesung hier rein auf die Syntax. 41:32.710 --> 41:37.610 Die Semantik ist ebenfalls wichtig, weil die Programmiersprachen 41:37.610 --> 41:41.270 natürlich eine Bedeutung haben, neben einer Syntax. 41:41.810 --> 41:46.370 Das heißt, je nachdem, wie die Semantik der Programmiersprache ist, 41:46.470 --> 41:51.410 könnte dasselbe Programm von einem anderen Compiler übersetzt 41:51.410 --> 41:52.890 unterschiedliche Bedeutung haben. 41:54.930 --> 41:58.050 Aber wir betrachten trotzdem hier jetzt nur die Syntax. 41:58.790 --> 42:02.290 Und die Pragmatik ist für die Kerninformatik eher von geringer 42:02.290 --> 42:02.810 Bedeutung. 42:04.990 --> 42:05.510 Okay. 42:06.970 --> 42:10.250 Um das alles zu beschreiben, muss ich am Anfang erstmal ein paar 42:10.250 --> 42:13.210 grundsätzliche Begriffe und Notationen einführen. 42:14.490 --> 42:16.650 Fangen wir an mit dem Alphabet. 42:19.030 --> 42:24.450 Das Alphabet ist eine endliche, nicht leere Menge von Zeichen. 42:25.470 --> 42:29.050 Also das natürliche Alphabet, die Buchstaben von A bis Z wären eine 42:29.050 --> 42:29.510 Möglichkeit. 42:30.250 --> 42:33.630 Die Zahlen oder die Ziffern von 0 bis 9 sind eine Möglichkeit. 42:34.710 --> 42:37.190 Ein anderes Beispiel für ein Alphabet sind einfach nur die 42:37.190 --> 42:39.730 Binärdarstellung, also 0 oder 1. 42:40.870 --> 42:47.970 Dieses Alphabet können Sie verwenden, um daraus Worte zu erzeugen. 42:49.790 --> 42:59.950 Und ein Wort über einem Alphabet ist eine Folge von Zeichen aus diesem 42:59.950 --> 43:00.330 Alphabet. 43:00.770 --> 43:03.470 Sie schreiben einfach verschiedene Zeichen aus dem Alphabet 43:03.470 --> 43:05.830 hintereinander und dann haben Sie ein Wort. 43:06.650 --> 43:10.470 Beispiele wären hier... Informatik ist ein Wort. 43:11.310 --> 43:14.750 Ich habe einfach erst ein I, dann ein N, dann ein F und so weiter 43:14.750 --> 43:15.850 hintereinander angereiht. 43:16.590 --> 43:22.770 Oder 1, 2, 3 wäre ein Wort über dem Alphabet 0 bis 9. 43:24.270 --> 43:30.230 Und dieses 01001011 ist ein Wort nach unserer Definition über dem 43:30.230 --> 43:31.010 Alphabet 01. 43:32.770 --> 43:36.490 So ein Wort hat eine Länge, in der man einfach die Anzahl der Zeichen 43:36.490 --> 43:48.210 zählt und die Länge wird bezeichnet durch diese zwei senkrechten 43:48.210 --> 43:49.950 Striche, die wir um das Wort herum machen. 43:50.430 --> 43:54.470 Also die Länge von dem Wort Informatik ist 10, die Länge von dem Wort 43:54.470 --> 43:56.870 1, 2, 3 ist 3 und so weiter. 43:57.930 --> 44:02.490 Wir brauchen auch noch ein leeres Wort, kein Leerzeichen. 44:02.970 --> 44:08.610 Ein leeres Wort ist einfach ein Wort der Länge 0, hat also überhaupt 44:08.610 --> 44:09.690 kein Zeichen im Prinzip. 44:10.910 --> 44:16.530 Dann bezeichne A hoch N die Menge der Wörter der Länge N. 44:16.530 --> 44:22.090 Das heißt, wenn wir beispielsweise hier N gleich 3 haben und A das 44:22.090 --> 44:28.010 Alphabet, nur die Nullen und die Einsen, dann wäre A hoch 3 genau 44:28.010 --> 44:32.970 diese Menge von Worten 0000, 001, 010 und so weiter. 44:33.150 --> 44:36.630 Alle möglichen Worte der Länge 3 über diesem Alphabet. 44:38.790 --> 44:44.930 A hoch Stern ist die Menge aller Worte über dem Alphabet. 44:46.010 --> 44:57.940 Das heißt, hier die Vereinigungsmenge, na, das ist irgendwie egal, die 44:57.940 --> 45:01.660 Vereinigungsmenge über alle A hoch N, von N gleich 0 bis unendlich. 45:02.180 --> 45:06.300 Das heißt, es fängt an mit dem leeren Wort Lambda, dann kommen alle 45:06.300 --> 45:10.720 Worte der Länge 1, also die 0 und die 1, dann kommen alle Worte der 45:10.720 --> 45:14.320 Länge 2, 00, 01, 11, 10 und so weiter. 45:17.000 --> 45:22.080 Dann haben wir noch A hoch Plus, das ist die Menge aller nicht leeren 45:22.080 --> 45:33.420 Wörter, also im Prinzip, das ist gleich A hoch Stern ohne Lambda. 45:35.760 --> 45:41.640 Und dann haben wir noch das L, L bezeichnet immer eine Sprache über 45:41.640 --> 45:47.380 einem bestimmten Alphabet, das heißt, eine Sprache ist eine Teilmenge 45:47.380 --> 45:49.640 aller möglichen Worte über einem Alphabet. 45:54.850 --> 46:01.710 Hier ist ein Beispiel, die Sprache aller Worte über dem Alphabet 01, 46:02.030 --> 46:07.890 also Element 01 Stern, mit der Bedingung, die Anzahl der Einsen in dem 46:07.890 --> 46:08.790 Wort ist gerade. 46:10.010 --> 46:13.330 Das sind jetzt nicht mehr alle möglichen Worte über dem Alphabet 01, 46:13.750 --> 46:17.430 sondern eben nur noch eine Teilmenge und diese Teilmenge bezeichnen 46:17.430 --> 46:18.210 wir als Sprache. 46:29.070 --> 46:34.030 Okay, es gibt drei Möglichkeiten, so eine Sprache zu beschreiben. 46:35.070 --> 46:41.010 Die eine ist erzeugend, das heißt, ich gebe Regeln an, mit denen ich 46:41.010 --> 46:44.570 alle Worte dieser Sprache erzeugen kann. 46:45.670 --> 46:49.050 Und alles, was ich nicht durch diese Regeln erzeugen kann, gehört 46:49.050 --> 46:52.610 nicht zur Sprache und alles, was ich dazu erzeugen kann, gehört zur 46:52.610 --> 46:53.010 Sprache. 46:54.130 --> 46:57.370 Die zweite Möglichkeit ist analysierend. 47:02.190 --> 47:06.430 Also wenn mir jemand ein Wort gibt, dann gebe ich das einfach diesem 47:06.430 --> 47:11.890 analysierenden System und dieses System oder dieser Automat spuckt mir 47:11.890 --> 47:15.550 dann aus, dieses Wort gehört dazu oder es gehört nicht dazu. 47:15.550 --> 47:19.110 Und dann kann ich die Sprache beschreiben, indem ich einfach diesen 47:19.110 --> 47:22.610 Automaten beschreibe und dann muss ich einfach für jedes mögliche Wort 47:22.610 --> 47:24.890 gucken, es gehört dazu oder es gehört nicht dazu. 47:25.350 --> 47:29.030 Der Automat beschreibt dann meine Sprache. 47:30.550 --> 47:35.050 Oder ich kann die Sprache beschreiben operationell durch einen Term 47:35.050 --> 47:37.550 aus Basismengen und Operationen. 47:37.550 --> 47:43.310 Also wir werden Beispiele für alle diese drei Dinge kennenlernen. 47:44.050 --> 47:47.970 Erzeugend, das wären die Grammatiken, analysierend, das wären die 47:47.970 --> 47:53.630 Automaten und operationell, das sind reguläre Ausdrücke. 47:55.190 --> 47:59.530 Und wir schauen uns dann das Zusammenspiel an zwischen erzeugenden und 47:59.530 --> 48:00.630 analysierenden Systemen. 48:01.870 --> 48:08.070 Was für Automaten, wie müssen die Automaten aussehen, um die Sprache 48:08.070 --> 48:11.450 zu erkennen, die von bestimmten Grammatiken definiert wird und 48:11.450 --> 48:12.070 umgekehrt. 48:16.670 --> 48:17.290 Okay. 48:18.910 --> 48:27.250 Für die Sprachen gibt es eine grundlegende Hierarchie, die sogenannte 48:27.250 --> 48:31.270 Chomsky -Hierarchie von einem Herrn Chomsky entwickelt. 48:32.350 --> 48:35.490 Ich habe da noch so ein Bild von ihm reingemacht, er lehrt wohl immer 48:35.490 --> 48:36.230 noch am MIT. 48:38.230 --> 48:43.430 Die Chomsky-Hierarchie, die einfach definiert, wie solche Sprachen, 48:43.710 --> 48:49.670 also die Regelsysteme im Prinzip definiert und auch klassifiziert in 48:49.670 --> 48:50.570 der Hierarchie. 48:51.630 --> 48:54.690 Als einführendes Beispiel, was Ihnen vielleicht bekannt ist, eine 48:54.690 --> 48:56.010 Dibakus -Nauer-Form. 48:57.010 --> 49:00.790 Die wird verwendet, um die Syntax von Programmiersprachen zu 49:00.790 --> 49:01.310 beschreiben. 49:02.190 --> 49:07.010 Und hier in diesem Beispiel schauen wir uns an, wie Namen oder 49:07.010 --> 49:09.830 Bezeichner in höheren Programmiersprachen aussehen dürfen. 49:10.770 --> 49:15.230 Und ein typisches Beispiel wäre eben, ein Name darf sich 49:15.230 --> 49:21.190 zusammensetzen aus einem Buchstaben und danach dürfen noch beliebig 49:21.190 --> 49:23.770 viele Buchstaben oder Ziffern infolge kommen. 49:26.310 --> 49:30.610 So wäre diese Dibakus-Nauer-Form oder diese Regel hier zu beschreiben. 49:31.750 --> 49:34.210 Jetzt muss man natürlich noch wissen, was ist ein Buchstabe? 49:34.950 --> 49:38.250 Okay, ein Buchstabe ist entweder ein A oder ein B oder ein C und so 49:38.250 --> 49:38.510 weiter. 49:39.230 --> 49:42.470 Und eine Ziffer ist entweder eine 0 oder eine 1 oder eine 2 und so 49:42.470 --> 49:42.730 weiter. 49:45.170 --> 49:51.110 Dadurch hätte ich jetzt definiert, welche Namen oder Bezeichner in der 49:51.110 --> 49:53.690 Programmiersprache gültig sind und welche nicht gültig sind. 49:54.610 --> 50:00.050 Nicht gültig sind beispielsweise alle, die mit einer Ziffer anfangen. 50:00.950 --> 50:05.030 Denn hier in dieser Regel ist eindeutig definiert, dass der Name mit 50:05.030 --> 50:08.870 einem Buchstaben anfängt und erst danach Ziffern kommen dürfen. 50:10.490 --> 50:14.910 Nicht gültig wäre auch beispielsweise ein Name, der ein Sonderzeichen 50:14.910 --> 50:18.310 enthält, weil ein Name sich nur aus Buchstaben und Ziffern 50:18.310 --> 50:19.390 zusammensetzen darf. 50:20.430 --> 50:27.830 Das wäre also so ein Beispiel für eine Art Grammatik, für ein System, 50:27.970 --> 50:33.110 wie man Namen, Bezeichner erzeugen kann und damit eine Sprache 50:33.110 --> 50:33.670 beschreibt. 50:35.510 --> 50:38.510 Dabei gibt es jetzt zwei wesentliche Begriffe. 50:39.910 --> 50:42.090 Wir haben einmal hier Non-Terminal-Symbole. 50:42.930 --> 50:45.130 Dazu gehört Name, Buchstabe und Ziffer. 50:45.130 --> 50:50.010 Im Prinzip sind das Variablen, die wieder ersetzt werden. 50:53.070 --> 50:56.050 Und wir haben Terminal-Symbole. 50:56.610 --> 50:59.910 Das sind dann die atomaren, letztendlichen Bestandteile, die nicht 50:59.910 --> 51:01.170 weiter ersetzt werden können. 51:01.550 --> 51:05.670 Wie hier die Buchstaben ABC oder die Ziffern 019. 51:07.150 --> 51:11.330 Alle Non-Terminal-Symbole muss ich beschreiben, wie ich die weiter 51:11.330 --> 51:14.590 ersetzen kann und alle Terminal-Symbole sind dann erledigt. 51:15.870 --> 51:22.090 Ich habe mein Wort erzeugt, wenn ich nur noch Terminal-Symbole habe, 51:22.170 --> 51:23.390 kann ich nichts weiter ersetzen. 51:24.630 --> 51:28.590 Ich habe in der Bacchus-Mauer-Form noch ein paar zusätzliche Symbole. 51:29.350 --> 51:33.070 Da habe ich dieses Doppel-Punkt-Doppel-Punkt-Gleich, das die 51:33.070 --> 51:35.070 Möglichkeit der Überführung anzeigt. 51:35.370 --> 51:39.210 Dann habe ich hier ein Sonderzeichen, den senkrechten Strich, Auswahl 51:39.210 --> 51:40.530 unter mehreren Alternativen. 51:40.690 --> 51:43.690 Also ich kann hier ein Buchstaben oder eine Ziffer wählen. 51:44.590 --> 51:48.110 Und ich habe hier die geschweiften Klammern, die mir sagen, alles was 51:48.110 --> 51:50.590 in geschweiften Klammern ist, darf ich beliebig oft wiederholen. 51:52.830 --> 51:56.430 So, das wäre ein Ihnen vielleicht bekanntes Beispiel gewesen. 52:00.410 --> 52:04.630 Die Chomsky-Hierarchie oder der Herr Chomsky hat eben versucht, so 52:04.630 --> 52:08.630 eine Grammatik noch allgemeiner zu spezifizieren, wie überhaupt sowas 52:08.630 --> 52:09.410 aussehen kann. 52:10.570 --> 52:14.930 Und was hier eben auftaucht, ist wieder die Menge der Non 52:14.930 --> 52:17.950 -Terminalsymbole und 52:22.200 --> 52:23.920 die Menge der Terminalsymbole. 52:25.040 --> 52:28.300 Eben einmal die Variablen und die Konstanten. 52:29.660 --> 52:34.080 Die bezeichnen wir jetzt hier jeweils als n mit n und t für Non 52:34.080 --> 52:35.640 -Terminal - und Terminalsymbole. 52:35.640 --> 52:38.300 Und dann haben wir noch die Regeln. 52:40.340 --> 52:49.700 Eine Regel ist eine Teilmenge aus Abbildungen von n vereinigt mit t. 52:50.260 --> 52:53.760 Also wir haben auf der linken Seite stehen irgendwelche Non-Terminale 52:53.760 --> 52:54.640 und Terminalsymbole. 52:57.800 --> 52:59.200 Und rechts auch. 53:02.560 --> 53:05.700 Zum Beispiel, also phi nach psi. 53:06.700 --> 53:13.640 Und phi ist irgendetwas aus dieser Menge n vereinigt t plus. 53:14.260 --> 53:16.500 Und psi ist irgendwas aus n vereinigt t Stern. 53:17.780 --> 53:19.400 Und wir brauchen dann noch ein Startsymbol. 53:19.920 --> 53:21.360 Warum brauchen wir dieses Startsymbol? 53:21.980 --> 53:25.140 Weil wir, dieses Regelsystem ist erzeugend. 53:25.440 --> 53:28.740 Wir fangen mit irgendeinem Symbol an und können dann diese Regeln 53:28.740 --> 53:30.520 anwenden, um alles mögliche zu erzeugen. 53:31.240 --> 53:34.260 Und dieses irgendwas, mit dem wir anfangen, ist eben dieses definierte 53:34.260 --> 53:35.280 Startsymbol s. 53:37.060 --> 53:39.500 n, t und p sind jeweils endlich und nicht leer. 53:40.040 --> 53:40.220 Gut. 53:42.640 --> 53:42.980 Okay. 53:43.700 --> 53:46.700 Das war also die Idee, wie der Herr Komsky eine Grammatik beschrieben 53:46.700 --> 53:47.000 hat. 53:48.720 --> 53:52.260 Jetzt schauen wir uns an, ob diese Bacchus-Nauer-Form, die wir schon 53:52.260 --> 53:54.040 kennengelernt haben, da reinpasst. 53:55.140 --> 53:55.480 Okay. 53:55.480 --> 53:58.640 Wir haben schon gesehen, dass wir in der Bacchus-Nauer-Form auch Non 53:58.640 --> 54:00.780 -Terminalsymbole und Terminalsymbole haben. 54:01.200 --> 54:02.960 Das heißt, die können wir einfach so auslisten. 54:04.480 --> 54:06.480 Unser Startsymbol ist Name. 54:09.040 --> 54:14.760 Und wir können jetzt verschiedene Regeln spezifizieren, die im Prinzip 54:14.760 --> 54:18.440 genau das gleiche tun, wie was in der Bacchus-Nauer-Form spezifiziert 54:18.440 --> 54:18.680 war. 54:19.740 --> 54:23.460 Wir können den Namen ersetzen durch einen Buchstaben. 54:24.200 --> 54:28.040 Oder wir können den Namen ersetzen durch einen Namen und anschließend 54:28.040 --> 54:28.740 einen Buchstaben. 54:29.660 --> 54:32.980 Oder den Namen ersetzen durch Name und Ziffer. 54:35.420 --> 54:40.080 Und wir können anschließend das Buchstabenvariable ersetzen durch eine 54:40.080 --> 54:41.460 konkrete Buchstabenkonstante. 54:42.740 --> 54:45.240 Oder eine Ziffer durch eben eine konkrete Ziffer. 54:47.820 --> 54:50.040 Ich glaube, wir machen nachher noch ein Beispiel dazu. 54:53.000 --> 54:58.460 Okay, jetzt nehmen wir mal an, wir hätten so eine Regelmenge P 54:58.460 --> 54:58.980 gegeben. 55:01.480 --> 55:10.020 Und zwei Worte, bestehend aus Non-Terminal- und Terminalsymbolen. 55:10.280 --> 55:15.660 Dann heißt V durch P unmittelbar überführbar in W. 55:16.820 --> 55:20.200 Und das schreibt man eben so. 55:22.980 --> 55:24.140 Genau dann, 55:28.750 --> 55:42.830 wenn sich dieses V schreiben lässt, in drei Teile, U, Phi, Z. 55:43.390 --> 55:46.490 Und das W lässt sich schreiben als U, Psi, Z. 55:48.110 --> 55:53.650 Also das U und das Phi und das Z sind jetzt nur Platzhalter für Teile 55:53.650 --> 55:54.290 des Wortes. 55:55.530 --> 55:58.050 Gucken wir uns am besten ein Beispiel an. 55:59.570 --> 56:01.490 Sagen wir, das V... 56:04.140 --> 56:07.020 Okay, das Schreiben braucht noch etwas Übung. 56:08.940 --> 56:18.940 Das V wäre ein Wort, das würde bestehen aus A, B, S, B, A. 56:20.900 --> 56:36.800 Und das W wäre ein anderes Wort, beispielsweise A, B, B, B, A. 56:39.340 --> 56:43.500 Bestehend aus Terminalsymbolen und Non-Terminalsymbolen. 56:43.760 --> 56:46.900 Dann könnte ich jetzt dieses Wort in Teile unterteilen. 56:47.920 --> 56:55.390 Also ich könnte beispielsweise sagen, das hier ist U und das hier ist 56:55.390 --> 56:56.170 Z. 57:02.980 --> 57:04.780 Und dann wäre dieses Mittelteil eben Phi. 57:07.220 --> 57:09.440 Und genau das gleiche kann ich hier auch machen. 57:10.430 --> 57:12.340 U, Z. 57:13.620 --> 57:14.940 Und das wäre das Psi. 57:18.410 --> 57:23.890 Und wenn jetzt S eine Regel von Phi nach Psi gibt, in unserem Fall 57:23.890 --> 57:30.090 also eine Regel S nach B. 57:31.510 --> 57:35.410 Dann könnten wir das Wort V in W überführen. 57:36.330 --> 57:40.370 Indem wir nämlich einfach in diesem Wort das S durch ein B ersetzen. 57:41.190 --> 57:43.390 Und dann kommen wir von V nach W. 57:47.570 --> 57:48.190 Okay. 57:48.830 --> 57:50.850 Jetzt schauen wir uns die Definition nochmal genau an. 57:51.410 --> 57:56.610 V heißt unmittelbar überführbar in W, genau dann, wenn es eine 57:56.610 --> 58:02.850 Verlegung gibt im Prinzip, so dass U und Z Element n vereinigt t Stern 58:02.850 --> 58:03.190 ist. 58:03.190 --> 58:09.590 Also einfach, das sind Teilworte über dem Alphabet Non-Terminal 58:09.590 --> 58:11.350 -Symbole und Terminal-Symbole. 58:12.730 --> 58:19.310 Und es gibt eine Regel Phi nach Psi, so dass wenn ich die zusammenfüge 58:19.310 --> 58:23.590 und ich habe das V kann ich darstellen als U, dann Phi, dann Z. 58:24.750 --> 58:27.930 Und das W kann ich darstellen als U, Psi, Z. 58:31.150 --> 58:35.810 Dann kann ich das genau machen, dann kann ich das U und das Z bleiben 58:35.810 --> 58:36.040 unverändert. 58:37.250 --> 58:40.970 Und das Phi ersetze ich durch das Psi entsprechend der Regel, dann 58:40.970 --> 58:43.150 habe ich das Wort V in das Wort W überführt. 58:46.070 --> 58:50.550 Diese Regel Phi nach Psi ist dann anwendbar auf V. 58:52.650 --> 58:55.950 Also die ist immer dann anwendbar im Prinzip, naja gut, da kommen wir 58:55.950 --> 58:56.530 gleich noch drauf. 58:57.910 --> 59:01.630 Okay, das war also die unmittelbare Überführbarkeit. 59:02.210 --> 59:04.910 Jetzt wollen wir aber auch noch, interessieren uns natürlich auch 59:04.910 --> 59:07.550 Überführungen über mehrere Schritte hinweg. 59:10.730 --> 59:16.050 Und dieses Zeichen, dieser Doppelpfeil mit dem Stern dran, bezeichnet 59:16.050 --> 59:21.270 reflexiv -transitive Hülle von dieser direkten Überführbarkeit. 59:22.810 --> 59:30.810 Reflexiv-transitive Hülle, das heißt die kleinste Relation, die 59:30.810 --> 59:34.370 reflexiv und transitiv ist und die trotzdem die ursprüngliche Relation 59:34.370 --> 59:35.310 enthält. 59:35.870 --> 59:37.570 Ich mache dazu mal noch ein Beispiel. 59:39.310 --> 59:49.430 Wenn wir wissen, dass folgende Überführungen möglich sind. 59:52.880 --> 59:54.620 Und von mir aus auch noch. 59:56.360 --> 01:00:08.620 Also wir hätten hier diese Relation Überführbarkeit und wir können A 01:00:08.620 --> 01:00:13.060 nach B überführen, B nach C, C nach D und von mir aus noch B nach D. 01:00:15.840 --> 01:00:20.600 Dann wäre die reflexiv-transitive Hülle, würde alle zusätzlichen 01:00:20.600 --> 01:00:23.960 Überführungen enthalten, die reflexiv und transitiv sind. 01:00:24.460 --> 01:00:30.620 Das heißt, wir hätten zusätzlich die reflexiven, also aus C kann ich 01:00:30.620 --> 01:00:35.460 natürlich nach C überführen und wir hätten die transitiven. 01:00:36.020 --> 01:00:40.960 Transitiv heißt, wenn A nach B und B nach C, dann muss auch A nach C 01:00:40.960 --> 01:00:41.420 gelten. 01:00:43.060 --> 01:00:46.680 Das heißt, wir haben hier ein paar zusätzliche Pfeile einfach und das 01:00:46.680 --> 01:00:47.660 war es glaube ich schon. 01:00:49.240 --> 01:00:53.160 Das wäre die reflexiv-transitive Hülle, das heißt einfach nur alle 01:00:53.160 --> 01:00:57.860 Überführungen, die über mehrere Schritte möglich sind, sind da jetzt 01:00:57.860 --> 01:00:59.020 mit zusammengefasst. 01:01:03.200 --> 01:01:10.240 Wenn V über diese reflexiv-transitive Hülle nach W überführbar ist, 01:01:10.240 --> 01:01:15.060 dann heißt einfach V überführbar in W, beziehungsweise umgekehrt W ist 01:01:15.060 --> 01:01:16.540 ableitbar aus V. 01:01:20.970 --> 01:01:26.730 Dieses P, das für das Regelsystem steht, das werden wir in Zukunft 01:01:26.730 --> 01:01:29.770 meistens weglassen, weil das aus dem Kontext ersichtlich ist. 01:01:30.310 --> 01:01:32.850 Das heißt, wir schreiben nur noch diesen Doppelpfeil für die direkte 01:01:32.850 --> 01:01:38.590 Überführbarkeit und den Doppelpfeil mit Stern für die Überführbarkeit, 01:01:38.770 --> 01:01:41.130 die eben auch über mehrere Schritte. 01:01:45.090 --> 01:01:45.710 Okay. 01:01:48.490 --> 01:01:52.410 Was ist denn die Sprache einer Chomsky-Hierarchie oder einer Chomsky 01:01:52.410 --> 01:01:52.990 -Grammatik? 01:01:53.790 --> 01:01:57.670 Für eine Chomsky-Grammatik, die definiert ist, wie wir es gerade eben 01:01:57.670 --> 01:02:00.350 gesehen haben, durch eine Menge von Non-Terminalsymbolen, von 01:02:00.350 --> 01:02:06.830 Terminalsymbolen, durch das Regelsystem P und das Startsymbol S, ist 01:02:06.830 --> 01:02:14.170 die Sprache dieser Grammatik alle Worte aus der Menge der 01:02:14.170 --> 01:02:19.190 Terminalsymbole, also die nicht mehr weiter verändert werden können, 01:02:20.110 --> 01:02:22.930 für die Terminalsymbole, die hören ja auf, die kann ich nicht mehr 01:02:22.930 --> 01:02:29.490 weiter ersetzen, so dass gilt, ich kann das S nach W überführen. 01:02:30.150 --> 01:02:33.590 Oder ich kann dieses Wort aus dem Startsymbol unter Anwendung dieser 01:02:33.590 --> 01:02:34.670 Regeln ableiten. 01:02:36.070 --> 01:02:40.850 Das ist dann die erzeugte Sprache, schreiben wir so als L von G. 01:02:44.750 --> 01:02:45.150 Okay. 01:02:47.090 --> 01:02:50.750 Manchmal kann eben so eine Ableitung über mehrere Schritte erfolgen, 01:02:51.210 --> 01:02:53.490 diese Schritte nennen wir dann Ableitungsfolge. 01:02:55.270 --> 01:02:59.890 Und hier haben wir nochmal ein Beispiel, diese Bacchus-Nauer-Form, die 01:02:59.890 --> 01:03:03.170 wir jetzt geschrieben haben in Art einer Chomsky-Grammatik. 01:03:05.490 --> 01:03:11.710 Eine mögliche Ableitung wäre, wir fangen mit unserem Startsymbol an, 01:03:12.970 --> 01:03:19.890 haben also hier unseren Namen, ersetzen diesen Namen durch Name und 01:03:19.890 --> 01:03:20.250 Ziffer. 01:03:24.370 --> 01:03:31.010 Okay, dann ersetzen wir hier wieder den Namen durch Name und Ziffer. 01:03:34.590 --> 01:03:37.350 Vielleicht nummerieren wir die Regeln mal durch. 01:03:38.650 --> 01:03:44.170 Haben wir hier 1, 2, 3, 4... 01:03:45.010 --> 01:03:46.630 Okay, die ersten sind wichtig. 01:03:47.130 --> 01:03:52.170 Also hier haben wir Regel 3 angewandt. 01:03:52.910 --> 01:03:56.030 Hier haben wir nochmal Regel 3 angewandt, um daher zu kommen. 01:03:58.270 --> 01:04:01.810 Jetzt haben wir hier den Namen ersetzt durch Buchstabe. 01:04:04.450 --> 01:04:08.870 Namen ersetzt durch Buchstabe, das heißt, das wäre Regel 1. 01:04:10.210 --> 01:04:13.770 Hier haben wir die Ziffer ersetzt durch eine 2. 01:04:15.530 --> 01:04:18.170 Hier haben wir diese Ziffer ersetzt durch eine 1. 01:04:18.290 --> 01:04:21.030 Und hier haben wir diesen Buchstaben ersetzt durch ein A. 01:04:21.230 --> 01:04:22.950 Das heißt, dieses hier wäre Regel 4. 01:04:23.870 --> 01:04:27.650 Ich habe nicht alle durchnummeriert, aber da ist eigentlich trivial. 01:04:28.770 --> 01:04:32.170 Okay, das heißt, durch sukzessive Anwendung dieser verschiedenen 01:04:32.170 --> 01:04:40.030 Regeln, haben wir aus dem Startsymbol Name die Zeichenfolge A1, 2 01:04:40.030 --> 01:04:40.890 generiert. 01:04:41.950 --> 01:04:46.250 Und weil wir diese Zeichenfolge generieren konnten, können wir sagen, 01:04:46.650 --> 01:04:51.030 A1, 2 gehört zur Sprache dieser Grammatik, beziehungsweise das ist ein 01:04:51.030 --> 01:04:56.230 korrekter Bezeichner, entsprechend der Bakusnauer Form. 01:04:58.090 --> 01:05:01.110 Fängt mit einem Buchstaben an, enthält keine Sonderzeichen und so 01:05:01.110 --> 01:05:01.390 weiter. 01:05:10.850 --> 01:05:18.730 Okay, einfach um uns die Kommunikation zu vereinfachen, machen wir 01:05:18.730 --> 01:05:19.470 bestimmte Vereinbarungen. 01:05:20.230 --> 01:05:23.990 Die Non-Terminalsymbole, die also weiter ersetzt werden, die Variablen 01:05:23.990 --> 01:05:28.170 im Prinzip, bezeichnen wir meistens mit großen lateinischen 01:05:28.170 --> 01:05:32.910 Buchstaben, also etwa Groß A, Groß B, Groß S für das Startsymbol und 01:05:32.910 --> 01:05:33.310 so weiter. 01:05:34.610 --> 01:05:40.130 Und die Terminalsymbole meist mit kleinen lateinischen Buchstaben oder 01:05:40.130 --> 01:05:43.950 mit nur eins, je nachdem, was für ein Alphabet wir eben betrachten. 01:05:45.590 --> 01:05:47.530 Das wäre dann klein a, b, c und so weiter. 01:05:49.550 --> 01:05:56.710 Wörter, typische Bezeichnungen für Wörter werden u, v, w oder auch 01:05:56.710 --> 01:06:00.590 griechische Buchstaben wie phi, psi, pi und so weiter. 01:06:07.510 --> 01:06:10.410 Okay, dann wollen wir uns noch ein bisschen vereinfachen. 01:06:12.230 --> 01:06:15.550 Wir haben vorhin schon gesehen, dass entstehen dann sehr, sehr viele 01:06:15.550 --> 01:06:16.330 solche Regeln. 01:06:17.090 --> 01:06:20.590 Ich kann phi ersetzen durch psi 1, ich kann phi ersetzen durch psi 2 01:06:20.590 --> 01:06:21.210 und so weiter. 01:06:21.990 --> 01:06:24.610 Da wollen wir uns ein bisschen Schreibarbeit sparen und wir schreiben 01:06:24.610 --> 01:06:29.690 sowas jetzt einfach als phi kann ersetzt werden durch entweder psi 1 01:06:29.690 --> 01:06:34.210 oder psi 2 oder psi 3 und so weiter. 01:06:42.910 --> 01:06:46.890 Okay, das war also die Definition, die grundlegende Definition von so 01:06:46.890 --> 01:06:48.190 einer Chomsky Grammatik. 01:06:48.950 --> 01:06:51.890 Die ist sehr allgemein, also wir haben gesehen, die Bakus-Nauer-Form 01:06:51.890 --> 01:06:53.210 passt da zum Beispiel rein. 01:06:54.030 --> 01:06:56.310 Ich kann damit sehr, sehr viele beschreiben. 01:06:56.430 --> 01:06:59.110 Ich habe ja nur solche Regeln, ersetze das eine durch was anderes. 01:07:00.270 --> 01:07:04.610 Die Problematik ist, dass man im Allgemeinen nicht algorithmisch 01:07:04.610 --> 01:07:10.050 entscheiden kann, ob jetzt so ein Wort zu der Sprache gehört, ob ich 01:07:10.050 --> 01:07:14.330 also einen Ableitungsbaum finden kann, der mir aus meinem Startsymbol 01:07:14.330 --> 01:07:16.410 das entsprechende Wort erzeugt oder nicht. 01:07:19.810 --> 01:07:25.890 Und das ist sehr unschön, weil das heißt auch, dass wir die nicht auf 01:07:25.890 --> 01:07:28.410 korrektes Syntax überprüfen können automatisch. 01:07:28.410 --> 01:07:33.030 Wenn es keinen Algorithmus gibt, der sowas entscheidet, dann kann ich 01:07:33.030 --> 01:07:37.150 auch nie wissen, ob jetzt mein Wort zur Sprache gehört oder nicht. 01:07:40.170 --> 01:07:44.030 Das hat dazu geführt, dass man eben verschiedene Grammatiktypen 01:07:44.030 --> 01:07:46.750 eingeführt hat, die unterschiedlich mächtig sind. 01:07:47.010 --> 01:07:48.910 Und das ist eben diese Chomsky-Hierarchie. 01:07:54.150 --> 01:07:57.210 Und das sind hier diese vier verschiedenen Typen. 01:07:57.850 --> 01:08:02.950 Wir haben einmal nach wie vor die Typ-0-Grammatik, die ganz allgemeine 01:08:02.950 --> 01:08:07.750 Chomsky -Grammatik, die genauso definiert ist, wie wir es vorhin schon 01:08:07.750 --> 01:08:11.750 gesehen haben, wo ich beliebige Regeln im Prinzip habe, darf die das 01:08:11.750 --> 01:08:13.090 eine durch das andere ersetzen. 01:08:14.870 --> 01:08:17.710 Und wir haben jetzt immer stärkere Einschränkungen. 01:08:18.810 --> 01:08:21.990 Die erste Einschränkung, die wir machen, ist die Typ-1-Grammatik. 01:08:21.990 --> 01:08:27.210 Die heißt auch kontextsensitive Grammatik oder monotone Grammatik. 01:08:27.890 --> 01:08:34.370 Und die sagt, okay, Produktionen, also Regeln, dürfen jetzt nur noch 01:08:34.370 --> 01:08:37.450 in folgender Form sein. 01:08:39.770 --> 01:08:42.850 Ich habe hier auf der linken Seite ein Wort stehen. 01:08:43.550 --> 01:08:50.690 Da steht irgendein Teilwort V1, dann ein Non-Terminal-Symbol A und ein 01:08:50.690 --> 01:08:51.570 Teilwort V2. 01:08:53.150 --> 01:08:55.670 Und ich darf jetzt diese Regel anwenden. 01:08:55.890 --> 01:08:58.810 Ich darf das A ersetzen durch ein Psi. 01:09:04.200 --> 01:09:07.320 Das A ist, wie gesagt, ein einzelnes Non-Terminal-Symbol. 01:09:07.480 --> 01:09:10.620 Das heißt, ich kann nur ein einzelnes Symbol ersetzen, nicht mehr 01:09:10.620 --> 01:09:11.180 beliebige. 01:09:13.200 --> 01:09:17.600 Und ich darf das eben nur tun, wenn dieses Symbol in einem gewissen 01:09:17.600 --> 01:09:18.480 Kontext steht. 01:09:18.480 --> 01:09:23.200 Wenn links und rechts bestimmte Dinge stehen, die ich spezifiziert 01:09:23.200 --> 01:09:25.300 habe durch dieses V1 und das V2. 01:09:25.940 --> 01:09:29.560 Deswegen heißt diese Grammatik eben kontextsensitiv, weil die 01:09:29.560 --> 01:09:33.580 Ersetzungen nur erlaubt, wenn links und rechts ein bestimmter Kontext 01:09:33.580 --> 01:09:34.040 da ist. 01:09:36.040 --> 01:09:43.720 Diese V1, V2 und das Psi sind aus N vereinigt T, also Non-Terminal- 01:09:43.720 --> 01:09:45.440 oder Terminal-Symbole, das ist egal. 01:09:45.440 --> 01:09:47.540 Und es dürfen auch mehrere sein. 01:09:48.440 --> 01:09:53.520 Eine Einschränkung gilt, das Psi darf nicht gleich Lambda sein. 01:09:55.180 --> 01:10:02.440 Der Grund ist, auch warum das monotone Grammatik genannt wird, man 01:10:02.440 --> 01:10:05.080 möchte vermeiden, dass die Wörter kürzer werden. 01:10:06.220 --> 01:10:09.540 Also man erlaubt nur Ersetzungen, wenn das Wort dadurch immer länger 01:10:09.540 --> 01:10:11.020 und länger und länger und länger wird. 01:10:12.660 --> 01:10:15.040 Mit einer einzigen Ausnahme. 01:10:15.940 --> 01:10:24.800 Und die eine Ausnahme ist, zusätzlich darf die Regel vom Startsymbol 01:10:24.800 --> 01:10:28.460 direkt zum leeren Wort enthalten sein. 01:10:29.640 --> 01:10:33.480 Aber ansonsten darf ich das Wort immer nur noch länger machen. 01:10:35.680 --> 01:10:36.160 Okay. 01:10:37.860 --> 01:10:41.400 Wir werden sehen, warum diese Einschränkungen Sinn machen und wie sich 01:10:41.400 --> 01:10:45.000 diese Einschränkungen, also was sie für einen Einfluss haben auf die 01:10:45.000 --> 01:10:46.120 Mächtigkeit der Sprache. 01:10:46.200 --> 01:10:49.160 Was ich damit beschreiben kann, was ich damit nicht mehr beschreiben 01:10:49.160 --> 01:10:52.060 kann, was ich algorithmisch erkennen kann und was nicht. 01:10:53.000 --> 01:10:55.880 Aber ich stelle jetzt diese verschiedenen eben erstmal vor. 01:10:57.020 --> 01:11:00.700 Die nächste Einschränkung, die wir uns anschauen, wären die Typ 2 01:11:00.700 --> 01:11:01.360 Grammatiken. 01:11:03.020 --> 01:11:05.130 Oder auch kontextfreie Grammatiken. 01:11:06.920 --> 01:11:13.560 Und hier haben alle Regeln die Form A nach C. 01:11:16.220 --> 01:11:21.000 Im Prinzip ganz ähnlich wie hier bei der kontextsensitiven Grammatik, 01:11:21.140 --> 01:11:24.000 aber ich darf die Ersetzung immer vornehmen. 01:11:24.820 --> 01:11:26.180 Unabhängig vom Kontext. 01:11:26.640 --> 01:11:28.280 Deswegen kontextfrei. 01:11:31.020 --> 01:11:34.840 Und das Psi hat keine Einschränkung mehr. 01:11:35.240 --> 01:11:36.620 Es darf auch ein Lambda sein. 01:11:38.320 --> 01:11:41.940 Das heißt, ich kann das Wort auch verkürzen. 01:11:43.040 --> 01:11:44.540 Dann ist es allerdings auch zu Ende. 01:11:48.560 --> 01:11:49.120 Gut. 01:11:51.200 --> 01:11:53.740 Und schließlich haben wir noch die Typ 3 Grammatiken, die sind am 01:11:53.740 --> 01:11:54.520 weitesten eingeschränkt. 01:11:59.040 --> 01:12:04.100 Da habe ich im Prinzip nur drei mögliche Regeln. 01:12:04.920 --> 01:12:08.120 Die eine Regel ist, entweder ich ersetze mein Non-Terminal-Symbol 01:12:08.120 --> 01:12:09.220 durch das leere Wort. 01:12:10.420 --> 01:12:15.140 Oder ich ersetze mein Non-Terminal-Symbol durch genau ein Terminal 01:12:15.140 --> 01:12:15.580 -Symbol. 01:12:16.580 --> 01:12:22.980 Oder ich ersetze mein Non-Terminal-Symbol durch genau ein Terminal 01:12:22.980 --> 01:12:25.480 -Symbol und ein Non-Terminal-Symbol. 01:12:25.480 --> 01:12:28.700 Und das Non-Terminal-Symbol steht rechts. 01:12:29.360 --> 01:12:31.560 Deswegen rechtslineare Grammatik. 01:12:32.280 --> 01:12:35.080 Also alles, was ich mit dieser Grammatik im Prinzip machen kann, ist, 01:12:35.160 --> 01:12:36.160 dass ich mein Wort habe. 01:12:38.280 --> 01:12:42.220 Und zwangsläufig steht das Non-Terminal-Symbol immer ganz rechts. 01:12:42.660 --> 01:12:46.500 Ich kann also nur entweder hinten immer was anfügen oder abbrechen, 01:12:46.600 --> 01:12:49.220 indem ich das durch ein Lambda oder durch eine Konstante ersetze. 01:12:52.240 --> 01:12:57.300 Gut, das ist also die Sikomsky-Hierarchie, die uns die nächsten sechs 01:12:57.300 --> 01:12:59.780 bis acht Wochen wahrscheinlich begleitet. 01:13:00.800 --> 01:13:04.700 Wir werden für jede dieser Grammatiken Beispiele kennenlernen und 01:13:04.700 --> 01:13:10.000 werden uns anschauen, welche Automaten können denn diese Grammatiken 01:13:10.000 --> 01:13:12.720 erkennen oder die Sprachen erkennen und so weiter. 01:13:17.320 --> 01:13:22.680 Entsprechend zu den Grammatiken können wir auch die Sprachen dann 01:13:22.680 --> 01:13:25.220 klassifizieren und in verschiedene Gruppen einteilen. 01:13:27.580 --> 01:13:33.500 Eine Sprache heißt Sprache, Sikomsky-Sprache von einem bestimmten Typ, 01:13:33.560 --> 01:13:42.640 also von Typ I, wenn es eine Grammatik gibt von diesem Typ, die diese 01:13:42.640 --> 01:13:43.420 Sprache erzeugt. 01:13:45.960 --> 01:13:50.460 Dazu ist anzumerken, wenn wir vielleicht gerade nochmal zurückgehen, 01:13:53.620 --> 01:14:05.400 es ist klar, jede Grammatik von Typ I ist natürlich auch Typ 0, weil 01:14:05.400 --> 01:14:06.660 ich habe hier nur eine Einschränkung. 01:14:06.660 --> 01:14:11.580 Wenn ich die Einschränkung von Typ I weglasse, dann lande ich bei Typ 01:14:11.580 --> 01:14:11.880 0. 01:14:13.940 --> 01:14:21.420 Jede Grammatik von Typ III ist natürlich auch von Typ II, denn all 01:14:21.420 --> 01:14:27.400 diese Regeln, A nach Lambda, A nach klein a oder A nach ab, sind auch 01:14:27.400 --> 01:14:28.800 von der Form A nach psi. 01:14:29.940 --> 01:14:32.740 Das heißt, jede Grammatik von Typ III ist auch Typ II. 01:14:33.620 --> 01:14:37.580 Von Typ II nach Typ I ist es nicht ganz so einfach. 01:14:38.440 --> 01:14:42.020 Die Schwierigkeit hier ist vor allen Dingen das leere Wort, weil ich 01:14:42.020 --> 01:14:49.180 eben hier spezifiziert habe, dass psi ist ungleich Lambda und hier 01:14:49.180 --> 01:14:53.320 aber spezifiziert habe, dass psi darf ein beliebiger Ausdruck sein, 01:14:53.420 --> 01:14:54.240 inklusive Lambda. 01:14:55.980 --> 01:14:59.800 Das ist so ein bisschen die Schwierigkeit von Typ II nach Typ I, aber 01:14:59.800 --> 01:15:04.940 im Wesentlichen gilt ansonsten, Typ III ist Typ II, Typ II ist bis auf 01:15:04.940 --> 01:15:08.380 Lambda Typ I, Typ I ist, wenn es Typ I ist, ist es auch Typ 0. 01:15:11.220 --> 01:15:13.360 Für die Sprachen gilt das in jedem Fall. 01:15:15.320 --> 01:15:19.500 Also da gilt immer, wenn die Sprache von Typ I ist, dann ist sie auch 01:15:19.500 --> 01:15:21.060 von Typ I-1. 01:15:21.060 --> 01:15:25.840 Also auch wenn die Sprache von Typ II ist, dann ist sie auch von Typ 01:15:25.840 --> 01:15:26.180 I. 01:15:26.600 --> 01:15:27.920 Das gilt für die Sprachen immer. 01:15:30.500 --> 01:15:34.540 Das heißt, die Grammatiken, je kleiner der Typ, desto mächtiger. 01:15:34.680 --> 01:15:36.060 Das ist wirklich eine Rangfolge. 01:15:40.610 --> 01:15:44.890 Okay, jetzt schauen wir uns verschiedene Eigenschaften von diesen 01:15:44.890 --> 01:15:45.850 Grammatiken an. 01:15:46.690 --> 01:15:49.050 Die erste ist die Äquivalenz von Grammatiken. 01:15:49.910 --> 01:15:52.470 Zwei Grammatiken, G1 und G2, heißen Äquivalent. 01:15:53.390 --> 01:15:58.170 Genau dann, wenn die Sprache, die durch diese Grammatiken beschrieben 01:15:58.170 --> 01:15:59.170 wird, die gleiche ist. 01:16:00.010 --> 01:16:02.450 Das ist eigentlich eine intuitive Definition. 01:16:05.510 --> 01:16:11.270 Wir werden sehen, dass es für manche Grammatiktypen Algorithmen gibt, 01:16:11.410 --> 01:16:14.270 die das effizient beweisen können, dass eine Grammatik gleich 01:16:14.270 --> 01:16:16.310 Äquivalent zu einer anderen ist. 01:16:16.930 --> 01:16:19.210 Für andere Grammatiktypen ist das sehr viel schwieriger. 01:16:20.990 --> 01:16:25.170 Okay, wir schauen uns im Folgenden eben diese unterlichen 01:16:25.170 --> 01:16:29.630 Grammatiktypen an und eben auch die dazugehörigen Klassen von 01:16:29.630 --> 01:16:36.590 Automaten, die solche Sprachen erkennen, die überprüfen können, ob ein 01:16:36.590 --> 01:16:38.990 Wort zu einer bestimmten Sprache gehört oder nicht. 01:16:40.070 --> 01:16:42.750 Und wir fangen an bei den N-Typen.