F Nous contacter


0

Documents  Albert, Luc | enregistrements trouvés : 17

O
     

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

De nombreux problèmes d'optimisation sont NP-complets. Nous ne connaissons pas de problème NP-complet qui admette un algorithme optimal de résolution s'exécutant en temps polynomial en la taille de l'instance (sinon P=NP serait établi), et l'intuition commune est que P =/= NP. Pour ces problèmes, la recherche de solutions optimales peut donc être prohibitive. Les algorithmes d'approximation offrent un compromis intéressant: par définition, ils s'exécutent en temps polynomial et fournissent des solutions dont la qualité est garantie. Nous introduirons la notion d'algorithme d'approximation et de schéma d'approximation en temps polynomial, et nous illustrerons ces notions sur de nombreux exemples. Nous montrerons également comment établir qu'un problème n'admet pas d'algorithme d'approximation (à moins que P=NP), ou comment établir une borne inférieure au facteur d'approximation de tout algorithme d'approximation (sauf si P=NP). De nombreux problèmes d'optimisation sont NP-complets. Nous ne connaissons pas de problème NP-complet qui admette un algorithme optimal de résolution s'exécutant en temps polynomial en la taille de l'instance (sinon P=NP serait établi), et l'intuition commune est que P =/= NP. Pour ces problèmes, la recherche de solutions optimales peut donc être prohibitive. Les algorithmes d'approximation offrent un compromis intéressant: par définition, ils ...

68W25 ; 68Q25 ; 68T20

Post-edited  Une deuxième révolution galiléenne ?
Dowek, Gilles (Auteur de la Conférence) | CIRM (Editeur )

L'introduction d'un nouveau concept scientifique permet souvent de donner de nouvelles réponses à des questions anciennes qui n'avaient jusqu'alors reçu que des réponses imparfaites. Cet exposé présente quelques questions qui ont trouvé de nouvelles réponses depuis que nous comprenons mieux la notion d'algorithme : qu'est-ce qu'un aéroport ?, qu'est-ce qu'une cellule, qu'est-ce qu'une loi physique ?, ... La prise de conscience du caractère algorithmique de ces objets scientifiques nous amène à considérer de nouveaux langages pour les décrire. Cette révolution, dans le langage dans lequel la science s'écrit, peut-être comparée à la révolution qui s'est produite, au début du XVIIe siècle, quand le langage mathématique a commencé à être utilisé pour décrire des phénomènes physiques. L'introduction d'un nouveau concept scientifique permet souvent de donner de nouvelles réponses à des questions anciennes qui n'avaient jusqu'alors reçu que des réponses imparfaites. Cet exposé présente quelques questions qui ont trouvé de nouvelles réponses depuis que nous comprenons mieux la notion d'algorithme : qu'est-ce qu'un aéroport ?, qu'est-ce qu'une cellule, qu'est-ce qu'une loi physique ?, ... La prise de conscience du caractère ...

00A30 ; 03B35 ; 68T15

