Hallo ihr Fleißigen,

ich erlaube mir zwischendurch einen Kommentar zur ProgAufg3 (d). Da geht es um Laufzeitmessungen.

Zum einen, damit kein Missverständnis herrscht: gemeint sind alle 16 Parameterkombinationen, die
die je vier Setzungen von nconn und maxrun ermöglichen. Macht das nicht per Handeingabe! Ihr werdet
sicherlich mehrere Anläufe zum Durchmessen brauchen.

Zum anderen: ja, die Kombination nconn = 80000 und maxrun = 800 rechnet wirklich eine ganze
Weile. So ist das mit Tests halt. Erst auf großen Instanzen beweist sich ein Algorithmus bzw. eine
Implementierung - oder eben nicht. Und es werden die Gewinne durch algorithmische Verbesser-
ungen so richtig greifbar.

Ich habe allerdings stichprobenweise gesehen, dass ihr noch recht freizügig mit Mehrfacharbeit in
den Methoden umgeht. Genau darum geht's gerade: wie kann man mit einem absoluten Minimum
an Aufwand das Geforderte erreichen? Von eurem Gespür das zu erkennen und zu vermeiden wird
ganz wesentlich euer Erfolg beim anstehenden Programmierprojekt abhängen!

Ich gebe euch hier zur Kontrolle die Laufzeiten meiner eigenen Implementation des Online Traffic
Monitoring auf dem SearchTree, gemessen auf einem Pool-Rechner mit 1 GHz. Solltet ihr bemerken,
dass eure Laufzeiten erkennbar darüber liegen, habt ihr noch Verbesserungsbedarf. 8-)

  nconn =  2000     10000     50000      80000
maxrun  
   20     0.1 s     0.3 s     5.0 s     33.1 s
  100     0.2 s     1.3 s    19.7 s    136.9 s
  500     0.6 s     5.0 s    86.6 s    679.5 s
  800     1.0 s     8.0 s   142.1 s   1083.1 s

Hoffe das hilft euch etwas. Dann vergleicht mal mit den Zeiten des AVL-Baums...!
Gruß von
-Martino

PS: wenn endlich technisch alles klappt, steht diese Mail im Mailarchiv unserer Homepage.

Hallo alle, die an der ProgAufg3 sitzen,

es kam mir zu Ohren einige von euch hätten beobachtet, dass der TrafficGen manchmal Runs
produziert, die um1 länger sind als maxrun.  Meine Nachforschungen haben ergeben: stimmt.
Ich habe beim Schreiben der Klasse einen intelligenten kleinen Fehler gemacht. ;-( Tatsächlich
laufen die Verbindungen auf zufälligen Längen zwischen 3 und maxrun+1.

Das stört aber nicht weiter. Nur zur Info, dass das nicht an euren Programmen liegt.

Gruß von
-Martino

Hallo ihr Fleißigen,

das CoMa-Projekt naht mit großen Schritten. Es wird euch sicher eine Menge Arbeit machen, aber sicher
ebenso viel Spaß!  >8-)

BITTE schicke mir JEDE/R von euch eine ganz kurze Mail, in der steht:

- JA, ich arbeite noch aktiv in Gruppe Nr. 1## (bitte angeben) mit und möchte das CoMa-Projekt
  mitmachen, oder
- NEIN, ich habe mich entschlossen den CoMa II-Schein nicht in diesem Semester zu erwerben.

Diesen Überblick brauche ich unbedingt, um zum Projektstart einen klaren Stand zu haben, wer
noch da und dabei ist und wer nicht. Dadurch kann ich niemanden übersehen, der evtl. noch eine
Firma braucht. Außerdem fürchte ich, dass nicht mehr alle CoMa-Gruppen drei Mitglieder haben.
Ihr solltet aber zu dritt sein, damit die Arbeitsbelastung in den Grenzen bleibt, die wir für euch
einplanen.

