Prog comp — Cours 1 -Notes de cours et TD Summary & Study Notes

🎯 But du cours

Objectif principal : comparer les modèles de programmation (impératif, fonctionnel, objet) et apprendre à choisir un style et à traduire entre langages. Courts paragraphes expliquent la sûreté, la performance et le niveau d'abstraction à considérer.

🧭 Langages étudiés

Les quatre langages de base sont C, Java, Python, OCaml. Chacun illustre un paradigme : C (impératif bas‑niveau), Java (objet), Python (multi‑paradigmes lisible), OCaml (fonctionnel typé). On note aussi mentions de Haskell, Prolog, Rust, etc.

⚖️ Critères de classification

On compare selon : typage (statique vs dynamique), sûreté (erreurs détectées à la compilation/exécution), gestion de la mémoire, introspection, haut vs bas niveau, et instructions vs expressions. Par exemple, OCaml est expressionnel et statiquement typé, Python est dynamique et introspectif.

🔁 Itération vs récursion

Expliquer la différence de style : itératif (boucles + accumulateurs, coût mémoire constant) vs récursif (définition par récurrence, coût mémoire proportionnel à la profondeur). Introduit la notion de récursion terminale (optimisable en boucle par OCaml) et la conversion récursion ↔ itération (introduire accumulateurs, fonctions auxiliaires).

🧠 Fonctions, lambdas et fermetures

Les fonctions sont des valeurs de première classe (paramètres, retours, closures). On présente l'application partielle (currification) et les différences d'implémentation entre langages (pointeurs de fonction en C sans fermeture automatique, lambdas en Java/Python/OCaml).

🧰 Ressources et évaluation

Rappels sur les supports (Moodle, GitLab), modalités d'évaluation (partiel, examen final, contrôle continu) et recommandations d'outil (IDE au choix).

🧩 Objectifs des TD/TME

Les TD visent à pratiquer programmation impérative et fonctionnelle, boucles et récursivité, ainsi que la traduction entre langages (C, Java, OCaml, Python). Les exercices portent sur fonctions simples, matrices, composition d'opérations, algorithmes classiques et parcours de graphe.

🔢 Exercices fondamentaux

• Fonctions basiques : identité, parité (pair/impair) en utilisant uniquement le prédécesseur et la comparaison à $0$.
• Racine carrée entière : énumérer les entiers depuis $1$ pour trouver le plus grand $i$ tel que $i \times i \leq n$, implémentation itérative et récursive; analyser récursivité terminale.

🧮 Fibonacci

• Définition : $fib(1)=1$, $fib(2)=1$, $fib(n)=fib(n-1)+fib(n-2)$.
• Implémentation récursive conforme à la définition (arbre d'appels, coût exponentiel), puis version linéaire (utiliser accumulateurs ou itération pour obtenir complexité $O(n)$). Discuter de la terminaison et optimisation tail‑call.

🔄 Transposition de matrice

Exemple OCaml fourni (itrans) : comprendre le type et les effets mémoire (échange en place), tester sur un tableau donné, puis écrire équivalents dans d'autres langages et comparer différences (mutabilité, indexation, coût mémoire).

∘ Composition et map

• Implémenter map (appliquer une fonction à chaque élément d'une liste/tableau).
• Composer calculs (ex. ajouter 3 puis multiplier par 5) et écrire une fonction compose pour chaîner ces transformations.

🔎 Recherche et sommes de sous‑ensembles

• Recherche dichotomique (binary search) : traduction du code C en version récursive, analyser si la récursion est terminale.
• Subset‑sum (check) : version récursive testant inclusion/exclusion; transformer en OCaml, discuter suppression des if via style fonctionnel (utilisation de valeurs booléennes, combinaisons logiques) et possibilité d'itératif (pile explicite). Impact sur la pile d'appel.

✨ Exponentiation

Deux algorithmes : naïf $x^{n+1}=x \times x^n$ et exponentiation rapide (si $n=2p$, $x^n=(x^2)^p$, sinon $x^n=x\times (x^2)^p$). Implémentations récursive et terminale, essais pour faire « exploser » la pile, et versions en plusieurs langages.

🚶 Distance de Manhattan (parcours en largeur)

Programme OCaml donné qui remplit une matrice avec la distance de Manhattan depuis $(px,py)$ en contournant des murs. Variantes : version récursive et version terminale utilisant une queue (BFS). Comparer complexité, ordre d'exploration et adapter pour taille variable et coordonnées des murs.

🛠 Création d'exécutables et environnement

Consignes pour construire des commandes exécutables (récupérer arguments via Sys.argv, main args en Java, argv en C, sys.argv en Python). Connexion au GitLab pour rendu des TME.

📚 Résumé rapide de la remise fournie

Le paquet fourni contient les notes de cours (cours-1_ok.pdf) et les exercices associés (TD1-etu.pdf). Le matériel couvre notions théoriques et exercices pratiques à implémenter dans plusieurs langages, et inclut indications pour GitLab/Moodle.

✅ Stratégie d'étude recommandée

1. Lire la partie cours pour comprendre paradigmes et notions clés (récursion terminale, typage, expressions vs instructions).
2. Résoudre les TD en écrivant chaque exercice dans au moins deux langages (ex. OCaml + C ou Python) pour assimiler différences de mutabilité et gestion de la pile.
3. Pousser les solutions sur GitLab comme demandé (TME rendus), tester cas limites (pile, performances).

🔗 Conseils pratiques

• Tester les versions récursives profondes et convertir en récursions terminales ou utiliser une pile/queue explicite si nécessaire.
• Utiliser les ressources listées (Moodle, documentation OCaml/Java/Python) pour les API et exemples.
• Privilégier la compréhension des invariants (ex. accumulateur pour factorielles, invariant de boucle pour itérations).