Informatique théorique - Problèmes et exercices corrigés

L'aspect nécessairement technique de la pratique de l'informatique masque trop souvent les bases théoriques de la discipline. Pour aider les étudiants des filières " informatique " et " mathématiques appliquées " à mieux appréhender ces notions abstraites, cet ouvrage propose un ensemble de 62 problèmes et de 75 exercices corrigés ayant trait à la théorie de l'informatique. Leur résolution constituera d'une part un excellent moyen de mieux maîtriser les cours, mais elle apportera aussi une réflexion modeste sur la rigueur de cette discipline. Une attention particulière a été portée à la rigueur et à la précision de la rédaction des démonstrations. Partant de la notion d'ensemble semi-reconnaissable (ou récursivement énumérable) pour s'attaquer aux problèmes décidables, l'ouvrage passe d'abord en revue différentes méthodes de preuve. Il aborde ensuite le thème de la génération inductive d'ensembles, avant d'exposer les fondements de la reconnaissance des langages formels. Il s'achève par l'étude des classes de complexité des algorithmes et des problèmes. Outre les étudiants, un tel ouvrage intéressera également les enseignants et tous ceux qui s'intéressent aux fondements de l'informatique.