Séance de cours

Programmation dynamique : nombres de Fibonacci

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 les concepts de programmation dynamique appliqués au calcul des nombres de Fibonacci. Il traite de la définition récursive des nombres de Fibonacci, de l'inefficacité de l'algorithme récursif, et de l'optimisation par la mémorisation et les approches itératives. En outre, il explore l'algorithme gourmand pour les problèmes de changement de pièce et son optimisation. La séance de cours se penche également sur les problèmes de coloration des graphiques, en analysant les algorithmes pour déterminer si un graphique peut être coloré avec deux couleurs et la complexité impliquée. Enfin, il présente une variante du problème de knapsack, en se concentrant sur la recherche du nombre maximum d'objets qui peuvent s'intégrer dans un knapsack de capacité limitée.

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (29)

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.

Algorithme glouton

Un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton.

Suite de Fibonacci

vignette|Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13 et 21. En mathématiques, la suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Notée , elle est définie par , et pour . Les termes de cette suite sont appelés nombres de Fibonacci et forment la : vignette|Représentation géométrique de la fraction continue de φ faisant apparaître les nombres de la suite de Fibonacci.

Coloration des arêtes d'un graphe

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.

Coloration fractionnaire

droite|vignette| 5: 2-coloration du graphe dodécaédrique. Il n'existe pas de 4: 2-coloration de ce graphe. En théorie des graphes, la coloration fractionnaire est une généralisation de la coloration des graphes ordinaire. Dans une coloration de graphe traditionnelle, une couleur est affectée à chaque sommet d'un graphe, et deux sommets adjacents ne doivent pas avoir la même couleur. Dans une coloration fractionnaire, un ensemble de couleurs est affecté à chaque sommet du graphe.

Afficher plus

Séances de cours associées (46)

Coloration graphique II

Explore les concepts avancés de coloration graphique, y compris la coloration plantée, le seuil de rigidité, et les variables gelées en points fixes BP.

Coloration graphique III

Explore les propriétés des grappes et le seuil de coloration dans la coloration graphique, y compris la connectivité moyenne et la rigidité.

Propagation de la croyance

Explore la propagation de la croyance dans les modèles graphiques, les graphiques de facteurs, les exemples de verre de spin, les distributions de Boltzmann et les propriétés de coloration des graphiques.

Arbres d'éclaboussure minimum: Algorithme de Prim

Explore l'algorithme de Prim pour les arbres à portée minimale et introduit le problème Traveling Salesman.

Théorie de calcul: Problèmes NP Exemples

Examine les problèmes de NP, la coloration des graphiques, l'optimisation des chemins et les distinctions de complexité computationnelle dans les classes P et NP.

Afficher plus

Concepts associés (29)

Coloration de graphe

Algorithme glouton

Suite de Fibonacci

Coloration des arêtes d'un graphe

Coloration fractionnaire

Afficher plus