# **NSI - Programme de Révisions S1**

<img src="https://drive.google.com/uc?id=12Wo3LubGGT4qOvYFAuLP4CyCuwjKNVuk" width="230" height="150" align = "right"/>

**O.Thöni - UCO**
*document à l'usage exclusif des personnes concernées par la formation Master MEEF - NSI de l'UCO*

* Le sujet ressemblera dans ses objectifs à celui d'une épreuve 1 d'écrit de CAPES

>
>

* Éléments de corrigés et rapports des épreuves passées du CAPES :
- https://capes-nsi.org/index.php?id=ressource
- 2021, épreuve 1 : https://irem.univ-reunion.fr/spip.php?article1102

*remarque sans importance* : ++dates des épreuves++ :

###### tags: `NSI`, `M1-MEEF`, `Révisions S1`

# **1. Algo et fonctions**
- structures
- conditionnelles (tests)
- itératives (boucles)
- paramètres d'entrée, de sortie
- spécifications
- récursion ?
- **jeux de tests**

# **2. Algo et fonctions classiques**

- recherche dicho (dans une liste triée, sur le principe "Juste prix" : on coupe en deux, c'est plus ou c'est moins)
>

- (descente de gradient)
- algos de tris classiques (insertion, fusion...) ou inédit
- Complexité et invariant de boucle, terminaison et variant de boucle
- KNN : (calcul de distance, k-plus proches voisins, prédiction à la majorité)

# **3. Types de données**

- types simples et opérateurs
- booléens
- entiers : conversions de base : ++binaire++, (y compris flottant) et autres bases
>https://colab.research.google.com/drive/1phgloHPy5V0U97hyXpN9cdFq2X6LPkok?usp=sharing
- types construits
- (sets)
- tuples
- listes et listes de listes (y compris par compréhension)
--> indexation, parcours (boucles, doubles-boucles)
--> méthodes et fonctions associées (append, pop, sort,...)
- dictionnaires
--> clé/valeur
--> ajout/suppression
--> recherche par clé
--> méthodes associées
- (DataFrame pandas)

# **4. Traitement de données en tables**
- (Récupération de données : exemple fichier CSV)
- Construction de table (python + bibliothèque)
- (visualisations)
- Extraction d'informations en fonction de paramètres (puis modélisation)
- Tri de données dans une table
- (Fusion de tables)
- listes de listes
- (DataFrame pandas)

# **5. Algo de tris, (terminaison), complexité**
- Sélection \
- Insertion -(O(N²))
- (bulle) (O(N²), avec amélioration à l'ordre N)
- (fusion) \
- (QuickSort)- (O(N.ln(N)) ou (O(N.log_2(N), il n'y a pas mieux, sauf améliorations d'ordre N)

colab du 06/01/2022 matin : https://colab.research.google.com/drive/1tXdVVdVcXwhVA6zYSA5NemBRgYLt0mDD?usp=sharing

**Complexités :**
>

# **6. Gloutons**

- meilleur choix à un instant t sans retour en arrière (optimum local)
- algos classiques :--> savoir refaire l'idée algo, savoir adapter
- sac à dos
- rendu de monnaie (système canonique or not canonique)
- (voyageur de commerce)