Hinweis: ihr könnt zum einen mit einer Dreiergruppe eine Firmenabteilung bilden. Ihr könnt aber
auch mit einer Firmenabteilung eine neue CoMa-Gruppe bilden, also den Projektanfang zur
Umstrukturierung eurer Arbeitsgruppe nutzen. Eure Wahl. Da die Anzahl der Projektteilnehmer
vermutlich kein ganzzahliges Vielfaches von 9 sein wird, werden wir manche Firmen ggf. mit 
8 oder 10 Mitarbeitern erlauben. Das bleibt aber die Ausnahme.

Die PROJEKT-HOMEPAGE ist auf der Leine, erreichbar über die CoMa-Homepage.
Dort steht die genaue Projektbeschreibung zum Download bereit. Ich erwarte, dass ihr sie alle

   --->  bis zum Kickoff gelesen  <---

habt. Wir sprechen an dem Tag noch darüber, ich kann aber unmöglich alles von vorne vorstellen.
Bildet bis zum Kickoff schon mal fleißig Firmen - umso schneller geht es dann los!


Denkt auch daran, die ProgAufg 3 rechtzeitig erfolgreich abnehmen zu lassen. Unter den
üblichen Bedingungen könnt ihr Verlängerung bekommen. Nehmt euch unbedingt vor,
zu Projektanfang den Kopf davon frei zu haben!

BIs dahin schönes Wochenende von
-Martino

Hallo ihr Gespannten,

ich habe eure Präferenzen ausgewertet. Ihr findet eure ersten Kundentermine auf der CoMa-
projektseite bei den Fotos. (Ich hoffe ich habe alle Mitarbeiter zu den richtigen Firmennamen
zugeordnet.)

Alle Kundentreffen finden statt in MA 606. Bitte seid unbedingt pünktlich!

Ihr bekommt alle noch jeweils eine Kopie eures Sitzungsprotokolls. Das gibt's zwanglos bei mir.

Schönes Wochenende!
-Martino

Hallo ihr Eifrigen,

es gibt ein paar neue Hinweise:

1) die VL am DO  9.6. fällt ja wie gesagt aus, die angekündigte UE wird auf FR verschoben.
    Dadurch findet am DO *keine* CoMa-Veranstaltung statt.

2) Die UE zur Einführung in CVS und die Grundlagen zur GUI-Programmierung wird am
    FR 10.6. zur gewohnten Zeit im gewohnten Raum statt finden. Dankenswerter Weise
    hat sich Torsten Gellert bereit erklärt, euch diese Themen vorzustellen!

3) Die Kapazität der Rechnerbetreuung wird ab MO 13.6. auf die Hälfte reduziert, da
    die Tutoren sich jetzt um je zwei Firmen zu kümmern haben. Bitte beachtet dazu
    den aktuellen Stundenplan. Die gewohnten Pool-Zeiten bleiben selbstverständlich
    weiter für euch reserviert.

4) Am DI 14.6. findet wie angkündigt keine VL statt, dafür dann die UE, die ich ursprüng-
    lich für den FR 10.6. geplant hatte. Wir werden voraussichtlich im Raum ausweichen müssen.
    Bitte beachtet dazu kurzfristig den Teil "Aktuelles" auf der Homepage.

5) Es gibt ab sofort die Spezifikation für Software zum Download von der Projektseite.
    Dieses Dokument stellt eine verbindliche Liste von Features dar, die alle Programme
    erfüllen müssen, die eine Chance beim Wettbewerb haben wollen!

6) Einige Instanzdaten stehen auch schon zur Verfügung. Die Liste wird laufend erweitert
    werden.

    Die staedte-Dateien enthalten ausgewählte Orte auf der Welt und sind nicht die Zielprobleme
    für eure Anwendung. Ich stelle sie euch als Testfamilie mit bekannten Optimalwerten zur
    Verfügung. Die richtigen Zielinstanzen sind die bohrer-Familie.

    Ich habe vor, stets die aktuell besten bekannten Lösungswerte für die Instanzen auf die Projektseite
    zu schreiben. Dazu könnt ihr jeweils nachschauen, welche beste Lösung aktuell bekannt ist und
    mir ggf. eure bessere mailen, falls ihr eine habt. Diese Aufstellung stellt sozusagen einen
    Showdown für den Stand der Entwicklung über alle Firmen hinweg dar. So etwas tun echte Firmen
    auch, um noch vor Fertigstellung eines Produktes zu zeigen, wie gut sie sind. 8-)

