• il y a 10 ans
Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel

Cours n°1 - Partie A/C
Introduction aux algorithmes d'approximation
• NP-complétude, PCP et Inapproximabilité
• Définitions: Problèmes d'optimisation et approximation
• Inapproximabilité du TSP non-métrique
• Une 2-approximation pour le TSP métrique
• Une 3/2-approximation pour le TSP métrique

TD n°1
• Dérandomisation par la méthode de l'espérance conditionnelle appliquée à Max-Cut
• Une O(√n)-approximation pour le coloriage de graphes 3-coloriables

Recommandations

2:46:55
[2017 MPRI 2.11.1] Molecular programming 3/4 (8 NOV)
Nicolas Schabanel
2:14:45
[2017 MPRI 2.11.1] Molecular programming 4/4 (15 NOV)
Nicolas Schabanel
2:39:19
[2017 MPRI 2.11.1] Molecular programming 2/4 (25 OCT)
Nicolas Schabanel
2:28:07
[2017 MPRI 2.11.1] Molecular programming 1:4 (18 OCT)
Nicolas Schabanel
2:30:29
[2016 MPRI 2.11.1] 7. Nature Programming: Intrisic Universality & Other models including Oritatami (2016/11/9)
Nicolas Schabanel
2:49:34
[2016 MPRI 2.11.1] 6. Nature Programming: Universality in Tile Assembly Systems (2016/11/2)
Nicolas Schabanel
2:17:47
[2016 MPRI 2.11.1] 4. Polynomial Time Approximation Schemes (2016/10/5)
Nicolas Schabanel
2:31:02
[2016 MPRI 2.11.1] 3. Mathematical Programming 2: Semi-Definite / Vector programming (28/9/2016)
Nicolas Schabanel
3:04:35
[2016 MPRI 2.11.1] 2. Mathematical Programming 1: Linear Programming & Randomized Rounding (2016/9/21)
Nicolas Schabanel
2:54:45
[2016 MPRI 2.11.1] 1. Introduction to Approximation Algorithms (2016/9/14)
Nicolas Schabanel
2:24
HoA
Nicolas Schabanel
59:00
[MPRI 2015] 1.24-4A Algorithmes randomisés et Structures aléatoires (Cours 4 Partie A/D)
Nicolas Schabanel
59:01
[MPRI 2015] 1.24-4C Algorithmes randomisés et Structures aléatoires (Cours 4 Partie C/D)
Nicolas Schabanel
32:19
[MPRI 2015] 1.24-4D Algorithmes randomisés et Structures aléatoires (Cours 4 Partie D/D)
Nicolas Schabanel
59:01
[MPRI 2015] 1.24-4B Algorithmes randomisés et Structures aléatoires (Cours 4 Partie B/D)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (2/ABC)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (3/ABC)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (15/ABC)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (14/ABC)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (13/ABC)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (12/ABC)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (1/ABC)
Nicolas Schabanel
15:00
[Oritatami] Folding Turing (0/ABC)
Nicolas Schabanel
59:00
[MPRI 2.11.1] Algorithmes avancés 2014.11.20 Cours n°8(B/C)
Nicolas Schabanel
59:00
[MPRI 2.11.1] Algorithmes avancés 2014.11.20 Cours n°8(A/C)
Nicolas Schabanel
1:46
3 séries pour se faire peur
yoogue
0:35
interview avec gon
raphman
0:23
Bénéficer de canva pro gratuitement grâce à cette astuce #astuce #astuces #tips #hack
Khironi Astuce
2:16
Petit trailer sur les prochaines programmes Marvel
Matthias Amona
0:34
@assadlake - Quand ta meuf t'appelle "bébé"
Koda