[PDF] L3 Info Cours 1 : notion de coût dun algorithme

View - Download L3 Info Cours 1 : notion de coût dun algorithme

Previous PDF

Next PDF

Algorithmique et Analyse d"Algorithmes

Algorithmique et Analyse d"Algorithmes

L3 Info

Cours 1 : notion de coût d"un algorithme

Benjamin Wack2023 - 2024

1 / 41

Algorithmique et Analyse d"Algorithmes

Plan

Présentation du cours

Problèmes et algorithmes

Coût d"un algorithme

Complexité

Méthodologie

Ordres de grandeur

Un problème, plusieurs algorithmes

2 / 41

Algorithmique et Analyse d"Algorithmes

Présentation du coursObjectifs du cours

Savoir

p roposer une solution algo rithmique

à un

p roblème p osé, savoir implanter la solution et savoir ana lyser celle-ci. Objectifs détaillés Savoirreconnaîtreet mettre en œuvre desschémas génériques Savoirconstruireune solution selon une démarche allant du plus Savoir commentévaluerla complexité d"une solution algorithmique : analyser la complexité au pire, en mo yenneavec des hypothèses probabilistes, analyser la complexité en utilisant des mesures sur des simulations ou desjeux de test.4 / 41

Algorithmique et Analyse d"Algorithmes

Présentation du coursStructure du cours

Cours(B. Wack)Une partie synthétique sur lesconcepts et schémas algo rithmiques Un algo rithmeclassique

afin de se constituer une culture de ré férenceTD1(V. Garnero, J.-M. Vincent, B. Wack)Exercices permettent derenfo rcerla comp réhensiondes concepts.

TD2(V. Danjean, D. Monniaux, K. Ouazine, A. Reynaud)Mise en œuvredes concepts et p réparationaux activités p ratiques

APNEES: Activités Personnelles Non Encadrées ÉvaluéesValidationdes c onceptspa rla p ratiqueet évaluation d ela comp réhension

+ le travail personnel! (exercices, petits programmes...) Adresse Mail enseignant :Prénom.Nom@univ-grenoble-alpes.fr5 / 41

Algorithmique et Analyse d"Algorithmes

Présentation du coursRessources

Bibliographie

Algorithmique, T. Cormen, R. Rivest & C. Leiserson, Dunod Algorithmes, R. Sedgewick, Pearson EducationPage Web

Planning, documents, annales

(ou par ma page Web)Moodle de l"UFR

Sujets et rendus d"Apnées

https: //im2ag-moodle.univ-grenoble-alpes.fr/course/view.php?id=2296 / 41

Algorithmique et Analyse d"Algorithmes

Présentation du coursÉvaluations

Note finale = 65 % Examen + 35 % CC

Les contrôles continus

2 quicks (début octobre et début novembre) : 10 % chacun

3 comptes-rendus d"APNEEs : 15 % au totalExamen terminal

2h30 sans documents ni calculatrice

Session 2 en

juin ...7 / 41

Algorithmique et Analyse d"Algorithmes

Présentation du coursProgramme (indicatif) du cours

Complexité des algorithmes

1. Coût d"un algo rithme(itérations, o rdresde grandeur) La star 2.

Réc ursivité,analyse en mo yenneQuicksort

Types abstraits élémentaires et implantation 3. Structures séquentielles Algorithme de parenthésage 4. Structures a rborescentesPartition Binaire de l"Espace

Preuves d"algorithmes

5. Inva riant,co rrection,terminaison Drapeau hollandais 6.

Logi quede Hoa reDichotomie

Arbres

7.

Arb resbinaires de recherche Arbres B

8.

Arb reso rdonnés,structure de tas

9.

Arb reset co dageAlgorithme de Huffman

Graphes et algorithmes

10.

Algo rithmesgloutons Coloration de graphes

11.

Algo rithmiquede graphes Prim et Kruskal

8 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmesNotion deproblèmedonnées

Effectuer une recherche dans un inventairestock

Résoudre une équationcoefficients

Trouver le plus court chemin sur un plan de villeplan Corriger des fautes d"orthographetexte + dictionnaire

Multiplier des matricescoefficients

