Tri par insertion

Résumé

En informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer. En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique. Le tri par insertion est cependant considéré comme l'algorithme le plus efficace sur des entrées de petite taille. Il est aussi efficace lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d'autres méthodes comme le tri rapide. En programmation informatique, on applique le plus souvent ce tri à des tableaux. La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à des listes est considérée plus loin. Description Le tri par insertion considère chaque élément du tableau et l'insère à la bonne

Source officielle

https://fr.wikipedia.org/wiki/Tri_par_insertion

À 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 (13)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (17)

Concepts associés

Chargement

Cours associés (9)

Cours associés

Chargement

Séances de cours associées (41)

Séances de cours associées

Chargement

Insertion techniques for job shop scheduling

EPFL2001

Chargement

Discrete Holomorphicity and Ising Model Operator Formalism

Clément Hongler, Ali Zahabi

We explore the connection between the transfer matrix formalism and discrete complex analysis approach to the two dimensional Ising model. We construct a discrete analytic continuation matrix, analyze its spectrum and establish a direct connection with the critical Ising transfer matrix. We show that the lattice fermion operators of the transfer matrix formalism satisfy, as operators, discrete holomorphicity, and we show that their correlation functions are Ising parafermionic observables. We extend these correspondences also to outside the critical point. We show that critical Ising correlations can be computed with operators on discrete Cauchy data spaces, which encode the geometry and operator insertions in a manner analogous to the quantum states in the transfer matrix formalism.

2014

Chargement

In-depth analysis of hyaline fibromatosis syndrome frameshift mutations at the same site reveal the necessity of personalized therapy

Matteo Dal Peraro, Thomas Lemmin, Suzanne Salvi, Françoise Gisou van der Goot Grunberg, Shixu Yan

Hyaline fibromatosis syndrome is an autosomal recessive disease caused by mutations in ANTXR2, a gene involved in extracellular matrix homeostasis. Sixty percent of patients carry frameshift mutations at a mutational hotspot in exon 13. We show in patient cells that these mutations lead to low ANTXR2 mRNA and undetectable protein levels. Ectopic expression of the proteins encoded by the mutated genes reveals that a two base insertion leads to the synthesis of a protein that is rapidly targeted to the ER-associated degradation pathway due to the modified structure of the cytosolic tail, which instead of being hydrophilic and highly disordered as in wild type ANTXR2, is folded and exposes hydrophobic patches. In contrast, one base insertion leads to a truncated protein that properly localizes to the plasma membrane and retains partial function. We next show that targeting the nonsense mediated mRNA decay pathway in patient cells leads to a rescue of ANTXR2 protein in patients carrying one base insertion but not in those carrying two base insertions. This study highlights the importance of in-depth analysis of the molecular consequences of specific patient mutations, which even when they occur at the same site can have drastically different consequences.

Wiley-Blackwell2013

Chargement