Algorithmus erstellen in O(n)

Was macht ihr denn so ein Drama daraus? Wer es selbst hinbekommt kann stolz auf sich sein und wer es abschreibt muss das ja mit sich selbst ausmachen. Am ende weiß doch jeder wieviel er selbst geleistet hat.

Ich finde hustbaer hat zu viel verraten (nämlich alles, der Rest ist ja nur noch Schreibarbeit) für einen ersten Tipp ein guter erster Tipp wäre der Hinweis gewesen, dass O(n) nicht immer ein oder mehrere Schleifen sein müssen die nacheinander kommen, sondern auch durchaus geschachtelt sein können, wenn man genügend Information mit jedem Schritt wegwerfen kann.

@ChrisM
du beginnst ja früh mit konkurrenzdenken...

ChrisM

besserwisser schrieb:

@ChrisM
du beginnst ja früh mit konkurrenzdenken...

Wenn es darum ginge, hätte ich absichtlich eine falsche Lösung präsentiert

Btw, wenn man nach der Lösung mit meinen oben angegebenen Schlüsselwörtern googelt, komme jetzt ich auf Platz 1 (zu krass)
http://img294.imageshack.us/my.php?image=screenie4sz9.png

Chris

MFK

Bin ich der einzige, der die Lösung in dem PDF der Uni Karlsruhe für wenn nicht falsch, dann doch zumindest für ziemlich wackelig hält?

Abgesehen davon, dass IMHO in Zeile 13 "<=" stehen müsste, wird da einfach ein kompletter Wert auf einen Rutsch von A nach B kopiert, und das in angeblich konstanter Zeit, obwohl genau das laut Aufgabenstellung nicht geht.

ChrisM

Hallo,

kopieren und vergleichen sind schon verschiedene Operationen, die auch unterschiedlich schnell sein können (z.B. das eine nur bitweise, das andere zahlenweise). Aber im Endeffekt ist das sowieso egal, im Notfall kopierst du halt nicht, sondern führst eine separate Liste mit, welche Indizies noch im Suchraum drin sind. Dort kannst du dann immer die entsprechenden rausnehmen, die es nicht mehr sein können (also an einer bestimmten Bitstelle "in der Mehrheit" sind).

Und der Algorithmus funktioniert, auf dem nächsten Blatt (das gerade aktuell ist) ist nämlich eine Aufgabe, wo man ihn auch wirklich mit Java implementieren soll.

Chris

MFK

ChrisM schrieb:

kopieren und vergleichen sind schon verschiedene Operationen, die auch unterschiedlich schnell sein können (z.B. das eine nur bitweise, das andere zahlenweise).

Dann ist der ganze Aufwand mit Bitzugriffen und Rekursion aber unnötig. Dann kann ich auch alle Werte in linearer Zeit in ein anderes Array kopieren, und dann einfach alle Werte verXORen.

ChrisM schrieb:

Aber im Endeffekt ist das sowieso egal, im Notfall kopierst du halt nicht, sondern führst eine separate Liste mit, welche Indizies noch im Suchraum drin sind. Dort kannst du dann immer die entsprechenden rausnehmen, die es nicht mehr sein können (also an einer bestimmten Bitstelle "in der Mehrheit" sind).

Die Indizes sind genauso groß wie die Werte selbst. Die können IMHO so groß werden, dass O(1)-Operationen darauf gar nicht mehr möglich sind. Wenn wir aber den Wertebereich von vornherein einschränken, dann ist das Ganze sowieso in O(1) machbar. Ich glaube, diese Aufgabe ist einfach nicht durchdacht.

ChrisM schrieb:

Und der Algorithmus funktioniert, auf dem nächsten Blatt (das gerade aktuell ist) ist nämlich eine Aufgabe, wo man ihn auch wirklich mit Java implementieren soll.

Hast du einen Link?

ChrisM

Hi,

stell dir mal folgendes Szenario vor:
Das Array, in dem die Zahl fehlt, liegt auf einem anderen Rechner, über den du nur mit geringer Bandbreite kommunizieren kannst. Kopieren daher ganz schnell (O(n), wenn n die Anzahl der kopierten Zahlen ist), solange du auf dem anderen Rechner bleibst. Du kannst also gerne in ein anderes Array kopieren- aber dann auch nur bitweise auf die Kopie zugreifen... sobald du aber anfängst, XORs durchzuführen, musst du im Endeffekt jedes Bit über die Leitung übertragen (der andere Rechner kann kein XOR), bist also wieder in O(n*log n) bei n Zahlen für deinen Algorithmus.