...Dans chacun de ces exemples on s"intéresse en fait à uneclasse de problèmes similaires, dont chaque instance est définie pa rdes données .Il faut également préciser lerésultat attendu. (par exemple pour l"inventaire : oui/non? quantité? localisation?)10 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmesQu"est-ce qu"un algorithme? Procédure de résolution den"importe quelle instanced"un problème

suffisamment élémentaire pour être exécutée de façon automatique.Problème informel

Problème formaliséAlgorithme

Données

InstanceProgrammeProgrammation

SolutionExécution

Exemple :plus court chemin11 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmes

Un algorithme

traite donc des données p ourp roduireun résultat ;mais avec quelles p rimitives et quelles ressources ?S"il fallait tenir compte : du matériel du système d"exploitation du langage de programmation on passerait son temps à réinventer les mêmes algorithmes.Algorithme versus programme Un algorithme décrit une méthode générale de résolution d"un problème : que l"on pourra traduire dans n"imp ortequel langage de programmation que l"on pourra analyser p ouren dégager les ca ractéristiquesContre-exemples : tri spaghetti

12 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmesNécessité d"unmodèleAlan M. TuringMachine " de papier »

1912-1954 1936

La machine est dotée :

d"un ruban infini (?mémoire) d"une tête de lecture/écriture d"un automate (?processeur) Un modèle donc tourné vers les opérations de lecture/écriture (?affectation, calculs)

13 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmesLes questions "résolues" par Turing Qu"est-ce qu"un calcul effectué automatiquement?

Peut-on tout calculer?

Peut-on décider automatiquement si une formule logique est vraie?

10 ans avant les premiers ordinateurs!

Cf.Modèles de calculau semestre 6

14 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmesNotre modèle de machine Une machine est constituée d"un processeur, d"unemémoireet d"un

Mémoire

- infinie (mais un calcul donné utilise un espace fini), - types élémentaires (finis)int, float,...

Opérations

- nombre fini d"opérations (arithmétiques, booléennes...); - chaque opération a un nombre fini de paramètres

Processeur

- processeur unique; - effectue les opérations en temps constant (1 top = 1 opération)15 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmesLes questions traitées en Algo5 Est-ce que je peux construire un programme qui résout mon problème

(sur une machine conforme à mon modèle)?Spécificationdu p roblèmeet construction d"un algo rithme

Est-ce que l"exécution de mon programme sur la machine donne bien le résultat souhaité?Vérification de propriétés qualitatives partest et p reuve Est-ce que mon programme me fournit le résultat en un temps acceptable?Validation de propriétés quantitatives parmesure et analyse

16 / 41

Algorithmique et Analyse d"Algorithmes

Problèmes et algorithmesLes questions traitées en Algo5

Problème concret

Problème formaliséspécification

Algorithmeconstruction

Données

InstanceProgrammeProgrammation

SolutionExécutionCorrection

preuve testEfficacité analyse de complexitémesure

Exemple :plus court chemin

16 / 41

Algorithmique et Analyse d"Algorithmes

Coût d"un algorithmeEfficacité d"un algorithme Est-ce que mon programme consomme une quantitéacceptablede ressources pour fournir un résultat? Étant donnés deux programmes résolvant le même problème, lequel est le "meilleur"?Notion(s) de coût(s) coût en temps = nombre d"opérations permettant d"obtenir le résultat à partir des données coût en mémoire = nombre maximal de variables utilisées simultanément durant le calcul18 / 41

Algorithmique et Analyse d"Algorithmes

Coût d"un algorithmeExemple (1)

Maximum de 3 éléments

MAX(a,b,c)

Données :Trois éléments de même type (comparable)a,betc Résultat :Le plus grand des troism≥aetm≥betm≥cetm=a,boucifa>bm:=aelse m:=bifc>mm:=cReturn(m)Coût de l"algorithme

Coût temps?2 comparaisons+ 1 ou 2 affectations

Coût en espace mémoire?1 variable

Coût constant, indépendant des données19 / 41

Algorithmique et Analyse d"Algorithmes

Coût d"un algorithmeExemple (2)

Comptage d"un élément

OCCURRENCES(x,T)

Données :Un élémentxet un tableauTde taillen

Résultat :Le nombre d"occurrences dexdansT

k:=0

Coût en temps :ncomparaisons

