Informatique théorique - Theoretical computer science

Une représentation artistique d'une machine de Turing . Les machines de Turing sont utilisées pour modéliser des appareils informatiques généraux.

L'informatique théorique ( TCS ) est un sous-ensemble de l' informatique générale et des mathématiques qui se concentre sur les aspects mathématiques de l' informatique tels que la théorie du calcul , le calcul lambda et la théorie des types .

Il est difficile de circonscrire précisément les domaines théoriques. Le Groupe d'intérêt spécial de l' ACM sur les algorithmes et la théorie du calcul (SIGACT) fournit la description suivante :

TCS couvre une grande variété de sujets , y compris des algorithmes , des structures de données , la complexité de calcul , parallèle et distribuée calcul, calcul probabiliste , le calcul quantique , théorie des automates , théorie de l' information , la cryptographie , la sémantique du programme et la vérification , l' apprentissage automatique , la biologie computationnelle , l' économie de calcul , de calcul géométrie , théorie des nombres computationnelle et algèbre . Les travaux dans ce domaine se distinguent souvent par l'accent mis sur la technique mathématique et la rigueur .

Histoire

Alors que l'inférence logique et la preuve mathématique existaient auparavant, en 1931, Kurt Gödel a prouvé avec son théorème d'incomplétude qu'il existe des limitations fondamentales sur les déclarations pouvant être prouvées ou réfutées.

Ces développements ont conduit à l'étude moderne de la logique et de la calculabilité , et même au domaine de l'informatique théorique dans son ensemble. La théorie de l'information a été ajoutée au domaine avec une théorie mathématique de la communication de 1948 par Claude Shannon . Dans la même décennie, Donald Hebb a introduit un modèle mathématique d' apprentissage dans le cerveau. Avec l'accumulation de données biologiques soutenant cette hypothèse avec quelques modifications, les domaines des réseaux de neurones et du traitement distribué parallèle ont été établis. En 1971, Stephen Cook et, travaillant indépendamment, Leonid Levin , ont prouvé qu'il existe des problèmes pratiquement pertinents qui sont NP-complets - un résultat marquant dans la théorie de la complexité computationnelle .

Avec le développement de la mécanique quantique au début du 20ème siècle est venu le concept selon lequel des opérations mathématiques pourraient être effectuées sur une fonction d'onde de particule entière. En d'autres termes, on pourrait calculer des fonctions sur plusieurs états simultanément. Cela a conduit au concept d'un ordinateur quantique dans la seconde moitié du 20e siècle qui a décollé dans les années 1990 lorsque Peter Shor a montré que de telles méthodes pouvaient être utilisées pour factoriser de grands nombres en temps polynomial , ce qui, s'il était mis en œuvre, rendrait certains les algorithmes de cryptographie à clé publique comme RSA_(cryptosystem) ne sont pas sécurisés.

La recherche informatique théorique moderne est basée sur ces développements de base, mais comprend de nombreux autres problèmes mathématiques et interdisciplinaires qui ont été posés, comme indiqué ci-dessous :

Exemple DFA.svg Courbe elliptique simple.png 6n-graf.svg Wang tuiles.svg P = NP  ?
Logique mathématique Théorie des automates La théorie du nombre La théorie des graphes Théorie de la calculabilité Théorie de la complexité computationnelle
GNITIRW-TERCES Diagramme commutatif pour morphism.svg SimplexRangeSearching.svg TSP Allemagne 3.png Blochsphere.svg
Cryptographie Théorie des types Théorie des catégories Géométrie computationnelle Optimisation combinatoire Théorie de l'informatique quantique

Les sujets

Algorithmes

Un algorithme est une procédure étape par étape pour les calculs. Les algorithmes sont utilisés pour le calcul , le traitement des données et le raisonnement automatisé .

Un algorithme est une méthode efficace exprimée comme une liste finie d'instructions bien définies pour calculer une fonction . Partant d'un état initial et d'une entrée initiale (peut-être vide ), les instructions décrivent un calcul qui, lorsqu'il est exécuté , passe par un nombre fini d'états successifs bien définis, produisant finalement une "sortie" et se terminant à un état final final. Le passage d'un état au suivant n'est pas forcément déterministe ; certains algorithmes, appelés algorithmes aléatoires , intègrent une entrée aléatoire.

