Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Algorithmes récursifs : induction et récurrence

Dans cours

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours couvre le concept des algorithmes récursifs, qui résolvent les problèmes en les réduisant à des instances plus petites du même problème. Les sujets abordés incluent les algorithmes factoriels récursifs et d'exponentiation, la recherche linéaire et binaire et leurs implémentations.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Concepts associés (24)

Recherche dichotomique

La recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.

Arbre binaire de recherche

En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

Arbre binaire

En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.

Algorithme de recherche

En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.

Afficher plus

Séances de cours associées (23)

Algorithmes récursifs : factorielle, exponentiation, recherche

Explique les algorithmes récursifs pour les problèmes factoriels, d'exponentiation et de recherche.

Arbre de recherche binaire optimal

Explore les arbres de recherche binaires optimaux pour minimiser efficacement les coûts de recherche attendus.

Algorithmes Préparation à l'examen

Offre un récapitulatif avant l'examen Algorithmes, couvrant les stratégies de résolution de problèmes et la mise en œuvre de l'algorithme avec des problèmes d'échantillon.

Récursion et recherche binaire

Introduit des algorithmes de récursion et de recherche binaire pour résoudre efficacement les problèmes.

Analyse algorithmique : croissance, recherche et logarithme

Explore la croissance des algorithmes, les complexités de recherche et les propriétés logarithmiques en profondeur, avec des exercices pratiques inclus.

Afficher plus

Concepts associés (24)

Recherche dichotomique

Arbre binaire de recherche

Self-balancing binary search tree

Arbre binaire

Algorithme de recherche

Afficher plus