Diskussion:Cocke-Younger-Kasami-Algorithmus

für ...

    bla bla 
    für ...
         bla bla 

Ich habe noch nie solchen Pseudecode gesehen. währe es nicht sinnvoller entweder for zu verwenden oder halt irgendein Wort das den Sinn (Schleife) offensichtlicher macht? Das für wirkt etwas gar komisch (nicht signierter Beitrag von 89.217.72.84 (Diskussion) 23:41, 22. Jan. 2013 (CET))

Beispiel

Das Beispiel ist falsch. Hab aber leider keine Zeit, das zu korrigieren. (nicht signierter Beitrag von 141.58.44.245 (Diskussion | Beiträge) 17:18, 24. Jul 2009 (CEST))

Bitte beim nächsten Mal etwas mehr Kontext. Wenn genug Zeit da ist den Diskussionsbeitrag zu verfassen, dann ist auch noch genug Zeit zu schreiben in welchen Zeile/Spalte oder wo auch immer der Fehler sein soll.

Solche unspezifischen Beiträge verursachen nur unnötig Arbeit.

Ich habe das Beispiel eben nochmal mit Papier und Bleistift gerechnet und bin zu der gleichen Tabelle gekommen.

Also, das Beispiel ist richtig. --Gms 12:23, 25. Jul. 2009 (CEST)

Also ich habe mir mehrere Skripte zum CYK-Algorithmus angeschaut und bin auch der Meinung, dass das Beispiel fehlerhaft oder zumindest nicht auf typischer Weise aufgeschrieben ist. (Falls zweiteres der Fall ist, wären Kommentare zu den einzelnen Schritten hilfreich!) --77.184.104.51 15:00, 26. Mär. 2011 (CET)

Wir haben es auch nachgerechnet, die Eintraege stimmen, es muessen aber Zeilen maximal nach rechts verschoben werden, sodass also alle Eintraege auf oder oberhalb der Hauptdiagonalen zu stehen kommen. (nicht signierter Beitrag von 138.246.2.116 (Diskussion) 17:49, 9. Jun. 2011 (CEST))

Könnte sich eventuell mal jemand die Mühe machen und das korrigieren? Ich saß auch davor, um für eine Klausur zu lernen, kam aber einfach nicht auf das Ergebnis, weil das Beispiel so anders aufgeschrieben ist, dass ich es nicht "richtig denken" kann. Außerdem bekomme ich eine andere Ableitung, wenn ich das Beispiel durch den Simulator vom zweiten Link jage! 78.94.169.141 17:23, 20. Feb. 2014 (CET)

Also ich bin auch der Ansicht, dass das Beispiel partiell nicht stimmt. Die Änderung vom 17.02 korrigiert den Fehler, daher diese bitte sichten. --Florian.Loch (Diskussion) 18:32, 18. Feb. 2016 (CET)

Ich bin auch sicher, dass das Beispiel fehlerhaft ist. Kann mal jemand von denen, die der Meinung sind, dass das Wort ist in der Sprache ist, eine Ableitung des Wortes geben? (nicht signierter Beitrag von Rückgängig (Diskussion | Beiträge) 15:47, 23. Jul 2016 (CEST))

Substring-Indizierung

Alle Versionen des Algorithmus, die ich bis jetzt gesehen habe, bauen die Tabelle anders auf. Dort bedeutet die Tabelle, dass man das Teilwort, angefangen von i, mit Länge j, bilden kann (anstatt von i bis j). Wenn man beim gegebenen Beispiel die Spalten jeweils spiegelt bekommt man das; so wird es übrigens z.B. auch im verlinktem Java-Applet gemacht. Ich wwürde es ändern, aber erstens hab ich momentan keine Zeit, und zweitens sind da einige Grafiken im Text, die auch geändert werden müssten.

An deutschen Hochschulen wirds exakt so gelehrt.. nur mal als Einwand. :-) --Schwarzer8Kater 11:15, 14. Feb. 2008 (CET)

Wenn ich mich recht entsinne, wurde es mir an eine deutschen Universität so gelehrt, wie es im Artikel steht. --Stefan Birkner 08:52, 15. Feb. 2008 (CET)

Und wenn man bisher keine Vorlesung besucht hat, die den CYK-Algorithmus behandelt, ist dieser Artikel schwere Kost und meines erachtens nach auch irgendwie schwammig. Fällt mir gerade sehr schwer das zu verstehen... --92.227.81.218 21:02, 24. Mai 2008 (CEST)

Also wie die Substrings/Teilwörter indiziert werden ist ja erstmal für 'die Version des Algorithmus' etwas beliebig. Also ob $w_{i,j}$ oder $w_{i,i+j}$, ob das einbuchstabige Wort mit $w_{i,i}$ oder $w_{i,i+1}$ bezeichnet wird usw. Es wird jedesmal der gleiche Algorithmus beschrieben.

Hauptsache die Notation ist klar definiert, wird im Artikel einheitlich verwendet und man orientiert sich an einer üblichen Notation.

Da die $w_{i,j}$-Notation wohl mit am weitesten verbreitet ist, habe ich diese bei den letzten Überarbeitungen auch verwendet und uneinheitliche Notationen eliminiert.

--Gms 13:22, 13. Aug. 2008 (CEST)

Pseudocode

Sorry, aber der Unterpunkt "Algorithmus" ist schwachsinn. Ich sehe nicht, inwiefern da der CYK-Algorithmus erklärt wird. Das klingt mehr wie "Jetz schaun wir halt mal, welche Wörter wir ableiten können" - etwas mehr steckt da schon dahinter. Pseudocode oder so wäre gut. 91.11.248.179 01:49, 16. Jun. 2008 (CEST)