Viel Spaß wünscht
-Martino

Hallo ihr Fleißigen überall,

nachdem sich herumgesprochen hat, dass man mit derselben Software sowohl Platinen optimal
bohren als auch Kleingeld optimal einsammeln kann, gibt es jetzt die erste Instanz dazu auf der
Projektseite.

Bitte schaut ab jetzt immer mal wieder selbständig auf diese Seite. Ich schreibe das Datum des
letzten Updates dazu und was neu ist.

Außerdem freue ich mich auf eure ersten Lösungen! 8-> Bitte denkt daran, dass eure Dateien
genau das in der Spezifikation angegebene Format einhalten müssen, sonst arbeitet ihr in-
kompatibel zu mir. Ich werde die Einsendungen natürlich erst kontrollieren.

Schönes Wochenende von
-Martino

Hallo ihr Fleißigen überall,

es gibt wieder einen Update der Projekt-Seite: 4 frische ungelöste Instanzen der staedte-Familie!
Dazu einen neuen Graphen mit Auswahlknoten.

Ich fordere euch nochmals freundlich auf, mir eure aktuell besten Lösungen (.sol-Dateien) zu
schicken! Ich stelle ihre Kenndaten (nicht die Lösungen selbst) auf die Projektseite, sodass alle
sehen können, wie gut ihr schon seid. Image-Marketing, sozusagen. 8-) Außerdem könnt ihr
selbst schauen, wo die momentane Bestmarke liegt, um euch selbst im Rennen einzuschätzen.


Dieser Patzer mit dem Beispiel, wo die push-Technik versagen sollte, hat mir natürlich keine
Ruhe gelassen. ;-( Ich habe rausgefunden, wo's gehakt hat: in meiner Implementation dieses
Algorithmus habe ich mir alle Arrayeinträge direkt noch in der for-Schleife über alle Knoten v
ausgeben lassen, also nachdem der Wert T(v) zu allen Nachbarn gepushed wurde. Der fragliche
Update von T(3) von 5 auf 3 passierte dann in der nächsten Iteration, als der Knoten 4 sein T(4)
an den Knoten 3 pushte. Das bekam ich nur nicht mehr zu sehen...

Also OK, die vorgestellte Instanz klappt mit der Reihenfolge 0,1,...,B-1 doch noch. Ich hoffe es war
trotzdem nachvollziehbar, warum es prinzipiell nicht korrekt ist, die Knoten v in einer vorher
festgelegten Reihenfolge zu durchlaufen. In keinem ungerichteten Graphen gibt es eine kano-
nische Reihenfolge, weil man ja zumeist Kreise hat. Man ist nur dann auf der sichere Seite,
wenn man einen Knoten v mit kleinstem T(v) aussucht unter allen Knoten, die noch nicht
sicher optimal erreicht wurden (Menge U). Dieses v wird sicher durch einen optimalen Weg
erreicht, der gemäß der optimalen Teilstruktur verlängert werden darf -> das ist das push, das
dann in scan(v) passiert. (Vielleicht hätte ich diese Unterroutine gleich push(v) nennen sollen.
In der Literatur heißt sie meist scan(v).)

Findet jemand eine Instanz für das Wechselproblem mit ungerichteten Kanten, bei dem die
push-Technik mit festgelegter Reihenfolge v = 0,1,...,B-1 tatsächlich versagt? 8-)

Schönes Wochenende von
-Martino

Hallo ihr Fleißigen,

auf meine Nachfrage gaben die Tutoren an, dass die Rechnerbetreuung praktisch nicht mehr
nachgefragt wird. Daher hebe ich sie mit sofortiger Wirkung auf.

Die reservierten Rechnerzeiten bleiben aber selbstverständlich erhalten.

Viel Erfolg wüsche ich euch für die letzte Programmierwoche!
-Martino

Hallo ihr Fleißigen,

