Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 23. November 2001
Christian Ehrhardt Blatt 7






Allgemeine Informatik 3 (WS 2001/2002)


Abgabetermin 11.12.2001 vor den Übungen

A conjecture both deep and profound
Is whether the circle is round.
In a paper of Erdös
Written in Kurdish
A counterexample is found.

Erdös

Der ungarische Mathematiker Paul Erdös (gestorben 1996) war einer der produktivsten und wohl der exzentrischste Mathematiker aller Zeiten. In den 83 Jahren seines Lebens veröffentlichte er 1475 wissenschaftliche Arbeiten und ein Mathematiker fühlte sich geehrt, wenn er die Gelegenheit hatte mit ihm zusammen eine Arbeit zu publizieren. Wem diese Ehre nicht vergönnt ist, der muß sich damit begnügen, mit jemandem zu publizieren, der mit Erdös publiziert hat.
Daraus entwickelte sich das Konzept der Erdöszahl eines Mathematikers: Erdös selbst hat als einziger die Erdöszahl $0$. Alle, die mit ihm publiziert haben, haben die Erdöszahl $1$. Diejenigen, die mit jemandem publiziert haben, der mit Erdös publiziert hat haben Erdöszahl $2$ usw.
Eure Aufgabe ist es, ein Programm zu schreiben, das eine Liste von Veröffentlichungen und deren Autoren einliest und dann für alle vorkommenden Autoren die Erdöszahl bestimmt. Dabei kann durchaus auch $\infty$ vorkommen.
Um das ganze etwas einfacher zu gestalten sieht die Eingabedatei so aus:

• Die erste Zeile enthält eine Zahl $N$, die angibt wieviele Autoren insgesamt vorkommen.
• Die nächsten $N$ Zeilen enthalten die Namen der vorkommenden Autoren (weniger als 50 Zeichen ohne Leerzeichen dazwischen). Der erste dieser Autoren bekommt die laufende Nummer $0$, der nächste die Nummer $1$, usw. Ihr könnt davon ausgehen, daß Erdös immer am Anfang dieser Liste steht, also die laufende Nummer 0 hat.
• Anschließend folgt wieder eine Zeile mit der Zahl $P$ der Veröffentlichungen in diesem Beispiel.
• Die restlichen $P$ Zeilen enthalten je eine Veröffentlichung. Die Beschreibung einer solchen Veröffentlichung besteht aus dem Titel (ein Wort ohne Leerzeichen) gefolgt von den laufenden Nummern der daran beteiligten Autoren. Ihr könnte davon ausgehen, daß keine Veröffentlichung mehr als 30 Autoren hat.

Anleitung

Zunächst empfiehlt es sich eine Datenstruktur für einen Autor zu entwerfen, die folgende Informationen enthält:

• Den Namen des Autors und ev. seine laufende Nummer $k$.
• Die Menge der laufenden Nummern aller Autoren mit denen zusammen er publiziert hat. Dafür könnt Ihr auf die Lösung des letzten Blattes zurückgreifen.
• Die Erdöszahl des Autors bzw. die Information, daß die Erdöszahl noch nicht bekannt ist.

Die Menge aller Autoren mit Erdöszahl $0$ enthält dann nur Erdös. Die Menge aller Autoren mit Erdöszahl $1$ enthält alle, die mit jemandem mit Erdöszahl $0$ publiziert haben, außer Erdös selbst. Die Menge aller Autoren mit Erdöszahl $2$ enthält alle, die mit jemandem mit Erdöszahl $1$ publiziert haben, es sei denn es wurde für denjenigen bereits eine Erdöszahl von $0$ oder $1$ errechnet. So kann man fortfahren, bis man in einem Schritt niemand neues mehr findet. Alle verbliebenen Autoren haben Erdöszahl $\infty$. Auch für diese Mengen kann wieder die Lösung des letzten Blattes verwendet werden.

Mehr über Erdös

Der folgende Text ist ein Auszug aus dem Buch ``The man who loved only numbers'' von Paul Hoffmann. Mehr Informationen liefert auch http://www.paulerdos.com. Die Wiedergabe des Texts erfolgt mit freundlicher Genehmigung des Autors.

Erdös (pronounced ``air-dish'') structured his life to maximize the amount of time he had for mathematics. He had no wife or children, no job, no hobbies, not even a home, to tie him down. He lived out of a shabby suitcase and a drab orange plastic bag from Centrum Aruhaz (``Central Warehouse''), a large department store in Budapest. In a never-ending search for good mathematical problems and fresh mathematical talent, Erdös crisscrossed four continents at a frenzied pace, moving from one university or research center to the next. His modus operandi was to show up on the doorstep of a fellow mathematician, declare, ``My brain is open,'' work with his host for a day or two, until he was bored or his host was run down, and then move on to another home.