Théorie des automates

La théorie des automates est l'étude des machines abstraites et des automates , ainsi que des problèmes informatiques qui peuvent être résolus en les utilisant. C'est une théorie en informatique théorique, sous mathématiques discrètes (une section de mathématiques et aussi d' informatique ). Automata vient du mot grec αὐτόματα signifiant "auto-agissant".

La théorie des automates est l'étude des machines virtuelles autonomes pour aider à la compréhension logique des processus d'entrée et de sortie, sans ou avec étape(s) intermédiaire(s) de calcul (ou toute fonction /processus).

Théorie du codage

La théorie du codage est l'étude des propriétés des codes et de leur adéquation à une application spécifique. Les codes sont utilisés pour la compression de données , la cryptographie , la correction d'erreurs et plus récemment également pour le codage réseau . Les codes sont étudiés par diverses disciplines scientifiques, telles que la théorie de l'information , le génie électrique , les mathématiques et l' informatique, dans le but de concevoir des méthodes de transmission de données efficaces et fiables . Cela implique généralement la suppression de la redondance et la correction (ou la détection) d'erreurs dans les données transmises.

Biologie computationnelle

La biologie computationnelle implique le développement et l'application de méthodes d'analyse des données et théoriques, de modélisation mathématique et de techniques de simulation informatique à l'étude des systèmes biologiques, comportementaux et sociaux. Le domaine est largement défini et comprend des bases en informatique, mathématiques appliquées , animation , statistiques , biochimie , chimie , biophysique , biologie moléculaire , génétique , génomique , écologie , évolution , anatomie , neurosciences et visualisation .

La biologie computationnelle est différente du calcul biologique , qui est un sous-domaine de l'informatique et du génie informatique utilisant la bio - ingénierie et la biologie pour construire des ordinateurs , mais est similaire à la bioinformatique , qui est une science interdisciplinaire utilisant des ordinateurs pour stocker et traiter des données biologiques.

Théorie de la complexité computationnelle

La théorie de la complexité computationnelle est une branche de la théorie du calcul qui se concentre sur la classification des problèmes de calcul en fonction de leur difficulté inhérente et sur la mise en relation de ces classes entre elles. Un problème de calcul est compris comme une tâche qui peut en principe être résolue par un ordinateur, ce qui équivaut à affirmer que le problème peut être résolu par l'application mécanique d'étapes mathématiques, telles qu'un algorithme .

Un problème est considéré comme intrinsèquement difficile si sa résolution nécessite des ressources importantes, quel que soit l' algorithme utilisé. La théorie formalise cette intuition, en introduisant des modèles mathématiques de calcul pour étudier ces problèmes et en quantifiant la quantité de ressources nécessaires pour les résoudre, telles que le temps et le stockage. D'autres mesures de complexité sont également utilisées, telles que la quantité de communication (utilisée dans la complexité de la communication ), le nombre de portes dans un circuit (utilisé dans la complexité du circuit ) et le nombre de processeurs (utilisés dans le calcul parallèle ). L'un des rôles de la théorie de la complexité computationnelle est de déterminer les limites pratiques de ce que les ordinateurs peuvent et ne peuvent pas faire.

Géométrie computationnelle

La géométrie computationnelle est une branche de l'informatique consacrée à l'étude des algorithmes qui peuvent être énoncés en termes de géométrie . Certains problèmes purement géométriques découlent de l'étude des algorithmes géométriques computationnels, et de tels problèmes sont également considérés comme faisant partie de la géométrie computationnelle. Bien que la géométrie computationnelle moderne soit un développement récent, c'est l'un des plus anciens domaines de l'informatique dont l'histoire remonte à l'Antiquité. Un ancien précurseur est le traité sanskrit Shulba Sutras , ou "Règles de l'accord", qui est un livre d'algorithmes écrit en 800 avant notre ère. Le livre prescrit des procédures étape par étape pour la construction d'objets géométriques comme des autels à l'aide d'une cheville et d'une corde.

L'impulsion principale pour le développement de la géométrie computationnelle en tant que discipline a été les progrès de l'infographie et de la conception et de la fabrication assistées par ordinateur ( CAO / FAO ), mais de nombreux problèmes en géométrie computationnelle sont de nature classique et peuvent provenir de la visualisation mathématique .

D'autres applications importantes de la géométrie computationnelle incluent la robotique (problèmes de planification de mouvement et de visibilité), les systèmes d'information géographique (SIG) (localisation et recherche géométriques, planification d'itinéraire), la conception de circuits intégrés (conception et vérification de la géométrie IC), l'ingénierie assistée par ordinateur (CAE) (génération de maillage), vision par ordinateur (reconstruction 3D).

Théorie de l'apprentissage informatique

Les résultats théoriques en apprentissage automatique traitent principalement d'un type d'apprentissage inductif appelé apprentissage supervisé. Dans l'apprentissage supervisé, un algorithme reçoit des échantillons qui sont étiquetés de manière utile. Par exemple, les échantillons peuvent être des descriptions de champignons et les étiquettes peuvent indiquer si les champignons sont comestibles ou non. L'algorithme prend ces échantillons préalablement étiquetés et les utilise pour induire un classificateur. Ce classificateur est une fonction qui attribue des étiquettes aux échantillons, y compris les échantillons qui n'ont jamais été vus auparavant par l'algorithme. L'objectif de l'algorithme d'apprentissage supervisé est d'optimiser certaines mesures de performance telles que la minimisation du nombre d'erreurs commises sur de nouveaux échantillons.

Théorie numérique des nombres

La théorie computationnelle des nombres , également connue sous le nom de théorie algorithmique des nombres , est l'étude des algorithmes permettant d'effectuer des calculs théoriques des nombres . Le problème le plus connu dans le domaine est la factorisation d'entiers .

Cryptographie

La cryptographie est la pratique et l'étude des techniques de communication sécurisée en présence de tiers (appelés adversaires ). Plus généralement, il s'agit de construire et d'analyser des protocoles qui surmontent l'influence des adversaires et qui sont liés à divers aspects de la sécurité de l'information tels que la confidentialité des données , l'intégrité des données , l' authentification et la non-répudiation . La cryptographie moderne recoupe les disciplines des mathématiques , de l' informatique et du génie électrique . Les applications de la cryptographie comprennent les cartes ATM , les mots de passe informatiques et le commerce électronique .

La cryptographie moderne est fortement basée sur la théorie mathématique et la pratique informatique ; Les algorithmes cryptographiques sont conçus autour d' hypothèses de dureté de calcul , ce qui rend ces algorithmes difficiles à briser en pratique par tout adversaire. Il est théoriquement possible de casser un tel système, mais il est impossible de le faire par tout moyen pratique connu. Ces schémas sont donc qualifiés de sécurité informatique ; les avancées théoriques, par exemple les améliorations des algorithmes de factorisation des nombres entiers , et la technologie informatique plus rapide nécessitent que ces solutions soient continuellement adaptées. Il existe des schémas de sécurité théorique de l'information qui ne peuvent pas être brisés même avec une puissance de calcul illimitée - un exemple est le bloc à usage unique - mais ces schémas sont plus difficiles à mettre en œuvre que les meilleurs mécanismes théoriquement cassables mais sécurisés du point de vue informatique.

Structures de données

Une structure de données est une manière particulière d'organiser les données dans un ordinateur afin qu'elles puissent être utilisées efficacement .

Différents types de structures de données sont adaptés à différents types d'applications, et certaines sont hautement spécialisées pour des tâches spécifiques. Par exemple, les bases de données utilisent des index B-tree pour de petits pourcentages de récupération de données et les compilateurs et les bases de données utilisent des tables de hachage dynamiques comme tables de recherche.

Les structures de données offrent un moyen de gérer efficacement de grandes quantités de données pour des utilisations telles que les grandes bases de données et les services d'indexation Internet . Habituellement, des structures de données efficaces sont essentielles à la conception d' algorithmes efficaces . Certaines méthodes de conception formelles et certains langages de programmation mettent l'accent sur les structures de données, plutôt que sur les algorithmes, en tant que facteur d'organisation clé dans la conception de logiciels. Le stockage et la récupération peuvent être effectués sur des données stockées à la fois dans la mémoire principale et dans la mémoire secondaire .

Calcul distribué

L'informatique distribuée étudie les systèmes distribués. Un système distribué est un système logiciel dans lequel des composants situés sur des ordinateurs en réseau communiquent et coordonnent leurs actions en transmettant des messages . Les composants interagissent les uns avec les autres afin d'atteindre un objectif commun. Trois caractéristiques importantes des systèmes distribués sont : la simultanéité des composants, l'absence d'horloge globale et la défaillance indépendante des composants. Les exemples de systèmes distribués varient des systèmes basés sur la SOA aux jeux en ligne massivement multijoueurs en passant par les applications peer-to-peer et les réseaux blockchain comme Bitcoin .

Un programme informatique qui s'exécute dans un système distribué est appelé programme distribué , et la programmation distribuée est le processus d'écriture de tels programmes. Il existe de nombreuses alternatives pour le mécanisme de transmission de messages, y compris les connecteurs de type RPC et les files d'attente de messages . Un objectif et un défi important des systèmes distribués est la transparence de l'emplacement .

Complexité basée sur l'information

La complexité basée sur l'information (IBC) étudie les algorithmes optimaux et la complexité de calcul pour les problèmes continus. IBC a étudié des problèmes continus tels que l'intégration de chemin, les équations aux dérivées partielles, les systèmes d'équations différentielles ordinaires, les équations non linéaires, les équations intégrales, les points fixes et l'intégration de très grande dimension.

Méthodes formelles

Les méthodes formelles sont un type particulier de techniques basées sur les mathématiques pour la spécification , le développement et la vérification de systèmes logiciels et matériels . L'utilisation de méthodes formelles pour la conception de logiciels et de matériel est motivée par l'attente que, comme dans d'autres disciplines d'ingénierie, l'exécution d'une analyse mathématique appropriée peut contribuer à la fiabilité et à la robustesse d'une conception.

Les méthodes formelles sont mieux décrites comme l'application d'une assez large variété de fondements théoriques de l'informatique, en particulier les calculs logiques , les langages formels , la théorie des automates et la sémantique des programmes , mais aussi les systèmes de types et les types de données algébriques à des problèmes de spécification logicielle et matérielle et vérification.

Théorie de l'information

La théorie de l'information est une branche des mathématiques appliquées , du génie électrique et de l' informatique impliquant la quantification de l' information . La théorie de l'information a été développée par Claude E. Shannon pour trouver des limites fondamentales sur les opérations de traitement du signal telles que la compression de données et sur le stockage et la communication fiables des données. Depuis sa création, il s'est élargi pour trouver des applications dans de nombreux autres domaines, notamment l'inférence statistique , le traitement du langage naturel , la cryptographie , la neurobiologie , l'évolution et la fonction des codes moléculaires, la sélection de modèles en statistique, la physique thermique, l'informatique quantique , la linguistique , la détection de plagiat, reconnaissance de formes , détection d'anomalies et autres formes d' analyse de données .

Les applications des sujets fondamentaux de la théorie de l'information incluent la compression de données sans perte (par exemple les fichiers ZIP ), la compression de données avec perte (par exemple les MP3 et les JPEG ) et le codage de canal (par exemple pour la ligne d'abonné numérique (DSL) ). Le domaine est à l'intersection des mathématiques , des statistiques , de l' informatique , de la physique , de la neurobiologie et du génie électrique . Son impact a été crucial pour le succès des missions Voyager dans l'espace lointain, l'invention du disque compact, la faisabilité des téléphones portables, le développement d' Internet , l'étude de la linguistique et de la perception humaine, la compréhension des trous noirs , et de nombreux autres domaines. Sous-domaines de la théorie de l' information sont importantes codage source , codage de canal , théorie de la complexité algorithmique , théorie de l' information algorithmique , la sécurité de l' information-théorétique , ainsi que des mesures d'information.

Apprentissage automatique

L'apprentissage automatique est une discipline scientifique qui traite de la construction et de l'étude d' algorithmes capables d' apprendre à partir de données. De tels algorithmes fonctionnent en construisant un modèle basé sur des entrées et en l'utilisant pour faire des prédictions ou des décisions, plutôt que de suivre uniquement des instructions explicitement programmées.

L'apprentissage automatique peut être considéré comme un sous-domaine de l'informatique et des statistiques . Il a des liens étroits avec l' intelligence artificielle et l' optimisation , qui fournissent des méthodes, des théories et des domaines d'application sur le terrain. L'apprentissage automatique est utilisé dans une gamme de tâches informatiques où la conception et la programmation d' algorithmes explicites basés sur des règles sont impossibles. Des exemples d'applications incluent le filtrage anti - spam , la reconnaissance optique de caractères (OCR), les moteurs de recherche et la vision par ordinateur . L'apprentissage automatique est parfois confondu avec l'exploration de données , bien que cela se concentre davantage sur l'analyse exploratoire des données. L'apprentissage automatique et la reconnaissance de formes "peuvent être considérés comme deux facettes du même domaine".

Calcul parallèle

Le calcul parallèle est une forme de calcul dans laquelle de nombreux calculs sont effectués simultanément, fonctionnant sur le principe que les gros problèmes peuvent souvent être divisés en plus petits, qui sont ensuite résolus "en parallèle" . Il existe plusieurs formes différentes de calcul parallèle : au niveau du bit , au niveau des instructions , aux données et au parallélisme des tâches . Le parallélisme est utilisé depuis de nombreuses années, principalement dans le calcul haute performance , mais son intérêt s'est accru ces derniers temps en raison des contraintes physiques empêchant la mise à l'échelle des fréquences . La consommation d'énergie (et par conséquent la production de chaleur) par les ordinateurs étant devenue une préoccupation ces dernières années, le calcul parallèle est devenu le paradigme dominant dans l'architecture informatique , principalement sous la forme de processeurs multicœurs .

Les programmes informatiques parallèles sont plus difficiles à écrire que les programmes séquentiels, car la concurrence introduit plusieurs nouvelles classes de bogues logiciels potentiels , dont les conditions de concurrence sont les plus courantes. La communication et la synchronisation entre les différentes sous-tâches sont généralement parmi les plus grands obstacles à l'obtention de bonnes performances de programme parallèle.

L' accélération maximale possible d'un seul programme à la suite de la parallélisation est connue sous le nom de loi d'Amdahl .

Sémantique du programme

Dans la théorie des langages de programmation , la sémantique est le domaine concerné par l'étude mathématique rigoureuse de la signification des langages de programmation . Il le fait en évaluant la signification des chaînes syntaxiquement légales définies par un langage de programmation spécifique, montrant le calcul impliqué. Dans un tel cas où l'évaluation serait des chaînes syntaxiquement illégales, le résultat serait un non-calcul. La sémantique décrit les processus suivis par un ordinateur lors de l'exécution d'un programme dans ce langage spécifique. Cela peut être montré en décrivant la relation entre l'entrée et la sortie d'un programme, ou une explication de la façon dont le programme s'exécutera sur une certaine plate - forme , créant ainsi un modèle de calcul .

Calcul quantique

Un ordinateur quantique est un système de calcul qui utilise directement des phénomènes de mécanique quantique , tels que la superposition et l' intrication , pour effectuer des opérations sur des données . Les ordinateurs quantiques sont différents des ordinateurs numériques à transistors . Alors que les ordinateurs numériques nécessitent que les données soient codées en chiffres binaires ( bits ), dont chacun est toujours dans l'un des deux états définis (0 ou 1), le calcul quantique utilise des qubits (bits quantiques), qui peuvent être dans des superpositions d'états. Un modèle théorique est la machine quantique de Turing , également connue sous le nom d'ordinateur quantique universel. Les ordinateurs quantiques partagent des similitudes théoriques avec les ordinateurs non déterministes et probabilistes ; un exemple est la capacité d'être dans plus d'un état simultanément. Le domaine de l'informatique quantique a été introduit pour la première fois par Yuri Manin en 1980 et Richard Feynman en 1982. Un ordinateur quantique avec des spins en tant que bits quantiques a également été formulé pour être utilisé comme espace-temps quantique en 1968.

En 2014, l'informatique quantique en est encore à ses balbutiements, mais des expériences ont été menées dans lesquelles des opérations de calcul quantique ont été exécutées sur un très petit nombre de qubits. La recherche pratique et théorique se poursuit, et de nombreux gouvernements nationaux et agences de financement militaires soutiennent la recherche en informatique quantique pour développer des ordinateurs quantiques à des fins de sécurité civile et nationale, telles que la cryptanalyse .

Calcul symbolique

L'algèbre informatique , également appelée calcul symbolique ou calcul algébrique, est un domaine scientifique qui fait référence à l'étude et au développement d' algorithmes et de logiciels pour manipuler des expressions mathématiques et d'autres objets mathématiques . Bien que, à proprement parler, le calcul formel doive être un sous-domaine du calcul scientifique , ils sont généralement considérés comme des domaines distincts car le calcul scientifique est généralement basé sur le calcul numérique avec des nombres à virgule flottante approximatifs , tandis que le calcul symbolique met l'accent sur le calcul exact avec des expressions contenant des variables qui n'ont pas n'importe quelle valeur donnée et sont donc manipulés comme des symboles (d'où le nom de calcul symbolique ).

