Problème algorithmique

Résumé

Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier. On distingue en particulier deux types de problèmes :

les problèmes de décision, qui consistent à répondre oui ou non à une question (par exemple, cet entier est-il premier ?) ;
les problèmes à promesse, qui consistent à répondre oui ou non à une question uniquement sous une hypothèse (la promesse) ;
les problèmes de recherche (ou de fonction), qui consistent à produire un objet spécifié par l'énoncé du problème (par exemple, la factorisation).

Les problèmes algorithmiques jouent un rôle central en

Source officielle

https://fr.wikipedia.org/wiki/Probl%C3%A8me_algorithmique

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

Publications associées

Chargement

Personnes associées

Aucun résultat

Unités associées

Aucun résultat

Concepts associés (25)

Concepts associés

Chargement

Cours associés (8)

Cours associés

Chargement

Séances de cours associées (9)

Séances de cours associées

Chargement

A Primer on Motion Capture with Deep Learning: Principles, Pitfalls, and Perspectives

Jessy Lauer, Mackenzie Mathis, Alexander Mathis, Steffen Schneider

Extracting behavioral measurements non-invasively from video is stymied by the fact that it is a hard computational problem. Recent advances in deep learning have tremendously advanced our ability to predict posture directly from videos, which has quickly impacted neuroscience and biology more broadly. In this primer, we review the budding field of motion capture with deep learning. In particular, we will discuss the principles of those novel algorithms, highlight their potential as well as pitfalls for experimentalists, and provide a glimpse into the future.

2020

Chargement

The Gene Family-Free Median of Three

Metin Balaban

The gene family-free framework for comparative genomics aims at developing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We present a model for constructing a median of three genomes in this family-free setting, based on maximizing an objective function that generalizes the classical breakpoint distance by integrating sequence similarity in the score of a gene adjacency. We show that the corresponding computational problem is MAX SNP-hard and we present a 0-1 linear program for its exact solution. The result of this program is a median genome with median genes associated to extant genes, in which median adjacencies are assumed to define positional orthologs. We demonstrate through simulations and comparison with the OMA orthology database that the herein presented method is able compute accurate medians and positional orthologs for genomes comparable in size of bacterial genomes.

Springer AG2016

Chargement

We consider several "provably secure" hash functions that compute simple sums in a well chosen group (G,*). Security properties of such functions provably translate in a natural way to computational problems in G that are simple to define and possibly also hard to solve. Given k disjoint lists Li of group elements, the k-sum problem asks for gi ∊ Li such that g1 * g2 ... gk = 1G. Hardness of the problem in the respective groups follows from some "standard" assumptions used in public-key cryptology such as hardness of integer factoring, discrete logarithms, lattice reduction and syndrome decoding. We point out evidence that the k-sum problem may even be harder than the above problems. Two hash functions based on the group k-sum problem, SWIFFTX and FSB, were submitted to NIST as candidates for the future SHA-3 standard. Both submissions were supported by some sort of a security proof. We show that the assessment of security levels provided in the proposals is not related to the proofs included. The main claims on security are supported exclusively by considerations about available attacks. By introducing "second-order" bounds on bounds on security, we expose the limits of such an approach to provable security. A problem with the way security is quantified does not necessarily mean a problem with security itself. Although FSB does have a history of failures, recent versions of the two above functions have resisted cryptanalytic efforts well. This evidence, as well as the several connections to more standard problems, suggests that the k-sum problem in some groups may be considered hard on its own, and possibly lead to provable bounds on security. Complexity of the non-trivial tree algorithm is becoming a standard tool for measuring the associated hardness. We propose modifications to the multiplicative Very Smooth Hash and derive security from multiplicative k-sums in contrast to the original reductions that related to factoring or discrete logarithms. Although the original reductions remain valid, we measure security in a new, more aggressive way. This allows us to relax the parameters and hash faster. We obtain a function that is only three times slower compared to SHA-256 and is estimated to offer at least equivalent collision resistance. The speed can be doubled by the use of a special modulus, such a modified function is supported exclusively by the hardness of multiplicative k-sums modulo a power of two. Our efforts culminate in a new multiplicative k-sum function in finite fields that further generalizes the design of Very Smooth Hash. In contrast to the previous variants, the memory requirements of the new function are negligible. The fastest instance of the function expected to offer 128-bit collision resistance runs at 24 cycles per byte on an Intel Core i7 processor and approaches the 17.4 figure of SHA-256. The new functions proposed in this thesis do not provably achieve a usual security property such as preimage or collision resistance from a well-established assumption. They do however enjoy unconditional provable separation of inputs that collide. Changes in input that are small with respect to a well defined measure never lead to identical output in the compression function.

EPFL2011

Chargement

EPFL2011