m

F Nous contacter

0
     
Multi angle

H 1 Introduction à la théorie de la complexité

Auteurs : Lassaigne, Richard (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
    complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
    verification - property testing

    Codes MSC :
    68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
    68Q17 - Computational difficulty of problems
    68W20 - randomized algorithms
    68W25 - Approximation algorithms
    68Q19 - Descriptive complexity and finite models

      Informations sur la Vidéo

      Langue : Français
      Date de publication : 27/08/14
      Date de captation : 22/04/14
      Collection : Research talks ; Computer Science
      Format : quicktime ; audio/x-aac
      Durée : 01:09:55
      Domaine : Computer Science
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2014-04-22_Lassaigne.mp4

    Informations sur la rencontre

    Nom de la rencontre : Algorithm and programming / Algorithmique et programmation
    Organisateurs de la rencontre : Dorra, Francis
    Dates : 21/04/14 - 25/04/14
    Année de la rencontre : 2014

    Citation Data

    DOI : 10.24350/CIRM.V.18596603
    Cite this video as: Lassaigne, Richard (2014). Introduction à la théorie de la complexité. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18596603
    URI : http://dx.doi.org/10.24350/CIRM.V.18596603


    Bibliographie

Ressources Electroniques (Depuis le CIRM)

Books & Print journals

Recherche avancée


0
Z