 |
 |
Automates et calculabilité 2003-2004
français seulement
|
|
|
|
||
| |||||
|
|
|
Automates et calculabilité 2003-2004
|
||
| |||||
|
français seulement
|
|||||
|
Bienvenue sur la page du cours « automates et calculabilité ». 
Le cours est donné le lundi de 14h15 à 17h00 en salle CM1
Les numéros préfixés par K correspondent aux chapitres du livre du cours.
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. Une bonne partie du matériel utilisé pour le cours est inspiré par un cours similaire de Luca Aceto. En particulier les ressources accessibles en ligne qu'il a lui même rassemblé. Nous le remercions pour son travail.
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 14 séances agendées selon cet horaire. Nous allons varier le schéma 2+1 et 1+2, en commançant parfois par la théorie et d'autres fois par les exercices.
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 le chapitre 1 de ce polycopié du Prof. Zahnd. Faites aussi quelques uns des exercices que vous y trouverez. 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.
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 16h15 à 17h00 après les deux heures de théorie. Durant ces exercices, vous pouvez,
L'examen est un écrit, il aura lieu, à choix, à la session de juillet ou de septembre 2004. Une session de réponses aux questions sera organisée en juillet avant l'examen final. A la fin du semestre d'hiver, le 6 février 2004, nous distribuerons un examen de test. Comme pour les exercices, il ne sera pas noté, mais vous aurez une semaine pour nous rendre vos solutions si vous désirez une correction. |