# Sommaire Algorithme

###### tags `Sommaire` `M1 S1` `Algorithme`
[**Page du cour**](https://moodle.u-paris.fr/course/view.php?id=10725)

[TOC]

## cour

### [Cour 1](/129McedVTHKxfO4OH71UbA)
> [time= 7 sept 2020]
- introduction
- Bactracking
- Introduction du probleme des *N* Reines

### [Cour 2](/gvyXVnEOQyCM91UM0SAsaw)
> [time= 14 sept 2020]
- Bactracking
- probleme des *N* Reines
- Subset Sum

### [Cour 3](/IdYcb7YBTBSveQ_t0efkLw)
> [time= 21 sept 2020]
- Diviser pour régner
- tri fusion
- quick_seclect
- algorithme BFPRT

### [Cour 4](/IKMxLzyLRZ--ApSIHlh1YQ)
> [time= 28 sept 2020]
- le kième plus petit élément (suite)
- analyse de compléxité
- multiplication de Karatsuba
- algo conventionel
- Aproche diviser pour regner
- Karatsuba
- Master théorem (version Erickson)

### [Cour 5](/iv7_YjPzRnKPIGlFmtuPOA)
> [time= 5 oct 2020]
- Karatsuba (rapelle)
- Preuve du master théorem
- Problème réputés difficiles
- Ensemble indépendant maximum

### [Cour 6](/Cy2DGQBnSUuO1akqrawPpg)
> [time= 12 oct 2020]
- Ensemble indépendant maximum (suite)
- P vs NP
- Cook - Levin 1971
- Exemple de problèmes réputés difficile
- Probleme P
- Probleme réputé difficile NP

### [Cour 7](/oMYgG0ACSsK_UFQxu9-SkA)
> [time= 19 oct 2020]
- probleme NP
- Cook - Levin
- Cicuit Sat

### [Cour 8](/gs0sBwUSTZilGC9h4tafRw)
> [time= 9 nov 2020]
- Rapelle Probleme NP
- SATC
- 3SAT
- Programmation synamique
- Thechnique 1: Mémoisation
- Technique 2: Prog Dynamique

### [Cour 9](/UX6iMJqKSYOTvIEAco-eaQ)
> [time= 16 nov 2020]
- programmation dynamique
- plssc

### [Cour 10](/Oe9sHfjzT4O4oZOcIlev0Q)
> [time= 23 nov 2020]
- distance d'édition

### [Cour 11](/nbznABCGTgmt_Gqn5zgYXw)
> [time= 30 nov 2020]
- fin de programtion dynamique
- algorithme glouton
- Problemes des caissières
- Mecanique de la preuve

### [Cour 12](/gY5KGipzSuCR9RDpvDtaxw)
> [time= 7 dec 200]
- fin algorithme glouton

## TD
### [TD 1](/GlXiiMXvTsmcdsTzvUHqxQ)
> [time= 16 sept 2020]
1. le problème des fous sur un échiquier n × n
2. plus longue sous-suite croissante

### [TD 2](/RGkzz50cTy66YC44XHyl2w)
> [time= 16 sept 2020]
1. Maxclique
2. coloration

### [TD 3](/0aSSk9tXSwq9rYIROuSBuA)
> [time= 1 oct 2020] et [time= 8 oct 2020]
1. Point fixe
2. selection d'un élément par son rang
3. max et min

### [TD 4](/4BpbMeCKQhelL-UidA8c9w)
> [time= 8 oct 2020] et [time= 15 oct 2020]
- stooge sort
- élément majoritaire

### [TD 5](/3oEMF6ZaRvWf26d2vC0cBQ)
> [time= 15 oct 2020] et [time= 22 oct 2020]
- retour sur les récurrences
- probleme NP

### [TD 6](/qzagPHacRbmH_Tc82iu2DQ)
> [time= 22 oct 2020] et [time= 5 nov 2020] et [time= 12 nov 2020]
- relation $\leq_p$
- cloture par ≤
- évaluation vs décicsion

### [TD 7](/bhz1MGtlQb6hwwDObWBl0w)
> [time= 19 nov 2020] et [time= 26 nov 2020]
- programmation dynamique

### [TD 8](/NNhn23CeQ5GtP9g9_5qkcw)
> [time= 26 nov 2020] et [time= 3 dec 2020]
- prog dynamique

### [TD 9](/z7VftWTDR6Khvx8w5fJj6Q)
> [time= 3 dec 2020] et [time= 10 dec 2020]
-