Algorithmus – die neusten Beiträge

Maze Solving Algorithmus?

Hi,

ich will mehrere Algorithmen implementieren, womit ich ein Maze lösen kann. Dabei gehts mir um Geschwindigkeit. Das gesamte Maze ist schon bekannt, also die "Maus" kann von jedem Punkt erfahren ob es eine Wand, oder ein Weg ist.

Derzeit habe ich den Wavepropagation, den Wallfollower und einen Kombi algorithmus implementiert. Der Kombi algorithmus entstand, nachdem ich Rekursion versucht hatte, bis ich gemerkt habe, dass das ja garnicht in C# geht xD

Dann hab ich per While loop einfach immer geguckt welche Richtungen sind möglich und dann halt random eine Richtung gewählt. Wenns deadend ist, halt wieder zurück, bis eine unbesichtigte Zelle kommt. Vllt habt ihr ja eine Idee wie der heißt.

Für mich neuling kling der Wavepropagation algorithmus derzeit am optimalsten, denn er hört auf, sobald das ziel gefunden ist.

Man könnte evtl. den noch Optimieren, indem man an an jeder Kreuzung ein Node setzt.

Der Djiktra klingt für mich als Neuling wie ähnlich des Wavepropagation Algorithmus, zumindest wenn man nicht die Map in nodes (bei jeder Kreuzung) plaziert.

Gibts einen viel schnelleren?

Die Map ist so um die 10k x 10k bis 15k x15k

Evtl auch mehr, wenn ich diese nicht painten würde, sondern nur als byte array lasse. Dauert aber so schon lang genug xD

Generiert wird dieses per Binary Tree derzeit. Dieser ist wenigstens Ultra schnell. Prims algorithmus ist mir zu langsam für diese Größenordnung.

Computer, Mathematik, programmieren, Datenverarbeitung, Informatik, Algorithmus

Bei Djkstra mit negativen Kantengewichten positive Konstante addieren?

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

Studium, Schule, Mathematik, rechnen, gewichte, Informatik, Theoretische Informatik, Universität, Algorithmus, Graphentheorie, Kante

C Programmcode Ceasar Cipher?

Hallo,

die aufgabe ist folgende:

