Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
LangageLe langage est la capacité d'exprimer une pensée et de communiquer au moyen d'un système de signes (vocaux, gestuel, graphiques, tactiles, olfactifs, etc.) doté d'une sémantique, et le plus souvent d'une syntaxe — mais ce n'est pas systématique (la cartographie est un exemple de langage non syntaxique). Fruit d'une acquisition, la langue est une des nombreuses manifestations du langage. Les langages sont constitués de signaux correspondant au support physique de l'information.
Grammaire de dépendanceOn désigne par grammaire de dépendance une approche de la syntaxe fondée par Lucien Tesnière. Elle se distingue par la place centrale donnée à une structure hiérarchique, appelée Stemma par Lucien Tesnière, mais plus connue aujourd'hui sous le terme d’arbre de dépendance. L'arbre de dépendance est un arbre, au sens mathématique du terme, représentant les liens syntaxiques entre les mots d'une phrase. Les grammaires de dépendance ne réfèrent donc pas à un cadre théorique restreint, mais la notion de dépendance peut être explicite ou implicite dans la formalisation des règles syntaxiques.
Grammaire non contextuelle déterministeEn informatique théorique, et particulièrement dans la théorie des grammaires formelles, les grammaires context-free déterministes ( DCFG ) ou grammaires non contextuelles déterministes sont un sous-ensemble des grammaires non contextuelles. Ce sont les grammaires non contextuelles qui peuvent être dérivées d'automates à pile déterministes, et ils engendrent les langages non contextuels déterministes. Les DCFG sont toujours inambigües et ils constituent une sous-classe importante des grammaires non contextuelles ; il existe cependant des CFG inambigües qui ne sont pas déterministes.
Langue contrôléeEn linguistique, une langue contrôlée (LC) est généralement définie comme sous-ensemble d'une langue naturelle, dont la grammaire et le vocabulaire ont été restreints afin de réduire l'ambigüité et la complexité des textes. On distingue traditionnellement deux groupes de langues contrôlées : les LC pour les humains, qui visent à améliorer la lisibilité des documents et à en faciliter la compréhension. les LC pour les machines, qui visent à faciliter le traitement automatique de textes.
Langage naturelUn langage naturel, ou langage ordinaire, est une langue « normale » parlée par un être humain. Il s'oppose au langage formel, tel que le langage informatique, ainsi qu'aux langues construites. histoire des langues On désigne par langage naturel le langage parlé par les humains, apparu entre et avant notre ère.
Grammaire générative et transformationnelleLa grammaire générative et transformationnelle est une théorie syntaxique s’inscrivant dans le courant de la linguistique générative. Majoritairement présente en Amérique du Nord, elle s’est développée depuis 1957 sous l’impulsion de Noam Chomsky. Cette théorie tente de caractériser la connaissance de la langue qui permet l'acte effectif du locuteur-auditeur. La grammaire générative est basée sur la distinction entre compétence et performance (connaissance que le locuteur-auditeur a de sa langue contre l’emploi effectif de la langue dans des situations concrètes).
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
Arbre syntaxiqueUn arbre syntaxique est un arbre permettant de représenter la syntaxe d'un objet. En linguistique, l'arbre syntaxique représente la structure syntaxique d'une phrase. Le nombre de catégories morphosyntaxiques correspondent à des classes distributionnelles, c'est-à-dire à la place qu'elles occupent dans la phrase, sur l'axe syntagmatique. En fonction de son voisinage, chaque élément peut commuter avec un autre élément de même catégorie.
Inversion (linguistique)En linguistique, l’inversion est un procédé par lequel on change l’ordre canonique (attendu, consacré, habituel, normal) de deux entités grammaticales, en intervertissant leurs places. Ces entités peuvent être les éléments d’une forme grammaticale composée, les composants d’un syntagme, des termes à fonction syntaxique d’une phrase simple ou des propositions d’une phrase complexe.
