Révision pré-intra
- Algorithme correct et Vérification d'algorithme
- Mesure de l'espace, temps et des données
- Algorithme efficace
- Notations asymptotiques et Les pires, moyens et meilleurs cas
- Classes de complexité
- Graphe : fortement connexe, chemin entre chaque paire de sommet n^3. Trouver méthode optimale pour tester la forte connexité n^2*log(n) d'un graphe orienté.
- Analyse de code source : addition et multiplication asymptotique
- Récursion: Caractériser correctement les données. Morceau moins gros ou pas? partitionnement? Analyser globalement si trop complexe. Récurrence T(n) = ? résolver la récurrence. Brassard p.140, 141, #4.1, 4.2, 4.36, 4.37.
- Convergence : Déterminer qu'un algorithme termine dans les cas. Formules mathématique. Positif et décrémente à 0. Tri Sélection. Variant de boucle
- Temps amorti VS temps moyen
- Représenter un graphe : approprier 200 sommets, 20000 arêtes, justification, consommation temps et espace
- Type d'algorithme : glouton, DNC, Dynamique, exemple et description courte de chaque type
- Développement : développer un algo pour trouver le k ième plus petit élément de T[1..N] non trié en O(N) au pire cas (algorithme du pigeonnier?)
- Matrice distance : Dÿkstra, Floyd
- Heuristique : Algorithme glouton pour le PVC, voyageur de commerce
- Bornes sup/inf. : évaluation d'une heuristique, qualité de l'approximation et marge d'erreur (temps, espace, pire cas). Borne inférieure non triviale.
- Compression avec ou sans perte : huffman pour texte/arbre pour image, arbre quaternaire pour une matrice de 200x100. Combien de noeuds dans l'arbre au pire cas. Temps pour construire l'arbre
- RSA : résumé en moins de 10 lignes
Notion
Définition
- Correct
- Un algorithme est correct s'il résout le problème pour lequel il est utilisé. En tout temps, il doit converger, terminer et donner la réponse correcte pour toutes les entrées propres à son domaine de définition et pour les fonctionnalités attendues. Un algorithme qui donne un résultat plausible, n'est pas un algorithme correct. La correctitude d'un algorithme n'est pas influencé par l'outil qui l'implémente. Pour tester la correctitude d'un algorithme, on doit tester toutes les entrées possibles ou utiliser une preuve formelle.
- Efficace
- Moins un algorithme consomme de temps et de ressource en fonction des données, plus il est efficace.
- Non acceptable
- Un algorithme n'est pas acceptable si on peut faire plus rapidement (exemple on peut faire N^2 au lieu de N^3).
- Mesure de temps
- Nombre d'instructions (ou de comparaisons calculé par des compteurs ou des baromètres) effectués par le programme en fonction du nombre de données N. On évalue ce temps avec la syntaxe Grand O.
- Mesure d'espace
- Espace maximale utilisé au cours de l'algorithme en fonction du nombre de données N. On évalue cet espace avec la syntaxe Grand O.
- Mesure de données
- Identifiée généralement par N.
- Variant
- Expression mathématique qui diminue de 1 à chaque tour de boucle, utilisant les variables de l'algorithme initialement > 0 et diminue de 1 à chaque itération et termine à 0. Noté par la lettre grecque Bêta.
- Exemple: N=0; TantQue < 10; N=N+1; Fin; Bêta=10-N.
- Exemple: N=0; TantQue < 10; N=N+0,5; Fin; Bêta=20-2N.
- Exemple: N=10; TantQue <= 0; N=floor(N/2); Fin; Bêta=N.
- Complexité cyclomatique
- 2 + Nombre arcs - Nombre noeuds
- Sous-types de Tests
- Chemin indépendants
- IF (2 fois le nb IF)
- Flot de données
- Boucles
- Séquence aléatoire
- séquence d'évènements imprévisibles et équiprobable
- Congréance linéaire
- x(i+1) = ( a*x(i) + c ) mod M où M = valeur limite de la longueur du cycle. C est relativement premier à M (pas de diviseurs communs). b = a - 1 (b est multiple de p, tout P divisant M) sinon 2 ou + cycles disjoints de périodes plus petites que M
Les cas
On analyse souvent le pire, le moyen et le meilleur cas. En tout temps, il faut connaître le type de données que l'algorithme utilise. On utilise généralement le pire cas. Le cas moyen peut être utilisé lorsqu'on peut prouver que le pire cas est exponentiellement improbable de se produire. Le meilleur cas est utile lorsque les conditions s'y appliquent.
(problème de Brassard #3.5 et 3.22)
Vérification
Regarder si on a un bonne solution (est-il correct).
Utiliser une stratégie systématique de vérification.
Vérification formelle ou vérification des sources (boîte blanche)
Classe de complexité
Polynomiale, exponentielle, factorielle, problèmes NP
n^4 n'est pas une classe de solution acceptable.
Graphe
- Fortement connexe
- Il existe un chemin entre chaque paire de sommets (en suivant les flèches si c'est un graphe orienté).
- Densité
- Nombre d'arêtes présentes sur le nombre d'arêtes possibles.
- Nombre d'arêtes possibles
- N (N-1)/2 (n = nombre de sommets).
- Grille
- Adjacent en O(1). Voisin en O(N).
- Dynamique
- Tableau pointant sur des listes chaînées d'éléments. 128 bits par arête présente. Meilleur si la densité est 1/128.
- Adjacent en O(N). Voisin en O(1).
- Implémentation double
- Grille + Dynamique, peut prendre 100 fois plus d'espace?
- Permet de s'assurer O(1) pour optenir l'adjacent et le voisin. Pour problème comme la compilation.
- Représentation hybride
- Former d'un vecteur dynamique verticale, et de vecteur d'adjacence horizontale. Utile lorsqu'on ne connaît pas le nombre de sommets.
Laboratoire #2
Ce qu'il reste à faire
- Limité nombre de sommets entre 40 et 1000
- Limité pourcentage entre 2% et 20%
- Augmenté le pourcentage (et avertir) s'il y a moins que le nombre de sommets (exemple 2% de 40*39/2 = 15.60, doit être augmenter à 40. (40/(40*39/2)*100 = 5% = (n-1)/2.
- Analysé en notation O la construction (du graphe?) et la coloration
- Placé baromètre pour analyser la construction et la coloration en fonction du nombre de noeuds/arêtes.
- Listé les problèmes rencontrés
- Suggéré méthode pour concevoir des graphes non-équiprobables pour simuler l'usage abusif de ressources et discuter de l'impact sur la performance et la coloration...
- Extra: 80% arêtes sur 20% des sommets...
Rapports
- page titre
- table des matières
- introduction (copier-coller ou résumé de l'énoncé)
- description des méthode employées pour construire et pour colorer
- analyse asymptotique
- tableau des résultats pour différentes tailles et densités
- conclusions personnelles sur vos résultats et sur l’exercice.
- Mentionnez vos références.
Hyperliens...