 |
 |
Informatique Théorique III - 2004/2005
français seulement
|
|
|
|
||
| |||||
|
|
|
Informatique Théorique III - 2004/2005
|
||
| |||||
|
français seulement
|
|||||
|
Le cours est donné le lundi et le mercredi de 13h15 à 16h00 en salle CE6. Les documents du cours sont rendus accessible ci-dessous sont en format pdf, mais aussi en format Postscript (ps) et Postscript "gzippé" (gz). Le format 4on1 contient 4 transparents (taille: 8ème) par pages et laisse beaucoup d'éspace pour des notes personnelles. Pensez au fait que les transparents sont assez grands (>10MB), surtout en format Postscript. Nous mettrons ces documents sur ce site les jours suivants:
La langue de travail sera le français. Mais nous sommes prêts à répondre aux questions in english, auf deutsch, in italiano, español, och på svenska. Nous vous recommandons fortement d'utiliser le forum: votre question intéresse très certainement d'autres personnes. Il sera plus facile pour tout le monde que vous posiez vos questions via ce canal, étant donné que nous utiliserons celui-ci pour nos réponses. Par ailleurs, vous avez certainement remarqué que parfois, le simple fait de formuler sa question de manière précise afin de se faire comprendre par son interlocuteur suffit à vous en donner la réponse.
Le sujet de ce cours fait partie du domaine plus large de la « théorie de la calculabilité ». Cette dernière est considérée, de pair avec la théorie des language formels, comme étant la base de l'informatique théorique. En bref, le but de ce cours est de fournir une compréhension des possibilités et limites fondamentales des ordinateurs à travers une étude mathématique précise. Nous considérerons également les implications pratiques de ces limites. La calculabilité est l'étude des problèmes calculables et des modèles mathématiques qui nous permettent de les exprimer. Les automates finis sont un modèle formel de base de la calculabilité. Nous verrons qu'il existe des problèmes pour lequels il n'y aura jamais aucune solution algorithmique. La découverte de l'existence de ces problèmes intrinséquement insolubles a été un des grand achèvements des mathématiques du vingtième siècle. Rapidement, l'objet d'étude de la théorie de la calculabilité est la définition précise de la notion informelle d'algorithme et la caractérisation des problèmes qui peuvent (ou, de manière plus intriguante, ne peuvent pas) être résolus par un algorithme. Au cours du developpement de cette théorie, nous allons aborder des sujets tels que :
Pour une excellente description alternative de ce cours, je recommande fortement la préface de « Computers Ltd.: What They Really Can't Do » Oxford University Press par David Harel (si vous desirez lire ce livre consultez cette critique du livre dans Plus magazine). A la fin de ce cours, l'étudiant devrait être capable de
Pour la complexité et les languages formels, référez vous à la seconde partie du cours intitulée « Langages Formels ». En résumé, la théorie de la calculabilité parle des problèmes qui peuvent être résolus (ou non) algorithmiquement, alors que la théorie de la complexité se donne pour but de caractériser les problèmes pour lesquels il existe une solution algorithmique efficace par rapport à sa consommation en temps et en espace. Le cours est constitué d'une série de 28 séances agendées selon cet horaire.
Ce cours suppose une connaissance de base des mathématiques discrètes, tel que celles utilisées dans des cours comme « Logique élémentaire ». Ceux d'entre vous qui souhaiteraient rafraîchir leur mémoire ou qui ne sont pas confiants dans leur compréhension de ces bases sont invités à consulter les deux ouvrages suivants:
Voici deux références sur la notion de preuve
Ce cours est donné sous cette forme pour la première fois; il n'y a donc pas de polycopié. Malheureusement, il n'existe pas encore de livre en français susceptible de fournir une base appropriée au cours de la manière dont nous voulons le donner. C'est pourquoi nous utiliserons un livre écrit en anglais comme support principal :
Si vous souhaitez lire des écrits français, vous pouvez consulter les deux références données ci-dessous. Notez cependant qu'ils ne couvrent pas exactement tout ce que nous allons faire et que nous ne pouvons dès lors pas indiquer les correspondances entre ces sources et le livre principal.
Pour les alémaniques, nous pouvons recommander:
Comme matériel supplémentaire de lecture sur l'informatique en général nous vous recommandons fortement,
Autre matériel de cours (rassemblé par Luca Aceto, en anglais) Pour quelques conseils sur la manière d'apprendre la substance de ce cours (et en fait de n'importe quel cours), vous pouvez consulter les transparents de l'exposé intitulé « Psychologists' tips on how and how not to learn » de Wilfrid Hodges. Essayez de réfléchir sur ses suggestions et de les comparer avec votre manière de travailler. Une autre lecture intéressante est « How to Read Mathematics » par Shai Simonson et Fernando Gouveau --- une collection utile et réaliste de suggestions sur la manière de lire et d'apprendre les mathématiques.
Chaque semaine, nous vous donnerons quelques exercices. Nous vous conseillons bien évidement de prendre le temps de les résoudre... Ils seront d'une difficulté variée, mais ils seront tous « faisables ». Ils contribueront fortement — vous vous en doutez — à votre compréhension des sujets abordés dans le cours. Le meilleur conseil que nous puissions vous donner est de les résoudre par vous même et d'être sûr de comprendre les solutions dans le cas où nous vous les donnerons sur un plateau. Surtout, n'abandonnez pas si vous n'arrivez pas à résoudre un problème immédiatement. La résolution d'un problème est souvent une question d'endurance et de créativité. Nous vous encourageons à travailler en groupes. Surtout, essayez d'avoir un regard critique sur vos solutions. Vous n'aurez peut être pas besoin de tout le matériel couvert par ce cours dans vos futures carrières, mais avoir une attitude analytique et critique vous sera certainement d'une grande aide. Les exercices ne sont pas notés. Un corrigé sera rendu accessible. A chaque cours nous associerons une heure d'exercices en salle, généralement de 15h15 à 16h00 après les deux heures de théorie. Durant ces exercices, vous pouvez,
L'examen est un écrit, il aura lieu à la session de printemps 2005 (entre le 7 et le 28 février). Une session de réponses aux questions sera organisée pendant la dernière leçon du cours. |