Natürlich wäre ein Array von Indizies in meinem Szenario nicht von der Bitweiser-Zugriff-Beschränkung betroffen, denn es liegt ja auf deinem eigenen Rechner. Ansonsten wird es auch absurd, schon der einfache Vergleich, ob dein Schleifenzähler am Ende der Liste angekommen ist, müsste bitweise durchgeführt werden.

Dass die Indizies im Bereich von 2^64 bleiben, kann man denke ich einfach annehmen. Oder kannst du ein Array bauen, dass mehr als 2^64 Elemente hat?

EDIT: Ja, ich weiß, dann wäre man wieder in O(64*n). Ein Dilemma... in der Hinsicht ist die Aufgabe wohl etwas schlecht formuliert.

Chris

PS: Nein, das Übungsblatt gibt es leider nicht öffentlich und ich werde es deshalb auch nicht hochladen.

Ich find die Musterlösung, wie sie hier genannt wurde Käse, die Aufgabe macht sinn, wenn man weder kopieren noch komplett auslesen kann und die gesuchte Lösung die von Seite 1 ist.
Hier wurde ja in der Musterlösung eine Definitionslücke der Aufgabe ausgenutzt, wo eigentlich klar sein sollte, dass dies ebenfalls ausgeschlossen wird.
Ich hasse es, dass Informatiker nicht in der Lage sind einwandfreie und eindeutige Aufgabenstellungen zu formulieren. Bei einem Matheblatt ist mir sowas noch nie untergekommen...

ChrisM schrieb:

Und der Algorithmus funktioniert, auf dem nächsten Blatt (das gerade aktuell ist) ist nämlich eine Aufgabe, wo man ihn auch wirklich mit Java implementieren soll.

Versteht wohl auch keiner was das soll. Die Aufgaben sind sowas von hingeklatscht und unzusammenhängend. Unlogisch und unschlüssig formiliert. Fand Info I schon grausam, aber Info II ist einfach absoluter Mist im Vergleich zu in meinen Augen gut strukturierten Vorlesen wie Analysis oder LA. Gerade das aktuelle Übungsblatt ist mal wieder das beste Beispiel dafür. Nur meine Meinung, villeicht kann ich das auch nur nicht beurteilen weil ich in Mathe zu wenig Vorwissen mitbringe, um daran rumzumeckern. Info I/II hats aber definitv geschafft mir jeden Spass an Info zu nehmen. Ich mach Vordiplom, hau für ne Weile ins Ausland ab und mach dann Mathe Lehramt.

Gibts denn Musterlösungen der Uni im Internet oder in dem Portal? Bin doch net so blöd und setz mich auch noch in Übung, wenn ich schon in der Vorlesung jedes mal einschlaf

@MFK:
"Implementieren Sie eine Javaversion des Algorithmus aus Übungsaufgabe 3.4c." 15 Praxispunkte - geschätzte Dauer: 1/2 Seite Pseudocode in Eclipse eintippen, ca. 15min

Im direkten Vergleich: Implementieren von Mergesort, randomisierter und deterministischer Quicksort. Laufzeiten experimentell für verschiedene Eingaben testen. - geschätzte Dauer: ca. 30min, weil ich mich mit den Algorithmen auskenn, und die nicht zum ersten mal eintipp. Jemand der die nur aus der Vorlesung kennt, kann das NIE einfach ausm Kopf programmieren. Witz: Auch 15Pkt.

Noch krasser: Ergebnisse sollen mit AWT als zweidimensionales Plot ausgegeben werden. AWT nie behandelt. 10 Praxispunkte. Scherzkekse.

Heulsuse schrieb:

