Algorithme amélioré : Jeux de parité à trois couleurs

Description

Cette séance de cours présente un algorithme amélioré pour résoudre les jeux de parité tricolore, en introduisant le concept de mesures de progrès et leur accélération. Il couvre les principales propriétés des jeux de parité, la complexité de l'informatique des états gagnants, et l'algorithme de mesure de progrès avec des règles de mise à jour. Le théorème de l'écart et la divergence de temps dans les jeux d'accessibilité sont discutés, ainsi que la mise en œuvre symbolique de mesures de progrès accélérées. Les résultats expérimentaux et les conclusions sur l'accélération pratique fournie par l'accélération sont mis en évidence, les travaux futurs étant axés sur l'extension de l'algorithme aux jeux de parité générale.

Connectez-vous pour regarder la vidéo

Source officielle

https://mediaspace.epfl.ch/media/0_bejup4vi

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Séances de cours associées (63)

Concepts associés (59)

Couleur

vignette|Peinture de Claude Monet. La couleur est la perception visuelle de l'aspect d'une surface ou d'une lumière, basée, sans lui être rigoureusement liée, sur la répartition spectrale de la lumière, qui stimule des cellules nerveuses spécialisées situées sur la rétine nommées cônes. Le système nerveux transmet et traite l'influx jusqu'au cortex visuel.

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.

Complexité en espace

En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées. L'espace compte le nombre maximum de cases mémoire utilisées simultanément pendant un calcul. Par exemple le nombre de symboles qu'il faut conserver pour pouvoir continuer le calcul. Usuellement l'espace que l'on prend en compte lorsque l'on parle de l'espace nécessaire pour des entrées ayant des propriétés données est l'espace nécessaire le plus grand parmi ces entrées ; on parle de complexité en espace dans le pire cas.

Progrès social

Le progrès social est la recherche d'une amélioration des conditions de vie de l'être humain par un changement dans l'organisation sociale. Le progrès social est essentiellement une notion contemporaine parce qu'il est associé aux conditions de vie de l'être humain dans la société moderne.

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.