Dans la deuxième partie de ce cours nous considérerons un problème lié, celui des algorithmes compétitifs. Dans le cadre de l'algorithmique « en-ligne », les caractéristiques d'une instance d'un problème ne sont découvertes qu'au fur et à mesure du traitement de l'instance (comme on ne découvre l'histoire d'un livre qu'au fur et à mesure où on en lit des pages). Ne pas connaître à l'avance toutes les caractéristiques d'une instance interdit souvent - mais pas toujours - de construire un algorithme optimal. Nous montrerons, entre autres, comment utiliser la technique de l'adversaire pour établir une borne inférieure au facteur de compétitivité de tout algorithme en-ligne (cette fois-ci en dehors de toute notion de complexité). Dans la deuxième partie de ce cours nous considérerons un problème lié, celui des algorithmes compétitifs. Dans le cadre de l'algorithmique « en-ligne », les caractéristiques d'une instance d'un problème ne sont découvertes qu'au fur et à mesure du traitement de l'instance (comme on ne découvre l'histoire d'un livre qu'au fur et à mesure où on en lit des pages). Ne pas connaître à l'avance toutes les caractéristiques d'une instance interdit ...

68W25 ; 68Q25 ; 68T20

Nous confions à nos ordinateurs de nombreux calculs mais la machine a des limites due à son arithmétique dite à virgule flottante. D'une part chaque calcul est effectué avec un certain nombre de chiffres (souvent environ 15 chiffres décimaux) et donc chaque calcul peut créer une erreur, certes faible, mais qui peut s'accumuler avec les précédentes pour fournir un résultat complètement faux. D'autre part, les valeurs que l'ordinateur appréhende ont des limites vers l'infiniment petit et l'infiniment grand. Hors de ces bornes, l'ordinateur produit des valeurs spéciales souvent inattendues. La première partie de cet exposé montrera que l'ordinateur n'est pas infaillible ou plutôt que son utilisation est parfois abusive. La seconde partie consisitera en une utilisation judicieuse de l'arithmétique flottante de façon à récupérer les erreurs ou à garantir un calcul
presque juste, même dans les cas pathologiques.
Nous confions à nos ordinateurs de nombreux calculs mais la machine a des limites due à son arithmétique dite à virgule flottante. D'une part chaque calcul est effectué avec un certain nombre de chiffres (souvent environ 15 chiffres décimaux) et donc chaque calcul peut créer une erreur, certes faible, mais qui peut s'accumuler avec les précédentes pour fournir un résultat complètement faux. D'autre part, les valeurs que l'ordinateur appréhende ...

65G50 ; 68T15 ; 65G20 ; 68Q60 ; 65Y04

L'apparition des "Big Data" est en train de modifier profondément notre compréhension du traitement algorithmique de l'information. Le centre de gravité s'est déplacé du calcul vers les données, et le passage à l'échelle est devenu une notion centrale. En particulier, la prise en compte de la localisation géographique des données, du coût de leur déplacement et de leur disponibilité sont devenus des facteurs majeurs de la conception des applications.
Cette nouvelle vision "centrée sur les données" et "consciente de l'échelle" (data-centric, scaling-aware) renouvelle complètement la problématique de l'algorithmique et de la programmation, à la fois dans les outils théoriques utilisés et aussi dans les méthodologies pratiques mises en oeuvre. Cet exposé présentera quelques-uns des aspects ainsi touchés et proposera des pistes pour adapter l'enseignement de l'informatique à ce nouveau paysage.
L'apparition des "Big Data" est en train de modifier profondément notre compréhension du traitement algorithmique de l'information. Le centre de gravité s'est déplacé du calcul vers les données, et le passage à l'échelle est devenu une notion centrale. En particulier, la prise en compte de la localisation géographique des données, du coût de leur déplacement et de leur disponibilité sont devenus des facteurs majeurs de la conception des ...

68P05 ; 68T05 ; 68W40

Explication de ce qu'est un buffer overflow, de la façon de l'exploiter, des protections possibles et des contournements...

68M10 ; 68N15 ; 68P25 ; 68Q60

Quelle est la puissance des machines de calculs analogiques (vs digitales)? Que peut-on calculer avec des équations différentielles ? Que cela nous apprend-t'il sur la physique et ses modèles de notre monde physique ?

03Dxx ; 68Q05 ; 68Q15

Cet exposé présente un certain nombre d'exemples d'exercices de programmation sur les arbres qui peuvent être effectués dans les premières années d'université. Les programmes étant eux-mêmes des arbres, écrire des programmes qui opèrent sur des arbres permet d'écrire des programmes qui opèrent sur d'autres programmes.

68Wxx ; 68N15

Il sera exposé divers exemples de modélisation en médecine (biologie du cancer, pharmacologie, imagerie fonctionnelle) pouvant donner lieu à des activités pédagogiques reposant de manières essentielles sur l'utilisation de l'informatique.

92C50 ; 65C20

Il sera exposé divers exemples de modélisation en médecine (biologie du cancer, pharmacologie, imagerie fonctionnelle) pouvant donner lieu à des activités pédagogiques reposant de manières essentielles sur l'utilisation de l'informatique.

92C50 ; 65C20

Multi angle  L'importance des langages en informatique
Berry, Gérard (Auteur de la Conférence) | CIRM (Editeur )

Paul Hough a mis au point sa "Transformée de Hough" au tout début des années soixante, pour mettre en évidence l'alignement de "points" sur une image. Une dizaine d'années plus tard, Duda et Hart, dans un article référence, montrait que le principe mis en place par Paul Hough permettait d'aller plus loin que la détection de droites, en favorisant la détection de courbes paramétrées dépendant de m paramétres au sein d'un nuage de points. Aujourd'hui, les travaux de recherche autour de cette approche continue à se développer, en particulier pour introduire de la "connaissance" dans la recherche d'occurrences de modèles paramétrés au sein d'un ensemble de données. Paul Hough a mis au point sa "Transformée de Hough" au tout début des années soixante, pour mettre en évidence l'alignement de "points" sur une image. Une dizaine d'années plus tard, Duda et Hart, dans un article référence, montrait que le principe mis en place par Paul Hough permettait d'aller plus loin que la détection de droites, en favorisant la détection de courbes paramétrées dépendant de m paramétres au sein d'un nuage de points. ...

68U05 ; 68U10

Dans la première partie nous introduirons la notion d'ordonnancement sur une ou plusieurs machines et les résultats classiques du domaine.

68M20

Dans la deuxième partie, nous nous intéresserons au problème d'ordonnancement de graphes de tâches sous contraintes mémoire.

68M20

Nuage de mots clefs ici

Z