 |  |  |  |  |
| | |
|||||||
| INFO0212-1 | Algorithmique et calculabilité | ||||||||
| |||||||||
| Durée : | 30h Th, 10h Pr | ||||||||
| |||||||||
| ECTS : |
| ||||||||
| |||||||||
| Titulaire(s) : | Michel Rigo | ||||||||
| |||||||||
| |||||||||
| Aperçu général : | 1.Machines de Turing et algorithmes : définition des fonctions calculables via des "ordinateurs de papier". 2.Décidabilité/Indécidabilité : description des problèmes admettant des solutions algorithmiques et de problèmes n'en admettant pas. 3.Complexité : classe P et NP, conjecture P¹NP et méthode de réduction pour évaluer la complexité d'algorithmes célèbres. (non exhaustif, susceptible de modifications) | ||||||||
| |||||||||
| Objectif du cours : | Familiariser les étudiants avec la notion de calculabilité ainsi qu'avec celle de complexité des algorithmes. | ||||||||
| |||||||||
| Pré-requis : | Néant | ||||||||
| |||||||||
| Organisation : | Les cours et les répétitions se déroulent à l'Institut de Mathématique suivant un horaire distribué à l'occasion de l'accueil. | ||||||||
| |||||||||
| Notes de cours : | Un syllabus est disponible. | ||||||||
| |||||||||
| Evaluation : | Examen oral à la fin de l'année académique. | ||||||||
| |||||||||
| Contacts : | Pierre Lecomte, professeur Institut de Mathématique, Bât. B37 - Grande Traverse, 12, 4000 Liège 1 (Sart Tilman) Tél. : 04/366.93.81 - e-mail : plecomte@ulg.ac.be Michel Rigo - Tél. : 04/366.94.87 | ||||||||
| |||||||||
ULg : Administration de l'Enseignement et des Etudiants - Affaires Académiques
Responsable de l'information : Monique Marcourt, directrice A.E.E.
Date de validité des données : 23/01/2004
Réalisation SEGI