Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Informatique theorique plan de cours

PLAN DE COURS Hiver IFT- - Informatique théorique Informations générales Crédits Temps consacré - - Mode d'enseignement Présentiel Site Web aucun Intranet Pixel https pixel fsg ulaval ca Enseignant s Tesson Pascal pascal tesson ift ulaval ca Responsable Tesson Pascal pascal tesson ift ulaval ca Date d'abandorenmsabnosuréscehmecenatve c Janvier à h Date d'abandroenmsbanous réscehmecensat n s Mars à h Description sommaire Introduction à la théorie des machines abstraites et des langages formels Classi ?cation des machines abstraites automates ?nis automates à pile machine de Turing Classi ?cation des langages réguliers non contextuels récursifs récursivement énumérables non récursivement énumérables Grammaires syntaxe classi ?cation de Chomsky rapports avec les machines abstraites et les langages Théorie des séquences Ensembles ?nis in ?nis dénombrables et non dénombrables Horaire et disponibilités Cours en classe Jeudi h à h VCH- Disponibilité de l'enseignant Mardi h à h PLT- du janv au avril Mercredi h à h PLT- du janv au avril Objectifs Description Les automates constituent un puissant outil mathématique de modélisation La meilleure façon d'apporter des solutions informatiques à des problèmes est de les abstraire en un modèle sur lequel Cnous pouvons raisonner facilement Les automates constituent un des modèles possibles L'objectif principal de ce cours est d'étudier les automates et leur pouvoir d'expression Les automates plus précisément les machines de Turing servent à étudier la notion de calculabilité Nous verrons qu'il existe une limite au pouvoir de calcul de n'importe quelle machine c'est-à- dire qu'il existe des problèmes qu'aucune machine ne peut résoudre Les langages informatiques sont à la base de tout développement Le problème qui occupe une place centrale dans ce cours est celui de l'analyse des langages formels le cours présente donc des connaissances utiles à l'étude de la compilation des langages de programmation Nous étudierons des mécanismes de reconnaissance des diverses classes de langages automates machines de Turing ainsi que les grammaires permettant de générer ces langages Objectifs généraux et spéci ?ques Apprendre à manipuler les modèles mathématiques suivants a Langages formels b Automates ?nis automates à pile et Machines de Turing c Grammaires d Expressions régulières Comprendre les liens entre les di ?érents modèles Comprendre les limitations de chaque modèle et son pouvoir d'expression Comprendre les notions de calculabilité et décidabilité à travers les machines de Turing Contenu Note Le découpage de la matière n'est donné qu'à titre indicatif Il pourrait y avoir un découpage di ?érent de la matière en fonction du rythme d'avancement dans le cours Chapitre Préliminaires et révision le contenu de ce chapitre étant couvert par le cours MAT- nous n'en ferons qu'un bref rappel Chapitre Automates ?nis et langages réguliers ? Automates ?nis et langages réguliers ? Notion de langage Alphabets Langages Diagrammes de transitions ? Automates ?nis déterministes ? Limites des automates déterministes Langages réguliers Langages non réguliers ? Automates ?nis non déterministes ? Grammaires régulières C ? Expressions régulières Union de deux langages Concaténation de deux langages Fermeture d'un langage Expressions régulières Chapitre Automates à pile langages non contextuels ? Automates à pile