Suite de Fibonacci, solution top-down
La suite de Fibonacci est une séquence de nombres entiers où chaque terme est la somme des deux termes précédents. Elle commence généralement avec les deux premiers termes, 0 et 1, et continue ainsi
Cours & Tutoriels
Algorithmes
Complexité, Tris ...
58 cours
Programmation dynamique
La programmation dynamique top-down ou la mémoisation
La programmation dynamique top-down est une technique pour optimiser les fonctions récursives. Elle consiste à stocker les résultats des appels récursifs dans une table de mémoire, afin d'éviter de recalculer les mêmes valeurs plusieurs fois. Cette technique est appelée mémoisation.
Diviser pour régner
Programmation dynamique
Rappel sur l'approche récursive
La récursivité est un concept fondamental en informatique et en programmation. Elle consiste à définir une fonction en utilisant une ou plusieurs instances de cette même fonction. En d'autres termes, une fonction récursive est une fonction qui s'appelle elle-même à l'intérieur de sa propre définition. Cela permet de résoudre des problèmes complexes en les divisant en sous-problèmes plus simples, qui sont ensuite résolus en appelant la fonction récursive sur les sous-problèmes.
Programmation dynamique
Méthodes de la programmation dynamique : Mémoisation et tabulation
La programmation dynamique est une technique d'optimisation qui résout des problèmes complexes en les décomposant en sous-problèmes plus simples, et en stockant les résultats intermédiaires pour éviter les calculs répétitifs. Mémoisation et tabulation sont deux approches couramment utilisées pour optimiser les solutions de programmation dynamique. Elles permettent de résoudre les problèmes plus efficacement en stockant les résultats intermédiaires pour éviter les calculs répétitifs.
Programmation dynamique
Le concept de sous-structure optimale
Le concept de sous-structure optimale fait référence à une propriété des problèmes d'optimisation où une solution optimale du problème global peut être construite à partir de solutions optimales de ses sous-problèmes. Cette propriété est essentielle pour appliquer la programmation dynamique et les algorithmes gloutons.
Programmation dynamique
Le concept de sous-problèmes superposés
Le concept de sous-problèmes superposés fait référence à une situation dans laquelle un problème peut être décomposé en sous-problèmes plus petits, mais certains de ces sous-problèmes sont résolus plusieurs fois lors de la résolution du problème initial. Cette répétition de sous-problèmes identiques est une caractéristique essentielle qui permet d'appliquer la programmation dynamique pour résoudre efficacement le problème.
Programmation dynamique
Différence entre la programmation dynamique, l'approche diviser pour régner, et les algorithmes gloutons
La programmation dynamique, l'approche diviser pour régner et les algorithmes gloutons sont des techniques d'optimisation algorithmique qui peuvent être utilisées pour résoudre des problèmes complexes. Chacune a ses propres caractéristiques, forces et faiblesses.
Programmation dynamique
Définition de la programmation dynamique
La programmation dynamique est une méthode algorithmique utilisée pour résoudre des problèmes d'optimisation, en particulier ceux qui présentent une structure de sous-problèmes imbriqués ou une nature récursive.
Initiation à l'algorithmique
Conception des algorithmes
Avant d'écrire un algorithme, vous devez vous poser les questions suivantes : (1) Quelles entrées voulez-vous utiliser pour l'algorithme ? (2) Quelles contraintes devez-vous garder à l'esprit lorsque vous essayez de résoudre ce problème ? ...
Initiation à l'algorithmique
Introduction à l'algorithmique
Un programmeur doit savoir ce qu'est un algorithme, afin de savoir comment l'utiliser pour écrire du code. Un algorithme est un ensemble de règles, d'instructions ou de processus qu'une machine ou un système doit suivre pour résoudre un problème. Il peut inclure le type d'opérations à utiliser et les variables à déclarer. En termes simples, un algorithme est un ensemble de règles définissant les étapes à suivre pour obtenir les résultats souhaités.
La sous-structure optimale en programmation dynamique
La sous-structure optimale signifie que la solution optimale à un problème de taille n (ayant n éléments) est basée sur une solution optimale au même problème de plus petite taille (moins de n éléments). c'est-à -dire que, tout en construisant la solution d'un problème de taille n, on la définit en fonction de problèmes similaires de taille plus petite, disons k (k
Langage c++
Langage Python
MP, PSI et la TSI
Diviser pour régner
Programmation dynamique
Exercices langage c
Exercices python
récursivité
Complexité
Calculer les nombres de catalan en C++ et Python
Les nombres catalans sont une suite d'entiers positifs qui apparaissent dans de nombreux problèmes de dénombrement en combinatoire. Ils comptent certains types de chemins de réseau, de permutations, d'arbres binaires et de nombreux autres objets combinatoires.