Informatique
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

La science informatique

La science informatique est une science formelle, son objet d'étude est le calcul, calcul au sens large, c'est-à-dire non limité exclusivement à la manipulation des nombres, mais de tout type d'information formelle que l'on peut traiter de manière systématique (En sciences de la vie et en histoire naturelle, la systématique est la science qui a pour objet de dénombrer et de classer les taxons dans un certain...) tel que : textes, couleurs, données, valeurs logiques. Selon les contextes, on parle d'un calcul, d'un algorithme, d'un programme, d'une procédure, etc.

Calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la...)

Un algorithme est une manière systématique de procéder pour arriver à calculer un résultat. Un des exemples classiques est l'algorithme d'Euclide (Euclide, en grec ancien Εὐκλείδης Eukleidês (né vers -325, mort vers -265 à Alexandrie) est un mathématicien de la...) du calcul du « Plus grand commun diviseur » (PGCD) qui remonte au moins à 300 ans av. J.-C.
Mais il s'agit déjà d'un calcul complexe ; encore avant cela, le simple fait d'utiliser un abaque demande d'avoir réfléchi sur un moyen systématique (et correct) d'utiliser cet abaque pour réaliser des opérations arithmétiques.

Des algorithmes existent donc depuis l'Antiquité, mais ce n'est que depuis les années 1930, avec les débuts de la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur l’observation ou...) de la calculabilité que les scientifiques se sont posés la question « qu'est ce qu'un modèle de calcul ? » et « est-ce que tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) est calculable ? ». Une des premières choses a été pour les scientifiques de répondre de manière formelle à ces deux questions.

Il existe de nombreux modèles de calcul, mais les deux plus centraux sont les « machine de Turing » et le « lambda calcul ». Ces deux systèmes formels définissent des objets qui peuvent représenter ce qu'on appelle de procédures de calcul, des algorithmes ou des programmes. Ils définissent ensuite un moyen systématique d'appliquer ces procédures, c'est-à-dire de calculer.

Le résultat le plus important de la calculabilité est probablement la thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à l'égard du sujet ou du thème qu'il évoque.) de Church qui postule que tous les modèles de calcul ont la même puissance (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :). C'est-à-dire qu'il n'existe pas une procédure que l'on pourrait exprimer dans un modèle mais pas dans un autre.

Un deuxième résultat fondamental est l'existence de fonctions incalculables. Une fonction étant ce que calcule une procédure ou un algorithme (ceux-ci désignant plutôt comment faire le calcul). On peut montrer qu'il existe des fonctions, bien définies, pour lesquelles il n'existe pas de procédure pour les calculer. L'exemple le plus connu étant probablement le problème de l'arrêt qui montre qu'il n'existe pas de machine de Turing calculant si une autre machine de Turing donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) s'arrêtera (et donc donnera un résultat) ou non. Selon la thèse de Church-Turing, tous les modèles de calcul sont équivalents, par conséquent ce résultat s'applique aussi aux autres modèles, ce qui inclut les programmes et logiciels que l'on peut trouver dans les ordinateurs courants. À noter qu'il existe un lien très fort entre les fonctions que l'on ne peut pas calculer et les problèmes que l'on ne peut pas décider (voir Décidabilité et indécidabilité).

Algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de résolution, par le calcul, d'un...)

Une fois la notion de calcul définie, la suite a été de se consacrer à l'algorithmique, c'est-à-dire l'étude des algorithmes.
Le but est trouver effectivement des procédures correctes et de les comparer entre elles. En effet, tous les algorithmes ne se valent pas : le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'opérations nécessaires pour arriver au résultat diffère d'un algorithme à l'autre. Ce nombre d'opération, appelé la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en sciences...) algorithmique est le sujet de la théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un problème peut être résolu par un...) des algorithmes, qui constitue une préoccupation essentielle en algorithmique.

