No video

Formale Sprachen #30 - CYK-Algorithmus

Wir sehen uns den CYK-Algorithmus an, welcher das Wortproblem für kontextfreie Sprachen löst. CYK steht für die Erfinder Cocke, Younger und Kasami.

Пікірлер: 92

  • @Leon-be4lx
    @Leon-be4lx4 жыл бұрын

    Ich wette es gibt kaum Studenten, die ihre eigentliche Vorlesung hilfreicher fanden als diesen KZreadchannel. Change my mind :D

  • @janboyega

    @janboyega

    3 жыл бұрын

    Mein prof meints echt gut und versuch sein bestes, aber an diese Videos kommt er nicht ran.

  • @philippladwig2861
    @philippladwig28618 жыл бұрын

    Das ist die beste und anschaulichste Erklärung, die ich bisher in Büchern und im Netz gefunden hab. Danke :)

  • @Xappreviews
    @Xappreviews9 жыл бұрын

    Danke für diese wunderbare Serie, es hat echt geholfen, mich auf meine Klausur vorzubereiten! Nur Schade dass du so abrupt aufgehört hast, es gibt noch so viele Themen in diesem Bereich. Lass dich nur nicht durch die wenigen Views unterkriegen, das ist bei Bildungsvideos normal. Gibt den Videos ein paar Jahre, und die Aufrufe werden von alleine kommen :) Deine Videos sind sehr gut, die Bewertungen und positiven Kommentare bestätigen das :)

  • @ziangduan9699

    @ziangduan9699

    4 жыл бұрын

    gut vision

  • @JoergMcFly

    @JoergMcFly

    3 жыл бұрын

    Es ist so viel leichter mit den Pyramiden - dankeschönst!! ☺️

  • @tostupidforname
    @tostupidforname4 жыл бұрын

    Unfassbar, dass wir das als algorithmus ohne die intuition einer pyramide gelernt habe.... Danke

  • @rcookie5128
    @rcookie51283 жыл бұрын

    Dieses Pyramidenschema ist viel einsichtiger und effektiver als die tabellarische Form mit der wir das gelernt haben, danke!

  • @jeffstarkmann6381
    @jeffstarkmann63815 жыл бұрын

    Bis zum letzten Punkt Schritt für Schritt super erklärt. Kein irritierendes Fehlerkorrigieren oder rumgeschafel - wirklich sehr verständlich. Hat mir sehr geholfen, Danke!

  • @M710Z
    @M710Z Жыл бұрын

    Total verständlich und intuitiv als Pyramide aufgebaut. Danke für die tolle Erklärung :)

  • @332tomtom
    @332tomtom9 жыл бұрын

    mit einem einzigen Satz, dem wo du sagst wie die marker wandern, hast du mir erklärt was aus unserem TGI Skript kaum rauszulesen ist weil da zu dem Thema keine einzige Pyramide abgedruckt ist sondern nur Definition nach definition. Vielen Dank, die videos sind super

  • @NLogSpace

    @NLogSpace

    9 жыл бұрын

    Danke für das Feedback! Es freut mich, dass es Dir geholfen hat! :)

  • @Anonymgibtsnich
    @Anonymgibtsnich6 жыл бұрын

    mein held, mein retter. danke für den aufwand den du betreibst um die videos zu produzieren. bester mann ;)

  • @nayjer2576
    @nayjer25762 жыл бұрын

    Fantastisch erklärt. Die Pyramidenform ist echt gut um zu verstehen was da passiert.

  • @anonymous1177
    @anonymous11777 жыл бұрын

    Eines deiner besten Videos. In unserem Skript wird der CYK in einem unglaublichen Maße kompliziert erklärt. Es wird im Prinzip das Gleiche gemacht, nur dass Variablenmengen definiert werden die dann rekursiv abgearbeitet werden. Durch die simple Visualisierung als Pyramide wird es hundertmal verständlicher.

  • @NLogSpace

    @NLogSpace

    7 жыл бұрын

    Dankeschön! :) Ja, genau deshalb gefällt mir die Darstellung als Pyramide viel besser als die rein formale Definition.

  • @Neos4398
    @Neos43982 жыл бұрын

    war wirklich schon am verzweifeln, aber du hast es so gut auf den Punkt gebracht und die Pyramide ist viel übersichtlicher und besser durchzulaufen als diese bescheuerte Tabelle.. Danke dir!!

  • @jonslow8868
    @jonslow88684 жыл бұрын

    Vielen Dank NLogSpace! Deine Videos haben mir sehr geholfen, um die Themen, wie CYK-Algorithmus, Chomsky-NF, Pumping-Lemma, Kellerautomaten usw, zu verstehen. Sehr gut erklärt, alles übersichtlich und verständlich. Ich habe mit 2,0 Automatentheorie und Formale Sprachen bestanden :)

  • @fastestwaydown
    @fastestwaydown8 жыл бұрын

    Nachdem ich jetzt die gesamte bisherige Playlist gesehen habe: Erstmal riesen Kompliment, Gute Beispiele, sehr verständliche Erklährungen - und tausendmal weniger einschläfernd bzw. deutlich anschaulicher als in der Vorlesung :D Zusätzliche Anmerkung für andere Viewer: - Schaut das Video(die Playlist) mit 1,5 facher Geschwindigkeit an, ist genauso gut noch verständlich, kostet aber weniger kostbare Lernzeit. - Macht leise im Hintergrund irgendein Instrumentalstück an, dann klingt das ganze Video viel dramatischer, ohne dass die Verständlichkeit beeinflusst wird xD

  • @NLogSpace

    @NLogSpace

    8 жыл бұрын

    Vielen Dank für das Feedback! :)

  • @deadmoldable

    @deadmoldable

    8 жыл бұрын

    ich schließe mich der positiven beurteilung an. du überspringst nichts, weil es vermeintlich "selbstverständlich" ist, und trägst die sachen ruhig und konsequent vor. noch eine ergänzung für die lerntricks von benjamin: - fragt auch euren prof ob ihr bei der prüfung das instrumentalstück abspielen dürft, um das wissen besser abrufen zu können :D

  • @arnoclaude317

    @arnoclaude317

    5 жыл бұрын

    genauso mach ich es auch :) gute Tipps!

  • @nektarmangotrinksaft3695
    @nektarmangotrinksaft36954 жыл бұрын

    Heute Klausur geschrieben, lief sehr gut. CYK Algorithmus kam dran. Danke für dieses Video 👍

  • @SchrottgamesLP
    @SchrottgamesLP2 жыл бұрын

    Super starkes Video! In unter 20 Minuten ein Thema erklärt, was unser Dozent nicht einer 4-Stunden Vorlesung hinbekommt. Danke dir!

  • @julius4858
    @julius48587 жыл бұрын

    Hatten den Algorithmus nur als Pseudocode vorliegen, komplett unverständlich. Du hast mein Leben gerettet

  • @haibangngo7357
    @haibangngo73578 ай бұрын

    beste ERKLÄRUNG,Viel vielen Danke

  • @BooBar2521
    @BooBar25213 жыл бұрын

    ich danke dir dass du so komplizierte themen so leicht und verständlich für uns erklärst. auch heute helfen alle deine videos mir bei meinem studium! vorallem da es so wenig videos zu diesen themen gibt und dann auch noch auf deutsch! vielen Dank!!!!

  • @dennis2599
    @dennis25996 ай бұрын

    Vielen Dank, du hast mir sehr geholfen durch meine Prüfungen zu kommen :)

  • @javaexpertsa8947
    @javaexpertsa89475 жыл бұрын

    Mit Abstand das beste Video zu den CYK-Algortihmus. Mein Dozent konnte es nach unzähligen Versuchen nicht so gut erklären wie du es getan hast. Vielleicht hättest du ja Intresse, den Platz unseres Dozenten zu übernehmen! :P

  • @huydang6059
    @huydang6059 Жыл бұрын

    Vielen Dank für deine super Erklärung

  • @primegraphics1249
    @primegraphics12494 жыл бұрын

    Sehr sehr gut erklärtes Video, vielen Dank

  • @JuneLetsPlays
    @JuneLetsPlays5 жыл бұрын

    Du bist ein Held. Danke!

  • @matzus1574
    @matzus15743 ай бұрын

    alter warum lernt man das in einer tabelle?! deine Form ist gold wert!

  • @champKabsn
    @champKabsn9 жыл бұрын

    Daumen hoch! Einfach, Übersichtlich, Verständlich. Werde dieses Verfahren gleich mal ausprobieren ;)

  • @modplayerMC
    @modplayerMC4 жыл бұрын

    Hat beim TGI lernen definitv geholfen. Dankeschön!

  • @janboyega
    @janboyega3 жыл бұрын

    Sehr gutes Video!

  • @TerrifyingSaviourGOO
    @TerrifyingSaviourGOO3 жыл бұрын

    Super Video

  • @norbertbalaz9421
    @norbertbalaz94215 жыл бұрын

    Sehr gut und sehr verständlich erklärt! Vielen Dank für deine Videos!

  • @hardcoretournaments1459
    @hardcoretournaments14594 жыл бұрын

    Danke ! sehr hilfreich

  • @Saadet-jp6lr
    @Saadet-jp6lr3 жыл бұрын

    sehr verständlich, danke

  • @bioinfo9386
    @bioinfo93867 жыл бұрын

    Vielen Dank, dieses Video hat mir, zusammen mit vielen anderen von Dir, die FSK-Klausur gerettet.. :D

  • @_ICARUS-

    @_ICARUS-

    Жыл бұрын

    bist/warst du auch LMU-Informatik? :D

  • @health.upgradedbyscience.7309

    @health.upgradedbyscience.7309

    Жыл бұрын

    @@_ICARUS- yep, genau genommen Bioinfo.. 😋 meinst du die Klausur hieß nur bei uns so?

  • @_ICARUS-

    @_ICARUS-

    Жыл бұрын

    @@health.upgradedbyscience.7309 ja ich denke schon haha bei anderen Unis heißt es immer theoretische Informatik. Hab meine fsk klausur heute xD

  • @redxxiv739
    @redxxiv7394 жыл бұрын

    Danke masta

  • @omercankucuk
    @omercankucuk5 ай бұрын

    Danke!

  • @Boogeyyyman
    @Boogeyyyman4 жыл бұрын

    Meisterschaft erklärt. Grandios ✌️

  • @albertpop1132
    @albertpop11325 жыл бұрын

    Sehr schön erklärt danke

  • @fedorcherinko6433
    @fedorcherinko64333 жыл бұрын

    Super erklaert.

  • @adabsurda
    @adabsurda6 жыл бұрын

    super erklärt, danke!

  • @nex7886
    @nex78869 жыл бұрын

    Danke für das Tutorial, das ist total gut erklärt!

  • @alberthebe9710
    @alberthebe97104 жыл бұрын

    Vielen Dank für das Video! Es hat mir sehr geholfen. Die Darstellung mit der Pyramide finde ich auch viel intuitiver als die Tabellenform, wie sie uns gelehrt wird.^^

  • @Terry211291
    @Terry2112919 жыл бұрын

    Super Videos ! Hab ein paar davon für meine Übungszettel nutzen können und alle mit voller Punktzahl bearbeitet. Vielen Dank :-)

  • @dasten123
    @dasten1238 жыл бұрын

    Super! Das Video hat es gebracht! :)

  • @Corrupter1313
    @Corrupter13138 жыл бұрын

    Mal wieder ein super Video! Hat mir echt weiter geholfen!

  • @MultiJake75
    @MultiJake757 жыл бұрын

    Herzlichen Dank für die Videos!!! Schade, dass du aufgehört hast...

  • @NLogSpace

    @NLogSpace

    7 жыл бұрын

    Tut mir Leid, dass schon so lange keine Videos mehr gekommen sind! Aber ich habe nicht aufgehört, ich habe nur leider sehr wenig Zeit und im Moment arbeite ich an anderen Projekten. Ich werde mir jedoch bald wieder Zeit nehmen, um weitere Videos zu machen. Gibt es Vorschläge für Themen?

  • @WishmobNr1

    @WishmobNr1

    7 жыл бұрын

    ->weiter bei Äquivalenz kontextfreie Grammatiken und Kellerautomat (z.B. Umformung in Beide Richtungen, wobei es kfG in NKA schon recht gut erklärt gibt, was eine Lücke darstellt ist NKA in eine kfG (Hab zumindest nichts gut verständliches gefunden. ) -Deterministische Kellerautomaten und Deterministische kontextfreie Sprachen -Bestimmte Klassen kontextfreier Sprachen wie LL(k) & LR(k) ->mehr zu Chomsky Typ 0/1 Sprachen ...sind vielleicht mal ein paar Anregungen :) Danke nochmal für die Videos. Große Klasse. Mal schauen wie ich mich in der Klausur schlage. Bis dahin wirst du es wahrscheinlich nicht mehr schaffen :D

  • @Ali-ny4wi
    @Ali-ny4wi4 жыл бұрын

    bester Mann :)

  • @sighmanthethird
    @sighmanthethird8 жыл бұрын

    Sehr gut erklärt, großes Dankeschön :)

  • @christoph-diefenthal
    @christoph-diefenthal9 жыл бұрын

    Eine Super Reihe Leif , wann kommt das nächste Video? :-)

  • @NLogSpace

    @NLogSpace

    9 жыл бұрын

    ***** Danke! :) Es ist gerade einiges in Planung, bald geht es weiter!

  • @LyubomiraGerova97
    @LyubomiraGerova976 жыл бұрын

    Danke für das Video!

  • @sofi1506
    @sofi15067 жыл бұрын

    Hallo! Danke für die super gut erklärte Videos ! Davor waren so viele Sache unklar und jetzt verstehe ich so viel : ) Könntest du auch ein Video über Kleene'sche Algebra/ Kleene Stern machen ? Bei uns würde das zusammen mit dem Thema Automaten erklärt aber ich verstehe es nicht.

  • @Blind_Hawk
    @Blind_Hawk2 жыл бұрын

    Hätte ich mal früher angefangen...

  • @MaZe741
    @MaZe7418 жыл бұрын

    super mit der pyramide, im skript waren das immer linkbündige dreiecke, und das auswählen der Felder macht viel weniger Sinn

  • @McFaceDrop
    @McFaceDrop5 жыл бұрын

    Ehrenmann

  • @akaari3820
    @akaari38204 жыл бұрын

    Sehr gute und erleuchtende Erklärung. Hab zwar nen guten Prof, aber beim CYK-A hat er leider völlig versagt...

  • @Mike-kq5yc
    @Mike-kq5yc3 жыл бұрын

    Hey. Dein Video ist besser erklärt als unser Prof. selbst. Danke sehr! Aber eine Frage, könntest du vielleicht eine Literatur empfehlen?

  • @NLogSpace

    @NLogSpace

    3 жыл бұрын

    Dankeschön! Literatur benutze ich leider wenig, daher kann ich keine empfehlen.

  • @SumbaSlice
    @SumbaSlice3 жыл бұрын

    Es wäre hilfreich, wenn du immer dazu sagen würdest, ob du von klein a oder groß a redest.

  • @arnabsaha4873
    @arnabsaha48733 жыл бұрын

    please explain the time complexity

  • @snickers7752
    @snickers77526 жыл бұрын

    Nice Video #Ehrenmann

  • @NLogSpace

    @NLogSpace

    6 жыл бұрын

    Danke :)

  • @flvh935
    @flvh9354 жыл бұрын

    Super Video, vielen Dank hat mir sehr geholfen. Ich habe eine Frage zu einem anderen Beispiel. Was tue ich, wenn das selbe Terminal von mehreren Nichtterm. abgeleitet werden kann. Also , A-> AS,a,b und B-> AD,a,b und D-> a. Geprüft werden soll das Wort aabaa. Die erste Reihe der Pyramide kann ja nun verschiedene Versionen annehmen weil a von A,B und D abgeleitet werden kann. Muss ich dann mehrere Tabellen erstellen Ich hoffe die Frage ist verständlich erklärt.

  • @NLogSpace

    @NLogSpace

    4 жыл бұрын

    Eine Zelle darf auch mehrere Nichtterminale enthalten. Wenn es mehrere Möglichkeiten gibt, dann schreibt man alle möglichen Nichtterminale in die Zelle. In deinem Beispiel wäre die erste Zeile der Pyramide wie folgt: ABD | ABD | AB | ABD | ABD Hierbei ist z.B. ABD als die Menge {A, B, D} zu verstehen. Man macht also nur eine Pyramide, aber schreibt dann mehrere Symbole in die Zellen.

  • @flvh935

    @flvh935

    4 жыл бұрын

    @@NLogSpace Ach klar! viel Dank. Da habe ich es mir selbst ein bisschen zu kompliziert gemacht.

  • @sieranon6751
    @sieranon67518 жыл бұрын

    Tolle Videos! Gibts eigentlich keine Fortsetzung nach diesem hier?

  • @dogan.y2k
    @dogan.y2k5 жыл бұрын

    Muss an der Spitze zwangsweise S stehen, damit es in der L(G) ist? In einer meiner Übungen endet meine Pyramidenspitze mit z.b. Y. Das würde doch bedeuten, dass das Wort trotzdem nicht in der L(G) ist, oder?

  • @NLogSpace

    @NLogSpace

    5 жыл бұрын

    Das Wort ist genau dann in L(G), wenn an der Spitze das Startsymbol steht.

  • @SpaceSebi
    @SpaceSebi7 жыл бұрын

    Super Video! Wäre toll, wenn du noch den erweiterten CYK-Algorithmus behandeln könntest, der dann auch den Ableitungsbaum angibt. (behandelt z.B. in ls1-www.cs.uni-dortmund.de/images/user/logidac/tick/Lehre/15SS/GTI/13-syntaxanalysew.pdf ) - die Folien sind für mich extrem verwirrend und vollgepackt ^^"

  • @SakazeImo
    @SakazeImo8 жыл бұрын

    Bei der Erklärung am Anfang wäre es sinnvoll, wenn du die Nichtterminale anders genannt hättest als die Terminale. Sonst war die Erklärung super!^^

  • @andrekohler5792
    @andrekohler57925 жыл бұрын

    Jetzt würde mich noch interessieren, wofür das in der Praxis tatsächlich eingesetzt wird.

  • @NLogSpace

    @NLogSpace

    5 жыл бұрын

    Das Wortproblem für kontextfreie Grammatiken muss zum Beispiel jedes mal gelöst werden, wenn man einen Quelltext geschrieben hat und dann auf "Kompilieren" drückt. Denn die Syntax einer Programmiersprache ist üblicherweise in einer kontextfreien Grammatik formuliert und ein syntaktisch korrekter Quelltext ist ein Wort in der Sprache. Dafür werden allerdings andere Algorithmen benutzt, die effizienter sind als der CYK-Algorithmus, da die Programmiersprachen auch in effizienteren Teilfragmenten der kontextfreien Sprachen liegen. Der CYK-Algorithmus klappt hingegen für beliebige kontextfreie Sprachen.

  • @jamalmonawer1964
    @jamalmonawer19645 жыл бұрын

    Vielen Dank, ..... kann man auch aus CYK-Tabelle irgendwie die Ableitung erhalten?

  • @NLogSpace

    @NLogSpace

    5 жыл бұрын

    Schau Dir das Video zum erweiterten CYK-Algorithmus an! (Nr. 30a)

  • @TheGanner1
    @TheGanner15 жыл бұрын

    11:39 was ich nicht ganz versteh warum hast du beim ersten mal DA zu AD umgewandelt aber beim zweiten mal DA nicht mehr zu AD ist doch eigentlich zweimal die gleiche Situation

  • @NLogSpace

    @NLogSpace

    5 жыл бұрын

    Ich verstehe nicht. Was meinst Du mit DA zu AD umgewandelt?

  • @TheGanner1

    @TheGanner1

    5 жыл бұрын

    @@NLogSpace hat sich erledigt hab die zustände A und D gemeint, aber du liest ja in der matrix immer von links nach rechts, deswegen war es einmal das zustands pärchen d und a und dann a und d beim zweiten dreier wort. Hat bissl gedauert bis ichs gecheckt hab. Gutes video aber

  • @D3rMesaa
    @D3rMesaa3 жыл бұрын

    Ich spreche es "SUK"

  • @DailyShit.
    @DailyShit.11 ай бұрын

    Als Pyramide ist das so viel anschaulicher als mit dem Dreieck

  • @tazplay3476
    @tazplay34765 жыл бұрын

    Danke!