Schreiben Sie eine Funktion, welche eine Variante des [Caesar Cipher](https://en.wikipedia.org/wiki/Caesar_cipher) auf einen String anwendet. Hierbei wird anstatt eines vorgegebenen Betrages und einer vorgegebenen Richtung für die Chiffrierung der Schlüssel für jeden Buchstaben des Klartextes neu berechnet.

Funktionsweise:

Jede Verschiebung erfolgt abhängig vom Schlüssel. Ist der Schlüssel für das aktuelle Zeichen eine gerade Zahl, so wird das aktuelle Zeichen um diesen Betrag im Alphabet nach rechts verschoben (z.B. beim Schlüssel 2 wird aus einem A ein C). Ist der Schlüssel ungerade, so erfolgt eine Verschiebung nach links (z.B. beim Schlüssel 3 wird aus einem D ein A).

Würde eine Verschiebung über das Ende des Alphabets hinaus erfolgen, so wird die Zählung bei Beginn des Alphabets fortgesetzt. Beim Schlüssel 2 wird aus einem Z also ein B bzw. beim Schlüssel 3 aus einem A ein X.

Es werden nur Buchstaben des englsichen Alphabets (A-Z und a-z) chiffriert. Alle anderen Zeichen bleiben unverändert.

Der Startschlüssel wird nur auf das erste Zeichen angewendet. Danach wird der Schlüssel nach jeder Anwendung neu berechnet, indem der Zahlenwert des zuletzt veränderten Klartext-Zeichens (also 1 für A und a, 2 für B und b, bis 26 für Z und z) durch den zuletzt verwendeten Schlüssel dividiert wird. Der neue Schlüssel für das nächste Zeichen ist der ganzzahlige Rest dieser Division. Falls es hierbei zu einer Division durch Null kommen würde (weil der zuletzt verwendete Schlüssel 0 war) wird der neue Schlüssel wieder auf den Wert des Startschlüssels gesetzt.

Folgenden Code habe ich bis jetzt geschrieben, allerdings bekomm ich bei großen Schlüsseln (zb: start_key = 100) falsche Ergebnisse raus. Weiß glaube ich auch warum: Mein Algorithmus funktioniert ja über Werteverschiebung, d.h. ab einem bestimmt großen Wert des Schlüssels verschiebt sich mein Zahlenwert des chars zu weit und dann stimmt meine "Formel" nicht mehr. Hätte es jetzt damit gelöst, dass ich zuerst mit einer if Schleife auf einen zu großen Key prüfe (zB.: if Key > 25), anschließend dividiere ich diesen Key und gehe mit dem Ergebniss in eine neue Schleife rein wobei jetzt anstatt des Keys der neue Wert addiert bzw subtrahiert wird. Anschließend durchlaufe ich diese Schleife Key%25 mal.

Aber wie setze ich das um? Zusätzlich dazu wird der Code dann mega unübersichtlich und viel zu lang für eine simple Funktion. Gibt es auch andere Möglichkeiten als meinen Code?

Ps: Ich sende den Code extra weil sonst das Zeichenlimit überschritten wird

Computer, Mathematik, IT, programmieren, EDV, Informatik, Kryptographie, Universität, Algorithmus

Gibt es einen effizienten Algorithmus um alle Wortkombination bestimmter Buchstaben zu erstellen?

Ich versuch die Frage mal ein bisschen präziser zu stellen: Man gibt einem Programm n Buchstaben, das Programm gibt jetzt alle möglichen Wortkombinationen aus diesen Buchstaben zurück, sodass für zb 6 Buchstaben 6! = 720 Wörter ausgegeben werden.

Ich habe mir bereits etwas dazu überlegt, aber der Algorithmus ist extrem ineffizient: Ich lasse alle Wörter der Länge von a bis z durch, also bei n=6 zb. aaaaaa, aaaaab, aaaaac, ... usw. und überprüfe dabei den Wert und die Anzahl eines Charakters, wenn Wert und Anzahl mit meinen eingegeben Buchstaben übereinstimmt wird das Wort zurückgegeben, ansonsten wird das nächste Wort betrachtet und dasselbe noch mal überprüft. Da nur n! Wörter gefunden werden können bricht das Programm dann ab wenn n! Wörter gefunden wurden (möglicherweise auch früher, wenn sich unter den eingegeben Buchstaben Dopplungen befinden). Das Problem ist, dass dieser Algorithmus extrem ineffizient ist, da er bis zu 26^n - n! falsche Wörter durchgehen kann bis er fertig wird, die 26 Potenz ist natürlich derbe, deshalb wollte ich fragen, ob es vielleicht einen clevereren Algorithmus gibt der das besser machen kann.

Vielleicht sowas in der Form, dass bestimmte Elemente an bestimmten Indizes auf eine bestimmte Art und Weise mit einem anderen Element vertauscht werden, sodass in jedem Schritt ein neues gesuchtes Wort entsteht und somit nur n! Rechenschritte benötigt werden, gibts sowas?

Mathematik, rechnen, Informatik, Algorithmus

Sind Hashwerte als Beweismittel zugelassen?

Moin,

wie im Titel steht, frage ich mich, ob Hashwerte als Beweismittel vor Gericht zugelassen sind.

Das Konzept der Hashwerte ist denkbar einfach, es kommt ein Input rein, dieser durchläuft den Algorithmus und am Ende kommt ein einzigartiger Hashwert bei raus.

In den USA wurden bereits einige Gerichtsurteile auf Hashwertbeweise gefällt. Kurz, es wurde eine Festplatte beschlagnahmt (bzw. alle Speichermedien). Diese "interessanten" Daten waren allerdings in einem passwortgeschützten Archiv und der Beschuldigte wollte das Passwort selbstverständlich nicht rausrücken. Da die Ermittler allerdings auf die Hashes zugreifen konnten und diese mit einer Hashdatenbank von KiPo-Hashwerten verglichen haben, konnten sie einige Treffer feststellen und der Beschuldigte wurde daraufhin verurteilt.

Allerdings ist Anfang 2017 ein vermeintlich "sicherer" Hashalgorithmus von einer Forschergruppe geknackt worden. Dabei wurde einfach eine "Abkürzung" im Code genutzt und sehr viel CPU-Zeit verwendet. Dadurch gibt es die Möglichkeit in relativ kurzer Zeit aus einem Hashwert eine zweite Datei (unterschiedlich zur ersten Datei) zur erstellen, mit genau denselbem Hash, wie die erste Datei.

Mit Hinblick auf die bisher gefällten Urteile, wäre es nun möglich, dass der Täter, Einspruch einlegen kann und sich auf die Unsicherheit der Algorithmen berufen kann oder würde dies vom Gericht abgelehnt werden, da zum einen beinahe ein Supercomputer möglich wäre, um eine zweite Datei mit demselben Hashwert zu bilden?

Auch wäre es sinnvoll sich die Frage zu stellen, ab wann dieser Hashalgorithmus als "unsicher" gebrandet werden würde, da die Computer mit jedem Jahr leistungsfähiger werden und es irgendwann selbst für Heimanwender relativ einfach wäre, sowas zu bewerkstelligen.

Danke schonmal, für die Antworten!

Computer, Technik, Recht, Hash, Informatik, IT-Recht, Algorithmus, Beweis, Beweismittel

Meistgelesene Beiträge zum Thema Algorithmus