Mathematisches Basisverfahren der Informatik - hier: Permutationen

Letztmalig dran rumgefummelt: 06.02.18 14:31:39

	Permutation ist der komplizierte Begriff für die simple Sache des Vertauschens von Anordnungen. Dabei muss in der mathematischen Betrachtung streng zwischen der Zulässigkeit sowie der Unzulässigkeit von Wiederholungen unterschieden werden.
	1. Definition 2. Mathematisches Modell   3. Große und kleine Zahlen 4. Permutationen von Elementen einer Meng e an Beispielen 5. Software-Lösungen 6. Verwandte Themen
	mathematische Ansätze der Informatik Logo für die Permutationen inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???

1. Definition

	Mathematiker haben den unvergleichlichen Sinn dafür, alles zu kürzen und dabei in eine fassliche Form zu bringen - an sich eine lobenswerte Initiative, nur mit dem Haken: Du musst Mathematik studiert haben, um die Ausdrücke ansatzweise zu verstehen. Deshalb hier nun an der Stelle der Versuch, alles auf ein verständliches Niveau zu transformieren.
	Hier nun die Definition - weiter unter versuchen wir, dies etwas zu erhellen: http://de.wikipedia.org/wiki/Permutation
	n über k CHATUHEIS permutiert zu: HAUSTEICH oder auch TEICHHAUS NONSENGENT permutiert zu: ENTENSONNG ;-)    ;-) NONNENTSEG FELDSGRON permutiert zu: FELDSGRON RESFORGLN LEFDSGORN DELFSGORN GRONSFELD PALME permutiert zu: LAMPE oder auch AMPEL EINBRECHER permutiert zu: BEREICHERN SCHUFTEREI permutiert zu: EIFERSUCHT GRUNDBESITZERIN permutiert zu: ZUBRINGERDIENST STAATSDIENER permutiert zu: DIAETENSTARS Binomialkoeefizient Sierpinsky-Dreiecke
	Permutationen über Buchstaben Ein Zeichen ohne Wiederholung - The best Case ;-) Zwei Zeichen ohne Wiederholung Drei Zeichen ohne Wiederholung Vier Zeichen ohne Wiederholung Permutation des Alphabets der Menge 1 auf sich selbst Permutation des Alphabets der Menge 2 auf sich selbst Permutation des Alphabets der Menge 3 auf sich selbst Permutation des Alphabets der Menge 4 auf sich selbst
	Schlacht bei Hastings ... mehr zur Schlacht bei Hastings Permutationsversuche mit dem Alphabet Berechnungen mit den Permutationen des Alphabets einige der Permutationen des Alphabets ohne Zeichenwiederholungen   Download als Textfile Hochrechnung zum Zeitaufwand zum Auffinden aller Permutationen Hochrechnung zum Zeitaufwand zum Auffinden aller Permutationen die rekursive Fakultätsfunktion Ein kleines Permutations-Experiment: Am 1. Airpl 1941 wrdue ein encglisehr Ofizefir vom Leatunnt zum Haputnman befdreört. Im ametlhicn Miteigltunsbltat des Krnigsemiisetruims wrdue irtrümiwclherseie als Duatm der Ragnerhhönug der l . April 104l agngebeen. Soiewt der Tabtetasnd. Wärhned der Berfödernguseifer riteen die libeen Kadermaen dem jugenn Haputnman im Secrhz, das Krigmiesinristeum zur Nahzcauhlng der Beüzge für die Ziet von 1041 bis 1941 zu vesrnslaaen. In fceuhtfröehhlicr Stnimumg wudre also ein ofizlifeles Sceribhen an das Krgiemisniteursim auzgefsett und acgeshbickt. Am ncäsehtn Moegrn kam dem Ofizeifr das Ggeawte seneis Vetralehns zum Besustwsein, und mit eneiigr Beiorgsns earrtwete er den Asnguag der Gecchisthe. Ncah shces Wohecn kam die Artwont des Mnisiteiumrs: Irhe Nahcforuderng auf Begüze, die bis zum 1. April 1041 zucükgreehn, wudre üebrprfüt und in Odrnnug guendfen. Wir hbean daehr ncoh am sleebn Tgae Iherm Knoto 39.999,00 Pnufd guebsgcehtrien. Es secihnt jeocdh Irehr Ausmefrkakmeit eatgnnegn zu sien, dass ncah dem kniögelichn Earsls jdeer Ofiezfir percönlsih für die Vuelsrte an Wafefn und Perfden, die dcurh Nahläscsigeikt velorrenehgen, hatbfar ist. Flält der Konmanmdat ducrh Tod aus, so ghet die Veuantwrortng auf den nchstäältsteen Ofizifer üebr. Aus Irhem Bierf geht eidwanfrnei hrveor, dsas Sie der leztte Üedrlebbene der Shlaccht von Hsiatngs im Jahre 1066 n. Chr. snid, bei der 20.000 Pfdree dcurh Fhraläsigskiet velroern gniegn. Jeeds Prfed wdrue mit 2 Pnufd beterwet. Sie snid deamcnh für die Esartzazhulng von 40.000,00 Pnfud hatabfr. Daimt beätgrt der Sadlo auf Ihrem Ktono 1 Pfnud zgusutnen der Knroe. zur Lösung ;-)
	und noch eines: von Ronny Strobd in Internet und Computer - FREIE PRESSE vom 19. August 2009 - Gein Mott, din ich burcheinander! Wich ollte nur ein neues Kandy haufen. Jetzt bin ich knurchgedallt. Föllig vertigstille Icherungen sind flausgerogen. Peng! Kandy haufen ist die Hölle, Hölle, Hölle. Was die weutzutage alles hissen wollen. Allein die Tandy-Hypen. Soll's ein Harren-Bandy sein? Oder ein Happ-Kandy? Oder ein Hiebe-Schandy? Soll's eine Spreifrech-Funktion haben, ein Kreuersteuz und einen Scrouchteen? Neiß ich wicht! Ich fin bertig. Total. All biese kledoppten Kabürzungen: MMS. GPS. MP3. DRM. UMTS. HSDPA. USB. WLAN-hääää? All biese kledoppten benglischen Egriffe: Push To Talk, Bluetooth, Downstream, Roaming, Softkey - hääää? All biese kledoppten benglischen Berbe-Schotwaften: Connecting People. Life's good. Oi can do. - Du mich auch! Noch kledoppter als Tandy-Hypen und Berbe-Schotwaften sind Tandy-Harife. Ein einziger Girr-Arten. Zum Rausasten! Von Relax 1000 XL Business über Combi Comfort SIM bis Time and More all in Web 100 - das sterveht seine Kau. Außer vielleicht Probelneis-Träger. Aber ich din so burcheinander, dass ich wicht neiß: Ist E plus 02 = Nokia? Und ergibt T - Mobile = Stunkfille? So nicht, Kandy-Verhäufer! Ich will bloß feletonieren. Hach nause bum Zeispiel. Direkt. Ohne Schnackschniek. Aber Ihr? Ihr macht mich kleif für die Rapse! Deshalb haufe ich kein neues Kandy. Ich saufe neue Kicherungen für keinen Mopf. , Aber ich bätte da noch eine Hitte an euch. „Kandy haufen kann rervückt machen"- das solltet Ihr in Kuzunft auf die Pervackung drucken. So als Harnwinweis Wie auf den Gizarettenpervackungen. Whe wenn nicht! Dann servende ich 'Post Nach Brüssel an die Büro-Eurokraten. Die herden mir welfen. Die sind noch viel rervückter als ich.
	Anwendungsbeispiele für Permutationen innerhalb der Informatik Rotationsschablonen   das Rundreiseproblem   Polynomzahlen ENIGMA Pangramme Anagramme ... um ein Anagramm zu "knacken" muss ich alle Permutationen der möglichen Zeichenfolgen ausprobieren - eine davon ist richtig ;-) Gartenzaun-Transpositions-Chiffre   Sägezahn-Transpositions-Chiffre   Lipogramme ... und hier nun nehmen wir nicht hinzu, um Verwirrung zu stiften - NEIN - wir lassen weg - in diesem Falle das "E" - viel Spass ;-) SUDOKU das Post'sche Korrespondenz-Problem Matrix-Chiffre das Dominospiel
	Verwandte Problemkreise die Komplexität eines Problems & Komplexitätsklassen NP-vollständige sowie NP-schwere Probleme