Les applications logicielles qui effectuent des calculs symboliques sont appelées systèmes d'algèbre informatique , le terme système faisant allusion à la complexité des principales applications qui incluent, au moins, une méthode pour représenter des données mathématiques dans un ordinateur, un langage de programmation utilisateur (généralement différent du langage utilisé pour la mise en œuvre), un gestionnaire de mémoire dédié, une interface utilisateur pour l'entrée/sortie d'expressions mathématiques, un grand ensemble de routines pour effectuer des opérations habituelles, comme la simplification des expressions, la différenciation à l' aide de la règle de la chaîne , la factorisation polynomiale , l' intégration indéfinie , etc. .

Très grande échelle d'intégration

L'intégration à très grande échelle ( VLSI ) est le processus de création d'un circuit intégré (IC) en combinant des milliers de transistors en une seule puce. Le VLSI a débuté dans les années 1970, lorsque des technologies complexes de semi - conducteurs et de communication étaient en cours de développement. Le microprocesseur est un dispositif VLSI. Avant l'introduction de la technologie VLSI, la plupart des circuits intégrés disposaient d'un ensemble limité de fonctions qu'ils pouvaient exécuter. Un circuit électronique peut être constitué d'un processeur , d'une ROM , d'une RAM et d'une autre logique de collage . VLSI permet aux fabricants de circuits intégrés d'ajouter tous ces circuits dans une seule puce.

