Séance de cours

Complexité algorithmique : visualisation et analyse

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre la visualisation des fonctions mathématiques à l'aide du module Matplotlib en Python, en se concentrant sur la complexité algorithmique et le sous-module pyplot. Il explique les concepts de gros oméga, de thêta et de notation O, fournissant des exemples et des définitions. L'instructeur démontre la croissance des algorithmes en notation asymptotique et l'analyse du temps de voyage des algorithmes, en mettant l'accent sur le pire scénario. La séance de cours se termine par une discussion sur le comportement asymptotique des algorithmes de recherche et l’importance d’optimiser l’efficacité des algorithmes.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Concepts associés (32)

Comparaison asymptotique

En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction au voisinage d'un point ou à l'infini, en la comparant à celle d'une autre fonction considérée comme plus « simple ». Celle-ci est souvent choisie sur une échelle de référence, contenant en général au moins certaines fonctions dites élémentaires, en particulier les sommes et produits de polynômes, d'exponentielles et de logarithmes.

Complexité en temps

En 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.

Computational complexity

In 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.

Notation L

La notation L est un analogue aux notations de Landau en notation asymptotique. Cette notation a été introduite par Carl Pomerance en 1982 pour comparer différents algorithmes de factorisation et a été généralisée à deux paramètres par Arjen Lenstra et Hendrik Lenstra. Elle est principalement utilisée en théorie algorithmique des nombres, où elle permet de donner une échelle entre les différents algorithmes exponentiels.

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.

Afficher plus

Séances de cours associées (64)

Algorithmes en informatique: techniques de recherche et de tri

Fournit un aperçu des algorithmes de recherche et de tri essentiels en informatique.

Complexité algorithmique : analyse du temps de déplacement

Couvre la complexité algorithmique et l'analyse du temps de trajet, en se concentrant sur la mesure du temps pris par les algorithmes et l'évaluation de leurs performances.

Programmation dynamique : le triangle de Pascal et l'algorithme de Floyd

Explore la programmation dynamique à travers le Triangle de Pascal et l'Algorithme de Floyd.

Complexité algorithmique: Notation Theta

Explore la complexité algorithmique, en comparant les taux de croissance en utilisant la notation Theta et en caractérisant différentes classes de complexité.

Optimisation du double primaire: méthode extra-gradient

Explore la méthode Extra-Gradient pour l'optimisation Primal-dual, couvrant les problèmes non convexes, les taux de convergence et les performances pratiques.

Afficher plus

Concepts associés (32)

Comparaison asymptotique

Complexité en temps

Computational complexity

Notation L

Théorie de la complexité (informatique théorique)

Afficher plus