The course presents practical approaches to problem solving (such as those used in symbolic AI) as well as more theoretical approaches related to different programming paradigms.
In the first part of the course, we discuss the design of efficient algorithmic solutions. The techniques of problem solving using decompositions and graph exploration algorithms (including acceleration by heuristics) form the heart of this part. . We also introduce the theory of complexity and we will present NP completeness as well as some known polynomial reductions of problems.
The second part deals with the formal study of procedural (imperative) and non-procedural (functional and logical) programming paradigms. This concerns an important part of program theory.
This is what is taught in the TPRO module at ESI in Algiers.
-------------------------------------------------------------------------------
A - Part One (Problem Solving and Algorithmic efficiency)
1- Complexity of algorithms (O-notation), Graph traversal algorithms - (handout)
2- Divide and Conquer / Dynamic Programming - (handout)
==> Slides
3- Problem solving by exploring search spaces - (handout)
- Depth First Search DFS and Backtracking
- MinMax and alpha / beta pruning in game trees (see example of C programs)
- Breadth First Search BFS
4- Heuristic-guided searches - (handout)
- Greedy Algorithms
- Heuristic-guided DFS, Hill Climbing
- Best First Search
- Branch and Bound
- A* algorithm
==> Slides
5- Complexity Theory - (handout)
- Decision problems and language recognition
- Classification of problems
- Polynomial reductions
- NP Completeness
==> Slides
B - Part Two (Programming paradigms and formal program manipulations)
6- Formal manipulations, Preliminary concepts
- Formal Systems
- Fixed Point Theory
==> Slides
7- Procedural programming
- Program models (Schema),
- Program transformations,
- Formal proofs (Hoare system)
==> Slides
8- Functional programming - (handout)
- lambda calculus,
- Lisp language
- Proof by induction (fixed point theorem)
==> Slides
9- Logic programming - (handout)
- Automatic proof of Theorems
- Declarative programming with Horn clauses
- Examples in Prolog language
==> Slides
C - Some Exam Corrections available
- On this link you will find some examination statements with their answers.
-------------------------------------------------------------------------------
الكلمات الرئيسية
التعقيد الحسابي ، خوارزميات اجتياز الرسم البياني ، اجتياز العمق ، اجتياز الاتساع: انظر الفصل 1
فرق تسد ، البرمجة الديناميكية: انظر الفصل 2
الاستكشاف المتعمق أولاً ، الاستكشاف في العرض أولا ، تقليم ألفا بيتا : انظر الفصل 3
البحث التقريبي ، الخوارزميات الجشعة (الجار الأقرب) ، عمليات البحث المستنيرة ، خوارزمية البحث "الأفضل أولاً" ،خوارزمية البحث عن الفرع الأمثل: انظر الفصل 4
نظرية التعقيد ، مشكلة القرار، تخفيضات المشاكل : انظر الفصل 5
الأنظمة الرسمية ، نظرية النقطة الثابتة: انظر الفصل 6
البرمجة الإجرائية ، تحويل البرامج ، برهانات البرامج : انظر الفصل 7
البرمجة الوظيفية ، حساب لامدا ، آلة التخفيضات ، إثبات رسمي باستخدام النقطة الثابتة: انظر الفصل 8
البرمجة المنطقية ، الإثبات الآلي للصيغ : انظر الفصل 9
Mot-clés (fr)
complexité algorithmique, O-notoation, algorithmes de parcours de graphes, parcours en profondeur, parcours en largeur : voir chapitre 1
diviser pour régner, programmation dynamique : voir chapitre 2
espace de recherche, recherche en profondeur, recherche en largeur, MinMax, élagage alpha-bêta, arbres de jeux : voir chapitre 3
heuristiques, algorithmes gloutons (voraces, du plus proche voisin), recherches informées, recherche du meilleur d’abord, séparation-évaluation, algorithme A* : voir chapitre 4
théorie de la complexité, problèmes de décision, réductions polynomiales, NP complétude : voir chapitre 5
systèmes formels, théorie du point fixe : voir chapitre 6
programmation procédurale (impérative), transformation de programmes, preuves de programmes, système de Hoare : voir chapitre 7
programmation fonctionnelle (applicative), lambda calcul, machine à réduction, combinateur Y, langage LISP, preuve par point fixe : voir chapitre 8
programmation logique (déclarative), démonstration automatique de théorèmes, la résolution, clauses de Horn, langage PROLOG : voir chapitre 9