Gestern kam eine Mail der GI rein:

Liebe Studierende in der GI,

wo anders als im ehrlichen Wettkampf kann man seine Fähigkeiten und
Fertigkeiten zur Schau stellen, sich selbst und anderen beweisen, was man
kann. Noch mehr Spass bringt dabei das Mannschaftsspiel oder auch die
Teamarbeit. Die "schönste" (Teil-)Definition von Teamarbeit ist diese:

In Unternehmen hat Teamarbeit inzwischen weithin Fuß gefasst. Dies ist
begründet damit, dass auf Grund wachsender Komplexität, höheren
Leistungsdrucks und immer besseren Zugangs zu Informationen mittels der
Verbreitung elektronischer Medien in den Betrieben
• das Management immer weniger Überblick über die Geschehnisse hat und
• Entscheidungsverantwortung nach unten delegiert wird.

(Quelle: Wikipedia)

Zum Stellenwert der Teamarbeit im Fach Informatik beachten Sie bitte
folgende (Google-) Hitliste:

teamarbeit +definition +informatik = 121.000 Treffer
teamarbeit +definition +mathematik = 158.000 Treffer
teamarbeit +definition +physik = 108.000 Treffer
teamarbeit +definition +maschinenbau = 98.000 Treffer

So schlecht stehen wir also in der Informatik gar nicht da. Dennoch kann man
ja üben, z.B. in unserem Studierendenwettbewerb informatiCup, der ein reiner
Teamwettbewerb ist. Einzelbewerbungen werden nicht angenommen. Der
informatiCup 2007 der GI richtet sich an eingeschriebene Studierende aller
Semester und aller Fachrichtungen an Universitäten und Fachhochschulen in
Deutschland, Österreich und der Schweiz. Er findet in diesem Jahr zum
dritten Mal statt. Dieser Wettbewerb soll Studierende herausfordern, sich
eigenständig in neue Technologien einzuarbeiten und aus dem erarbeiteten
Wissen in Teamarbeit (zwei bis höchstens vier Personen) Problemlösungen zu
entwickeln. Zur Lösung der Aufgabenstellung ist theoretisches Wissen, die
Fähigkeit zum eigenständigen Arbeiten sowie die Beherrschung moderner
Softwaretechniken erforderlich. Die Preise für die besten Teams stifetet die
Deutsche Bank. Die Aufgaben sind online auf <www.informaticup.de> zu finden.

Apropos Shubidua. Ich hätte noch eine Trainingsaufgabe für Sie ganz allein,
gewissermaßen als Eignungstest. Die Aufgabe kommt aus einem Projekt des
Bundeswettbewerbs Informatik, dem Informatik-Biber <www.informatik-biber.de>
(11. - 13. Klasse, schwer):

Noamesisch

Auf der kleinen Insel Noam sprechen die Eingeborenen eine ganz besondere
Sprache. In langjähriger Arbeit konnte eine Sprachforscherin folgendes
feststellen:

   1. Es gibt die Wörter ba, di und du.
   2. Durch Verdopplung eines Worts entsteht ein neues Wort; Beispiel: baba.
   3. Ein neues Wort entsteht auch, indem ein Wort vorne und hinten an ein
anderes Wort angefügt wird; Beispiel: baduba

Als sie versuchte, mit den Noamesen zu reden, funktionierte das ganz gut,
doch bei einem der folgenden Worte zuckten die Noamesen nur verständnislos
mit den Achseln.

Bei welchem?

A) dudubabadudubabadudu
B) didudubadududi
C) dudubadibadibadu
D) dididudidibadibadididudidi

Wenn Sie es geschafft haben, suchen Sie sich Mitstreiterinnen und
Mitstreiter, wir sehen uns dann hoffentlich im Rahmen der
Schlusspräsentationen der besten Teams am 14./15. Mai in Bonn. Der
Wettbewerb ist auch offen für Nicht-Mitglieder. Machen Sie an Ihrer
Hochschule gerne ein wenig Werbung für den Wettbewerb.

Mit freundlichen Grüßen

Ludger Porada
——————————————–
Gesellschaft fuer Informatik e.V. (GI)
Wissenschaftszentrum
Ahrstrasse 45
D-53175 Bonn
Tel.: +49(0)228/302-146 / Fax: +49(0)228/302-167
ludger.porada@gi-ev.de
WWW: <http://www.gi-ev.de/>
Geschaeftsstelle:
Tel.: +49(0)228/302-145 / Fax: -167 / e-mail: gs@gi-ev.de
——————————————–

Und wer zuerst eine kontextfreie Grammatik für Noamesisch
angibt, bekommt ein Lob und darf sich einmal freuen [28]

