Nicht deterministischer, aber determinierter Algorithmus Beispiel?

Ich suche Beispiele für nicht deterministische, aber determinierte Algorithmen.

Determinismus ist dabei die Eindeutigkeit als dynamische Eigenschaft, also während der Laufzeit ist klar, welcher Handlungsschritt als nächster folgt.

Determiniertheit bedeutet, dass der Algorithmus bei gleichen Voraussetzungen das gleiche Ergebnis liefert.

Vielen Dank für Beispiele!

2 Antworten

Aurel8317648

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

07.06.2018, 18:45

"So gibt es Algorithmen, die nicht-deterministisch, aber trotzdem determiniert sind (d. h. das gleiche Ergebnis liefern).^[2] Zum Beispiel teilt der Sortieralgorithmus Quicksort eine vorgegebene Liste immer in Teillisten ein, welche in ihrer Größe zufällig gewählt werden können, das Ergebnis ist jedoch stets das Gleiche."

Quelle: https://de.wikipedia.org/wiki/Determinismus_(Algorithmus)

speedcuber1682

08.06.2018, 16:25

Es ist nur dann das gleiche Ergebnis, wenn kein Element derselben Größe doppelt vorkommt. Quicksort ist nicht stabil^^

Ucanaskme

Beitragsersteller

07.06.2018, 18:49

Merci, das ging schnell

Ucanaskme

Beitragsersteller

07.06.2018, 18:52

@Ucanaskme

Kuchen backen ist mir jetzt auch noch eingefallen. Da kann man schließlich auch erst vorheizen etc., selbst, wenn der Kuchen am Ende genauso schmeckt.

Aurel8317648

07.06.2018, 19:00

@Ucanaskme

Vielleicht auch noch interessant in diesem Zusammenhang:

"Instabile Sortierverfahren:

Quelle: https://de.wikipedia.org/wiki/Stabilit%C3%A4t_(Sortierverfahren)

Aurel8317648

07.06.2018, 19:07

@Ucanaskme

ja, da passt irgendwie das Sprichwort "viele Wege führen nach Rom" wenn man es ergänzt: "auch vom selben Ausgangsort" - denn die Eingabe soll ja gleich sein!

Roderic

07.06.2018, 23:50

https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus#Probabilistische_Bestimmung_der_Zahl_Pi

Bild zum Beitrag

Ähnliche Beiträge

Determinismus in Informatik?

Laut definition ist ein Algorithmus deterministsich, wenn für alle Eingabedaten die Reihenfolge auszuführender Schritte eindeutig bestimmt ist.

Gilt das dann auch für einen Algorithmus mit einer if-else Anweisung? Oder sind alle Algorithmen mit einer if-else Anweisung nicht deterministisch.

...zum Beitrag

Unterschied zwischen terminiert und determiniert?

Wenn ein Algorithmus terminiert, bedeutet es, dass er ein Ergebnis liefert und "zum Ende" kommt. Wenn er aber determiniert, bedeutet es doch das Gleiche, oder?

...zum Beitrag

Büchner Determinismus

Hallo:)

mir ist grad aufgefallen.... wenn Büchner doch ein deterministisches Weltbild hatte (Mensch ist durch Umwelt determiniert), warum schreibt er dann politische Schriften wie den Hessischen Landboten...ist doch unlogisch...warum sollte ich mich wehren, wenn ich doch glaube, dass doch eh alles vorherbestimmt ist?

...zum Beitrag

Speedcubing: eckige Klammern in Algorithmen?

Ich lerne gerade OLL bei meinen 3x3 Cube und frage mich, was eckige Klammern bedeuten.

