Séance de cours

Programmation dynamique : Coefficients binômes

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 programmation dynamique comme méthode pour résoudre les problèmes avec une structure séquentielle répétitive, en se concentrant sur l'exemple du calcul des coefficients binomiaux. Il explique l'approche récursive, l'inefficacité des solutions récursives et la transformation en un algorithme de programmation dynamique plus efficace. La complexité de l'approche récursive est analysée, ce qui conduit à l'introduction d'une solution de programmation dynamique qui optimise le calcul en stockant des valeurs préalablement calculées. La séance de cours conclut en soulignant l'importance de la mémorisation dans la programmation dynamique, illustrée par l'exemple du triangle de Pascal.

Source officielle

Concepts associés (27)

Coefficient binomial

En mathématiques, les coefficients binomiaux, ou coefficients du binôme, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de parties à k éléments d'un ensemble à n éléments. On les note - qui se lit « k parmi n » - ou , la lettre C étant l'initiale du mot « combinaison » Les coefficients binomiaux s'expriment à l'aide de la fonction factorielle : Ils interviennent dans de nombreux domaines des mathématiques : développement du binôme en algèbre, dénombrements, développement en série, lois de probabilités, etc.

Algorithme récursif

Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus petites du même problème. L'approche récursive est un des concepts de base en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité. Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même.

Récursivité

La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle.

Formule du binôme de Newton

vignette|Visualisation de l'expansion binomiale La formule du binôme de Newton est une formule mathématique donnée par Isaac Newton pour trouver le développement d'une puissance entière quelconque d'un binôme. Elle est aussi appelée formule du binôme ou formule de Newton. Si x et y sont deux éléments d'un anneau (par exemple deux nombres réels ou complexes, deux polynômes, deux matrices carrées de même taille, etc.

Formule du binôme généralisée

La formule du binôme généralisée permet de développer une puissance complexe d'une somme de deux termes sous forme d'une somme de série et généralise la formule du binôme de Newton et celle du binôme négatif. Dans le cas d'un exposant rationnel, elle a été énoncée sans démonstration par Newton dans ses Principia Mathematica en 1687, puis prouvée par Euler en 1773.

Afficher plus

Séances de cours associées (47)

Design d'algorithme: Diviser et conquerer

Couvre la récursion, la programmation dynamique et la conception d'algorithmes en utilisant des stratégies de partage et de conquête.

Programmation dynamique : résoudre efficacement les problèmes séquentiels

Explore la programmation dynamique pour une résolution efficace des problèmes, illustrée par des coefficients binomiaux et le triangle de Pascal.

Coefficients binômes : Estimation et formule de Stirling

Explore l'estimation des coefficients binomiaux, la formule de Stirling et les propriétés de la courbe de la cloche.

Programmation dynamique: Complexité de calcul des Coefficients Binomiaux

Explore la complexité du calcul des coefficients binomiaux à l'aide de la programmation dynamique.

Limites fondamentales de l'apprentissage basé sur le graduat

S'inscrit dans les limites fondamentales de l'apprentissage par gradient sur les réseaux neuronaux, couvrant des sujets tels que le théorème binôme, les séries exponentielles et les fonctions génératrices de moments.

Afficher plus

Concepts associés (27)

Coefficient binomial

Algorithme récursif

Récursivité

Formule du binôme de Newton

Formule du binôme généralisée

Afficher plus