Uuuh, das mit den Grammatiken ist echt lange her. Geht das wirklich mit einer kontextfreien Grammatik? Ich wüsste noch nichteinmal mehr wie man die Sprache [latex]L:=\{ww|w\in\Sigma^*\}[/latex] als kontextfreie Grammatik ausdrückt (kann mich nur an [latex]w\overline{w}[/latex] erinnern) – man, ohne Übung vergisst man sowas wirklich schnell.

Wie dem auch sei. Die erste Aufgabe klingt ja ganz witzig. Hätte direkt Lust mich ranzumachen, wenn ich nicht für die blöde Quantenphysik-Prüfung lernen müsste …

Uuuh, das mit den Grammatiken ist echt lange her. Geht das wirklich mit einer kontextfreien Grammatik?

Ja, die Sprache ist einfacher als die obigen Regeln zuerst vermuten lassen [15]

Ich wüsste noch nichteinmal mehr wie man die Sprache [latex]L:=\{ww|w\in\Sigma^*\}[/latex] als kontextfreie Grammatik ausdrückt (kann mich nur an [latex]w\overline{w}[/latex] erinnern) – man, ohne Übung vergisst man sowas wirklich schnell.

Also [latex]\{ww\mid w\in\Sigma^*\}[/latex] ist auch nicht kontextfrei (man schneide
einmal mit a*b*a*b* und wende auf das Ergebnis das Pumping-Lemma an).

Wie dem auch sei. Die erste Aufgabe klingt ja ganz witzig. Hätte direkt Lust mich ranzumachen, wenn ich nicht für die blöde Quantenphysik-Prüfung lernen müsste …

Hm, schade. Aber es ist ja noch bis zum 15. Januar Zeit!

Uuuh, das mit den Grammatiken ist echt lange her. Geht das wirklich mit einer kontextfreien Grammatik?

Ja, die Sprache ist einfacher als die obigen Regeln zuerst vermuten lassen [15]

Argh, ja, hast Recht.

Also [latex]\{ww\mid w\in\Sigma^*\}[/latex] ist auch nicht kontextfrei (man schneide
einmal mit a*b*a*b* und wende auf das Ergebnis das Pumping-Lemma an).

Dachte ich mir doch, dass meine Erinnerung hier korrekt war. Aber ich habe mich zu sehr auf die Regeln verbissen. Mir scheint, als sei die Lösung das von mir oben erwähnte Paradebeispiel einer kontextfreien Grammatik.

Wie dem auch sei. Die erste Aufgabe klingt ja ganz witzig. Hätte direkt Lust mich ranzumachen, wenn ich nicht für die blöde Quantenphysik-Prüfung lernen müsste …

Hm, schade. Aber es ist ja noch bis zum 15. Januar Zeit!

Hast du vor mitzumachen? Oder anders gefragt: Hast du schon heimlich alle Aufgaben gelöst? [15]

Dachte ich mir doch, dass meine Erinnerung hier korrekt war. Aber ich habe mich zu sehr auf die Regeln verbissen. Mir scheint, als sei die Lösung das von mir oben erwähnte Paradebeispiel einer kontextfreien Grammatik.

Ja, genau (abgesehen davon, dass auch die Palindrome ungerader Länge dabei sind) [23]

Hast du vor mitzumachen? Oder anders gefragt: Hast du schon heimlich alle Aufgaben gelöst? [15]

Ich hab leider im Moment keine Zeit [19] und außerdem hab ich ja
schonmal teilgenommen… [25]

Aber ich kenne da jemanden, der sehr gerne mitmachen will und den
die erste Aufgabe auch interessieren würde. Soll ich mal den Kontakt
herstellen? (Er studiert Physik und liest hier nicht mit.)

Aber ich kenne da jemanden, der sehr gerne mitmachen will und den
die erste Aufgabe auch interessieren würde. Soll ich mal den Kontakt
herstellen? (Er studiert Physik und liest hier nicht mit.)

Wie gesagt, habe ich derzeit ja auch keine Zeit. Dann geht auch schon bald das nächste Semester los. Wenn ich da genug Zeit finde, werde ich drauf zurückkommen ;-)

Ist die Grammatik wirklich kontextfrei? Also eindeutig bestimmt nicht. Das ist schon ein tolles Volk, das bei einer solchen Grammatik nicht durcheinanderkommt. Aber das ist ja im Deutschen auch nicht viel anders. ;)

Die Katze fängt die Maus.

Und wenn man zwei Jahre lang kein Prolog mehr gesehen hat, dauert die Lösung halt seine Zeit. Aber es ist elegant geworden.

Roland

