11

Informatik (Fach) / A&D (Modellierung) (Lektion)

TP, Tsp Modell

Diese Lektion wurde von scarvy erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

Anzeige
  • Welche Probleme der Modellierung auch scheinbar einfacher Aufgaben erkennt man am Beispiel des Tübinger Parkplatzes?   !!! Hier gibt es also laut Modell halbe Fahrzeuge, negative Motorräder und gelegentlich mehr Pkw als Fahrzeuge insgesamt.   Wir müssen die Verwendung der Lösung einschränken: n und r sind natürliche Zahlenr ist gerade 2n <= r <= 4n Minimale/maximale Räderzahl   _____________ Auf einem Parkplatz der Uni Tübingen stehen Pkw und Motorräder (ohne Beiwagen). Wir zählen p Pkw und m Motorräder.   Wie viele Räder haben sie insgesamt?= 4p + 2m Wie viele Pkw bzw. Motorräder stehen da? r = 4p + 2m (7)n = p + m (8)   Wir lösen (8) nach m auf und setzen in (7) ein r = 4p + 2(n - p) (9)p = (r – 2n)/ 2 (10)m = n - (r – 2n)/ 2 (11)      
  • Wie lautet die Problemstellung bei TSP?   Ein Vertreter will in missionarischerAbsicht 12 deutsche Elite-Universitäten besuchen. Die Standorte und ihre Entfernungen (Straßenkilometer) sind in Tabelle Dist angegeben. Aufgabenstellung: Eine Rundtour mit beliebigem Ausgangspunkt und minimaler Gesamtstrecke. Jede Stadt darf dabei nur einmal besucht werden
  • TSP: Wie viele verschiedene Rundtouren gibt es allgemein für n Städte?   Zahl der Permutationen p(n) = n! = n (n -1) *..* 1 Zahlen der Touren t)n): p(n - 1) Für 12 Städte t(12) = 39:916:800 (14)
  • TSP: Naiver Lösungsansatz?   Wir erzeugen alle möglichen Abfolgen der Städte (Permutationen) Für jede Abfolge bestimmen wir deren Länge Von allen Abfolgen wählen wir die mit der kleinsten Länge
  • TSP: Implemetierung _______ ALLGEMEINES > -- Typsynonyme, für bessere Lesbarkeit des Codes > type Tour     = [City]> type Distance = Int> type Result   = (Distance, Tour) -- Distance zuerst, da man dann minimum verwenden kann________ BERECHNUNG DER PERMUTATIONEN> -- Berechnet alle Permutationen einer Liste > perms :: (Eq a) => [a] -> [[a]]> perms [] = [[]]> perms xs = [(y:ys) | y <- xs, ys <- perms (delete y xs)]> -- Mit Startpunkt: so werden nicht gleiche Touren mit anderem Startpunkt mehrmals (n-mal) berechnet werden.> permsTail (x:xs) = [ (x:(y:ys)) | y <- xs, ys <- perms (delete y xs)]_________ BERECHNUNG DER DISTANZEN> -- Berechnet von einer gegebenen Tour ihre Länge, inklusive Rückweg, dabei berechnet die Hauptfunktion nur den Weg zwischen letzter und erster Stadt,> -- während lengthRest einmal durch die Liste geht und alle anderen Abstände berechnet.> -- Wenn nur noch ein Element in der Liste ist, terminiert die Funktion.> -- die Hauptfunktion summiert alles auf und addiert auch den Rückweg.> -- der Rückgabewert ist also die ganze Distanz einer Rundtour.> tourLength :: Tour -> Distance> tourLength []     = error "tourLength: emptyList"> tourLength [_]    = 0> tourLength (x:xs) = dist x (last xs) + sum (lengthRest (x:xs))>  where>   lengthRest [_]      = []>   lengthRest (a:b:bs) = (dist a b):lengthRest (b:bs)> -- Berechnet aus einer Liste von Touren ihre Längen und gibt sie mit den Städtelisten als Tupel (Result) zurück.> -- Die Listen werden durch die rekursiven Aufrufe nacheinander abgearbeitet. > allDistances :: [Tour] -> [Result]> allDistances []        = []> allDistances (tour:ts) = (tourLength tour, tour) : allDistances ts> -- Hauptfunktion; ruft erst permsTail auf, um alle möglichen Touren zu bekommen.> -- diese werden durch allDistances alle auf einmal verarbeitet (Rückgabetyp Result bzw. [Result]!),> -- daraus wird dann das Minimum zurückgegeben. > tsp :: Tour -> Result> tsp xs = minimum (allDistances $ permsTail xs)
  • Welche Strategien wurden zur Lösung des TSP betrachtet? - Opportunistische Suche (Greedy)= man fährt immer zum nächsten, unbesuchen Ort tspgreedy(X) = greedy(s,X-{s})   - Erschöpfende Suche= man berechnet alle Rundtouren ausgehend vom Startort, bewerte sie und nimmt die kürzeste: tsp (X,x) = s:( tx {länge (s:t) | tx e perm (X-{s}}) -> tx: das t,was (s:t) minimiert
  • TSP: Abschätzung des Rechenaufwands Wir betrachten die Anzahl der berechneten Routen, und dieBerechnung einer Entfernungssumme für n Städte: Die Erschöpfende Suche braucht etwa (n - 1)!  n = n! Rechenschritte.Die Opportunistische Suche braucht etwa n² Rechenschritte.
  • Warum dient Musik als erstes umfangreiches Beispiel der Modellierung? - Notenschrift mit eigenen Regeln > Musikstücke bestenhend aus Noten (gleichzeitig ++/nacheinander *)> jede Tonhöhe hat Ton und Dauer> 12.Tonhöhen in verschiedenen Oktaven>Takt: Dauer einzelner Töne sind Takrbruchteile> Pausen
  • Wie schreibt man ein Tonleiterm wie ein harmonisches Gesetz als Formel auf? - Daten durch Konstruktor dargestellt- Funktionen durch Gleichungen C-Dur:N (C,1/4) * N (D,1/4)* N (E,1/4)* N (F,1/4)* N (G,1/4)* N (A,1/4)* N (H,1/4)* N (C1,1/4)
  • Wie universell ist das Konzept der Datenpräsentation durch Formeln? - ziemlich universell (=vielseitig), z.B. beim Thema Musik - auch komplizierte strukturierte Objekte lassen sich mit Formeln präsentieren -wichtig: Geschickte Auswahl von Konstruktoren - Formelwelt hat Gesetze, die durch Gleichungen für die definierten Funktionen gegeben sind
  • Anzeige
  • Eigenschaften der asymptotischen Klassen? f e T(f ) (Reflexivität)                      f e T(g) ^ g T(h) ) -> f e T(h) (Transitivität) f e (g) ) -> g e (f ) (Symmetrie) cf e T(f ) loga n e (logb n)

zurück  |  weiter 1 / 1