Hat sich erledigt. --Gms 13:22, 13. Aug. 2008 (CEST)

Weblink

funktioniert bei mir nicht liegts an meim java, oder ist der kaputt?

Liegt an dir. Das Applet funktioniert - benötigt aber Javascript für die korrekte Funktion Eingabefelder, während Java für die Ausführung des Applets verantwortlich ist. -- 87.173.94.59 16:51, 26. Jun. 2010 (CEST)

Forum Link

Mir kommt dieser Forum-Link nicht besonders hilfreich vor.

Es wird nicht mal erklärt, wie der Eingabestring indiziert wird, und auf welchen Substring sich der Inhalt in Zelle i,j bezieht. Desweiteren enthält der Link Werbung.

Die farbige Markierung der Beispiel-Tabellen ist ja ganz nett - man könnte natürlich auch den Beispiel-Abschnitt in dem Artikel entsprechend erweitern.

Wie ist die allgemeine Meinung dazu? --Gms 21:05, 24. Sep. 2010 (CEST)

Was heißt |P|?!

Bei der Betrachtung der Zeitkomplexität steht: |P| bezeichnet hier die Größe der Produktionen. Was heißt das? Wahrscheinlich nicht die Anzahl der Regeln; s. die weiteren Erklärungen im Artikeltext. (Allerdings wäre das genau das, was |P| bedeuten sollte, denn P ist die Menge der Regeln.) Bedeutet es die Summe der Längen der rechten Regelseiten? Oder was? -- UKoch 22:17, 17. Jun. 2011 (CEST)

Anscheinend ist mit |P| doch die Anzahl der Regeln gemeint. Dann lässt sich der Algorithmus aber beschleunigen, denn die Regelmenge müsste nicht linear durchsucht werden -- man bräuchte nur eine Hashtabelle, die jede rechte Regelseite alpha auf alle Nichtterminale abbildet, die auf der linken Seite einer Regel stehen können, deren rechte Seite alpha ist. Suchen in einer Hashtabelle hat deutlich niedrigeren Zeitaufwand. -- Sollten wir uns nicht an die Formulierung des Wortproblems halten und |P| bzw. p in der Komplexitätsbetrachtung einfach weglassen? -- UKoch 01:48, 24. Jun. 2011 (CEST)

Seltsamerweise wird damit argumentiert, dass G in CNF vorliegt. Damit wird suggeriert, |P| sei ansonsten nicht die Anzahl der Regeln und für andere kontextfreie Grammatiken müsste man |P| nur anders berechnen – dabei funktioniert der Algorithmus in der Form nur für Grammatiken in CNF. Man kann den Umweg zu p über |P| also einfach streichen. Ich finde es aber auch am sinnvollsten (da in der Literatur so vorgefunden), die Grammatik als gegeben anzusehen und p auch wegzulassen. --Zahnradzacken 17:39, 4. Jul. 2011 (CEST)

Ich habe |P| und p jetzt weggelassen. Im Pseudocode des Algorithmus ragt jetzt die Zeile mit der Formel etwas weit 'raus -- das könnte man noch verbessern, wenn man elegant sicherstellen könnte, dass die Einrückung dann noch stimmt. -- UKoch 21:29, 9. Dez. 2011 (CET)

Hopcroft/Ullman

Ich habe die Beschreibung und den Algorithmus selbst nach H/U geändert. Bei der Literaturangabe konnte ich leider nicht unterbringen, dass es der 1., korrigierte Nachdruck ist (der allererste Druck der 3. Auflage ist von 1994, liegt mir aber nicht vor). Jetzt sollte es endlich stimmen. -- UKoch 01:32, 24. Jun. 2011 (CEST)

Tabelle im Beispiel ist Mist

Die Tabelle im Beispiel am Ende des Artikels ist falsch. Laut ihrer Beschreibung ist sie so gedacht, dass in der $i$‑ten Zeile und $j$‑ten Spalte die Menge $V_{ij}$ angegeben ist. Demnach müsste in der sechsten Spalte der ersten Zeile die Menge $V_{1,6}$ zu finden sein, die angeblich das Startsymbol $S$ enthält. Die Menge in der Tabelle lautet aber $\left\{A,C\right\}$.

Meines Erachtens müsste die Tabelle, wenn in der $i$‑ten Zeile und $j$‑ten Spalte die Menge $V_{ij}$ angegeben sein soll, eine obere rechte Dreiecksform haben. Außerdem finde ich die Notation „{-}“ für die leere Menge nicht schön. --77.186.104.187 13:53, 16. Mai 2016 (CEST)

Zumindest jetzt steht im Artikel, dass $V_{ij}$ in der $i$-ten Spalte und $j$-ten Zeile steht. Sieht mir richtig aus. - Bzgl. der leeren Menge gebe ich Dir Recht. -- UKoch (Diskussion) 18:42, 11. Jun. 2017 (CEST)

Verständlichkeit

Wäe nett, wenn man als durchschnittlicher Softwareentwickler wenigstens verstehen könnte um was es geht. https://de.wikipedia.org/wiki/Wikipedia:Allgemeinverst%C3%A4ndlichkeit Freimatz (Diskussion) 09:19, 22. Mai 2017 (CEST)

Dafür müsste man schon ein paar der verlinkten Artikel lesen, mindestens muss man kontextfreie Grammatiken verstehen. -- UKoch (Diskussion) 18:45, 11. Jun. 2017 (CEST)

Komplexität: Was ist g?

Für eine Variante des Earley-Algorithmus ist im Artikel folgende Laufzeit angegeben:

${\mathcal {O}}\left(gn^{3}/\log(n)\right)$

Was ist g? -- UKoch (Diskussion) 14:48, 26. Okt. 2023 (CEST)