diff options
| -rw-r--r-- | tp1-files/liste1 | 24 | ||||
| -rw-r--r-- | tp1.tex | 188 |
2 files changed, 212 insertions, 0 deletions
diff --git a/tp1-files/liste1 b/tp1-files/liste1 new file mode 100644 index 0000000..ca3cf28 --- /dev/null +++ b/tp1-files/liste1 @@ -0,0 +1,24 @@ + +a +aa +aaa +aaaaaaa +aaabbb +aab +aabaa +aabaaaaabb +ab +aba +ababb +ababba +abb +abbbb +b +ba +baa +bab +bb +bba +bbabbb +bbb +bbbbbb @@ -0,0 +1,188 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage[hyperindex=false]{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} +\renewcommand{\qedsymbol}{\smiley} +% +\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\relax\else\egroup\fi\par} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{TP \texttt{egrep} — Corrigé} +\else +\title{TP \texttt{egrep}} +\fi +\author{David A. Madore} +\maketitle + +\centerline{\textbf{INF105}} + +{\footnotesize +\immediate\write18{sh ./vc > vcline.tex} +\begin{center} +Git: \input{vcline.tex} +\end{center} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pretolerance=8000 +\tolerance=50000 + + +% +% +% + +Le programme Unix \texttt{egrep} a pour fonction de rechercher +(\emph{filtrer}) les lignes d'un fichier dont une partie (au sens : +facteur d'un mot) vérifie une certaine expression rationnelle. La +syntaxe est : « \texttt{egrep} \textit{regexp} \textit{fichiers} » où +\textit{regexp} désigne l'expression à chercher et \textit{fichiers} +la liste des fichiers (un par argument) dans lesquels la recherche +doit être menée : par exemple, « \texttt{egrep toto monfichier} » +cherche dans \texttt{monfichier} toutes les lignes contenant +\texttt{toto} ; en retour, \texttt{egrep} produit les lignes +recherchées, éventuellement précédées du nom du fichier où elles ont +été trouvées, et en colorisant éventuellement la partie qui vérifie +l'expression (selon les options passées et/ou la colorisation). + +\texttt{egrep} comporte de nombreuses options et particularités +d'expressions rationnelles, dont la liste peut être connue en +consultant le manuel (« \texttt{man egrep} »). Par exemple, l'option +\texttt{-c} sert à compter le nombre de lignes trouvées au lieu de les +afficher. + +Il faut prendre garde au fait que le shell Unix va interpréter +certains caractères spéciaux : le moyen le plus simple de l'éviter est +d'entourer le paramètre à protéger de caractères \texttt{\char"27} +(apostrophe droite, ou guillemet simple), qui protège tous les +caractères jusqu'au prochain caractère \texttt{\char"27} rencontré. +Par exemple, « \texttt{egrep \char"27xy*z\char"27{} monfichier} » +cherche dans \texttt{monfichier} toutes les lignes dont une partie +vérifie l'expression rationnelle \texttt{xy*z}, c'est-à-dire, les +lignes contenant un \texttt{x} suivi d'un nombre quelconque +(éventuellement nul) de \texttt{y} et d'un \texttt{z}. + +Pour rechercher les lignes vérifiant une certaine expression +rationnelle du début à la fin, on peut utiliser les caractères +spéciaux \texttt{\char"5E} et \texttt{\char"24} qui servent à ancrer +l'expression au début et à la fin de la chaîne respectivement : par +exemple, « \texttt{egrep \char"27\char"5Ex\char"27{} monfichier} » +renvoie les lignes de \texttt{monfichier} qui commencent par +\texttt{x}, et « \texttt{egrep \char"27\char"5Exy*z\char"24\char"27{} + monfichier} » renvoie celles qui sont exactement formées d'un +\texttt{x} (en début de ligne) suivi d'un nombre quelconque de +\texttt{y} et d'un \texttt{z} (en fin de ligne). + +\exercice + +Le fichier \texttt{\char"7Emadore/inf105/liste1} contient 25 mots sur +l'alphabet $\{\texttt{a},\texttt{b}\}$, tous distincts, à raison de un +par ligne. (On pourra commencer par jeter un coup d'œil au fichier, +par exemple en tapant \texttt{cat \char"7Emadore/inf105/liste1} pour +l'afficher dans le terminal.) Utiliser \texttt{egrep} pour répondre +aux questions suivantes : + +(a) Combien de mots de cette liste ne contiennent aucun \texttt{a} ? + +(b) Combien de mots commencent par \texttt{b} ? + +(c) Combien de mots sont formés d'un nombre quelconque de \texttt{a} +suivi d'un nombre quelconque de \texttt{b} ? + +(d) Combien de mots sont formés d'un nombre non nul de \texttt{a} +suivi d'un nombre non nul de \texttt{b} ? + +(e) Dans combien de mots chaque \texttt{a} est-il suivi d'(au moins) +un \texttt{b} ? + +(f) Dans combien de mots le nombre de \texttt{a} est-il congru à $1$ +modulo $3$ ? + +\begin{corrige} +(a) \verb=egrep -c '^b*$'= (ou bien \verb='^[^a]*$'=) + renvoie $5$. + +(b) \verb=egrep -c '^b'= (ou bien \verb='^b(a|b)*$'= ou encore + \verb='^b[ab]*$'=) renvoie $9$. + +(c) \verb=egrep -c '^a*b*$'= renvoie $14$. + +(d) \verb=egrep -c '^aa*bb*$'= (ou bien \verb='^a+b+$'=) renvoie $5$. + +(e) \verb=egrep -c '^b*(abb*)*$'= (ou bien \verb='^b*(ab+)*$'=) + renvoie $11$. + +(f) Si l'alphabet ne contenait que la lettre \texttt{a}, l'expression + rationnelle désignant le langage constitué des mots formé d'un + nombre de $a$ congru à $1$ modulo $3$ s'écrirait \texttt{a(aaa)*}. + On intercale des \texttt{b*} dans cette expression de manière à les + ignorer : \verb=egrep -c '^b*a(b*ab*ab*a)*b*$'= (ou bien + \verb='^b*ab*(ab*ab*ab*)*$'= ou toutes sortes d'autres variantes) + renvoie $11$. +\end{corrige} + + +% +% +% +\end{document} |