---
# System prepended metadata

title: Cour 1 -- Algorithme
tags: [M1 S1, Algorithme, cour]

---

# Cour 1 -- Algorithme

###### tags `cour` `M1 S1` `Algorithme`

[Somaire](ueYXUIJIQ6C6hcYzKYeojA#)\
[~~precedent~~]()
> [time= 7 sept 2020]
> 
[TOC]


## note de début de cour
#### distanciel
*explain everything* (platform utiliser pour le cour en ligne)
attention utiliser firefox sur mac

#### exam
- 35% controle continue
- 65% controle final

## introduction
- backtracking
    - récurence temps (compléxité)
    - récurence structurel (récurence pour trouver la solution du probleme)
- divisé pour régner
    - tri fusion 
    - quick sort
    - recherche dicotomique
- les problemes dificile 
    - NP 
    - NP hard (dificile)
    - NP complet
- programation dynamque
- algo gloutons + algo d'approximation
:::info
algo d'approximation -- (heuristique A*?)
:::

## Bibliographie

- **Algorithms Etc.** -- jeff Erickson (disponible en ligne)


## Backtracking
### Probleme des 8 reines (N reines)
**On a un échéquité nxn**
On souhaite placer N reines sur un échiquier NxN de sorte à ne jamais avoir 2 reiners sur la meme ligne, colone, 2 diagonales.
Trouver une configuration ou décider qu'il n'en existe pas.

![jeux des reines](https://www.iechecs.com/img/huitdames.jpg)

[suivant](/gvyXVnEOQyCM91UM0SAsaw)