Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Complexité en moyenne des algorithmesLa complexité en moyenne d'un algorithme est la quantité d'une ressource donnée, typiquement le temps, utilisée par l'algorithme lors de son exécution pour traiter une entrée tirée selon une distribution donnée. Il s'agit par conséquent d'une moyenne de la complexité, pondérée entre les différentes entrées possibles selon la distribution choisie. Le plus souvent, on ne précise pas la distribution et on utilise implicitement une distribution uniforme (i.e.
Complexité dans le pire des casEn informatique, la complexité dans le pire des cas, ou complexité dans le cas le plus défavorable, mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles. Elle est exprimée comme une fonction de la taille de l'entrée de l'algorithme. Implicitement, on cherche à construire des algorithmes s'exécutant en utilisant le moins de ressources possible (e.g. le plus vite possible), et il s'agit par conséquent d'une borne supérieure des ressources requises par l'algorithme.
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.
Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Exponential time hypothesisIn computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, i.e., for all constant , where n is the number of variables in the formula. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement.
Authentificationthumb|Authentification renforcée basée sur une cryptocard L'authentification est un processus permettant à un système informatique de s'assurer de la légitimité de la demande d'accès faite par une entité (être humain ou un autre système) afin d'autoriser son accès à des ressources du système (système d'exploitation, réseaux, applications...) conformément au paramétrage du contrôle d'accès. Le système attribue à cette entité les données d'identité pour une session d'accès (ces attributs sont détenus par le système ou peuvent être fournis par l'entité lors du processus d'authentification).
Message authenticationIn information security, message authentication or data origin authentication is a property that a message has not been modified while in transit (data integrity) and that the receiving party can verify the source of the message. Message authentication does not necessarily include the property of non-repudiation. Message authentication is typically achieved by using message authentication codes (MACs), authenticated encryption (AE), or digital signatures.
Mutual authenticationMutual authentication or two-way authentication (not to be confused with two-factor authentication) refers to two parties authenticating each other at the same time in an authentication protocol. It is a default mode of authentication in some protocols (IKE, SSH) and optional in others (TLS). Mutual authentication is a desired characteristic in verification schemes that transmit sensitive data, in order to ensure data security. Mutual authentication can be accomplished with two types of credentials: usernames and passwords, and public key certificates.
Best, worst and average caseIn computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. Usually the resource being considered is running time, i.e. time complexity, but could also be memory or some other resource. Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n.
Contrôle d'accèsthumb|Contrôle d'accès physique par serrure à code numérique Le contrôle d'accès désigne les différentes solutions techniques qui permettent de sécuriser et gérer les accès physiques à un bâtiment ou un site, ou les accès logiques à un système d'information. On distingue ainsi le contrôle d'accès physique et le contrôle d'accès logique. Les entreprises sont de plus en plus amenées à tracer leurs accès informatique à l'aide d'un Reporting des Droits d'Accès. Droit d'accès Reporting des Droits d'Accès Contrôl
Durabilité (informatique)Dans le contexte des bases de données, la durabilité est la propriété qui garantit qu'une transaction informatique qui a été confirmée survit de façon permanente, quels que soient les problèmes rencontrés par la base de données ou le système informatique où cette transaction a été traitée. Par exemple, dans un système de réservation de sièges d'avion, la durabilité assure qu'une réservation confirmée restera enregistrée quels que soient les problèmes rencontrés par l'ordinateur qui gère le système de réservation (panne d'électricité, écrasement de la tête sur le disque dur, etc.
Database transactionA database transaction symbolizes a unit of work, performed within a database management system (or similar system) against a database, that is treated in a coherent and reliable way independent of other transactions. A transaction generally represents any change in a database. Transactions in a database environment have two main purposes: To provide reliable units of work that allow correct recovery from failures and keep a database consistent even in cases of system failure.
Serveur informatiquethumb|Des serveurs empilés. Un serveur informatique est un dispositif informatique (matériel et logiciel) qui offre des services à un ou plusieurs clients (parfois des milliers). Les services les plus courants sont : l'accès aux informations du World Wide Web ; le courrier électronique ; le partage de périphériques (imprimantes, disque durs) ; le commerce électronique ; le stockage en base de données ; la gestion de l'authentification et du contrôle d'accès ; le jeu et la mise à disposition de logiciels applicatifs.
Multi-factor authenticationMulti-factor authentication (MFA; two-factor authentication, or 2FA, along with similar terms) is an electronic authentication method in which a user is granted access to a website or application only after successfully presenting two or more pieces of evidence (or factors) to an authentication mechanism. MFA protects personal data—which may include personal identification or financial assets—from being accessed by an unauthorized third party that may have been able to discover, for example, a single password.
Lecteur de carteA card reader is a data input device that reads data from a card-shaped storage medium. The first were punched card readers, which read the paper or cardboard punched cards that were used during the first several decades of the computer industry to store information and programs for computer systems. Modern card readers are electronic devices that can read plastic cards embedded with either a barcode, magnetic strip, computer chip or another storage medium. A memory card reader is a device used for communication with a smart card or a memory card.
Canal de communication (théorie de l'information)vignette En théorie de l'information, un canal de communication ou canal de transmission est un support (physique ou non) permettant la transmission d'une certaine quantité d'information, depuis une source (ou émetteur) vers un destinataire (ou récepteur). Souvent, le canal altère l'information transmise, par exemple en ajoutant un bruit aléatoire. La quantité d'information qu'un canal de communication peut transporter est limitée : on parle de capacité du canal.
Code d'authentification de messagethumb|upright=1.8|Schéma de principe d'un code d'authentification de message Un code d'authentification de message (CAM), souvent désigné par son sigle anglais MAC (de message authentication code) est un code accompagnant des données dans le but d'assurer l'intégrité de ces dernières, en permettant de vérifier qu'elles n'ont subi aucune modification, après une transmission par exemple. Le concept est relativement semblable aux fonctions de hachage. Il s’agit ici aussi d’algorithmes qui créent un petit bloc authentificateur de taille fixe.
Programmation concurrenteLa programmation concurrente est un paradigme de programmation tenant compte, dans un programme, de l'existence de plusieurs piles sémantiques qui peuvent être appelées threads, processus ou tâches. Elles sont matérialisées en machine par une pile d'exécution et un ensemble de données privées. La concurrence est indispensable lorsque l'on souhaite écrire des programmes interagissant avec le monde réel (qui est concurrent) ou tirant parti de multiples unités centrales (couplées, comme dans un système multiprocesseurs, ou distribuées, éventuellement en grille ou en grappe).
