Sect. 6: scheduling Sect. 7: ProLog and Eclipse
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Part Number | 10 | |
| Number of Parts | 12 | |
| Author | ||
| License | CC Attribution - ShareAlike 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/45132 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
5
9
11
00:00
Bounded variationConstraint (mathematics)Scheduling (computing)Data modelChannel capacityHorizonBoom (sailing)Hausdorff spaceSpeciesScientific modellingProbability distributionZielfunktionComputer animation
02:06
Scheduling (computing)Constraint (mathematics)Channel capacitySlide ruleFederal Department for Media Harmful to Young PersonsSummationZeitintervallKontinuumConstraint (mathematics)Computer scienceMathematical modelWordVariable (mathematics)State of matterPredicate (grammar)Recursive languageMathematicsGrand Unified TheoryAnalogyQuery languageProgramming languageComputer animation
08:34
Scheduling (computing)User profileFeasibility studySupersonic speedSet (mathematics)Computer animation
09:42
Scheduling (computing)Civil engineeringComputer animation
11:04
Scheduling (computing)Data modelFundamental theorem of algebraReduction of orderMereologyLogical constantSequenceNumberDistanceZahlPhysical quantityOperator (mathematics)Interpreter (computing)String (computer science)ArithmeticArithmetische FunktionPredicate (grammar)Plane (geometry)Transfinite ZahlComputer animation
14:19
Bounded variationSoftware frameworkSlide ruleScheduling (computing)Semantics (computer science)Constraint (mathematics)Transformation (genetics)Maß <Mathematik>DistanceAlgorithmMatrix (mathematics)LengthExecution unitDesire pathRegulärer Ausdruck <Textverarbeitung>Variable (mathematics)Mountain passComputer animation
16:44
Scheduling (computing)Supersonic speedFundamental theorem of algebraReduction of orderData modelTape driveSlide ruleSequenceConstraint (mathematics)Term (mathematics)Hill differential equationBroadcast programmingComplete metric spaceChannel capacityHorizonWordRegulärer Ausdruck <Textverarbeitung>Kapazität <Mathematik>String (computer science)Physical quantityInformationOperatorListe <Informatik>NumberNormal operatorC++Similarity (geometry)Informationstechnische IndustrieComputer animation
19:32
Scheduling (computing)RandOperator (mathematics)Computer animation
20:45
Slide ruleScheduling (computing)Channel capacityFrequencyKapazität <Mathematik>Absolute valueComputer animation
22:00
Scheduling (computing)Virtual machineApproximationZusammenhang <Mathematik>PlanningComputer animation
24:04
PrologSheaf (mathematics)Direction (geometry)Programming languageVERKAUF <Programm>Field extensionComputer animation
28:01
Rule of inferencePrologQuery languageoutputConstraint (mathematics)Instance (computer science)Derived set (mathematics)EmulationWissensverarbeitungZielfunktionAtomic nucleusRow (database)Direction (geometry)outputLinieArtificial intelligenceTOUR <Programm>Computer programObject (grammar)Constraint (mathematics)Knowledge baseInstanz <Informatik>Computer animation
33:04
Inheritance (object-oriented programming)PrologLogical constantPhysical quantityExpert systemPoint cloudWordBinary fileImplikationZifferVariable (mathematics)Row (database)EXCELObject (grammar)Computer animation
39:51
PrologPredicate (grammar)Variable (mathematics)Logical constantWordSpecial markMoment (mathematics)ZeichensatzPredicate (grammar)Programming languageZifferComputer scienceComputer animation
45:10
PrologTerm (mathematics)Query languagePredicate (grammar)Rule of inferenceElement (mathematics)Parameter (computer programming)Variable (mathematics)Knowledge basePredicate (grammar)Query languageImplikationComputer animation
46:59
PrologFrequencyRule of inferenceVariable (mathematics)Statement (computer science)Inheritance (object-oriented programming)QuantificationQuery languageKnowledge baseEmailComputer animation
48:36
PrologInheritance (object-oriented programming)Query languageGenderKnowledge basePredicate (grammar)Direction (geometry)Logical constantQuery languageVariable (mathematics)Derived set (mathematics)Computer animation
53:41
PrologQuery languageVariable (mathematics)SequencePlastikkarteSlide rulePhysical systemLogical constantInformationVariable (mathematics)CHART <Programm>Instanz <Informatik>EPSONComputer animation
55:58
PrologPerformance appraisalQuery languageProcess (computing)RootVertex (graph theory)Level (video gaming)Network topologyInfinityPredicate (grammar)Gebiet <Mathematik>Knowledge baseSoftware developerEnergieComputer animation
58:53
Tube (container)PrologInclined planeMenu (computing)10 (number)Boom (sailing)Haar measureComputer animation
01:02:31
PrologAlgorithmNetwork topologyPlastikkartePhysicsVertex (graph theory)Feasibility studyQuery languageDepth-first searchComputer animation
01:03:36
PrologPerformance appraisalNetwork topologyPredicate (grammar)Inheritance (object-oriented programming)Predicate (grammar)Computer scienceAnalogyRecursive languageMathematicsRecursionProgramming languageComputer animation
01:07:50
PrologPredicate (grammar)Inheritance (object-oriented programming)Recursive languageQuery languageBuffer overflowComputer animation
01:09:20
Query languageProcess (computing)Network topologyVariable (mathematics)Feasibility studyPrologPerformance appraisalPredicate (grammar)Inheritance (object-oriented programming)Plane (geometry)Predicate (grammar)Computer animation
01:11:45
PrologPerformance appraisalPredicate (grammar)Network topologyRecursionSlide ruleInfinityProcess (computing)Query languageState of matterExpressionRegulärer Ausdruck <Textverarbeitung>Transfinite ZahlZahlExpert systemExpressionInterpreter (computing)Form (programming)Physical quantityWell-formed formulaAtomic nucleusNumberComputer animation
01:18:19
PrologVariable (mathematics)String (computer science)Pairwise comparisonOperator (mathematics)Numerical analysisIdentity managementBinary fileMatching (graph theory)Electronic mailing listQuery languageLogical constantInformationPrologInequality (mathematics)ZahlOperator (mathematics)NumberString (computer science)Computer animation
Transcript: German(auto-generated)
00:00
der Seite ist. Und da haben wir genau einen, wenn ich das richtig sehe. Ne, zwei sogar. John hier ist John hier. Jenny hier ist Jenny hier. Und diese, ah ja, ich hätte es gleich hier vor oben ablesen können. Und die beiden werden hochgereicht bis hier. Das Ganze läuft aber aus Evidenzgründen, um die Möglichkeit
00:25
auch zu haben, nicht vollständig auszuwerten, sondern fertig zu sein, wenn vielleicht eine Möglichkeit gefunden wurde oder wenn zehn Möglichkeiten gefunden wurden oder so. Das läuft dann eher tiefensuchmäßig ab, dass hier lang gesucht wird, so weit wie möglich nach links.
00:48
Was ist die erste Möglichkeit der Instanzierung hochgeholt? Hier die erste Möglichkeit bis hier oben hin hochgeholt. Hier die erste Möglichkeit bis hier oben hin hochgeholt. Passt nicht. Also zweite Möglichkeit hier hochgeholt. Passt leider alles nicht. Also Joe ist ein schlechtes. Ne,
01:05
John. Doch, das zweite passt dann und das wird dann hochgeholt. Hier dann die zweite Möglichkeit. John, Jenny hochgeholt. Dann hier geschaut. Erste Möglichkeit. Hier unten Joe,
01:23
John. Passt nicht. Zweite Möglichkeit hochgeholt. John, Jenny. Passt nicht. Erste, dritte Möglichkeit. Jenny, Jodie. Passt nicht. Doch, das passt. Also zweite Möglichkeit gefunden. Dann würde noch die dritte Möglichkeit. Jenny, Jodie. Hier durchsucht werden. Wird hier hoch geholt und dafür guckt man dann nach links. Erster Fall hochgeholt. Passt nicht. Zweiter Fall
01:44
hochgeholt. Passt nicht. Dritter Fall hochgeholt. Passt nicht. Also Sie wissen, Problematik von Bäumen. Bäume können natürlich sehr groß werden. Insbesondere dann, wenn sie sich so wie hier verzweigen. Ja, dafür reicht ja schon binäre Verzweigung, damit es recht groß wird. Also haben Sie, ja, wenn Sie wirklich das sämtliche Fälle, sämtliche Möglichkeiten von
02:11
unten nach oben hoch holen, schrittweise hoch, ist das natürlich die saubere Lösung. Aber unter Umständen kann das Ganze viel zu groß sein. Deshalb macht man das nicht so, weil man in der
02:23
Praxis dann oft zufrieden sein kann, dass man wenigstens eine Lösung gefunden hat. Oder oft genug ist man nur an einer Lösung interessiert, nicht an allen. So, das steht ja hier vielleicht noch mal, was ich jetzt nur angedeutet habe, was ich nicht explizit gesagt habe, dass dieser Baum
02:42
natürlich nicht wirklich aufgebaut wird, weil er viel zu groß ist im Allgemeinen. Und bottom up ist zwar für unser Denken sinnvoll, aber geht algorithmisch nicht vernünftig, weil der Baum zu groß ist, kann man auch nicht bottom up machen, sondern Tiefensuche, so wie es eben skizziert habe, von links nach rechts. Warum ist das eine Smart Variant? Gute
03:07
Frage. Gut, weil man immer nur so viel rechnet, wie unbedingt notwendig sein muss, wenn man
03:22
immer nur so weit, bis man zur nächsten Antwort kommt. Deshalb Smart. Ja, Sie haben ja in Queries in den Beispielen gesehen, dass man mehrere Beispiele, dass man mehrere Antworten finden kann, potenziell viele Antworten. Baum ist strikt von links nach rechts. Das heißt also,
03:44
die Klauseln werden grundsätzlich immer von oben nach unten strikt durchlaufen. Ja, wenn es mehrere Klauseln gibt, wo man mal gucken kann, ob es da weitergeht, wird immer die erste, noch nicht betrachtete als nächstes genommen. Und auch die Prädikate on the right hand side,
04:00
auf der rechten Seite. Man würde im Englischen eher nicht sagen on the right side, sondern man würde immer sagen on the right hand side. Offen equation oder offen implication oder so etwas. Auch die von links nach rechts. Mehr machen wir hier nicht an algorithmischen Details. Also wie gesagt, man könnte über Prolog und Evaluation von Prolog Anfragen eine
04:28
ganze Semester lang Vorlesung halten. Aber das machen wir hier nicht. So, aber wofür wir insbesondere ein bisschen verstehen müssen, wie die Auswertungsreihenfolge ist, sind
04:43
Prädikate. Das da oben, das haben wir schon gesehen. Das sehen wir jetzt nochmal. Für alle xy gilt, wenn x Vater von y ist, dann ist x Elternteil von y. Genauso für alle xy gilt,
05:04
wenn x Mutter von y ist, dann ist x Elternteil von y. So, jetzt nehmen wir das Prädikat Ancestor mit der üblichen sprachlichen Bedeutung. Ancestor heißt Vorfahr. Also wir gehen jetzt
05:23
nicht so weit. Es wäre typische mathematische, informatische Notationspraxis zu sagen, jeder Mensch ist Ancestor von sich selbst. Soweit gehen wir jetzt doch nicht. Sie kennen Beispiele, analoge Beispiele zu dem, was ich eben gesagt habe. Jeder ist Ancestor
05:42
von sich selbst. Soweit gehen wir doch nicht, sondern aber wir sagen, was vielleicht außerhalb von Mathematik und Informatik auch erstmal gewöhnungsbedürftig ist, dass auch schon Elternteil ein Vorfahr ist. Ist korrekt, aber eben wie gesagt vielleicht etwas gewöhnungsbedürftig.
06:02
Hätte man nicht so machen müssen, hätte man auch natürlich erst bei Grandparent oder bei noch weiter auseinander anfangen können. Aber Ancestor mit Parent beginn zu lassen, ist sicherlich für die meisten Zwecke auch die pragmatisch sinnvolle Lösung. So, für alle xy gilt, x ist Parent von y. Wenn x Parent von y ist, dann ist x auch Ancestor
06:27
von y. Und für alle xy gilt, wenn es ein z gibt, ja sie erinnern sich, dieses z kommt nicht auf der linken Seite vor, nur auf der rechten Seite, ist also Existenz unter gebunden. Wenn es ein z gibt, sodass x Parent von z und z Parent von y ist, dann
06:46
ist x Ancestor von y ist, dann ist x Ancestor von y. So, hier sehen Sie die Rekursion drin. Rekursion heißt schlicht und einfach im Prolog. Das was links ist, einer Regel
07:02
taucht auch rechts auf. Und hier ist jetzt die Auswertungsreihenfolge wichtig, aus dem selben Grund, warum in normalen Programmiersprachen wie Java, C, C++, warum es da bei einer Rekursiven Methode, bei einer Rekursivfunktion wichtig ist, nicht erst rekursiv aufzurufen
07:27
und dann abzufragen, ob das Rekursionsende erreicht ist, sondern erst abfragen, ob es Rekursionsende erreicht ist und nur dann, wenn es nicht der Fall ist, rekursiv aufrufen. Also wenn wir die beiden Klauseln hier vertauscht hätten, also die Rekursion
07:51
zuerst und dann der rekursive Schritt zuerst und dann der Rekursionsanker danach, dann würde das ganze in, die Prolog-Leute werden mich dafür prügeln, aber es ist so, in
08:04
eine Endlosschleife laufen. Oder eine Endlossrekursion mit Stackoverflow halt. Das will ich nochmal an der Tafel klar machen. Mithilfe dieser Regeln, Evaluation einer Query. So, so
08:58
wie das da steht, haben wir Ancestor, entweder zurückgeführt auf Parents. Jetzt muss ich
09:17
mal ganz kurz nochmal gucken, wie die Notation von Bäumen war. So ein Fall kam hier gar
09:30
nicht vor. Dann muss ich das jetzt mal schnell improvisieren. So, ich setze hier
09:43
so ein Knubbel für die Verundung ein und haben hier Parents und hier Ancestor. Und hier dasselbe wieder eingesetzt. Parents und Knubbel für die Verundung und dann
10:07
Parents und Ancestor. Und Sie sehen, machen wir vielleicht nochmal einen Schritt weiter, aber ich glaube es wird schon deutlich. Hier Parents, hier Knubbel und Parents und
10:28
Ancestor. Sie sehen, dass dieser Baum unendlich rechtslastig ist. So, die Evolutionsordnung
11:02
ist strikt von links nach rechts. Das heißt, wenn es irgendwo mal einen Ausgang gibt, wenn es irgendwo mal passt, dann kommt es zu einem Ende. Egal wie tief, irgendwo nach endlicher Zeit. Wenn Sie sich jetzt vorstellen, wir hätten das umgedreht,
11:21
die beiden Klauseln vertauscht und vielleicht noch die beiden Prädikate vertauscht auf der rechten Seite der zweiten Klausel, dann wäre dieser ganze Baum spiegelbildlich. Und das erste, was er machen würde, ist in diesen einen unendlichen Pfad reinzugehen, wo immer nur Ancestor steht auf jeder Ebene. Und damit hätten wir entweder Endlosschleife
11:43
oder Stackoverflow erreicht. So, wenn wir versuchen, alle Antworten zu berechnen, dann würde es in dem Fall natürlich immer noch sein, dass wir einen unendlichen Prozess kriegen. Weil wir jetzt erst nach einer unendlichen Zahl von Möglichkeiten feststellen,
12:05
dass es keine weiteren Möglichkeiten mehr gibt. So, noch ein Beispiel. Das ist eigentlich der Kernpunkt. Dieses Beispiel ist eigentlich am Her... Nee, wie sagt man? At the heart of... Wie sagt man im Deutschen? Ist eigentlich die Art von Beispielen, die man eher im
12:27
Sinn hatte, als man Prolog entwickelt hat, nach meinem Verständnis. Das ist ein einfaches Beispiel für einen Interpreter für arithmetische Formeln. Einfach arithmetische
12:40
Formeln, Klammer, Ausdruck, plus, minus, mal, geteilt. So, hier sehen Sie noch eine... Hier sehen Sie noch ein Schlüsselwort, glaube ich, ist es in diesem Fall, ist links steht ein String, rechts steht eine Zahl und das ist korrekt, wenn dieser String
13:06
als eine Zahlinterpreter ist, die genau diesen Wert hier hat. So, das ist auch ein Beispiel für die etwas merkwürdige Logik, zumindest am Anfang erst mal, merkwürdige
13:23
Logik von Prolog. Wir berechnen nicht einen Wert für einen mathematischen Ausdruck, für einen arithmetischen Ausdruck, sondern wir sagen, value ist der Wert dieses Ausdrucks, wenn irgendwelche Eigenschaften erfüllt sind. Ja, hier sind die Eigenschaften
13:42
für plus, hier sind die Eigenschaften für minus, also wenn das letzte auszuwertende arithmetische Funktion ein plus ist, die im arithmetischen Berechnungsbaum ganz oben in der
14:01
Wurzel steht, hier wenn es ein minus ist, hier wenn es mal ist, hier wenn es geteilt ist und hier wenn es gar keine, wenn es gar keine, wenn der Ausdruck gar keine arithmetischen Operatoren mehr enthält, sondern nur ein reiner Zahlenwert ist, hier vorne erster Schritt, erste Klausel, wenn es Klammern gibt, wenn hier Klammern sind. Hier sehe ich gerade,
14:27
ist ein kleiner Fehler. Expression 1 und Expression 1 müsste dasselbe sein. Also value ist der Wert von Expression, wenn Expression sich schreiben lässt, als irgendein
14:44
Existenzquantor gebunden. Ja, hier Expression 1 ist eine Existenzquantor gebundene Variable, wenn es ein Expression 1 gibt, sodass das in Klammern gleich dem Expression ist.
15:02
Und hier muss leider 1 stehen, nicht 2. Ich bitte um Entschuldigung. Und wenn value auch der Wert dieses Expression 1 ist. Ja, damit wird ein Ausdruck in Klammern behandelt, wenn der Ausdruck sich als andere Ausdruck in Klammern schreiben lässt und wenn der
15:24
Ausdruck in Klammern, innerhalb der Klammern, eben genau dieses value ist. Ja, also was da passiert ist, dass dann tatsächlich dieser Wert berechnet wird und auch gar nicht mal so ineffizient, wie es jetzt zuerst aussieht. Aber die Logik von Prolog ist eine andere.
15:48
Man gibt einen Wert aus, der auf diesen Expression passt. Oder genauer gesagt ist man gibt alle Werte aus, die auf diesen Expression passen. Wenn das ein variablenfreier Ausdruck
16:03
ist, also wenn wir keine Variablen drin haben, so wie es in diesem kleinen Beispiel hier ist, dann kommt natürlich nur ein Wert raus. So, value, Expression, value dasselbe wieder. Großvalue ist der Wert dieses Ausdrucks, Großexpression. Wenn
16:20
sich Expression schreiben lässt als Expression 1 plus ein Expression 2 und, wenn der Wert hier gleich dem Wert value 1 und dem Wert value 2 ist, wenn es 2 wieder und wenn value 1 der Wert
16:41
von Expression 1 und value 2, sorry, hier gehört jeweils noch value 2 hin. Ich weiß gar nicht, was da passiert ist. Hier gehört jeweils noch mal value 2 hin an diese vier Stellen. Wenn der value 2 der Wert von Expression 2 ist. Also, was steht hier? Für alle Strings, Expression,
17:02
für alle Zahlen, value gilt, dass value der Wert von Expression ist, wenn Expression, wenn es ein Expression 1 und ein Expression 2 gibt und wenn es ein value 1 und ein value 2 gibt, dass Expression gleich als String, Expression 1 plus Zeichen, Expression 2 ist und wenn value,
17:28
hier das ist, ist arithmetischer, echter, normale Gleichheit, wenn der Wert von value, der Zahlenwert value, gleich dem Zahlenwert value 1 und dem Zahlenwert value 2 ist und wenn value 1 der Wert von Expression 1 und value 2 der Wert von Expression 2 ist. Es ist eine
17:45
komische Logik, aber kann man sich dran gewöhnen. Wir müssen uns aber hier nicht wirklich intensiv dran gewöhnen. Sie können sich vorstellen, dass Prolog und Eclipse, Sie haben ja auch gesehen, dass es keine Übungsaufgabe dazu gibt, dass es natürlich in den Prüfungen durchaus eine Rolle spielt, aber jetzt nicht die ganz tiefgehende Rolle.
18:07
Selbe mit Minus mal geteilt. Gucken wir vielleicht, um uns ein bisschen näher noch dran zu gewöhnen, das uns beim nächsten Mal nochmal an. Hier gut die Erklärungen dazu.
18:28
Gucken wir uns vielleicht beim nächsten Mal doch mal an. Normalerweise überspringe ich die Erklärungen immer ein bisschen. Listen ist dann ein nächstes Thema, aber gehen wir einmal nur mal ganz kurz hier zum Ende durch. Wir haben noch ein paar Minuten Zeit. Also
18:43
Prolog ist eine Sprache, in der es eigentlich nur Strings gibt. Das ist eine der Grundideen von Prolog. Alle Informationen sind Strings und wenn wir den normalen Operator gleich haben, das was Sie in C, C++ und Java als Operator gleich haben, dann ist das einfach Übereinstimmung
19:00
zweier Strings. Es bedeutet nicht, wenn Sie zwei Strings haben, Sie sich beide als Zahlen darstellen lassen. Auf der einen Seite 1.0 und auf der anderen Seite nur eine 1. Dann gibt Ihnen Operator gleich false zurück. Obwohl es der gleiche Zahlenwert ist, ist es eben nicht
19:20
der gleiche String. Hier sehen Sie den Unterschied. Gleichheit bedeutet Stringgleichheit 4 plus 3 als String. X ist 4 plus 3 bedeutet Wertgleichheit. X gleich 7. Während dann die
19:44
Vergleichsoperatoren, die wir jetzt in dem Beispiel nicht drin haben, die sind wieder ganz normal, wie sie es aus anderen Sprachen gewöhnt sind, auch wieder numerisch zu verstehen. Ich meine, mir ist nicht ganz klar, welche Semantik diese Operatoren haben sollen bei Stringgleichen.
20:03
Könnte man sich natürlich irgendwas vorstellen, wie lexicografische Ordnung, aber das ist irgendwie gut. Damit sind wir für heute zu Ende. Ich darf mich bedanken und dann sehen wir
20:21
uns beim nächsten Mal wieder. Bis dann.