Structures élémentaires decontrôle

Joël QuinquetonDépt MIAp, UFR IV

UPV − Université Montpellier III

Algorithmique (rappels)

• La cohérence du programme (ducontenu) n'est pas examinée ouévaluée par le compilateur

• L'analyse du problème à traiter, lapreuve de la cohérence et de lapertinence de sa solution sont préalableà l’écriture du programme

Algorithmique: la démarche

• On doit– fixer l'objectif du programme– établir la liste des données à manipuler et

des opérations à exécuter, et les ordonner.• La description de la suite des

opérations élémentaires ordonnéescapables de résoudre le problème poséconstitue un algorithme

Structure générale

• Algorithme:– Imprimer(« bonjour »)

• Programme:<script type=« text/javascript »>Alert(« bonjour »);</script>

Traitement d’une entréevariable

• Algorithme(entree):– Imprimer(« bonjour »)– Imprimer(entree)

• Programme:<script type=« text/javascript »>Var entree = « salut »Alert(« bonjour »);Alert(entree);</script>

Condition sur une entrée• Algorithme(entree):

– Si (entree = « salut »)• Alors imprimer(« bonjour »)• Sinon imprimer(entree)

• Programme:<script type=« text/javascript »>Var entree = « salut »;If (entree==« salut »)Alert(« bonjour »);

Else Alert(entree);</script>

Boucle itérative• Calcul de la somme des entiers de 1 à 10:

– Somme = 0, entier=0– Tant que (entier < 10)

• Somme = Somme + entier, entier = entier + 1– imprimer(Somme)

• Programme:<script type=« text/javascript »>Var somme = 0; var entier=0;While (entier < 10)

{somme = somme + entier; entier = entier + 1;}Alert(somme);</script>

Boucle itérative « for »

• Calcul de la somme des entiers de 1 à 10:– Somme = 0– Pour (entier de 1 a 10)

• Somme = Somme + entier– imprimer(Somme)

• Programme:<script type=« text/javascript »>Var somme = 0; var entier=0;for (entier = 0; entier < 10; entier=entier + 1)

{somme = somme + entier;}Alert(somme);</script>

Algorithmique

• Techniques de tris élémentaires– Qu'est-ce qu'un tri?– On suppose qu'on se donne une suite de N

nombres entiers et on veut les ranger en ordrecroissant au sens large.

Ainsi, pour N = 10, la suite18, 3, 10, 25, 9, 3, 11, 13, 23, 8

devra devenir3, 3, 8, 9, 10, 11, 13, 18, 23, 25

Tri par sélection

• On trie N nombres entiers, rangés dansun tableau

• Tri par sélection (le plus simple)– Trouver l'emplacement de l'élément le plus

petit du tableau : l'entier m tel que, pourtout i, am ≤ ai

– On échange les éléments a1 et am– Puis on recommence ces opérations sur la

suite a2, a3, ..., aN

Tri par sélection

• Cette solution utilise la solution à unsous-problème– La recherche de la position du plus petit

élément d’un tableauindElmtMin = 0 // pos de l’élmt min courantj = 0tant que j < N faire { si (T[j] < T[indElmtMin]) alors indElmtMin = j j = j + 1}

Tri par sélection

18, 3, 10, 25, 9, 3, 11, 13, 23, 8

indElmtMin

j

18, 3, 10, 25, 9, 3, 11, 13, 23, 8

indElmtMin

j

Tri par sélection

18, 3, 10, 25, 9, 3, 11, 13, 23, 8

indElmtMin

j

18, 3, 10, 25, 9, 3, 11, 13, 23, 8

indElmtMin

j

Tri par sélectiontriSelection { min = 0 i = 0 tant que i < N - 1 faire { min = i j = i + 1 tant que j < N faire { si (T[j] < T[min]) alors min = j j = j + 1 } echanger(i, min) i = i + 1}

Tri par sélection

18, 3, 10, 25, 9, 3, 11, 13, 23, 8

3, 18, 10, 25, 9, 3, 11, 13, 23, 8

3, 3, 10, 25, 9, 18, 11, 13, 23, 8

Tri par sélectiontriSelection { min = 0 i = 0 tant que i < N - 1 faire { min = i j = i + 1 tant que j < N faire { si (T[j] < T[min]) alors min = j j = j + 1 } echanger(i, min) i = i + 1}

Tri par sélectiontriSelection { t, min = 0 i = 0 tant que i < N - 1 faire { min = i j = i + 1 tant que j < N faire { si (T[j] < T[min]) alors min = j j = j + 1 } t = T[j], T[j] = T[min], T[min] = t i = i + 1}

Tri par sélection

• Ses performances ?– Evaluation du coût de l ’algorithme– Combien d’opérations doit-on effectuer

pour trier un tableau de N entiers ?

Tri par sélectiontriSelection { t, min = 0 i = 0 tant que i < N - 1 faire { min = i j = i + 1 tant que j < N faire { si (T[j] < T[min]) alors min = j j = j + 1 } t = T[j], T[j] = T[min], T[min] = t i = i + 1}

N échanges:

Tri par sélectiontriSelection { t, min = 0 i = 0 tant que i < N - 1 faire { min = i j = i + 1 tant que j < N faire { si (T[j] < T[min]) alors min = j j = j + 1 } t = T[j], T[j] = T[min], T[min] = t i = i + 1}

N-i comparaisons:

Tri par sélection

• Coût de l’algorithme

2)1(

12

0

!=!!+"

!

=

NNiNN

N

i

Echanges

Comparaisons

Tri par sélection

• Coût de l’algorithme

Taille du tableau

Tempsd’exécution

Les objets en Javascript• Structure hiérarchique• Pré

– Arbre• Branche

– nid• Tronc

– Balançoire• nid

• Désignation: Pré.arbre.branche.nid

Accéder à la page

• La structure d’une page est hiérarchique:• document

– images[]• src• width

– forms[]– title– body– …

• <img src=« fichier.jpg »>– document.images[0].src

Modifier la page

• Document.write(«  le texte qui varemplacer celui de la page »);– Remplace le contenu de la page– Ne peut être utilisé qu’une fois– Peut (et doit?) contenir des balises HTML

• Permet à la page de se modifier elle-même pendant son affichage