Séance de cours

Programmation dynamique: combien de façons de faire le changement

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.

Dans cours

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

Description

Cette séance de cours présente un exemple travaillé de programmation dynamique pour résoudre un problème lié au nombre de façons d'apporter des changements. L'instructeur explique le processus étape par étape, en se concentrant sur les différentes dénominations de pièces et le montant total du changement. À travers les diapositives, le public suit l’évolution de la solution, en commençant par le cas de base et en construisant progressivement jusqu’au résultat final. Différents scénarios sont explorés, illustrant la polyvalence et l'efficacité de la programmation dynamique dans la lutte contre les problèmes combinatoires. La séance de cours conclut en soulignant les connaissances clés tirées de l'exemple et l'applicabilité plus large de la programmation dynamique dans la conception et l'optimisation des algorithmes.

Enseignant·e·s (2)

Rom Pinchasi

Enseignement et PhD Cours The Maths of Puzzles MATH-704

Friedrich Eisenbrand

Enseignement et PhD Doctorant·es actuel·les Ruben Manuel Skorupinski, Neta Singer, Lukas Vogl, Jiaye Wei A dirigé les thèses EPFL de Thomas Rothvoss, Nicolai Hähnle, Martin Niemeier, Adrian Aloysius Bock, Carsten Moldenhauer, Alfonso Bolívar Cevallos Manzano, Manuel Francesco Aprile, Igor Malinovic, Christoph Hunkenschröder, Moritz Andreas Venzin, Jana Tabea Cslovjecsek A co-dirigé les thèses EPFL de Puck van Gerwen Cours Algèbre linéaire avancée II - diagonalisation MATH-115(a) L'objectif

Source officielle

Concepts associés (21)

Optimisation combinatoire

L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

Programmation dynamique

En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman. À l'époque, le terme « programmation » signifie planification et ordonnancement. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires.

Palourde

Infobox Biohomonymie | nom = Palourde | autre = | image = Palourde.jpg | légende = Palourde fraîchement pêchée, ouverte au couteau et prête à déguster.

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Optimisation de code

En programmation informatique, l'optimisation de code est la pratique consistant à améliorer l'efficacité du code informatique d'un programme ou d'une bibliothèque logicielle. Ces améliorations permettent généralement au programme résultant de s'exécuter plus rapidement, de prendre moins de place en mémoire, de limiter sa consommation de ressources (par exemple les fichiers), ou de consommer moins d'énergie électrique. La règle numéro un de l'optimisation est qu'elle ne doit intervenir qu'une fois que le programme fonctionne et répond aux spécifications fonctionnelles.

Afficher plus

Séances de cours associées (64)

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

Optimisation avec contraintes : conditions KKT

Couvre les conditions KKT pour l'optimisation avec des contraintes, essentielles pour résoudre efficacement les problèmes d'optimisation.

Programmation dynamique : Découpe de bâtonnets et transformation

Explore la programmation dynamique à travers la coupe de tiges et les problèmes d'optimisation de changement.

Bandits à bras multiples

Discute des algorithmes pour équilibrer l'exploration et l'exploitation dans les processus décisionnels.

Afficher plus

Concepts associés (21)

Optimisation combinatoire

Programmation dynamique

Palourde

Infobox Biohomonymie | nom = Palourde | autre = | image = Palourde.jpg | légende = Palourde fraîchement pêchée, ouverte au couteau et prête à déguster.

Algorithme

Optimisation de code

Afficher plus