Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Oracle of Kevin Bacon
Ich komme einfach nicht weiter bei der ganzen Aufgabe, ich finde keinen guten Ansatz 
Aufgabe 3 (Oracle of Kevin Bacon):
Dem Orakel von Kevin Bacon liegt der Schauspielergraph S zugrunde: Schauspieler sind
durch Knoten repr ̈asentiert. Zwei Schauspielerknoten sind durch eine Kante verbunden,
wenn sie gemeinsam in einem Film gespielt haben. Der Knoten von Kevin Bacon hat
die Kevin-Bacon-Zahl (KBZ) 0; die KBZ eines anderen Schauspielers ist die L ̈ange ei-
nes ku ̈rzesten Weges im Schauspielergraphen S zu Kevin Bacon. Beispielsweise hat Tom
Hanks die KBZ 1, da er mit Kevin Bacon in Apollo 13 gespielt hat. Falls kein verbindender
Weg existiert, ist die KBZ des betrachteten Schauspielers als unendlich definiert.
Das Orakel ist im Web verfu ̈gbar: http://oracleofbacon.org/. Die zugrundeliegenden
Filmdaten sind der Internet Movie Database entnommen: http://www.imdb.com/.
a) Wir betrachten einen Pfad fu ̈r die KBZ z eines Schauspielers A als ein ku ̈rzester
Pfad in S, der Kevin Bacon und A verbindet und der aus z + 1 Knoten besteht.
Gib einen Schauspieler mit mindestens KBZ 4 und einen entsprechenden Pfad an.
(Hinweis: Man kann die Suchoptionen ver ̈andern, d.h. zum Beispiel verschiedene Genre
ein- und ausschalten, um den zugrundeliegenden Graphen zu ̈andern. Bitte ̈andert die Gr-
undeinstellung nicht, da die Bewertung dieser Aufgabe auf diesen Einstellungen basiert.)
b) Wenn man Schauspieler mit m ̈oglichst großer KBZ sucht, muss man davon ausge-
hen, dass man diese nicht kennt; man muss sie also erst als Teil der Suche finden.
Beschreibe eine allgemeine Strategie zum sicheren Finden (ohne Raten) von Schau-
spielern mit hoher KBZ, die jeweils nur ein Browserfenster/-tab mit dem Orakel von
Bacon und ein Browserfenster/-tab mit der IMDb verwendet. Welche Rolle spielt
dabei die Breitensuche? Welche spielt die Tiefensuche?
c) Wenn man einen Server wie das Kevin-Bacon-Orakel betreibt, muss man damit
rechnen, dass in kurzer Zeit sehr viele Anfragen hereinkommen, die jeweils schnell
beantwortet werden mu ̈ssen. Deshalb lohnt es sich, zwischen Verfahren zu unter-
scheiden, die eine Aufgabenstellung nur einmal l ̈osen, und solchen, die (nach einem
gewissen Aufwand fu ̈r “Preprocessing” zur Erstellung einer geeigneten Datenstruk-
tur) dieselbe Frage immer wieder neu fu ̈r unterschiedliche Anfragen (“Queries”)
beantworten k ̈onnen. Bei einer Anfrage soll nun nicht nur die KBZ des betrachte-
ten Schauspielers, sondern auch ein entsprechender Pfad ausgegeben werden, siehe
Aufgabenteil a). Wie kann man es als Betreiber eines Orakels vermeiden, dass man
fu ̈r jede Anfrage eine neue Breitensuche ausfu ̈hren muss, ohne dass man gigantische
Datenmengen vorhalten muss?*
*Hier geht es nicht um rein technische L ̈osungen wie Caching, sondern um das Ausnutzen von Struktur.
Du postest hier einfach ne komplette Aufgabe der Uni Braunschweig rein - wo genau scheitert es denn bei dir?
Stell doch am besten ein paar konkrete Fragen und sag uns, was du dir schon dabei gedacht hast. Und vll die Formatierung auch vorher überarbeiten…
Zudem ist es auch eigtl das Forum der Uni Erlangen - gibt es bei euch kein vergleichbares Portal? Oder ist es dort nur einfach verboten, komplette Aufgabenstellungen zu posten?
Leider gibt es von unserer Uni aus kein forum für so etwas und ja es wäre verboten, bei uns sind die tutoren sehr streng.
Ich würde gernen einen Ansatz posten, aber AlgoDat ist ein Modul was ich so gar nicht verstehe bisher, das mit den Graphen geht ja noch also BFS, DFS… aber bei diesen aufgaben finde ich wirklich keinen brauchbaren ansatz…
Ich verlange nicht das jemand hier die Musterlösung postet, aber ein Ansatz wie ich die jeweiligen Aufgaben angehen kann wäre schon sehr hilfreich für mich, welche Beweis Methode ich z. B. für welche aufgabe nehme. :-/
Ansatz: Nimm dir 10 zufällige Filme. Mach dir für jeden Film eine Liste: Schauspieler, Bacon Number. Was fällt dir auf?
Sehr geehrter Mitness,
gerne sind wir Ihnen behilflich. Im Anhang finden Sie Ihre gewünschte Musterlösung.
Mit freundlichen Grüßen.
Bacon ipsum dolor amet short loin ribeye frankfurter, pastrami shank t-bone porchetta. Turkey biltong bresaola jowl pastrami capicola leberkas frankfurter beef ribs filet mignon porchetta pork. Pastrami jerky buffalo spare ribs doner cow. Venison turkey sirloin swine salami beef ribs beef.
Shoulder leberkas burgdoggen pork short ribs tri-tip. Strip steak pastrami pork belly beef ribs hamburger tongue meatloaf turducken. Andouille buffalo picanha tongue jowl meatball. Shoulder leberkas cupim bresaola ground round chuck spare ribs ham hock swine tongue. Capicola picanha pork biltong spare ribs, turkey landjaeger rump alcatra jowl kielbasa tri-tip ball tip. Rump tongue tail leberkas beef ribs.
Fatback swine venison kevin spare ribs tenderloin cow shoulder capicola, flank pancetta tri-tip ball tip sirloin bacon. Short loin pork chop burgdoggen chuck, turkey shoulder shankle. Strip steak porchetta cow pig. Pancetta tongue chicken turkey pig. Pastrami pork chop buffalo cow, meatloaf leberkas turducken brisket shank tri-tip.
Buffalo shoulder turkey beef ham hock. Kielbasa drumstick bacon corned beef swine tongue short ribs prosciutto. Swine ribeye tongue salami meatball ground round. Ribeye prosciutto jerky porchetta, jowl andouille leberkas pork loin sirloin.
1 „Gefällt mir“
Da erschaudert der Vegetarier. 