École Privée d’Ingénierie du Niger — L’école du nouveau monde

✉ elearning@epiniger.edu.ne    🌐 epiniger.edu.ne

EPI e-Learning

L'école du nouveau monde · Plateforme e-Learning

Unité d’enseignement : CYB · S4 · UE2 — Science fondamentale

  • Recherche opérationnelle 2

    Ce cours de recherche opérationnelle du semestre 4 est la suite du cours du semestre 3 (programmation linéaire, simplexe, dualité et sensibilité). Il élargit la boîte à outils du futur technicien supérieur en informatique et cybersécurité à trois familles de modèles très présentes dans les métiers du numérique : les modèles linéaires multipériodes (planification de production, de stocks et de budgets), la programmation en nombres entiers (choix de projets de sécurité sous budget, coûts fixes, décisions oui/non) et les problèmes de réseaux (plus court chemin pour le routage, arbre couvrant minimal pour le dimensionnement d’un réseau de fibre, flot maximal pour la capacité d’une infrastructure, transport et affectation). Les modèles sont formulés, résolus à la main sur de petits exemples puis saisis dans LINDO.

    Objectifs d’apprentissage

    • Formuler des modèles de planification multipériode avec équations de stock et les saisir dans LINDO.
    • Modéliser des décisions discrètes avec des variables entières et binaires (coûts fixes, choix exclusifs, contraintes logiques).
    • Appliquer la méthode de séparation et évaluation (branch and bound).
    • Résoudre des problèmes de plus court chemin (Dijkstra) et d’arbre couvrant minimal (Kruskal, Prim).
    • Calculer un flot maximal et la coupe minimale associée ; résoudre des problèmes de transport et d’affectation.

    Prérequis

    Cours de recherche opérationnelle du semestre 3 (ROP2324) : formulation, simplexe, dualité. Notions de graphes (sommets, arcs, chemins).

    Plan du cours

    1. Leçon 1 — Modèles multipériodes : stocks, planification et mise en œuvre sous LINDO
    2. Leçon 2 — Programmation en nombres entiers et séparation-évaluation
    3. Leçon 3 — Réseaux : plus court chemin et arbre couvrant minimal
    4. Leçon 4 — Flots, transport et affectation

    Modalités d’évaluation

    Volume horaire : 13 h de CM, 7 h de TD, 0 h de TP, 20 h de TPE ; 2 crédits. Contrôle continu (40 % : deux interrogations et un mini-projet de modélisation sous LINDO) et examen terminal écrit de 2 heures (60 %).

    Bibliographie

    • F. S. Hillier, G. J. Lieberman, Introduction to Operations Research, McGraw-Hill.
    • W. L. Winston, Operations Research: Applications and Algorithms, Duxbury Press.
    • H. A. Taha, Operations Research: An Introduction, Pearson Prentice Hall.
    • R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
    • L. A. Wolsey, Integer Programming, Wiley, 1998.

  • Théorie des langages 2

    Ce cours du semestre 4 est la suite directe de « Théorie des langages » du semestre 3, consacré aux langages réguliers et aux automates finis. Il monte dans la hiérarchie de Chomsky : langages algébriques et automates à pile, qui modélisent l’analyse syntaxique des programmes et des formats structurés, puis machines de Turing, qui définissent la notion même d’algorithme, et enfin les limites du calcul (langages décidables et semi-décidables, problème de l’arrêt, théorème de Rice). Pour un futur professionnel de la cybersécurité, ces résultats expliquent pourquoi les analyseurs d’entrées doivent être stricts et bornés, et pourquoi aucun antivirus ne peut détecter parfaitement tous les programmes malveillants.

    Objectifs d’apprentissage

    • Manipuler les grammaires algébriques : arbres de dérivation, ambiguïté, simplification, forme normale de Chomsky.
    • Décider l’appartenance d’un mot avec l’algorithme CYK.
    • Construire et faire fonctionner des automates à pile ; passer d’une grammaire à un automate à pile.
    • Prouver qu’un langage n’est pas algébrique avec le lemme de pompage.
    • Construire et tracer des machines de Turing simples ; expliquer la thèse de Church-Turing.
    • Distinguer décidable et semi-décidable, prouver une indécidabilité par réduction et en tirer les conséquences en sécurité.

    Prérequis

    Théorie des langages S3 (mots, langages, grammaires, hiérarchie de Chomsky, automates finis, expressions régulières, lemme de l’étoile) ; raisonnement par récurrence et par l’absurde.

    Plan du cours

    1. Grammaires algébriques : arbres, ambiguïté, formes normales et CYK
    2. Automates à pile et propriétés des langages algébriques
    3. Machines de Turing et thèse de Church-Turing
    4. Langages décidables, semi-décidables et problème de l’arrêt

    Modalités d’évaluation

    Volume horaire : 13 h de cours magistral, 7 h de travaux dirigés, 20 h de travail personnel (2 crédits). Évaluation : contrôle continu (quiz en ligne, exercices de TD : conversions en FNC, tables CYK, traces d’automates à pile et de machines de Turing) et examen terminal écrit.

    Bibliographie

    • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson (Addison-Wesley).
    • Michael Sipser, Introduction to the Theory of Computation, Cengage Learning.
    • Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008.
    • Pierre Wolper, Introduction à la calculabilité, Dunod.
    • Alan M. Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society, 1936.