Séance de cours

Stratégies de résolution de problèmes 2: Récursion

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 porte sur les stratégies de résolution de problèmes, y compris la récursion et les méthodes de division et de conquête. Il explique comment trouver efficacement des éléments égarés dans une liste, le concept de division et de regroupement des données pour résoudre des sous-problèmes plus simples, et l'approche récursive de la résolution des problèmes. Des exemples tels que les Tours de Hanoi et le calcul de la somme des entiers sont discutés.

Source officielle

Concepts associés (27)

Diviser pour régner (informatique)

thumb|652x652px|Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion En informatique, diviser pour régner (du latin , divide and conquer en anglais) est une technique algorithmique consistant à : Diviser : découper un problème initial en sous-problèmes ; Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ; Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.

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.

Course-of-values recursion

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence . The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are primitive recursive.

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.

Afficher plus

Séances de cours associées (55)

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.

Algorithmes récursifs : Diviser et conquerer

Explore le concept de diviser et de conquérir dans les algorithmes récursifs, illustré par les Tours de Hanoi.

Stratégies de résolution des problèmes : Aperçu général

Présente les méthodes de résolution de problèmes, en mettant l'accent sur « Divide and Conquer », la récursion et la programmation dynamique.

Tour de Hanoi: Récursion et programmation dynamique

Explore l'algorithme de la Tour de Hanoi, la récursion et la programmation dynamique pour résoudre les problèmes efficacement.

Programmation dynamique : Coefficients binômes

Explore la programmation dynamique par le calcul des coefficients binomiaux, en mettant l'accent sur l'efficacité et la mémorisation dans la résolution des problèmes.

Afficher plus

Concepts associés (27)

Diviser pour régner (informatique)

Algorithme récursif

Récursivité

Course-of-values recursion

Algorithme

Afficher plus