Ist die Grammatik wirklich kontextfrei? Also eindeutig bestimmt nicht. Das ist schon ein tolles Volk, das bei einer solchen Grammatik nicht durcheinanderkommt. Aber das ist ja im Deutschen auch nicht viel anders. ;)

Also für die Menge der Palindrome (das ist ja im wesentlichen Noamesisch) gibt es eine
eindeutige kontextfreie (sogar lineare) Grammatik. Die eindeutige lineare Grammatik für
Noamesisch sieht dann entsprechend so aus:
S -> baSba | diSdi | duSdu | baba | didi | dudu | ba | di | du

Die Katze fängt die Maus.

Und wenn man zwei Jahre lang kein Prolog mehr gesehen hat, dauert die Lösung halt seine Zeit. Aber es ist elegant geworden.

Die Katze fängt die Maus? Ich hätte jetzt eher Sachen erwartet wie "Dracula's Alu-Card" oder "Gnutötung"… [25]

Ist die Grammatik wirklich kontextfrei?

Also für die Menge der Palindrome (das ist ja im wesentlichen Noamesisch) gibt es eine
eindeutige kontextfreie (sogar lineare) Grammatik. Die eindeutige lineare Grammatik für
Noamesisch sieht dann entsprechend so aus:
S -> baSba | diSdi | duSdu | baba | didi | dudu | ba | di | du

Oh, jetzt bin ich beleidigt. Mit ein bißchen Nachdenken und einem simplen strukturellen Beweis hätte ich auch selbst drauf kommen können. Bis eben wollte ich noch behaupten, dass es auch noamesische Wörter gibt, die keine Palindrome sind, aber das ziehe ich lieber zurück. :)

Mit der eindeutigen Grammatik hast Du jedoch unrecht, wenn Du damit meinst, dass jedes gültige Wort genau eine mögliche Ableitung hat.

% -*-prolog-*- % % Quelle: http://www.informatik-biber.de/aufgaben/aufgaben_senior.html % % In der noamesischen Sprache gibt es nur drei Silben, aus denen jedoch % komplizierte Wörter gebildet werden können. % silbe(du). silbe(ba). silbe(di). % wort(+Liste von Silben, -Ableitungsbaum). % % Prüft, ob die Liste von Silben ein gültiges Wort der noamesischen % Sprache ist und gibt den Ableitungsbaum der Grammatik zurück. % % Es gibt drei mögliche Ableitungen: eine einfache Silbe wird durch sich % selbst dargestellt, eine Verdoppelung eines Wortes durch den Term % 2(Wort, Wort) und ein Einschluss eines Wortes von zwei anderen Wörtern, % die aber gleich sind, wird durch den Term 3(Links, Mitte, Rechts) % dargestellt, wobei Links und Rechts gleich sind. % wort([S], S) :- silbe(S). wort(S, '2'(TA, TA)) :- append(A, A, S), A \= [], wort(A, TA). wort(S, '3'(TA, TB, TA)) :- % Die Reihenfolge der append()s ist wichtig, damit Prolog nicht in eine % Endlosschleife gerät. Mit diesem ersten append werden AB und A schon % mal auf ein Präfix bzw. Suffix von S beschränkt und sind damit voll % instanziiert. append(AB, A, S), AB \= [], A \= [], wort(A, TA), append(A, B, AB), A \= [], B \= [], B \= A, wort(B, TB). test(S) :- write(S), write(':'), nl, (wort(S, Tree), write(' '), write(Tree), nl, fail ; true). main :- test([du,du,ba,ba,du,du,ba,ba,du,du]), test([di,du,du,ba,du,du,di]), test([du,du,ba,di,ba,di,ba,du]), test([di,di,du,di,di,ba,di,ba,di,di,du,di,di]).
[edit: Tabs durch Leerzeichen ersetzt, damit die Einrückung stimmt.]

Mit der eindeutigen Grammatik hast Du jedoch unrecht, wenn Du damit meinst, dass jedes gültige Wort genau eine mögliche Ableitung hat.

Hmm, gib doch mal ein Beispiel?

Ein A \= [] kannst Du bei Deinem Code noch einsparen. Und das B \= A bei Dir finde ich interessant, da hatte ich die Aufgabenstellung anders gelesen (und Georg wohl auch). Kann man aber durchaus so lesen wie Du. Ansonsten eine hübsche Lösung. Ich mag Prolog [23]

Mit der eindeutigen Grammatik hast Du jedoch unrecht, wenn Du damit meinst, dass jedes gültige Wort genau eine mögliche Ableitung hat.

Hmm, gib doch mal ein Beispiel?