endlich: die Berliner Straßen sind online! Die sind der größte Graph für CoinCollect und die härteste Nuß.


Damit es am Dienstag zügig los gehen kann, hier schon einmal die Spielregeln für die Präsentationen:

1) Es geht unbedingt pünktlich los. Der Zeitrahmen ist bei 10 Firmen und drei Doppelstunden eben so
knapp wie er ist. (Auch in der Praxis hat ein Kunde nicht viel Zeit. Deshalb hat er eine umfangreiche
Aufgabe ja nach außen vergeben.) Die jeweils erste bzw. nächste Firma steht bitte schon mindestens
fünf Minuten vor Anfang ihres Auftritts bereit. Wenn alles gut klappt, braucht ihr nur euren Laptop
anzuschließen. Der Beamer wird bereit stehen.

2) Haltet euch nicht mit Unnötigem auf. Ihr könnt die Aufgabenstellung des Projekts als allgemein
bekannt voraussetzen. Kommt gleich zur Sache, d.h. eurer Lösung dafür. Wie gesagt sieht eine optimale
Zeiteinteilung so aus, dass ihr innerhalb von 15 Minuten sowohl euer Produkt anpreist als auch durch
gezielte Einblicke in die Ideen der Lösungsstrategien den Kunden von eurer Kompetenz überzeugt.
Die letzten 5 Minuten sind Pufferzeit, um sozusagen den letzten Satz noch zu Ende zu sprechen und
Fragen zu beantworten. Lasst möglichst wenige offen.

3) Um euch zu unterstützen werde ich euch nach 10 Minuten eine gelbe Karte hochhalten und nach
15 Minuten eine rote. Die ablaufende Zeit wird euch extrem kurz vorkommen - vertraut mir, dass es
dann wirklich schon 10 bzw. 15 Minuten sind. 8-)

4) Die Präsentation wird in mehrfacher Hinsicht bewertet werden:
    a) ist das Produkt als Softwarelösung gut präsentiert worden? Hier zählt der Vergleich.
    b) hat die Firma ihre fachliche Kompetenz gut heraus gestellt?
a) und b) gehen in die Wettbewerbsplatzierung ein.
    c) hat sich jeder Präsentator ausreichend "gezeigt"? remember: die Präsentationen sind für die
    Präsentatoren eine Scheinleistung. Wir verzichten bei denjenigen Präsentatoren auf die Projekt-
    rücksprache die vor aller Augen und Ohren ihr Engagement im Projekt hinreichend unter Beweis stellen.
    Wer nur im Wesentlichen still dabei steht oder unklare, wolkige Worte sagt, wird eine Projektrücksprache
    haben wie alle anderen auch.

Ist noch etwas unklar? Bitte fragt rechtzeitig!


Bitte denkt unbedingt daran, mir am Dienstag einen Anprechpartner zu benennen, den ich rückfragen
kann, falls die Installation eures Programms auf meinem Rechner nicht klappen sollte! Er oder sie sollte
am besten online erreichbar sein und Zugang zu sowohl Mail als auch eurem Programm in der Privat-
installation haben. 

Er oder sie darf auch gern zwischen 14-16 Uhr oder nach 20 Uhr zu mir ins Büro kommen und wir
machen das zusammen.

Ich melde jeder Firma affirmativ den Erfolg der Installation. Erst dann kann sich der Ansprechpartner
ausklinken.

Also viel Erfolg und CU!
-Martino

Hallo ihr Fleißigen,

ich bin jetzt so oft gefragt worden, dass es offenbar noch ein weiteres Missverständnis gab, was
die Spezifikation angeht: der Teil über .gra- und .nod-Dateien betrifft nur diejenigen Firmen, die
CoinCollect bearbeiten. Schließlich muss diese Schnittstelle ja geregelt sein. Alle Firmen, die
CoinCollect nicht bearbeiten, brauchen sich damit nicht zu befassen!

Ich war wohl zu sehr davon ausgegangen, dass es offensichtlich sinnfrei ist, Dateien einzulesen,
die nicht weiter verarbeitet werden. OK, ich lerne dazu. ;-(

Gruß von
-Martino