Metraipolis › archive › dc_74f69cd97336

Algorithme de Cocke-Younger-Kasami — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T11:42:50.586Z
SHA-256 of the archived text
715441554291ac1e26ab22e50cc765fbb7d60270d400619312365cc2709f60ec
Stable URL of this page
https://metraipolis.com/documento/dc_74f69cd97336

How to cite

Algorithme de Cocke-Younger-Kasami — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_74f69cd97336 (Metraipolis archive dc_74f69cd97336, sha256 715441554291ac1e26ab22e50cc765fbb7d60270d400619312365cc2709f60ec)
BibTeX
@misc{dc74f69cd97336,
  title = {Algorithme de Cocke-Younger-Kasami — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_74f69cd97336; sha256 715441554291ac1e26ab22e50cc765fbb7d60270d400619312365cc2709f60ec},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En informatique théorique et en théorie des langages, l'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles, publié par Itiroo Sakai en 1961. Il permet de déterminer si un mot est engendré par une grammaire, et si oui, d'en donner un arbre syntaxique. L'algorithme est nommé d'après trois autres personnes qui l'ont redécouvert indépendamment : T. Kasami, D.H. Younger, puis J. Cocke et J.T. Schwartz. L'algorithme opère par analyse ascendante et emploie la programmation dynamique. L'algorithme suppose que la grammaire est en forme normale de Chomsky. Cette restriction n'est pas gênante dans la mesure où toute grammaire non contextuelle admet une grammaire en forme normale de Chomsky équivalente. Le temps de calcul de cet algorithme est en O ( | m | 3 ⋅ | G | ) {\displaystyle O(|m|^{3}\cdot |G|)} , où | m | {\displaystyle |m|} est la longueur du mot m {\displaystyle m} à analyser et | G | {\displaystyle |G|} est la taille de la grammaire.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Algorithme de Cocke-Younger-Kasami» — https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami
Wikidata Q954821 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q954821
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 232410320, consultata il 2026-10-17T11:13:55.668Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b19712bb233a3ea0b8dce3281f07fd3a972eadb1f9f69d3be01a426ff6ab4844