Hast Du das Programm mal laufengelassen? Allein an der Art, wie ich die Ausgabe aufbereitet habe, sieht man schon, dass es mehrere Varianten geben kann. Zum Beispiel:
[di, du, du, ba, du, du, di]: 3(di, 3(2(du, du), ba, 2(du, du)), di) 3(di, 3(du, 3(du, ba, du), du), di)

Ein A \= [] kannst Du bei Deinem Code noch einsparen.

Ich weiß, aber ich hatte beim Schreiben mehr auf strukturelle Gleichförmigkeit als auf Effizienz geachtet. :)

Und das B \= A bei Dir finde ich interessant, da hatte ich die Aufgabenstellung anders gelesen (und Georg wohl auch). Kann man aber durchaus so lesen wie Du. Ansonsten eine hübsche Lösung. Ich mag Prolog [23]

Und gerade durch meine Lesart sind nicht alle Palindrome auch gleich noamesisch, so dass die Grammatik auch nicht kontextfrei ist.

die Menge der Palindrome (das ist ja im wesentlichen Noamesisch)

Wie das denn Georg?
'baba' ist noamesisch und doch wahrlich kein Palindrom.
Auch 'badiba' ist kein Palindrom und dennoch noamesisch….
Ich bin verwirrt.

Hast Du das Programm mal laufengelassen? Allein an der Art, wie ich die Ausgabe aufbereitet habe, sieht man schon, dass es mehrere Varianten geben kann. Zum Beispiel:

Die Darstellung mit der noamesischen Grammatikdefinition hat genausowenig mit der Eindeutigkeit von Georgs Grammatik zu tun wie irgend ein Prolog-Programm zum Erzeugen der Wörter.

Es zählt hier nur, dass kein abgeleitetes Wort in der kontextfreien Grammatik von Georg
zwei verschiedene Linksableitungen (also auch verschiedene Ableitungsbäume) besitzt!
Warum diese Grammatik denn nun wirklich korrekt ist ist dann noch zu zeigen/zu begründen!

die Menge der Palindrome (das ist ja im wesentlichen Noamesisch)

'baba' ist noamesisch und doch wahrlich kein Palindrom.
Auch 'badiba' ist kein Palindrom und dennoch noamesisch….

Ich vermute georg bezieht das mit den Palindromen auf die Silben, daher wäre [ba][ba] ein Palindrom genauso wie [ba][di][ba]

die Menge der Palindrome (das ist ja im wesentlichen Noamesisch)

Wie das denn Georg?
'baba' ist noamesisch und doch wahrlich kein Palindrom.
Auch 'badiba' ist kein Palindrom und dennoch noamesisch….
Ich bin verwirrt.

Genau, ich meinte das, was DualJ sagte. Sind P die Palindrome
(außer dem leeren Wort) über a,b,c und h der Hom. mit h(a)=ba,
h(b)=di, h( c)=du, dann ist Noamesisch genau h(P).

Dass jedes noamesische Wort in h(P) ist, sieht man an den Regeln aus
der Aufgabe. Sind nämlich v und w Palindrome, dann ja auch vwv und
ww. Umgekehrt kann man mit diesen Regeln jedes Wort aus h(P) ableiten
(für die Palindrome ungerader Länge braucht man nur die Regel
v,w => vwv und für die Palindrome gerader Länge nimmt man einmal
w => ww, um baba,didi,dudu abzuleiten und dann wieder v,w => vwv
für den Rest).

Die Darstellung mit der noamesischen Grammatikdefinition hat genausowenig mit der Eindeutigkeit von Georgs Grammatik zu tun wie irgend ein Prolog-Programm zum Erzeugen der Wörter.

Na schön, dann habe ich halt genauso schlecht formuliert wie Georg etwas weiter oben. Einigen wir uns auf ein Unentschieden? ;)

Roland

'baba' ist noamesisch und doch wahrlich kein Palindrom.
Auch 'badiba' ist kein Palindrom und dennoch noamesisch….
Ich bin verwirrt.

Natürlich ist "baba" ein Palindrom. In der noamesischen Sprache sind die Grundelemente jeden Wortes die Zeichen "ba", "di" und "du". Da ein alleinstehendes "i" für Noamesen deshalb keine Bedeutung hat, ist es auch kein Zeichen. Menschen, die an das lateinische Alphabet mit Umlauten gewöhnt sind, also insbesondere Deutsche, sehen ein "Ü" ja auch als ein Zeichen und trennen nicht die Punkte (U+0308) von dem darunterstehenden Bogen (U+0055). Genauso komisch wäre es, wenn man im Japanischen die Zeichen in ihre Radikale aufteilt und dann erst zu lesen beginnt. ;)

Roland