INFO-4xx-ALGO2-Notes de cours

IF4 ALGO2Algorithmiquelinéaireetautres.NotesrédigéesparDartiguelongueGilleser1 avril2006TABLEDESMATIÈRESTabledesmatièresI Recherchesdemotifs 51 Recherchedemotifs 71.1 Algorithmenaïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2passinaïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Approcheparautomatesfinis . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 RechercheparAutomateFini(RAF) . . . . . . . . . . . . . . . . . . . . . . 91.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4.2 Constructiondel’automateetpreuve . . . . . . . . . . . . . . . . . 91.4.3 Significationdesétats . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4.4 Constructiondel’automate . . . . . . . . . . . . . . . . . . . . . . . 101.4.5 Preuvedel’algorithmeRAFetconstructiondeδ . . . . . . . . . . . 101.4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4.7 Calculeffectifdedelta . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5 AlgorithmeKMP(Knuth Morris Pratt) . . . . . . . . . . . . . . . . . . . . 121.6MP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.6.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.7 ConstructiondeF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13TraitementdeséquencesPage3TABLEDESMATIÈRESPage4PremièrepartieRecherchesdemotifsPage5CHAPITRE1. ...