Coût variable, dépend de latailledes données mais toujoursncomparaisons pour un tableau de taillen20 / 41

Algorithmique et Analyse d"Algorithmes

Coût d"un algorithmeExemple (3)

Maximum d"un tableau

MAXIMUM(T)

Données :Ttableau denéléments

Résultat :L"indice d"un élément maxi

max:=T[0] fori:=0ton-1ifT[i]≥maxi max:=i max:=T[i]

Traiter(max)Return(imax)Coût de l"algorithme

Modèle de coût?

pour T=[1,2,...,10]?10 pour T=[1,2,...,n]?n pour T=[n,1,2,...,n-1]?1 Dépend de latailledes donnéesDépend aussi de lavaleurdes Il s"exprime toujours en fonction de latailledes données Si trop de variation on cherche uneborne supérieure(pire cas)21 / 41

Algorithmique et Analyse d"Algorithmes

ComplexitéGénéralisation

Espace des donnéesAlgorithmeEspace des résultats

EntierEntiertailletemps

Caractériser l"efficacité générale de l"algorithme = trouver la relation entre la taille des donnéeset lecoût de l"algorithme sur un (modèle de) machine donnée Remarque : attention aux entiers, le temps de calcul dexndépend den qui n"est pas la taille de la donnée.23 / 41

Algorithmique et Analyse d"Algorithmes

ComplexitéCoût d"un algorithme

Coût (au pire)

Le coût d"un algorithmeAestfonctionde latailledes données : C

Suppose d"avoir fixé la notion de taille

Maximum = garantie quelles que soient les conditions d"utilisation

Concrètement :

majo rer le coût + e xhiberun cas défavo rableCoût au mieux C Correspond au cas le plus favorableQuel comportement privilégie-t-on?

24 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

MéthodologieCoûts des structures de base

Instructions en séquence

Le coût de

Faire Truc

Faire Machin

est la somme des coûts de Truc et de MachinComposition des coûts

Le coût d"une boucle est donc la somme

des coûts de chaque itérationInstructionsFOR, WHILE, REPEAT,...26 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

MéthodologieCoûts des structures de base (2)

Instructions conditionnelles

ifconditionFaire Truc else

Faire Machin

Coût del"unedes branches plus le coût d"évaluation de la conditionMajoration du coût Pour le coût au pire on peut donc prendre le maximum des coûts de chaque branche. +max{Cout(A),Cout(B)}InstructionsIF, SWITCH,...27 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

MéthodologieCoûts des structures de base (3)

Appel de procédure

Le coût de l"appel d"une procédure est :

le coût du corps de la procédure pour ses paramètres d"appel plus le coût de l"évaluation de ses paramètres.Méthode de calcul de coût Le calcul du coût d"un algorithme s"obtient donc encomposantles coûts assemblage et reconstruction méthode par composition se fait à laconception de l"algorithme28 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

MéthodologieExemple

Calcul de la somme des entiers de 1 àni := 1

somme := 0 somme := somme + i Coût d"une itération = 2 (additions)+ 1 test Coût de l"algorithme = 3n+1Niveau de détail judicieux?

29 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

Ordres de grandeurOrdres de grandeur

La complexité est une prédiction du temps d"exécution du programme codant l"algorithme. Mais ce temps dépend de l"architecture de la machine, donc c"est une abstraction (approximation) On s"intéresse au passage à l"échelle des algorithmes plus qu"à une mesure précise du temps d"exécutionCe qui est important c"est : 1. l"o rdrede gran deur; 2. de p ouvoircompa rerle salgo rithmesComplexité d"un algorithme On appellecomplexitéd"un algorithme une fonction de référence (logarithme, polynome, exponentielle...) comparable à son coût.31 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

moyenne des éléments d"un tableau de taillen ?complexité ennopérations

1/1000

es tri par insertion des éléments d"un tableau de taillen ?complexité enn2opérations 1/4 h

énumération des vecteurs de bits de taillen

?complexité en 2nopérations 10

300 000annéesObjectif : définir des ordres de grandeur comparables

Pour se donner une représentation concrète : sur un PC récent, environ 1 milliard d"opérations / seconde32 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

Ordres de grandeurBorne supérieure asymptotique NotationOPour une fonction donnéegon noteO(g)l"ensemble de fonctions :

