IFT-2002

Informatique Théorique

H14 - cours 1

Julien Marcil - julien.marcil@ift.ulaval.ca

Objectifs

• Comprendre les fondements théoriques de l’informatique.
• Formaliser la notion de calcul automatique.
• Raisonner à propos de la puissance et des limites d’un modèle de calcul donné.

Modèles de calcul

Nous étudierons des modèles de calcul de plus en plus sophistiqués, en analysant les limites de chaque modèle.

• Automates finis et expressions régulières
• Automates à piles et grammaires hors contexte
• Machines de Turing

Pourquoi prendre le temps d’étudier des modèles non-sophistiqués?

• Parce que plus un modèle de calcul est sophistiqué et moins on peut raisonner à propos de son comportement.
• Parce que ces modèles sont utilisés en pratique… même si ça semble surprenant!

Limites des ordinateurs

En apprenant à programmer, on a souvent l’impression que toute tâche de calcul est réalisable par un programme suffisamment long et complexe. Cette intuition est fausse et certaines tâches n’admettent aucun algorithme.

Préliminaires et Révision

Théorie des ensemble

• L’ensemble vide, noté $\{\}$ ou $\emptyset$ est l ’ensemble qui ne contient aucun élément.
• L’appartenance de l’élément $a$ à l’ensemble $A$ est noté $a \in A$.
• Si $a \in A \Rightarrow a \in B$ alors l’ensemble $A$ est contenu dans l’ensemble $B$, ce que l’on note $A \subseteq B$.
• Si $A \subseteq B$ et $B \subseteq A$ alors $A$ et $B$ sont égaux, c’est-à-dire qu’ils contiennent les mêmes éléments.

Ensemble puissance

L’ensemble puissance de $A$, noté $\mathcal P(A)$, est l’ensemble de tous les sous-ensembles de $A$.

$$\mathcal P(A) = \{E \mid E \subseteq A\}$$

\[\begin{aligned} \mathcal P(\{0,2,4\}) = \{ &\emptyset,\{0\},\{2\},\{4\}, \\ & \{0,2\},\{2,4\},\{0,4\},\{0,2,4\}\} \end{aligned} \]

Cardinalité d’un ensemble

La cardinalité d’un ensemble $S$, notée $\left\vert{S}\right\vert$, est la taille de cet ensemble, la quantité d’éléments qu’il contient.

Exemple

$$ \left\vert{\{i \in \mathbb{N} \mid 0 \le i < n\}}\right\vert = n $$

Definition

La cardinalité d’un ensemble $S_1$ est inférieure ou égale à la cardinalité d’un ensemble $S_2$ (dénoté par $\left\vert{S_1}\right\vert \le \left\vert{S_2}\right\vert$) ssi il existe une fonction injective $f: S_1 \to S_2$.

La cardinalité d ’un ensemble $S_1$ est égale à la cardinalité d’un ensemble $S_2$ (dénoté par $\left\vert{S_1}\right\vert=\left\vert{S_2}\right\vert$) ssi il existe une fonction bijective $f: S_1 \to S_2$.

La cardinalité d ’un ensemble $S_1$ est inférieure à la cardinalité d’un ensemble $S_2$ (dénoté par $\left\vert{S_1}\right\vert < \left\vert{S_2}\right\vert$) ssi $\left\vert{S_1}\right\vert \le \left\vert{S_2}\right\vert$ et $\left\vert{S_1}\right\vert \ne \left\vert{S_2}\right\vert$.

Ensembles finis et infinis

Un ensemble $S$ est dit fini ssi $\left\vert{S}\right\vert < \left\vert{\mathbb{N}}\right\vert$

Un ensemble $S$ est dit infini ssi $\left\vert{S}\right\vert \ge \left\vert{\mathbb{N}}\right\vert$

Ensembles dénombrables et non dénombrables

Un ensemble $S$ est dénombrable ssi on peut donner une méthode pour énumérer ses éléments de telle sorte que n’importe quel élément soit nommé après un nombre fini d’étapes.

Il existe donc une bijection $ f : \mathbb{N} \to S $.

Exemple

Soit $T = \{k \mid \exists_{n \in \mathbb{N}} k = 3n\}$

La fonction $f: \mathbb{N} \to T$, définie $f(n)=3n$, est bijective. Alors $T$ est dénombrable $$\left\vert{T}\right\vert=\left\vert{\mathbb{N}}\right\vert$$

Chapitre 1

Automates finis et langages réguliers

Qu’est-ce qu’un calcul?

Language

Concaténation

Définition: La concaténation de deux séquences $s_1$ et $s_2$ notée $s_ 1s_2$ est une séquence composée de tous les symboles de $s_1$ suivis de ceux de $s_2$.

Séquence vide

Définition: La séquence ne contenant aucun symbole, appelée séquence vide, fait partie des séquences de symboles. Elle est dénotée $\lambda$.

$$\lambda s = s\lambda= s$$

Remarques

• Un langage peut être fini ou infini.
• Un langage peut contenir la séquence vide ou ne pas la contenir.
• Les séquences d’un langage sont toujours finies (par définition de $\Sigma^*$).

Remarques

L’ensemble de tous les langages sur un alphabet $\Sigma$ est $\mathcal P(\Sigma^*)$.

Comme $\Sigma^*$ est infini et que $$\left\vert{\Sigma^*}\right\vert < \left\vert{\mathcal P(\Sigma^*)}\right\vert$$ on voit que l’ensemble des langages sur un alphabet donné est non dénombrable.

Pourquoi s’intéresser aux langages

Considérons des machines $M$ dont les entrées sont un mot d’un alphabet $\Sigma$ et dont la sortie est toujours $0~\text{ou}~1$.

$$ \begin{align} \text{Entrée} \longrightarrow & \boxed{M}& \longrightarrow & \text{Sortie} \\ \Sigma^* \longrightarrow & f : \Sigma^* \to \{0,1\} & \longrightarrow & \{0,1\} \end{align} $$

On peut aussi dire que la machine accepte ou rejette son entrée.

Language d'une machine

L’ensemble des mots acceptés par la machine $M$ est un langage que l’on notera $L(M)$

$$ L(M) \in \mathcal P(\Sigma^*) $$

Automates finis déterministes

Automates finis déterministes

• Premier modèle de calcul que nous allons étudier.
• Simple (voire primitif)
• Facile à comprendre et à étudier
• Permet de modéliser un grand nombre de systèmes.