Ich find die Musterlösung, wie sie hier genannt wurde Käse, die Aufgabe macht sinn, wenn man weder kopieren noch komplett auslesen kann und die gesuchte Lösung die von Seite 1 ist.
Hier wurde ja in der Musterlösung eine Definitionslücke der Aufgabe ausgenutzt, wo eigentlich klar sein sollte, dass dies ebenfalls ausgeschlossen wird.
Ich hasse es, dass Informatiker nicht in der Lage sind einwandfreie und eindeutige Aufgabenstellungen zu formulieren. Bei einem Matheblatt ist mir sowas noch nie untergekommen...

Auch Karlsruhe Info2?

@Student der nur trinkt, ja auch Info in Ka. Die Bepunktung beim aktuellen Blatt ist schon sehr fragwürdig, ich glaub ja die 15 Bonuspunkte für die Implementierung von 3.4 c) sind dazu da, dass man die grafische Auswertung sich sparen kann

Mal sehen ob ich mir die Aufgabe überhaupt antue...

Mich stört die Formulierung der Aufgabe auch extrem, aber das steht ja auch schon oben und ich glaub das geht den meisten so.

Student der nur trinkt... schrieb:

Versteht wohl auch keiner was das soll. Die Aufgaben sind sowas von hingeklatscht und unzusammenhängend. Unlogisch und unschlüssig formiliert. Fand Info I schon grausam, aber Info II ist einfach absoluter Mist im Vergleich zu in meinen Augen gut strukturierten Vorlesen wie Analysis oder LA. Gerade das aktuelle Übungsblatt ist mal wieder das beste Beispiel dafür.

Die Vorlesungsfolien finde ich schlimmer. In mindestens jedem dritten Programmschnipsel ist ein Fehler drin und auch der Rest ist alles andere als fehlerfrei. Off-by-1 Fehler sind eher die Regel als die Ausnahme. Sorry aber so etwas darf einfach nicht passieren. Hin und wieder mal ein Flüchtigkeitsfehler ok aber das ist nicht mehr hin und wieder.

Student der nur trinkt... schrieb:

Nur meine Meinung, villeicht kann ich das auch nur nicht beurteilen weil ich in Mathe zu wenig Vorwissen mitbringe, um daran rumzumeckern.

Die Mathe Vorlesungen sind definitiv viel besser wenn auch sehr trocken. Ich finde jedoch, dass in LA die analytische Geometrie bis jetzt ein bischen arg kurz kam. Aber wahrscheinlich wird das dieses Semester noch nachgeholt.

Student der nur trinkt... schrieb:

Im direkten Vergleich: Implementieren von Mergesort, randomisierter und deterministischer Quicksort. Laufzeiten experimentell für verschiedene Eingaben testen. - geschätzte Dauer: ca. 30min, weil ich mich mit den Algorithmen auskenn, und die nicht zum ersten mal eintipp. Jemand der die nur aus der Vorlesung kennt, kann das NIE einfach ausm Kopf programmieren. Witz: Auch 15Pkt.

Noch schlimmer ist, dass wenn man den Quicksort genau so implementiert wie er in der Vorlesung "formal" eingeführt wurde er sich gerne in Endlosrekursionen verstrickt.

Info2 Karlsruhe

ChrisM

Hallo,

Student der nur trinkt... schrieb:

@MFK:
"Implementieren Sie eine Javaversion des Algorithmus aus Übungsaufgabe 3.4c." 15 Praxispunkte - geschätzte Dauer: 1/2 Seite Pseudocode in Eclipse eintippen, ca. 15min

Im direkten Vergleich: Implementieren von Mergesort, randomisierter und deterministischer Quicksort. Laufzeiten experimentell für verschiedene Eingaben testen. - geschätzte Dauer: ca. 30min, weil ich mich mit den Algorithmen auskenn, und die nicht zum ersten mal eintipp. Jemand der die nur aus der Vorlesung kennt, kann das NIE einfach ausm Kopf programmieren. Witz: Auch 15Pkt.

Noch krasser: Ergebnisse sollen mit AWT als zweidimensionales Plot ausgegeben werden. AWT nie behandelt. 10 Praxispunkte. Scherzkekse.

da muss ich dir leider recht geben.

Was mich bei den Programmieraufgaben aber ebenso aufregt, sind die schwammigen Anforderungen.