2. Mathematisches Modell

	Hier zeigen wir auf, dass bereits mit wenigen Elementen n die Anzahl der möglichen Kombinationsmöglichkeiten zwar endlich, aber eben schnell extrem groß werden kann. Aufwandsbetrachtungen gehören hier schnell zur Analyse einer generellen Lösbarkeit, jedoch vor allem vor einer Lösbarkeit in einer definierbaren Zeit.
	... ohne Wiederholungen der Zeichen ... mit möglicher Wiederholungen einiger Zeichen ... mit möglicher Wiederholungen aller Zeichen Permutation einer Elementemenge ohne zulässige Wiederholungen Permutation einer definierten Elementemenge  zulässiger Wiederholungen Permutation aller definierten Elemente der Menge in der Wiederholungen

3. Kleine und große Elemente-Mengen

	Wir betrachten an dieser Stelle einen einfachen CÄSAR-Chiffre mit Keyword und fragen uns, welche Chancen hat ein potentieller Angreifer mittels der "Brute-Force-Methode"? Logische Antwort nach Kontrolle der vorhandenen Muster: keine!!! Statistisch ist selbst Kollege Zufall ausgeschlossen, dabei reden wir von einer Informationsvorhaltezeit von wenigen Stunden bis Tagern in der Praxis!!!
	... 26 klingt ja nun wirklich nicht nach gerade viel - wenn wir allerdings die Fakultätsfunktion 26! dazu betrachten wird das gigantisch ... ... wir lassen das englischsprachige Alphabet unter folgenden Bedingungen permutieren ... 26 Buchstaben des Alphabets - momentan sind keine Wiederholungen der Zeichen zugelassen ... ... es gilt also 26! = 403291461126605635584000000 besser: 403.291.461.126.605.635.584.000.000 ... wir sprechen also von einer 27stelligen Zahl ... die Bundesrepublik Deutschland hat derzeit geschätzte 80 Mio. Einwohner (vom Säugling bis zur Oma) und alle machen mit (das sind also nicht gerade wenige)... ,,, es gibt kein Wochenende - wir schlafen nicht mehr und wir machen keinen Urlaub - das Jahr hat durchschnittlich 365 Tage ... jeder erledigt eine Permutation pro Sekunde (es ist nicht Gegenstand der Diskussion, wie wir das technisch organisieren), keiner macht Fehler und/oder wiederholt eine Permutation eines anderen ... ... es ist auch alles so organisiert, dass nichts vergessen werden kann!!! ... wir setzen an: eine Minute: 60 Sekunden (also auch 60 geprüfte Permutationen!) eine Stunde: 60 Minuten - ergo 3600 Sekunden der Tag 24 Stunden - ergo 86400 Sekunden 365 Tage - macht ergo 31536000 Sekunden im Jahr zum besseren Lesen: 31.536.000 Sekunden im Jahr ... wir haben 80.000.000 Einwohner: bedeutet: 80000000 × 31536000 Versuche pro Jahr für alle beteiligten Einwohner - und das sind bekanntlich alle!!! keine Pausen, keine Wiederholungen, keine Fehler macht 2522880000000000 getestete Permutationen pro Jahr ... zum besseren Denken: 2.522.880.000.000.000 ... wir sprechen also von einer 17stelligen Zahl ... Schlussrechnung: das Vorgenannte bedeutet: 403291461126605635584000000 : 2522880000000000 ergibt die Anzahl der Jahre - und das sind: 1598536042644,1433424657534246575 wir vernachlässigen die Nachkommastellen und erhalten 1598536042644 ... ich setze mal ein paar Tausender-Punkte: 1.598.536.042.644 ... Fazit: das Universum existiert nach neuesten Betrachtungen rund 16 Milliarden Jahre also 16.000.000.000 wir berechnen mal ganz kurz die Anzahle der "Existenzen" des Universums bis zum heutigen Tag nach unseren Erkenntnissen: das sind dann 1598536042644 : 16000000000 = 9,9908502665 ... einigen wir uns auf rund 10!!! ... Fazit: das englische Alphabet umfasst 26 Zeichen - nicht eben viel!!! zur Erfassung aller möglichen Permutationen ohne zulässige Wiederholungen benötigen wir unter den genannten Bedingungen 10 Mal so lange, wie das Universum derzeit existiert - für einen Brute Force-Angriff eine gewaltige Dimension ... trotzdem bleibt die "Restchance", das Melory zufällig das korrekte Zeichenmuster anwendet, aber die ist faktisch in der Realität bereits hier gleich 0!!!
	... 26 klingt ja nun wirklich nicht nach gerade viel - wenn wir allerdings die Funktion 2626 dazu betrachten wird das astronomisch gigantisch ... ... wir lassen das englischsprachige Alphabet unter folgenden Bedingungen permutieren ... 26 Buchstaben des Alphabets - alle Wiederholungen der Zeichen sind zugelassen ... ... es gilt also 2626 = 6,1561195802071573107966742884002e+36 ... nicht mehr ganzzahlig mit unseren Bordmitteln darstellbar ... wir sprechen also von einer 37stelligen Zahl!!! ... die Bundesrepublik Deutschland hat derzeit geschätzte 80 Mio. Einwohner (vom Säugling bis zur Oma) und alle machen mit (das sind also nicht gerade wenige)... ,,, es gibt kein Wochenende - wir schlafen nicht mehr und wir machen keinen Urlaub - das Jahr hat durchschnittlich 365 Tage ... jeder erledigt eine Permutation pro Sekunde (es ist nicht Gegenstand der Diskussion, wie wir das technisch organisieren), keiner macht Fehler und/oder wiederholt eine Permutation eines anderen ... ... es ist auch alles so organisiert, dass nichts vergessen werden kann!!! ... wir setzen an: eine Minute: 60 Sekunden (also auch 60 geprüfte Permutationen!) eine Stunde: 60 Minuten - ergo 3600 Sekunden der Tag 24 Stunden - ergo 86400 Sekunden 365 Tage - macht ergo 31536000 Sekunden im Jahr zum besseren Lesen: 31.536.000 Sekunden im Jahr ... wir haben 80.000.000 Einwohner: bedeutet: 80000000 × 31536000 Versuche pro Jahr für alle beteiligten Einwohner - und das sind bekanntlich alle!!! macht 2522880000000000 getestete Permutationen pro Jahr ... zum besseren Denken: 2.522.880.000.000.000 ... wir sprechen also von einer 17stelligen Zahl ... Schlussrechnung: das Vorgenannte bedeutet: 6,1561195802071573107966742884002e+36 : 2522880000000000 ergibt die Anzahl der Jahre - und das sind: 2440115891444364104038,5092784438 wir vernachlässigen die Nachkommastellen und erhalten 2440115891444364104038 ... ich setze mal ein paar Tausender-Punkte: 2.440.115.891.444.364.104.038 ... Fazit: das Universum existiert nach neuesten Betrachtungen rund 16 Milliarden Jahre also 16.000.000.000 wir berechnen mal ganz kurz die Anzahl der "Existenzen" des Universums bis zum heutigen Tag nach unseren Erkenntnissen: das sind dann 1598536042644 : 16000000000 = 152507243215,272756502375 rund: 152507243215 - 152.507.243.215 ... einigen wir uns auf rund 152.507.243.215!!! ... Fazit: das englische Alphabet umfasst 26 Zeichen - ist nicht eben wirklich viel!!! zur Erfassung aller möglichen Permutationen mit zugelassenen Wiederholungen benötigen wir unter den genannten Bedingungen 152 Milliarden Mal so lange, wie das Universum derzeit existiert - für einen Brute Force-Angriff eine doch etwas große Dimension ... trotzdem bleibt die "Restchance", das Melory zufällig das korrekte Zeichenmuster anwendet!!!

