Komplexität und Komplexitätsklassen

Letztmalig dran rumgefummelt: 27.08.26 09:27:21

	Die Primzahlen sind Klassiker der Mathematik und auch für findige Algorithmen in der Informatik eine erste Adresse :-) International laufen sich Computer heiß, werden neue, und vor allem effizientere Algorithmen gesucht, welche die Forschung nach weiteren, vor allem sehr großen Primzahlen beschleunigen sollen und hoffen vor allem Kryptologen, dass dies nicht so schnell gelingen möge.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Komplexität, Mächtigkeit und Aufwand Logo für die Komplexität inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Basiswissen der Informatik Wissen für Fortgeschrittene der Informatik
	Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff.

1. Problembeschreibung

	Es gibt keine Periodizität und kein Muster in den Primzahlen. Soviel ist sicher, der Anteil der Primzahlen unter den ersten N natürlichen Zahlen sinkt mit steigendem N. Unter den ersten 100 natürlichen Zahlen gibt es 25 Primzahlen (25%), unter den ersten 1000 sind es 168 (16.8%), unter den ersten 100000 sind es 9592 (9.6%) und unter den ersten 10 Millionen sind es 664759 Primzahlen (6.65%).
	bei einer ganzen Reihe der nun folgenden Probleme stoßen wir auf die Klasse der NP-vollständige sowie NP-schwere Probleme - unbedingt vorab dazu informieren, was das ist und welche Aufgaben da auf uns zukommen
	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich - Beispiel: M = {-11, -9, -5, -3, 2, 4, 13,21, 23} Antwort: JA - nämlich für die Teilmenge m = {-11, -9, -5, 2, 23}

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten.
	linearer Aufwand (propoertionaler Aufwand) logarithmischer Aufwand quadratischer Aufwand exponetieller Aufwand
	Ein komplexer Algorithmus ist eine präzise, mathematisch fundierte Schrittfolge zur Lösung anspruchsvoller Probleme, die sich durch nicht-triviale mathematische Strukturen, ressourcenintensive Berechnungen oder fortgeschrittene Entwurfsprinzipien auszeichnet. In der Informatik wird die "Komplexität" primär über die O-Notation (Zeit- und Speicherplatzbedarf bei steigender Eingabemenge) oder über die strukturelle Kompliziertheit definiert.
	1. Graphen- und Netzwerkalgorithmen Diese Verfahren lösen Optimierungs- und Routingprobleme in vernetzten Strukturen, wie sie in sozialen Netzwerken, Navigationssystemen oder dem Internet vorkommen. Dijkstra- & A*-Algorithmus: Finden den kürzesten Pfad in gewichteten Graphen (Einsatz in Navigationssystemen). Ford-Fulkerson-Algorithmus: Berechnet den maximalen Fluss in einem Transportnetzwerk. PageRank-Algorithmus: Bewertet die Relevanz von verknüpften Dokumenten anhand der Graphenstruktur (Fundament der Google-Suche)
	2. Kryptographische Algorithmen Sie sichern Daten und Kommunikation durch komplexe mathematische Einwegfunktionen und Primzahltheorie ab. RSA-Verschlüsselung: Asymmetrisches Verfahren, das auf der Schwierigkeit der Faktorisierung großer Primzahlen beruht. AES (Advanced Encryption Standard): Symmetrische Blockverschlüsselung, die auf komplexen Permutationen und Substitutionen (Substitution-Permutation-Netzwerk) basiert. Diffie-Hellman-Schlüsselaustausch: Ermöglicht einen sicheren Austausch von kryptographischen Schlüsseln über einen unsicheren Kanal via diskretem Logarithmus.
	3. Fortgeschrittene Sortier- und Suchverfahren Während einfache Sortierverfahren quadratischen Aufwand (O(n²)) haben, nutzen komplexe Verfahren das Divide-and-Conquer-Prinzip, um hocheffizient zu arbeiten. Quicksort & Mergesort: Sortieren große Datenmengen in optimaler Zeit von \(O(n \log n)\). Binäre Suchbäume (z. B. AVL-Bäume, Rot-Schwarz-Bäume): Selbstbalancierende Bäume, die garantieren, dass Suchen, Einfügen und Löschen immer in logarithmischer Zeit (\(O(\log n)\)) erfolgen.
	4. Algorithmen der Künstlichen Intelligenz (KI) und Optimierung Diese Algorithmen verarbeiten gigantische Datenmengen, um Muster zu erkennen oder nahezu optimale Lösungen für extrem schwere (NP-schwere) Probleme zu finden. Backpropagation-Algorithmus: Berechnet die Gradienten in neuronalen Netzen, um die Gewichte beim maschinellen Lernen anzupassen. Genetische Algorithmen: Evolutionäre Optimierungsverfahren, die Prinzipien der Natur (Mutation, Selektion, Rekombination) nutzen, um komplexe Suchräume zu durchforsten.Transformer-Architekturen (z. B. Self-Attention): Verarbeiten Sequenzen parallel und gewichten die Relevanz einzelner Elemente zueinander (Basis moderner Sprachmodelle).
	5. Komplexitätsklassen: Wann wird ein Problem "komplex"? In der theoretischen Informatik teilt man Probleme nach ihrer inhärenten Schwierigkeit auf: Klasse Beschreibung Beispiel P In polynomieller Zeit lösbar (schnell/effizient) Sortieren einer Liste NP Lösung ist schwer zu finden, aber in polynomieller Zeit überprüfbar Sudoku-Rätsel lösen NP-schwer Mindestens so schwer wie die schwersten Probleme in NP Das Problem des Handlungsreisenden (TSP)

3. Lösungsalgorithmus

Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 25. Dezember 2007