Algorithme récursif

Résumé

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. On oppose généralement les algorithmes récursifs aux algorithmes itératifs, qui eux, utilisent plutôt des boucles pour et des boucles tant que, pour répéter des opérations. Un exemple préliminaire : les permutations Commençons par un exemple tiré du Bourgeois gentilhomme (Acte II Scène IV) de Molière. Le héros, Monsieur Jourdain, veut connaître toutes les manières « galantes » d'écrire un billet. De la phrase Belle Marquise, vos beaux yeux, me font mourir d'amour, il pourrait tirer Vos beau

Source officielle

https://fr.wikipedia.org/wiki/Algorithme_r%C3%A9cursif

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (23)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (83)

Concepts associés

Chargement

Cours associés (33)

Cours associés

Chargement

Séances de cours associées (130)

Séances de cours associées

Chargement

Global spectral methods offer the potential to compute solutions of partial differential equations numerically to very high accuracy. In this work, we develop a novel global spectral method for linear partial differential equations on cubes by extending the ideas of Chebop2 (Townsend, A. & Olver, S. (2015) The automatic solution of partial differential equations using a global spectral method. J. Comput. Phys., 299, 106-123) to the three-dimensional setting utilizing expansions in tensorized polynomial bases. Solving the discretized partial differential equation involves a linear system that can be recast as a linear tensor equation. Under suitable additional assumptions, the structure of these equations admits an efficient solution via the blocked recursive solver (Chen, M. & Kressner, D. (2020) Recursive blocked algorithms for linear systems with Kronecker product structure. Numer. Algorithms, 84, 1199-1216). In the general case, when these assumptions are not satisfied, this solver is used as a preconditioner to speed up computations.

OXFORD UNIV PRESS2022

Chargement

Efficient Massively Parallel Join Optimization for Large Queries

Anastasia Ailamaki, Bikash Chandra, Riccardo Mancini, Srinivas Karthik Venkatesh

Modern data analytical workloads often need to run queries over a large number of tables. An optimal query plan for such queries is crucial for being able to run these queries within acceptable time bounds. However, with queries involving many tables, finding the optimal join order becomes a bottleneck in query optimization. Due to the exponential nature of join order optimization, optimizers resort to heuristic solutions after a threshold number of tables. Our objective is two fold: (a) reduce the optimization time for generating optimal plans; and (b) improve the quality of the heuristic solution. In this paper, we propose a new massively parallel algorithm, MPDP, that can efficiently prune the large search space (via a novel plan enumeration technique) while leveraging the massive parallelism offered by modern hardware (Eg: GPUs). When evaluated on real-world benchmark queries with PostgreSQL, MPDP is at least an order of magnitude faster compared to state-of-the-art techniques for large analytical queries. As a result, we are able to increase the heuristic-fall-back limit from 12 relations to 25 relations with same time budget in PostgreSQL. Also, in order to handle queries with even larger number of tables, we augment MPDP to a well known heuristic, IDP2 (iterative DP version 2) and a novel heuristic UnionDP. By systematically exploring a much larger search space, these heuristics provides query plans that are up to 7 times cheaper as compared to the state-of-the-art techniques while being faster to compute.

2022

Chargement

On Verification by Translation to Recursive Functions

Régis William Blanc, Etienne Kneuss, Viktor Kuncak, Philippe Paul Henri Suter

We present the Leon verification system for a subset of the Scala programming language. Along with several functional features of Scala, Leon supports imperative constructs such as mutations and loops, using a translation into recursive functional form. Both properties and programs in Leon are expressed in terms of user-defined functions. We discuss several techniques that led to an efficient semi-decision procedure for first-order constraints with recursive functions, which is the core solving engine of Leon. We describe a generational unrolling strategy for recursive templates that yields smaller satisfiable formulas and ensures completeness for counter-examples. We evaluate the benefits of these techniques on a set of examples.

2013

Chargement