Transducteur finiEn informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie.
Automate fini déterministeUn automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.
Automate fini non déterministeUn automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation.
Théorie algorithmique de l'informationLa théorie algorithmique de l'information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d'un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing. Cette théorie permet également de formaliser la notion de complexité d'un objet, dans la mesure où l'on considère qu'un objet (au sens large) est d'autant plus complexe qu'il faut beaucoup d'informations pour le décrire, ou — à l'inverse — qu'un objet contient d'autant plus d'informations que sa description est longue.
Automate quantiqueEn informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis.
Machine de MealyEn informatique théorique, notamment en théorie des automates, et en théorie de la calculabilité, une machine de Mealy ou automate de Mealy est un transducteur fini (i.e. un automate fini avec une sortie) pour lequel les sorties dépendent à la fois de l'état courant et des symboles d'entrée. Cela signifie que l'étiquette de chaque transition est un couple formé d'une lettre d'entrée et d'une lettre de sortie. En particulier, la longueur du mot de sortie est égale à la longueur du mot d'entrée.
Code universelEn compression de données, un code universel est un code préfixe dont les mots ont une longueur dont l'espérance mathématique ne dépasse pas celle de la longueur des mots du code optimal à un facteur constant près. Les codages gamma, delta et omega d'Elias, les codages Zeta, de Fibonacci, de Levenshtein, d'Even-Rodeh produisent des codes préfixes et universels. Les codages unaire, de Rice et de Golomb produisent des codes préfixes non universels. Codage entropique Catégorie:Codage entropique Catégorie:Théo
Information quantiqueLa théorie de l'information quantique, parfois abrégée simplement en information quantique, est un développement de la théorie de l'information de Claude Shannon exploitant les propriétés de la mécanique quantique, notamment le principe de superposition ou encore l'intrication. L'unité qui est utilisée pour quantifier l'information quantique est le qubit, par analogie avec le bit d'information classique.
Codage de HuffmanLe codage de Huffman est un algorithme de compression de données sans perte. Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d'une estimation des probabilités d'apparition des symboles de source, un code court étant associé aux symboles de source les plus fréquents. Un code de Huffman est optimal au sens de la plus courte longueur pour un codage par symbole, et une distribution de probabilité connue.
Théorie des codesEn théorie de l'information, la théorie des codes traite des codes et de leurs propriétés et de leurs aptitudes à servir sur différents canaux de communication. On distingue deux modèles de communication : avec et sans bruit. Sans bruit, le codage de source suffit à la communication. Avec bruit, la communication est possible avec les codes correcteurs. En définissant l'information de façon mathématique, l'étape fondatrice de la théorie des codes a été franchie par Claude Shannon.
Ensemble flouLa théorie des sous-ensembles flous est une théorie mathématique du domaine de l’algèbre abstraite. Elle a été développée par Lotfi Zadeh en 1965 afin de représenter mathématiquement l'imprécision relative à certaines classes d'objets et sert de fondement à la logique floue. Les sous-ensembles flous (ou parties floues) ont été introduits afin de modéliser la représentation humaine des connaissances, et ainsi améliorer les performances des systèmes de décision qui utilisent cette modélisation.
Universal setIn set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, it can be proven in multiple ways that a universal set does not exist. However, some non-standard variants of set theory include a universal set. Many set theories do not allow for the existence of a universal set. There are several different arguments for its non-existence, based on different choices of axioms for set theory. In Zermelo–Fraenkel set theory, the axiom of regularity and axiom of pairing prevent any set from containing itself.
Video coding formatA video coding format (or sometimes video compression format) is a content representation format for storage or transmission of digital video content (such as in a data file or bitstream). It typically uses a standardized video compression algorithm, most commonly based on discrete cosine transform (DCT) coding and motion compensation. A specific software, firmware, or hardware implementation capable of compression or decompression to/from a specific video coding format is called a video codec.
Audio coding formatAn audio coding format (or sometimes audio compression format) is a content representation format for storage or transmission of digital audio (such as in digital television, digital radio and in audio and video files). Examples of audio coding formats include MP3, AAC, Vorbis, FLAC, and Opus. A specific software or hardware implementation capable of audio compression and decompression to/from a specific audio coding format is called an audio codec; an example of an audio codec is LAME, which is one of several different codecs which implements encoding and decoding audio in the MP3 audio coding format in software.
Théorie des ensembles approximatifsThéorie des ensembles approximatifs – est un formalisme mathématique proposé en 1982 par le professeur Zdzisław Pawlak. Elle généralise la théorie des ensembles classique. Un ensemble approximatif (anglais : rough set) est un objet mathématique basé sur la logique 3 états. Dans sa première définition, un ensemble approximatif est une paire de deux ensembles : une approximation inférieure et une approximation supérieure. Il existe également un type d'ensembles approximatifs défini par une paire d'ensembles flous (anglais : fuzzy set).
Codage entropiqueLe codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d'une source de données pour sa compression ou sa transmission sur un canal de communication. Les principaux types de codage entropique sont le codage de Huffman et le codage arithmétique. Le codage entropique utilise des statistiques sur la source pour construire un code, c'est-à-dire une application qui associe à une partie de la source un mot de code, dont la longueur dépend des propriétés statistiques de la source.
Set-builder notationIn set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy. Defining sets by properties is also known as set comprehension, set abstraction or as defining a set's intension. Set (mathematics)#Roster notation A set can be described directly by enumerating all of its elements between curly brackets, as in the following two examples: is the set containing the four numbers 3, 7, 15, and 31, and nothing else.
Théorie naïve des ensemblesLes ensembles sont d'une importance fondamentale en mathématiques ; en fait, de manière formelle, la mécanique interne des mathématiques (nombres, relations, fonctions, etc.) peut se définir en termes d'ensembles. Il y a plusieurs façons de développer la théorie des ensembles et plusieurs théories des ensembles existent. Par théorie naïve des ensembles, on entend le plus souvent un développement informel d'une théorie des ensembles dans le langage usuel des mathématiques, mais fondée sur les axiomes de la théorie des ensembles de Zermelo ou de Zermelo-Fraenkel avec axiome du choix dans le style du livre Naive Set Theory de Paul Halmos.
Algorithmethumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
Complémentaire (théorie des ensembles)En mathématiques, et plus particulièrement en théorie des ensembles, le complémentaire d'une partie d'un ensemble est constitué de tous les éléments de n'appartenant pas à . Le complémentaire de est . En cas de risque de confusion, si l'on veut préciser que l'on parle du complémentaire de dans , on note . Si est différent de l'ensemble vide et de , alors et forment une partition de l'ensemble . Lorsque est un ensemble fini, la somme des cardinaux de et est égale au cardinal de : D'où on déduit : Exemple Pour dénombrer les absents dans une assemblée prévue de cinquante personnes, il suffit de compter les présents.