Ein Beispiel: R2 [D (R' U2) R] [D' (R' U2) R'

Habe ich vielleicht auch einfach einen Fehler in diesem Algorithmus?

Meine Ausgangssituation:

Das Ergebnis:

...zum Beitrag

Samstag? Sonntag und daneben stehende leere Zelle in dynamischen Kalender gleiche Farbe zuweisen?

Hallo,

Erst mal vorweg. Ich bin Anfänger.
Ich habe mir einen dynamischen Jahres-Kalender aufgebaut.
Beispiel:
Spalte A "Tag" Spalte B "Wochentag" Spalte C "Leere Zelle" usw.
Mein Problem, wie kann ich die leere Zelle "C" mit "A" und "B" kombinieren,
so das diese beim dynamischen Kalender Farbmässig mitwandert?

...zum Beitrag

Was ist ein optimaler Algorithmus?

Hallo,

Ich suche momentan nach der Begriffsklärung für die Eigenschaft "optimal" in Bezug auf Algorithmen. Ich kann die antwort leider nur zum Beispiel in dieser Form finden:

Unter der Zeitkomplexität eines Problems wird in der Datenverarbeitung die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. (Von Wikipedia)

Da steht aber nirgends was denn nun Optimal bedeutet. Weiß das jemand?

...zum Beitrag

P/NP-Problem?

Beim P/NP-Problem geht es soweit ich weiß darum das ein effizienter Algorithmus für ein Problem zum Beispiel die Färbung von Graphen, die Existenz von effizienten Algorithmen für alle anderen Probleme der selben Komplexität impliziert, korrigiert mich gerne falls ich das falsch verstanden habe. Ich verstehe nur gerade nicht wie man die Komplexität eines Problems definiert wenn man nicht den effizientesden Algorithmus kennt? "Ein Problem ist K-schwer wenn sich alle anderen Probleme der Klasse K auf den Algorithmus zur diesem Problem zurückführen lassen", damit beißt sich die Katze aber in den Schwanz du definierst die Komplexität eines Problems K dadurch daß sich alle anderen Probleme der Klasse K auf den den selben Algorithmus zurückzuführen wie unseres Anfangsproblems lassen. Weiterhin stellt sich mir die Frage ob es unendlich viele Probleme einer Komplexitätsklassen oder allgemein unendlich viele Komplexitätsklassen gibt?

...zum Beitrag

Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

...zum Beitrag

Sollte man Informatik nicht studieren, wenn man auf solch einem Niveau ist?

Ich kenne einigen, die so in Gruppen schreiben:

Ich brauch Nachhilfe in Datenstrukturen und Algorithmen

Tiefensuche ,

Fluss und Flussnetzwerk ,

Z-Algorithmus , Suffixbäume ,

Dynamisches Programmieren ,

Hashing ,

Rekursive Algorithmen ,

NP-Vollständigkeit (light) , Approximationsalgorithmen ,

Ich verstehe nicht alles gut.

Man kann nicht selbststaendig lernen und recherchieren.

Ingenieure entwickeln hochkomplexe Loesungen.

Deutschland ist Exportnation; aber wir exportieren nicht die Massenware, sondern High Tech, Spezialmaschinen, Premiumfahrzeuge und Gedöns. Dafür brauchen wir schlaue Köpfe, die uns einen möglichst einen technologischen Vorsprung erarbeiten; sonst kauft die Welt anderswo.

...zum Beitrag

Wie begründet man die Anwendung der Sortieralgorithmen auf gegebene Beispiele?

Hallo liebes Forum,
ich versuche mich gerade etwas an dem Thema Sortieralgorithmen.
Die Theorie von Insertion Sort, Quicksort, Mergesort, Heapsort, Selection Sort, Bubblesort ist mir bekannt, habe auch jeden schon mal selbst programmiert und etwas getestet, nur war mir die Anwendung nie richtig klar.
Besser gesagt, wie und wann werden die außerhalb der Theorie verwendet.

Mir ist klar, dass man Insertion Sort und Selection Sort wegen ihrer mäßigen Worst Case Laufzeit nur für geringe Datenmengen einsetzt, bzw Insertion Sort auch, wenn die Daten schon vorher stark sortiert wurden.

Quicksort, Mergesort und Heapsort, weißen für großen Datenmengen die besten Laufzeiten auf, wobei man bei Quicksort darauf achten muss, das die zu sortierenden Elemente nicht schon sortiert sind, denn sonst geht die Laufzeit im Worst Case katastrophal nach oben. Weiter ist wenn es um die Speicherkapazität des Systems geht, Heapsort und vielleicht auch Qicksort zu bevorzugen, denn dank des speicherns der Ergebnisse auf ein Hilfsarray ist Mergesort ziemlich Speicher verbrauchend.

Nun habe ich diese ehemalige Klausuraufgabe aus einer Uni gefunden wobei es natürlich keine richtige Musterlösungen gab, sondern nur ein Hinweis (steht in Klammern), ich aber gerne einmal wüsste, wie man es richtig lösen könnte.

Aufgabe:

"Wählen Sie den effizientesten Algorithmus um diese Probleme zu lösen, begründen Sie außerdem ihre Entscheidung mittels der Kriterien Laufzeit und Stabilität.
Eine kurze Begründung ist ausreichend! "

An einer Verkehrskreuzung wurde über 10 Tage hinweg die Anzahl der Autos gezählt, die links abbiegen. Die Tageswerte liegen zwischen 10 und 2000 Autos. (SelectionSort)
An hunderten Wetterstationen Weltweit werden seit 1950 Temperaturwerte gesammelt. Die Werte werden auf ganze Zahlen gerundet. Der niedrigste Wert ist -89°C und der höchste 70°C. Insgesamt sind es ca. 1 Mrd. Werte. (CountSort)
Im Sonnensystem des Sterns "Sonne" gibt es 8 Planeten. Ihr Abstand zur "Sonne" ist zwischen 58 Mio. Km und 4495 Mio. Km. Die Planeten sollen Danach sortiert werden. (BubbleSort)
Ein Online-Shop hat ein Bewertungssystem für Seine Produkte, auf der Startseite sollen alle Produkte absteigend nach der Anzahl ihrer Bewertungen angezeigt werden. Diese Anzahl liegt in einem Array von Structs als Wert vor. Die Startseite soll jede Minute aktualisiert werden, somit wird der Algorithmus 1x pro Minute laufen. Da der Shop noch sehr klein ist, kommen selten neue Bewertungen zu Produkten dazu. (InsertionSort)
Ein neuer Zufallsgenerator hat 1 Mrd. Zahlen mit max. 512 Bit generiert. Um zu prüfen, wie gleichmäßig die Zahlen verteilt sind, sollen sie sortiert werden. (MergeSort)

Über eure Hilfe wäre ich sehr Dankbar

Lara

...zum Beitrag

Argumente für die Freiheit?

Im Rahmen eines Schulprojektes müssen einige Schüler und Schülerinnen, darunter ich selbst, eine Diskussion bezüglich Freiheit vs Determinismus führen. Im Zusammenhang mit der Diskussion müssen wir eine Minute lang Vortrag halten. Dabei nehme ich einen Standpunkt zur Freiheit ein. Also warum sind wir frei und nicht Determiniert? Diesbezüglich habe ich das Problem, dass mir keinerlei Argumente einfallen, weder mit Kant, Aristoteles oder Satre. Könnte mir jemand dabei helfen, Anreize schaffen oder gleich eine ganzes Argument schreiben. Argumente für Determinismus habe ich bereits selbst geschrieben das wir anschließend an der eine Minute Rede eine zwei halten müssen aber nur für die andere Seite. Ihn meinen Fall wäre es dann Determinismus zu dem ich bereits was habe. An alle die mit diesbezüglich helfen können, sage ich schon mal danke.

...zum Beitrag

Urknall - Determinismus - Ist alles genau vorbestimmt?

Es gibt diese Theorie, dass aufgrund des Urknalls alles exakt vorbestimmt ist - also determiniert. Das heisst, die Zukunft ist real, die Vergangenheit auch. Jeder einzelne Gedanken, jede Tat, jeder Moment, jedes Ereignis ist schon vor Milliarden von Jahren genau festbestimmt sowie auch die ganze Zukunft und wie sich das Universum entwickelt, denn es breitet sich ja kontinuierlich aus seit dem Urknall. Diese Information macht mir Angst! Das nimmt mir jegliche Motivation im Leben, denn egal was ich mache, es stand ja schon von Anfang an fest was ich zum Beispiel am 27.04.2026 um 12:01 machen werde und wo ich bin. Stimmt diese Theorie? Das heisst, es gibt keinen eigenen Willen. Hoffentlich stimmt das nicht und ich kann selbst noch was bestimmen!

...zum Beitrag

Ternärer Baum als Pseudocode?

In dieser Aufgabe betrachten wir gewurzelte ternäre Bäume. Jeder Knoten v kann also ein linkes Kind v.L, ein mittleres Kind v.M und/oder ein rechtes Kind v.R haben. Wir möchten nun herausfinden, wie viele Knoten im Baum sind.Gebe jeweils einen rekursiven Algorithmus in Pseudocode an, der durch den Aufruf count(v0) die Anzahl n der Knoten im Baum mit Wurzel v0 bestimmt. Begründe die Korrektheit der Algorithmen.

a) Gehe für den Entwurf deines Algorithmus zuerst davon aus, dass der Baum vollständig ist, also jeder Knoten entweder genau drei Kinder oder gar kein Kind besitzt und für jedes Blatt der Weg von der Wurzel die gleiche Länge hat. Stelle eine Rekursionsgleichung für die Laufzeit auf und löse diese mithilfe des Master-Theorems. Der Algorithmus soll eine Laufzeit von o(n)haben.

b) Wie verändern sich Algorithmus und Laufzeit, wenn Sie allgemeine ternäre Bäume betrachten?

________________________________________________________

Es geht um Pseudo-Code. In der Vorlesung benutzen wir C (obwohl wir C eigentlich erst nächstes Semester lernen), also wir lassen immer Klammern auf und schließen diese erst in der nächsten oder ubernächsten Zeile und erhöhen Variablen durch i++.

Ich habe mir überlegt, weil das ganze ein ternärer Baum sein soll und die Länge gezählt wird:

var counter = 0
    for b = 0; b ≤ n; b++) {
        for (l = 1, l++) {
             l = l + 1
}
        for (m = m, m++) {
             m = m + 1
}
        for (r = r, r++) {
             r = r + 1
}
        counter = counter + 1
}

wobei b die, ich nenn's jetzt einfach mal "Oberschleife" ,für den Baum an sich ist und l, m und r jeweils Unterschleifen, wobei l = links, m = mitte, r = rechts. Glaube aber, dass ich's mir hiermit zu einfach mache.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden, also der Form T (n) = a * T (n/b) + f(n), wobei b in diesem Fall = 3 ist, weil es ja ein ternärer Baum ist. Aber was ist a? Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

...zum Beitrag

Gibt man bei der Laufzeit von Algorithmen immer den worst case an?

Zum Beispiel Bubblesort (O(n^2)).

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen