Das k-Next-Neighbor-Problem - oder: sage mir, wo Du wohnst und ich sage Dir, wer Du bist

Letztmalig dran rumgefummelt: 17.08.26 10:05:38

	Maschinelles Lernen (ML) ist ein zentraler Teilbereich der künstlichen Intelligenz. Dabei entwickeln Computer eigenständig Muster und Regeln aus Beispieldaten, anstatt starr nach vorgegebenen Programmierungsregeln zu arbeiten. Die Algorithmen nutzen große Datenmengen, um Vorhersagen oder Entscheidungen für neue, unbekannte Daten zu treffen.
	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
	Probleme & Problemlösungsverfahren   Logo für das k-Next-Neighbor-Problem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff.

1. Problembeschreibung

	Grundlagen und Funktionsweise: Stichpunkt Daten als Basis: Statt Code schreiben Menschen Trainingsdaten in das System. Stichpunkt Mustererkennung: Algorithmen suchen nach statistischen Zusammenhängen und Gesetzmäßigkeiten. Stichpunkt Modellbildung: Das Ergebnis des Trainings ist ein funktionierendes Modell für Vorhersagen? Wichtigste Arten des Lernens: Stichpunkt Überwachtes Lernen: Das System bekommt Daten mit den passenden Lösungen vorgegeben (z. B. Bilder mit dem Label „Katze“). Stichpunkt Unüberwachtes Lernen: Das System sucht eigenständig nach Strukturen in unbeschrifteten Daten. Stichpunkt Verstärkendes Lernen: Ein Agent lernt durch Belohnung und Bestrafung (Versuch und Irrtum). Typische Anwendungsbereiche: Stichpunkt Empfehlungsdienste: Vorschläge für Filme oder Produkte bei Online-Händlern. Stichpunkt Bild- und Spracherkennung: Erkennung von Personen auf Fotos oder Sprachbefehle am Smartphone. Stichpunkt Betrugserkennung: Automatisches Aufspüren unüblicher Kreditkartenzahlungen.
	Binäre Bäume bei WIKIPEDIA
	Maschinelles Lernen funktioniert, indem Computer mithilfe von mathematischen Algorithmen Muster in großen Datenmengen erkennen, statt starr programmiert zu werden. Ein System wird mit Beispielen trainiert, vergleicht seine Ergebnisse mit den richtigen Antworten, korrigiert seine Fehler und trifft so eigenständig Vorhersagen für neue Daten.
	Der Ablauf des Lernens: Stichpunkt Datensammlung: Der Computer erhält viele Beispiel-Daten (wie Bilder, Texte oder Zahlenwerte). Stichpunkt Training: Ein Algorithmus sucht nach Regeln und Zusammenhängen in den Daten. Stichpunkt Korrektur: Das System prüft seine Ergebnisse und passt sich an, um Fehler zu verringern. Stichpunkt Anwendung: Das fertige Modell wendet das gelernte Wissen auf neue, unbekannte Aufgaben an.

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.

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. Mai 2026 um 18.36 Uhr