INF4230 – Intelligence artificielle (Hiver 2017)

Sem.
#

Date

Contenu du cours magistral 
(les mardis 18h00-21h00 au SB-M230)

Travaux pratiques

Lectures

1

mardi
10 janvier

Présentation du cours.

• Plan de cours officiel : [ HTML | PDF ].
• Livre de référence obligatoire pour le cours (voir la référence en bas de cette page).
• Politiques sur les langages de programmation et environnement de développement acceptés dans le cours.
• Entente d'évaluation (les dates des TPs peuvent varier) :

Promotion des stages d'initiation à la recherche au de premier cycle :

• Procédure du Service de la recherche et de la création (SRC) de l'UQAM.
• Description du programme Bourses de recherche de 1er cycle.
• Trouver un professeur pour un stage CRSNG 1er cycle.
• Date limite : Février 2017

• En milieu pratique : http://www.nserc-crsng.gc.ca/Students-Etudiants/UG-PC/Experience-Experience_fra.asp

Introduction à l'IA.

[RN] Chapitre 1.

2

mardi
17 janvier

Agents intelligents (rendu diapo #9).

Résolution de problèmes par recherche.

• Rappel théorie des graphes et algorithmes de base.
• Formalisation d'un problème.
• Stratégies non informées.
• En largeur, en profondeur, profondeur limité (itérative).

[RN] Chapitre 2.

[RN] Chapitre 3 : 3.1-3.4.

3

mardi
24 janvier

Résolution de problèmes par recherche.

• Rappel théorie des graphes et algorithmes de base.
• Formalisation d'un problème.
• Stratégies non informées.
• En largeur, en profondeur, profondeur limité (itérative).

Recherche heuristique / Algorithme A* 

• Stratégies informées.
• Meilleur d'abord.
• Heuristiques.
• Algorithme A*.

Exercice 1  avec solution  

TP1 – Algorithme A*

[RN] Chapitre 3 : 3.5-3.6.
- Démo 1 : algorithmes de recherche. Si l'applet Java ne se lance pas essayez en ligne de commande:
appletviewer http://ericbeaudry.ca/INF4230/demos/search/.
- Démo 2 : algorithmes de recherche (DFS non présenté).

4

mardi
31 janvier

Recherche en situation d'adversité.

• Jeux / Jeux à sommes nulles.
• Adaptation de la recherche à des jeux : Algorithme MiniMax.
• MiniMax avec Élagage Alpha-Beta (Alpha-Beta pruning).
• Prise de décisions imparfaites en temps réel.
• Généralisation aux jeux avec du hasard.

[RN] Chapitre 5 : 5.1 - 5.5 *.

* 5.5 en survol uniquement.

5

mardi
7 février

Quiz #1 portant sur les lectures pointées aux chapitres 2 et 3 (4%)

Retour et conclusion sur la recherche en situation d’adversité

Techniques de recherche locale.

• L'escalade (Hill climbing).
• Recuit simulé (Simulated Annealing).
• Recherche Tabu (Tabu Search).
• Recherche en faisceau (Beam Search).
• Algorithmes génétiques.

[RN] Chapitre 4 : 4.1.

Autres types de recherche (pas de diapositives et non présentés en classe)

• Sous incertitude (avec effets non déterministes).
• Avec observation partielle.

[RN] Chapitre 4 : 4.3 - 4.4.

6

mardi
14 février

Retour et conclusion sur la recherche locale

Problèmes à satisfaction de contraintes (CSP).

• Formalisation d'un problème à l'aide de variables et des contraintes.
• Algorithme Back-Tracking.
• Heuristiques : MRV, Degré, Forward-Checking, AC-3.

[RN] Chapitre 6 : 6.1, 6.2.1, 6.2.2, 6.2.5, 6.3, 6.4.

7

mardi
21 février

Quiz #2 (4%).

Conclusion CSP : Exercices; Solutions

TP2 - Algorithme pour jeux avec adversaire

[RN]
 - Chapitre 7 : 7.1 - 7.4, 7.5.1 - 7.5.3;

Représentation de connaissances et raisonnement logique.

• Logique propositionnelle.
• Inférence.
• Logique du premier ordre.
• Inférence.
• Unification.
• Résolution.

Préparation de l’examen intra :

·      Exemple d’examen --------------   Solution

·      Note : La représentation de connaissances et raisonnement logique ne font pas partie de la matière de l’intra.

28 février

Semaine de relâche

8

mardi
7 mars

Examen de mi-session (22%).

9

mardi
14 mars

Représentation de connaissances et raisonnement logique (Suite)

• Exercice page #43.
• Exercice sur l'algorithme d'unification de prédicats.
• Exercice sur logique du premier ordre et résolution.

Systèmes experts.

[RN]
 - Chapitre 8 : 8.1-8.3;
 - Chapitre 9 : 9.1 - 9.2, 9.3 - 9.4, 9.5.

[RN] Chapitre 9 : 9.3 - 9.4.

10

mardi
21 mars

Réseaux bayésiens.

Exemple de calculs pour diapositive #29 sur le système d'alarme : 11-reseaux-bayesiens-calculs.pdf.

[RN] : Chapitre 14 : 14.1 - 14.2, 14.3 - 14.4 (14.4.1), 14.5.1.

11

mardi
28 mars

Processus décisionnels de Markov (MDP).

Formation de groupes pour le TP3

[RN] : Chapitre 17 : 17.1-17.3.

Démo de l'algorithme d'itérations par valeurs.

12

mardi
4 avril

Quiz 3 (4%).

Processus décisionnels de Markov (MDP). (Suite)

Validation des projets.

Apprentissage machine (Introduction)

TP3-Projet  (Nouveau)

13

mardi
11 avril

Apprentissage machine (invité)

[RN] Chapitre 18 : 18.1-18.7.
[L] Chapitre 10.

Démo NEAT.

Librairie Weka.

14

mardi
18 avril

Tour rapide sur les Ontologies et les logiques de description

Révision en prévision de l'examen (Nouveau)

1)      Ce que vous devez savoir et savoir faire

2)      Ancien Examens (à titre indicatif seulement) :

·                 Examen final 2016    ________   Solution

·                 Examen final 2013    ________   Solution

3)      Solutions Quiz 2 et Quiz 3   

Annexes Quiz : Annexe Quiz2   et Annexe Quiz 3

15

mardi
25 avril

Examen Final (25%)

Durée : 3h

Quelques consignes : (Nouveau)

-          Une seule feuille de note (format 8.5x11) permise.

-          Une calculatrice de base (non programmable) et sans dispositif sans-fil est permise. Notez que les calculs sont tout de même faisables sans calculatrice.

-          Tous les autres appareils électroniques, sont strictement interdits.