---
# System prepended metadata

title: Sommaire Algorithme
tags: [M1 S1, Algorithme, Sommaire]

---

# 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]
- 