16

PI (Subject) / Algorithmus (Lesson)

This lesson was created by blace.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• Was bedeutet Durchführbarkeit im Kontext von Algorithmen? Durchführbarkeit setzt sich aus 3 Eigenschaften zusammen. statische Endlichkeit (Der Algorithmus besitzt eine endliche Beschreibung also das Verfahren kann mit einem endlichen Text beschrieben werden) dynamische Endlichkeit (der Algorithmus benötigt eine endliche Anzahl an Resourcen und eine endliche Speichernutzung) Effektivität ( Die Schritte sind eindeutig und effektiv ausführbar)
• Wann ist ein Algorithmus determiniert? Gib ein Beispiel an. Ein Algorithmus ist determiniert, wenn es immer die gleichen Ausgabewerte für die gleichen Eingabewerte gibt Eingabe x ist eine beliebige ganze Zahl. addiere x mit 10 schreibe Ergebnis auf gleiche Ausgabe bei gleicher Eingabe
• Wann ist ein Algorithmus deterministisch? Gib ein Beispiel an. Ein Algorithmus ist deterministisch, wenn der Ablauf des algorithmus zu jedem Zeitpunkt fest vorgeschrieben ist. Eingabe y ist eine beliebige ganze Zahl nehme eine Zahl x ungleich 0 berechne (3x+x)/x + y schreibe das Ergebnis auf jeder Schritt fest vorgeschrieben Algorithsmus ist deterministisch UND determiniert
• Wann ist ein Algorithmus partiell korrekt? Wenn es ein Ergebnis gibt und die Eingabe der Eingabe Spezifikation entspricht, dann ist das Ergebnis im Sinne der Spezifikation korrekt.
• Wann ist ein Algorithmus total korrekt? der Algorithmus ist total korrekt, wenn sowohl partielle Korektheit und Terminierung zutreffen, falls die Eingabe der Skezifikation entspricht. Terminierung: Wenn die Eingabe der Spezifikation entspricht erhält man das Ergebnis in endlich vielen Schritten.
• Wie ist ein Algorithmus typischerweise aufgebaut? Aus welchen Schritten besteht die Abarbeitung? Typischerweise besteht ein Algorithmus aus dem Namen, der Parameterliste und den Spezifikationen für das Ein- und Ausgabeverhalten. Die Abarbeitung besteht aus folgenden Schritten: Schritt 1: Vorbereitung ist die Einführung von Hilfsgrößen Schritt 2: Trivialfall - falls ein einfacher Fall existiert wird der Algorithmus sofort mit einem Ergebnis beendet Schritt 3: Arbeit(Problemreduktion/ergebnisaufbau) - Das große Problem X auf ein kleineres X`reduzieren und Teilergebnis aufbaeun(gemäß der Reduktion) Schritt 4: Rekursion bzw. Iteration - Weiterverarbeitung des kleineren Problems - Rekursion(Algorithmus mit kleinerem Problem ausführen) - Iteration ( fahre mit dem kleinerem Problem bei Schritt 2 fort)
• Erläutere verschiedene Vorgehensweisen beim Entwurf von Algorithmen. bottom-up - in Richtung höherer Abstraktionsstufen fertif wenn die Methode das Gesamtproblem löst top-down - Zerlegung des Gesamtproblems in kleinere Teile fertig wenn alle Teile direkt programmierbar sind. Die Schnittstellen erlauben parallele Entwicklung Praxis - Entwurf top-down Programmierung bottom-up
• Welche Ansätze zur Problemlösung mittels Algorithmen gibt es? Iterative Algorithmen (Startwert festgelegt, neuen Wert errechnen so lange wiederholen bis die Lösung oder ein Ergebnis gefunden wird das gut genug ist. Gierige Algorithmen (Immer die beste Teillösung bei jedem Schritt(z.b das lokale Minimum/Maximum) Divide and conquer(Reduktion in zwei oder mehr Teilprobleme, lösen der Teilprobleme, Kombination der Teillösungen) Backtracking dynamische Programmierung Zufallsgesteuerte Algorithmen Genetische Algorithmen Heuristische Algorithmen Probabilistische Algorithmen
• Wie arbeitet ein gieriger Algorithmus? Gib ein Beispiel an. Ein gieriger oder auch greedy Algorithmus arbeitet, indem er immer bei jedem Schritt die vielversprechendste teillösung nimmt. Hat man nun nur eine bestimmte Menge Geld und möchte dafür so viele Produkte wie möglich einkaufen, würde der Greedy Algorithmus nur jeweils zwei Produkte anschauen und das jeweils billigere auswählen, was zu nicht Idealen Gesamtergebnissen führen kann.
• Wie arbeitet ein Algorithmus, der nach dem Ansatz Divide-and-Conquer verfährt? Gib ein Beispiel an! Ein Algorithmus, der mit dem Divide and Conwuer Prinzip arbeitet, teilt das Problem in zwei oder mehr Teilprobleme auf, löst diese Teilprobleme und fügt dann die Lösungen zusammen. Bsp. Sortieren der Liste 3, 40, 7, 2, 34 3, 40, 7 || 2, 34 3, 40 || 7             2 || 34 3 || 40      7         2, 34 3, 40         7         2, 34 3, 7, 40                2, 34 2, 3, 7, 34, 40
• Advertisement
• Wie arbeitet ein Algorithmus, der nach dem Ansatz Dynamische Programmierung verfährt? Gib ein Beispiel an! Ein Algorithmus mit dem Ansatz der dynamischen Programmieruzng arbeitet damit, dass er die Teillösungen in einer Tabelle zwischenspeichert und sie dann bei Bedarf wieder ausliest. Dieser wird also verwendet wenn die Teillösungen merhfach benötigt werden. Bsp. Fibonacci Zahlen bei den Fibonacci Zahlen wird jede Fibonacci Zahl fn n>1 mit fn= fn-2 + fn-1 errechnet. also mit dem zweiten Vorgänger minus plus dem ersten Vorgänger f0 =0 und f1=1, sodass f2 =1 f3 = 2 f4=3 f5 = 5 f6 =8 f7 = 13 etc.
• Wie arbeitet ein zufallsgesteuerter Algorithmus? Gib ein Beispiel an! Der Ablauf wird per Zufall gesteuert. Bsp. globales Minimum eines Graphen aus Messwerten finden Man sucht in die richtugn kleinerer Werte man hat ein Minimum gefunden wenn die Werte wieder größer werden, damit findet man immer mindestens ein lokales Minimum Metropolis-Algorithmus (Simulated Annealing) Man geht aus von dem Startpunkt X0 man sucht den nächsten Wert in zufälliger Richtugn Xneu Wenn Xneu < Xalt wird Xneu akzeptiert Wenn Xneu >= Xalt wird Xneu manchmal akzeptiert um kleine Hügel zu überwinden Man muss darafu achten einen geeigneten Suchbereich zu wählen
• Wie arbeitet ein genetischer Algorithmus? Gib ein Beispiel an! Ein genetischer Algorithmus ist an die Evolutionstheorie angelehnt und stellt die möglichen Lösungen als Gene von Individuen dar Man erzeugt eine erste Generation von Individuen mit zufälligen Genen und wiederholt dann die Fortpflanzung mittels Selektion Kombination und Mutation solange bis das Abbruchkriterium erfüllt wird Selektion - Mutter/Vater werden ausgewählt - zwei zufällige Individuen werden gewählt, ihr Fitnesslevel wird bestimmt und das stärkere Gen wird Mutter/vater Kombination - die Gene der zwei ausgewählten Mutter und Vater werden vermischt und ein Kind entsteht welches der neuen Population hinzugefügt wird Mutation - Ein Gen des kindes wird durch eine festgelegte Wahrscheinlichkeit geändert Bsp. Rucksackproblem Rucksack hat Kapazität c es gibt n Gegenstände mit Gewicht gi und Wert wi das Ziel ist den maximalen wert zu erreichen Gene sind die Werte ja oder nein (Gegenstand mitnehmen oder nicht) eine zufällige Population mit 50% Wahrscheinlichkeit für ja oder nein wird erstellt (hier könnte der Rucksack überladen werden) Nun wird die Fitness Funktion erstellt mit den Variablen W, G und C für den Wert das Gewicht und die Kapazität Wenn G <= C ist ist die Fitness = W, Wenn G> C ist Fitness = W-(G-C) Kombination mit einer zufallszahl zwischen 0 und n, die ersten z Gene kommen von der Mutter die letzten n-z Gene kommen vom Vater Mutation jedes Gen kippt mit einer Wahrscheinlichkeit von 1% (von ja zu nein)
• Wie arbeitet ein heuristischer Algorithmus? Gib ein Beispiel an! Erweitert bekannte Algorithmen zu völlig neuen Algorithmen zB. statistische Zusammenhänge oder Bewertungen - Schachcomputer - Die Figuren erhalten Werte die Stellungen erhalten Werte Bsp. BucketSort Die folgenden Zahlen aufsteigend sortieren 26, 85, 70, 28, 63, 57, 98, 53, 10, 3 die offensichtlichen Eigenschaften -  alle Zahlen sind kleiner als max = 100, die Zahlen sind relativ gleichmäßig über das Intervall [0, max] verteilt Erfahrung - Position kann in solchen Fällen erraten werden Positionz = [ z*n/max] n Eimer eimerinhalte müssen sortiert werden
• Wie arbeitet ein heuristischer Algorithmus? Gib ein Beispiel an! Erweitert bekannte Algorithmen zu völlig neuen Algorithmen zB. statistische Zusammenhänge oder Bewertungen - Schachcomputer - Die Figuren erhalten Werte die Stellungen erhalten Werte Bsp. BucketSort Die folgenden Zahlen aufsteigend sortieren 26, 85, 70, 28, 63, 57, 98, 53, 10, 3 die offensichtlichen Eigenschaften -  alle Zahlen sind kleiner als max = 100, die Zahlen sind relativ gleichmäßig über das Intervall [0, max] verteilt Erfahrung - Position kann in solchen Fällen erraten werden Positionz = [ z*n/max] n Eimer eimerinhalte müssen sortiert werden
• Wie arbeitet ein probabilistischer Algorithmus? Gib ein Beispiel an! Grundlagen–Las-Vegas-Verfahren●wenn Ergebnis, dann korrekt(kann also evtl. ohne Ergebnis bleiben)–Monte-Carlo-Verfahren●liefert mit bestimmter Wahrscheinlichkeit fehlerhaftes Resultat Idee–verwandtes Problem für ursprüngliche Aufgabenstellung finden●mit geringerem Aufwand bzw. überhaupt lösbar–Übertragung der Erkenntnisse auf ursprüngliche Aufgabenstellung–falls keine Fehler erlaubt●Las-Vegas-Verfahren–falls Ergebnis Prima!→–falls kein Ergebnis ursprüngliche Aufgabenstellung lösen→–falls (kleine) Fehler akzeptabel●Monte-Carlo-Verfahren–iterativ bis Fehler hinreichend klein Beispiel: Primzahlbestimmung–Problem: Ist z eine Primzahl?–wähle Basis a > 1, so dass a nicht durch z teilbar ist*●wenn az-1 mod z # 1, dann ist z sicherkeine Primzahl●wenn az-1 mod z = 1, dann ist z wahrscheinlich eine Primzahl

back  |  next 1 / 1