4. Permutationen von Elementen einer Menge an Beispielen

	Klar, verwende ich als Geocacher einfach einmal ein paar Geocache-Beispiele zur Demonstration des Anliegens sowie natürlich auch zur Darstellung des Faktes, dass Unbedarfte hiermit für eigentlich kleine Probleme doch auch gefordert werden ;-)
	CHATUHEIS HAUSTEICH oder auch TEICHHAUS
	NONSENGENT ENTENSONNG ;-)    passt auf: NONNENTSEG
	GERNEVIE ;-)    passt auf: VIGENIER
	FORTEBAU ;-)    passt auf: BEAUFORT FOUTBEAR

5. Software-Lösungen

	Programmtechnisch gibt es an dieser Stelle schon mal zwei Möglichkeiten: Zufalls-Kombinationen suchen oder systematisch alle Kombinationen. Dazwischen liegen größenabhängig allerdings Welten - vor allem der Aufwand
	Permutation von acht definierten Zeichen via Zufallsgenerator Permutation von acht definierten Zeichen via System-Repeater

6. Verwandte Themen

	Überall ist es mir bisher eigentlich gelungen, zu den Verwandtschaften einen dummen Satz zu schreiben, welcher in etwa auch den Kern des Problems trifft - geht hier nicht - 's gibt keinen. Der Begriff ist derart zentral und so absolut unklar, dass es einfach keinen Blödsinn gibt, um ihn zu beschreiben. Und nun ist eigentlich wirklich alles irgendwie mit diesem Begriff verwandt.
	Bereich Begriffswelt der Informatik Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching
	Bereich Kryptologie Grundlagen der Kryptologie Allgemeines zur Verschlüsselung Steganografie CÄSAR-Chiffre Vigenère-Chiffre der Babbage bzw. Kasiski-Test Angriff auf den ENIGMA-Chiffre: Projekt ULTRA- oder Shark
	Problemstellungen aus dem Bereich der Informatik Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Zufall und Computer Graphentheorie Petri-Netze Rekursion

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 8. Dezember 2008