On écritf=O(g)pourf? O(g).

On dit quegest une borne supérieure asymptotique pourf.Vite dit :f est dépassée par g à partir d"une certaine taille de donnéesPause courbes

Exemples

n=O(n3)1250n3=O(2n) n+⎷n=O(n)nlogn+n2=O(n2)33 / 41

Algorithmique et Analyse d"Algorithmes

Complexité

Ordres de grandeurÉchelles de comparaison(à connaître)

Deux propriétés utiles

Sif=O(g)alorsg+f=O(g)etk×f=O(g)Échelle polynomiale log(n) =O(n)Échelle exponentielle

Pour tousa>1 etp≥0 on anp=O(an)34 / 41

Algorithmique et Analyse d"Algorithmes

Un problème, plusieurs algorithmesProblème : trouver la star

Soit un groupe denpersonnes numé-

rotées de 1 àn.

Une personnei connaît jou bien elle

ne la connaît pas.Unesta rest une p ersonne: que tout le monde connaît mais qui ne connaît personne1 2 34567

Spécifions le problème :

Résultat :Si on renvoie un indice, c"est une star.

Sinon, il n"y a aucune star.

Postcondition

Données :L"entiern, " qui connaît qui »Modèle de coût : On comptera le nombre de questions "est-ce que i connaît j ?»36 / 41

Algorithmique et Analyse d"Algorithmes

Un problème, plusieurs algorithmesAlgorithme naïf naïf = lent mais assez simple pour se persuader qu"il est correct

STAR_NAIF(n)

fori:=1toni star:=true forj:=1tonifj?=i et j ne connaît pas ii star:=false (i est-elle connue de tous?) forj:=1tonifj?=i et i connaît ji star:=false (i connaît-elle quelqu"un?) ifistarReturn(i)Return(" pas de star »)Complexité enO(n2)37 / 41

Algorithmique et Analyse d"Algorithmes

Un problème, plusieurs algorithmesFaire mieux

Peut-on accélérer cet algorithme?

Factoriser les 2 bouclesforjen une seuleNon: on économise quelques compa raisons(entre indices) mais on ne

pose pas moins de questions.Remplacer les bouclesforpar des boucleswhileNon plus: on gagne quelques questions en général, mais d ansle pire des

cas on reste enO(n2).Mieux exploiter les réponses aux questions Oui

Éviter de poser deux fois la même question

Siiconnaîtj, alorsin"est pas une star38 / 41

Algorithmique et Analyse d"Algorithmes

Un problème, plusieurs algorithmesUne tentative Idée : suivre les liens " ... connaît ... ». 1 2 34567

Mais après...???

La priorité : résoudre le problème

Mieux vaut un algorithme :

lent mais correct que " optimisé » mais qui fait n"importe quoi...39 / 41

Algorithmique et Analyse d"Algorithmes

Un problème, plusieurs algorithmesReprenons calmement

Siine connaît pasj, alorsjn"est pas une starOn devrait donc pouvoir éliminer un candidat àch aquequestion .

STAR_EFFICACE(n)

i:=1//Candidat star j:=2//Prochain candidat à éliminer j:=j+1//Puis vérifier (comme avant) si iest bien une starComplexité enO(n)40 / 41

Algorithmique et Analyse d"Algorithmes

Un problème, plusieurs algorithmesConclusion

Un même

p roblème p eutêtre résolu pa rdes algo rithmes très

L"analyse de

complexité ... mais pas le seulLa prochaine fois schémas récursifs analyse du coût en moyenne tri rapide41 / 41quotesdbs_dbs28.pdfusesText_34

[PDF] taux de rendement production trp

[PDF] trp production definition

[PDF] taux de rendement de production

[PDF] calcul trp production

[PDF] trp calcul

[PDF] faire des statistiques sur excel 2010

[PDF] calculer les cotés d'un triangle rectangle avec les angles

[PDF] longueur mediane triangle equilateral

[PDF] calcul mental 5eme

[PDF] séquence mesure de longueur cm1

[PDF] grandeurs et mesures cm1

[PDF] calcule mentale rapide

[PDF] calcul mental cm1 ? imprimer

[PDF] fiches calcul mental cm2

[PDF] calcul mental cm1 pdf