Organisations

Revues et newsletters

Conférences

Voir également

Remarques

  1. ^ "SIGACT" . Récupéré le 2017-01-19 .
  2. ^ « Tout algorithme mathématique classique, par exemple, peut être décrit en un nombre fini de mots anglais » (Rogers 1987 : 2).
  3. ^ Bien défini par rapport à l'agent qui exécute l'algorithme : « Il existe un agent informatique, généralement humain, qui peut réagir aux instructions et effectuer les calculs » (Rogers 1987 :2).
  4. ^ "un algorithme est une procédure pour calculer une fonction (par rapport à une notation choisie pour les nombres entiers) ... cette limitation (aux fonctions numériques) n'entraîne aucune perte de généralité", (Rogers 1987:1).
  5. ^ « Un algorithme a zéro ou plusieurs entrées, c'est-à-dire des quantités qui lui sont données initialement avant que l'algorithme ne commence » (Knuth 1973 : 5).
  6. ^ « Une procédure qui a toutes les caractéristiques d'un algorithme, sauf qu'elle manque peut-être de finitude, peut être appelée une « méthode de calcul » » (Knuth 1973 : 5).
  7. ^ "Un algorithme a une ou plusieurs sorties, c'est-à-dire des quantités qui ont une relation spécifiée avec les entrées" (Knuth 1973:5).
  8. ^ Le fait qu'un processus avec des processus intérieurs aléatoires (sans compter l'entrée) soit ou non un algorithme est discutable. Rogers est d'avis que : « un calcul est effectué de manière discrète par étapes, sans l'utilisation de méthodes continues ou de dispositifs analogiques...
  9. ^ « Définition de travail du NIH de la bioinformatique et de la biologie computationnelle » (PDF) . Initiative des sciences et technologies de l'information biomédicale. 17 juillet 2000. Archivé de l'original (PDF) le 5 septembre 2012 . Consulté le 18 août 2012 .
  10. ^ "À propos du CCMB" . Centre de biologie moléculaire computationnelle . Consulté le 18 août 2012 .
  11. ^ Rivest, Ronald L. (1990). "Cryptologie". Dans J. Van Leeuwen (éd.). Manuel d'informatique théorique . 1 . Elsevier.
  12. ^ Bellare, Mihir; Rogaway, Phillip (21 septembre 2005). "Introduction". Introduction à la cryptographie moderne . p. dix.
  13. ^ Menezes, AJ; van Oorschot, CP ; Vanstone, SA (1997). Manuel de cryptographie appliquée . ISBN 978-0-8493-8523-0.
  14. ^ Paul E. Black (éd.), entrée pour la structure de données dans Dictionary of Algorithms and Data Structures . Institut national américain des normes et de la technologie . 15 décembre 2004. Version en ligne Consulté le 21 mai 2009.
  15. ^ Structure des données d' entréedans l' Encyclopædia Britannica (2009) Entrée en ligne consultée le 21 mai 2009.
  16. ^ un b Coulouris, George; Jean Dollimore ; Tim Kindberg ; Gordon Blair (2011). Systèmes distribués : concepts et conception (5e éd.). Boston : Addison-Wesley. ISBN 978-0-132-14301-1.
  17. ^ Andrews (2000) . Dolev (2000) . Ghosh (2007) , p. dix.
  18. ^ RW Butler (2001-08-06). « Qu'est-ce que les méthodes formelles ? » . Récupéré le 16/11/2006 .
  19. ^ C. Michael Holloway. "Pourquoi les ingénieurs devraient envisager des méthodes formelles" (PDF) . 16e Conférence sur les systèmes d'avionique numérique (27-30 octobre 1997). Archivé de l'original (PDF) le 16 novembre 2006 . Récupéré le 16/11/2006 . Citer le journal nécessite |journal=( aide )
  20. ^ Monin, pp.3-4
  21. ^ F. Rieke; D. Warland; R Ruyter van Steveninck ; W Bialek (1997). Pointes : Explorer le code neuronal . La presse du MIT. ISBN 978-0262681087.
  22. ^ Huelsenbeck, JP; Ronquist, F.; Nielsen, R.; Bollback, JP (2001-12-14). « Inférence bayésienne de la phylogénie et son impact sur la biologie évolutive ». Sciences . Association américaine pour l'avancement des sciences (AAAS). 294 (5550) : 2310–2314. Bibcode : 2001Sci ... 294.2310H . doi : 10.1126/science.1065889 . ISSN  0036-8075 . PMID  11743192 . S2CID  2138288 .
  23. ^ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider , Michael Dean (1998) Organisation du gène ABCR : analyse des séquences de jonction de promoteur et d'épissage, Gène 215 : 1, 111-122
  24. ^ Burnham, KP et Anderson DR (2002) Sélection de modèle et inférence multimodèle : Une approche théorique de l'information pratique, deuxième édition (Springer Science, New York) ISBN  978-0-387-95364-9 .
  25. ^ Jaynes, ET (1957-05-15). « Théorie de l'information et mécanique statistique ». Examen physique . Société américaine de physique (APS). 106 (4) : 620-630. Bibcode : 1957PhRv..106..620J . doi : 10.1103/physrev.106.620 . ISSN  0031-899X .
  26. ^ Charles H. Bennett, Ming Li et Bin Ma (2003) Chain Letters and Evolutionary Histories , Scientific American 288 : 6, 76-81
  27. ^ David R. Anderson (1er novembre 2003). « Quelques informations sur les raisons pour lesquelles les personnes dans les sciences empiriques peuvent vouloir mieux comprendre les méthodes de la théorie de l'information » (PDF) . Archivé de l'original (PDF) le 23 juillet 2011 . Récupéré le 2010-06-23 .
  28. ^ Ron Kovahi; Foster Provost (1998). "Glossaire des termes" . Apprentissage automatique . 30 : 271-274. doi : 10.1023/A:1007411609915 .
  29. ^ un bcm Bishop (2006). Reconnaissance de modèles et apprentissage automatique . Springer. ISBN 978-0-387-31073-2.
  30. ^ Wernick, Yang, Brankov, Yourganov et Strother, Machine Learning in Medical Imaging, IEEE Signal Processing Magazine , vol. 27, non. 4, juillet 2010, p. 25-38
  31. ^ Mannille, Heikki (1996). Exploration de données : apprentissage automatique, statistiques et bases de données . Conf. int. Gestion de bases de données scientifiques et statistiques. Société informatique IEEE.
  32. ^ Friedman, Jérôme H. (1998). "Exploration de données et statistiques : quel est le lien ?". Informatique et Statistiques . 29 (1) : 3-9.
  33. ^ Gottlieb, Allan; Almasi, George S. (1989). Calcul hautement parallèle . Redwood City, Californie : Benjamin/Cummings. ISBN 978-0-8053-0177-9.
  34. ^ SV Adve et al. (novembre 2008). "Recherche d'informatique parallèle à l'Illinois : L'ordre du jour de l'UPCRC" Archivé 2008-12-09 à la Wayback Machine (PDF). Parallel@Illinois, Université de l'Illinois à Urbana-Champaign. « Les principales techniques pour ces avantages en termes de performances - une fréquence d'horloge accrue et des architectures plus intelligentes mais de plus en plus complexes - frappent maintenant ce qu'on appelle le mur de puissance. L'industrie informatique a accepté que les futures augmentations de performances doivent provenir en grande partie de l'augmentation du nombre de processeurs (ou ) sur un dé, plutôt que de faire aller plus vite un seul noyau."
  35. ^ Asanovic et al. Ancienne [sagesse conventionnelle] : L'électricité est gratuite, mais les transistors sont chers. La nouvelle [sagesse conventionnelle] est [que] l'énergie est chère, mais les transistors sont "gratuits".
  36. ^ Asanovic, Krste et al. (18 décembre 2006). « Le paysage de la recherche informatique parallèle : une vue de Berkeley » (PDF) . Université de Californie, Berkeley. Rapport technique n° UCB/EECS-2006-183. "Ancien [sagesse conventionnelle] : l'augmentation de la fréquence d'horloge est la principale méthode d'amélioration des performances du processeur. Nouveau [sagesse conventionnelle] : l'augmentation du parallélisme est la principale méthode d'amélioration des performances du processeur... Même les représentants d'Intel, une société généralement associée au " une vitesse d'horloge plus élevée est meilleure », a averti que les approches traditionnelles pour maximiser les performances en optimisant la vitesse d'horloge ont été poussées à leur limite."
  37. ^ Hennessy, John L.; Patterson, David A.; Larus, James R. (1999). Organisation et conception informatique : l'interface matériel/logiciel (2. éd., 3e impression. éd.). San Francisco : Kaufmann. ISBN 978-1-55860-428-5.
  38. ^ " Quantum Computing with Molecules " article dans Scientific American par Neil Gershenfeld et Isaac L. Chuang
  39. ^ Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [ Calculable et non calculable ] (en russe). Sov.Radio. p. 13-15. Archivé de l'original le 10 mai 2013 . Consulté le 4 mars 2013 .
  40. ^ Feynman, RP (1982). « Simuler la physique avec des ordinateurs ». Journal international de physique théorique . 21 (6) : 467-488. Bibcode : 1982IJTP ... 21..467F . CiteSeerX  10.1.1.45.9310 . doi : 10.1007/BF02650179 . S2CID  124545445 .
  41. ^ Deutsch, David (1992-01-06). "Calcul quantique". Monde de la physique . 5 (6) : 57-61. doi : 10.1088/2058-7058/5/6/38 .
  42. ^ Finkelstein, David (1968). "Structure de l'espace-temps dans les interactions à haute énergie". Dans Gudehus, T.; Kaiser, G. (éd.). Interactions fondamentales à haute énergie . New York : Gordon & Brèche.
  43. ^ "Le nouveau contrôle qubit est de bon augure pour l'avenir de l'informatique quantique" . Consulté le 26 octobre 2014 .
  44. ^ Feuille de route des sciences et technologies de l'information quantique pour avoir une idée de l'orientation de la recherche.
  45. ^ A b c d e Le 2007 australien Classement des conférences TIC archivées 2009-10-02 à la Wayback Machine : niveau A +.
  46. ^ MFCS 2017
  47. ^ RSE 2018
  48. ^ a b c d e f g h i j Le classement australien 2007 des conférences sur les TIC Archivé le 02/10/2009 à la Wayback Machine : niveau A.
  49. ^ FCT 2011 (récupéré le 03-06-2013)

Lectures complémentaires

Liens externes