Ein Beispiel: Die Implementierung der Liste (also eine Implementierung des java.util.List-Interface). Ich sitze also da und implementiere das komplette Interface und natürlich auch den kompletten ListIterator und hatte bis auf hash() schon alles implementiert, außer natürlich den Collections-Methoden, die auf dem Übungsblatt ja ausgeschlossen wurden. Dann schaue ich ins Forum und dort steht "equals(), hash() etc. brauchen Sie nicht zu implementieren". Also rausgelöscht.

Irgendwann läuft dann alles so und gestern (nach Abgabe) schaue ich nochmal ins Forum. Jetzt dürfen wir offenbar sogar eine AbstractList verwenden. Im Endeffekt heißt das, dass man nur noch add(), remove(), get(), set() und size() implementieren muss, alles andere (auch der ListIterator) ist schon da!

Oder bei der AWT-Aufgabe. Jetzt wurde ja auch Swing erlaubt, was natürlich nirgends auf dem Blatt draufsteht. Wenn du nicht in das Info 2-Portal reinschaust, weißt du das wahrscheinlich noch gar nicht...

Offenbar ist es also wirklich das Beste, wenn man einfach bis auf den letzten Drücker faul rumsitzt und wartet, ob die Aufgabe noch "vereinfacht" wird. Ich werde auf jeden Fall nicht mehr direkt am Abend des Erscheinens mit dem Programmieren anfangen.

Und was die Vorlesung angeht, so stimmt es, dass da öfters Fehler drin sind. Im Grunde sind die zwar nicht weiter störend (Böhm bemerkt sie i.d.R. und weist darauf hin bzw. korrigiert sie mit einer Annotation), aber ich frage mich, warum die nicht schon vorher behoben wurden. Immerhin hält er ja nicht zum ersten Mal Info 2 und hat wohl kaum die ganze Vorlesung neu geschrieben...

Chris

Und was die Vorlesung angeht, so stimmt es, dass da öfters Fehler drin sind. Im Grunde sind die zwar nicht weiter störend (Böhm bemerkt sie i.d.R. und weist darauf hin bzw. korrigiert sie mit einer Annotation), aber ich frage mich, warum die nicht schon vorher behoben wurden. Immerhin hält er ja nicht zum ersten Mal Info 2 und hat wohl kaum die ganze Vorlesung neu geschrieben...

Na dann pass mal besser auf. Die Fehler die er bemerkt und verbessert sind nämlich arg in der Minderheit.

Nur mal ein Beispiel: Countingsort in einem Array das von 1 bis n läuft:

for (max=0, i=1; i<=n; i++)
if (x[i]> max) max=x[i];
// Neues Feld
 // der Länge max+1 initialisieren
s = new int[max+1];
for (i=0; i<=max; i++) s[i]=0;
// Zähle, wie oft welche Zahl
// in x vorkommt
for (i=1; i<n; i++) s[x[i]]++;
// x neu auffüllen
for (i=0, j=0; i<=max; i++)
while (s[i]>0)
{x[j++]=i; s[i]--};

Es wurde nichts verbessert.

1. Der Code geht implizit aus, dass alle Zahlen im Array positiv sind. Entweder man packt die Schranken in die Spezifikation des Problem (welche es natürlich nicht gibt) oder man ermittelt beide. Eine zu ermitteln und die andere implizit anzunehmen ist inkonsequent und deswegen war dies meiner Meinung nach dem Autor der Folien nicht bewusst.

2. In der dritten Schleife muss das ein <= sein, also eindeutig einen Bug, egal wie man die nicht existierende Spezifikation auslegt.

Anderes Beispiel, Quicksort:

Teile: Wähle ein Pivotelement x
und partitioniere A in Arrays A1 und A2,
so daß Elemente in A1 ≤ x < Elemente in A2.
2. Herrsche: Sortiere A1 und A2 rekursiv.

Mach das mal mit {1, 1, 1, 1, 1} und zwar genauso wie das da steht und nicht so wie er es danach in den Beispielen gemacht hat.

Pivot = 1 (und zwar unabhängig von der Pivotwahl) also ist A1 = A = {1, 1, 1, 1, 1} und A2 = {}. Ne schöne Endlosrekursion.

Das sind jetzt nur zwei Beispiel. In fast jedem dritten Code- oder Pseudocodeschnipsel sind solche Fehler drin.