Topic outline

  • General Description

    Collapse all Expand all

  • Contact Sheet

    Contact Sheet Contact (téléphone, E-mail Et L'icône De La Souris) Bouton Carré Blanc Banque D'Images et Photos Libres De Droits. Image 56061664

    • Institution:  University Mohamed Khider Biskra Faculty
    • Faculty: Faculty of Exact Sciences and Natural and Life Sciences 
    • Department: Computer Science
    •  Target Audience: 1st-year Master's students, 
    • Specializing in Software Engineering and Distributed Systems within the Computer Science field.
    •  Course Title: Calculability Theory 
    • Teaching Unit: Credits: 05 | Coefficient: 03
    • Duration: 12 weeks
    • Instructor: Dr. Mohamed RAMDANI
    • Contact via Email: mohamed.ramdani@univ-biskra.dz

  • Communication Space

  • Objectives

    Les objectifs du cours de Calculabilité pour les Masters 2 en Génie Logiciel et Systèmes Distribués peuvent être décomposés en termes de savoir, savoir-faire et savoir-être comme suit :

    En terme Savoir :

    1. Comprendre les concepts fondamentaux de la calculabilité, y compris la Thèse de Church et les modèles de calcul.
    2. Connaître les différents modèles de calcul, tels que les Machines de Turing, et leurs propriétés.
    3. Reconnaître les langages formels et les machines abstraites utilisées pour formaliser les problèmes de calculabilité.
    4. Comprendre les notions de langages récursifs et récursivement énumérables, ainsi que leur relation avec les machines de Turing.
    5. Expliquer les extensions des modèles de calcul de base et leur impact sur la calculabilité.

    En terme Savoir-faire :

    1. Pouvoir utiliser les modèles de calcul, en particulier les Machines de Turing, pour analyser et résoudre des problèmes de calculabilité.
    2. Être capable de formaliser des problèmes de calculabilité et de déterminer leur nature à l'aide d'outils tels que les langages formels et les machines abstraites.
    3. Pouvoir analyser les langages acceptés et décidés par les Machines de Turing, ainsi que de distinguer les langages récursifs des langages récursivement énumérables.
    4. Être en mesure d'appliquer les concepts de calculabilité à des problèmes concrets en génie logiciel et systèmes distribués.

    En terme Savoir-être :

    1. Développer une attitude analytique et critique envers les problèmes de calculabilité et les résultats théoriques associés.
    2. Faire preuve de rigueur dans la formalisation et l'analyse des problèmes de calculabilité.
    3. Cultiver une curiosité intellectuelle et un intérêt pour la théorie de la calculabilité et ses implications pratiques.
    4. Collaborer efficacement avec d'autres étudiants pour résoudre des problèmes complexes liés à la calculabilité.
    5. Développer une attitude d'ouverture et de persévérance face aux défis théoriques et pratiques rencontrés dans le domaine de la calculabilité et de la complexité.

     

  • Prerequisite

     

    Pour suivre ce cours, il est généralement bénéfique de posséder une solide base dans certains sujets préalables. Cela peut inclure :

    • Fondements en Informatique : Une compréhension des concepts fondamentaux de l'informatique, y compris les structures de données, les algorithmes et la complexité algorithmique, est essentielle.
    • Théorie des Langages de Programmation : Il est recommandé d'avoir une connaissance préalable de la théorie des langages de programmation, y compris la reconnaissance des langages formels, les automates finis, les expressions régulières et les grammaires formelles.
    • Logique Mathématique : Une compréhension de base de la logique mathématique est nécessaire, en particulier des concepts tels que les prédicats, les quantificateurs, les implications logiques et les preuves formelles.
    • Algèbre : Une familiarité avec les concepts d'algèbre, y compris les ensembles, les relations et les fonctions, est importante pour aborder les aspects formels de la calculabilité.
    • Programmation : Il est utile d'avoir de l'expérience en programmation dans au moins un langage de haut niveau pour comprendre les concepts liés à l'approche par les langages de programmation et pour effectuer des exercices pratiques.
    • Théorie de la Complexité : Une connaissance de base de la théorie de la complexité, y compris les classes de complexité P, NP et NP-complet, peut également être bénéfique pour contextualiser les concepts de calculabilité.

     

  • Chapitre 01 Notions de Problème Vs Programme

  • Chapitre 02: Formalisation de la procédure effective

  • Exploration de la Complexité Algorithmique

    • assign icon
      Assignment
      Sujets des Exposés Assignment
      Opened: Sunday, 25 February 2024, 12:00 AM
      Due: Saturday, 20 April 2024, 12:00 AM
      Thèmes d'Exposés pour les Étudiants en Master 1 GLSD ! 
      Voici un aperçu des sujets que vous explorerez cette année :
      1. Exposé 01: "Introduction à la complexité algorithmique". Affecter pour Sahraoui - ElGuerni- Laiadi - Bekkari (groupe 02)
      2. Exposé 02: "Analyse de la complexité dans les algorithmes classiques". Affecter pour Boughediri- Gherbi- Benkhelif (groupe 04).
      3. Exposé 03: "Théorie de la complexité et réduction de problèmes". Affecter pour Badi -Fethallah-Redjouh-Zebila( groupe 01)
      4. Exposé 04: "Complexité dans les algorithmes distribués et parallèles". Affecter pour Ghabeche - Ferhati (groupe 03)
       Pour plus de détails sur les présentations check Moodle .
      Bonne préparation et bonnes explorations !

  • Chapitre 03 Extensions des machines de Turing et puissance de calcul

  • Chapitre 04: Preuve de l’indécidabilité et problème de l’arrêt

  • Bibliography

  • Votre Avis Nous Intéresse