La complexité algorithmique sert en particulier à déterminer comment le nombre d'opérations nécessaires évolue en fonction du nombre d'éléments à traiter (la taille des données) :

  • soit l'évolution peut être indépendante de la taille des données, on parle alors de complexité constante ;
  • soit le nombre d'opérations peut augmenter selon un rapport logarithmique, linéaire, polynomial ou exponentiel (dans l'ordre décroissant d'efficacité et pour ne citer que les plus répandues) ;
    • une augmentation exponentielle (La fonction exponentielle est l'une des applications les plus importantes en analyse, ou plus généralement en mathématiques et dans ses domaines d'applications. Il existe plusieurs définitions équivalentes : un morphisme...) de la complexité aboutit très rapidement à des durées de calcul déraisonnables pour une utilisation en pratique,
    • tandis que pour une complexité polynomiale (ou meilleure), le résultat sera obtenu après une durée de calcul réduite, même avec de grandes quantités de données.

Nous arrivons maintenant un problème ouvert fondamental en informatique : « P est-il égal à NP ? »

En simplifiant beaucoup : P est « l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) des problèmes pour lesquels on connaît un algorithme efficace » et NP « l'ensemble des problèmes pour lesquels on connaît un algorithme efficace pour vérifier une solution à ce problème ».
Et en simplifiant encore plus : existe-t-il des problèmes difficiles ? Des problèmes pour lesquels il n'existe pas d'algorithme efficace.

Cette question est non seulement d'un grand intérêt théorique mais aussi pratique. En effet un grand nombre de problèmes courants et utiles sont des problèmes que l'on ne sait pas résoudre de manière efficace. C'est d'ailleurs un des problèmes du prix du millénaire (Un millénaire est une période de mille années, c'est-à-dire de dix siècles.) et le Clay Mathematical Institute s'est engagé à verser un million (Un million (1 000 000) est l'entier naturel qui suit neuf cent quatre-vingt-dix-neuf mille neuf cent quatre-vingt-dix-neuf (999 999) et qui...) de $ aux personnes qui en trouveraient la solution.

Comme nous venons de le dire : c'est un problème ouvert, donc formellement il n'y a pas de réponse reconnue. Mais, en pratique, la plupart des spécialistes s'accordent pour penser que P≠NP, c'est-à-dire qu'il existe effectivement des problèmes difficiles qui n'admettent pas d'algorithme efficace.

Cryptologie

Ce type de problème de complexité algorithmique est directement utilisé en cryptologie. En effet les méthodes de cryptologie modernes reposent sur l'existence d'une fonction facile à calculer qui possède une fonction réciproque (La réciproque est une relation d'implication.) difficile à calculer. C'est ce qui permet de chiffrer un message (La théorie de l'information fut mise au point pour déterminer mathématiquement le taux d’information transmis dans la communication d’un message par un canal de communication, notamment en présence de parasites...) qui sera difficile à décrypter (sans la clé).
La plupart des chiffrements (méthode de cryptographie) reposent sur le fait que la procédure de Décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant...) en produit de facteurs premiers n'a pas d'algorithme efficace connu. Si quelqu'un trouvait un tel algorithme il serait capable de décrypter la plupart des cryptogrammes facilement. On sait d'ailleurs qu'un calculateur quantique (Un ordinateur quantique (ou rarement calculateur quantique) repose sur des propriétés quantiques de la matière : superposition et intrication d'états quantiques. De...) en serait capable, mais ce genre d'ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des...) n'existe pas, en tout cas pour le moment.

Autre

Plus récemment, et à la frontière (Une frontière est une ligne imaginaire séparant deux territoires, en particulier deux États souverains. Le rôle que joue une frontière peut fortement varier suivant les régions et les époques. Entre les pays...) avec la logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et raisonnement) est dans une première approche...) mathématique : la correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le terme désigne des échanges de courrier personnels plutôt qu'administratifs.) de Curry-Howard a jeté un pont (Un pont est une construction qui permet de franchir une dépression ou un obstacle (cours d'eau, voie de communication, vallée, etc.) en passant par-dessus cette séparation. Le...) entre le monde (Le mot monde peut désigner :) des démonstrations formelles et celui des programmes.

Citons aussi l'étude de la mécanisation des procédés de calcul et de pensée qui a permis de mieux comprendre la réflexion humaine, et apporté des éclairages en psychologie cognitive et en linguistique.

Page générée en 0.128 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique