(+212) 616 374 790 contact@developpement-informatique.com
| Connexion
Analyse des algorithmes

Analyse des algorithmes - Opérations élémentaires et modèles de coût

23 Apr 2020 23 Apr 2020 8412 vues ESSADDOUKI Mostafa 6 min de lecture
Complexité algorithmique
1 Introduction à l'analyse des algorithmes 2 Notations asymptotiques 3 Opérations élémentaires et modèles de coût 4 Complexité temporelle et spatiale 5 Méthode de comptage des pas 6 Méthode de comptage des pas pour les boucles
Diviser pour régner & algorithmes de tri
7 Rappel sur l'approche récursive 8 Diviser pour régner 9 la recherche dichotomique 10 Tri par fusion 11 Tri rapide 12 Analyse des fonctions récursives
Les arbres binaires
13 Introduction aux arbres binaires 14 Définitions récursives des arbres 15 Propriétés des arbres binaires 16 Types d'arbre binaire 17 Parcours en profondeur des arbres binaires 18 Parcours en largeur des arbres binaires 19 Exercices corrigés sur les arbres - TD 1 20 Exercices corrigés sur les arbres - TD 2 21 Exercices corrigés sur les arbres - TD 3 22 DS - Arbres binaires de recherche équilibrés (AVL) 23 DS - Codage de Huffman - Compression de données
Algorithmes gloutons
24 Introduction aux algorithmes gloutons 25 Problème de la sélection d'activités 26 Problème de séquencement des tâches 27 Problème du Sac à Dos fraction
Programmation dynamique
28 Introduction à la programmation dynamique 29 Le concept de sous-structure optimale 30 Le concept de sous-problèmes superposés 31 Méthodes de la programmation dynamique 32 Différence entre la programmation dynamique, l'approche diviser pour régner, et les algorithmes gloutons 33 Calculer les nombres de catalan en C++ et Python 34 Calculer le coefficient binomial 35 Le nombre de façons pour construire un mur de dimension 4*N 36 Défi de conversion de mots 37 Décomposition de phrases à partir d'un dictionnaire 38 La collection de pièces dans un labyrinthe 39 Nombre de façons de regrouper les étudiants 40 Compter tous les chemins possibles dans une grille MxN
Méta heuristique
41 Algorithmes heuristiques et métaheuristiques 42 Algorithme de Recuit simulé 43 Algorithme Colonies de fourmis
Théorie des graphes
44 Introduction et notions fondamentales 45 Chemins, cycles et connexité 46 Représentations des graphes 47 Parcours de graphes 48 Algorithme de Dijkstra 49 Algorithme A* 50 Algorithme de Bellman-Ford 51 Algorithme Floyd-Warshall 52 Coloration des graphes
Base de données et SQL
53 Introduction au langage SQL 54 Concepts de base de SGBDR 55 Syntaxes de différentes instructions SQL 56 Création et suppression d'une base de données 57 Opérateurs SQL 58 Les contraintes en SQL 59 Création et suppression des tables en SQL 60 Insertion et modifications des enregistrements 61 Extraction des données - SELECT 62 Filtrer les données - WHERE 63 Recherche de motifs - LIKE 64 Trier les données - ORDER BY 65 Les jointures en SQL - JOIN 66 Fonctions d'agrégation en SQL - SUM, COUNT, AVG, MIN et MAX 67 Organiser des données identiques en groupes - GROUP BY et HAVING 68 Les sous-requêtes en SQL 69 Les fonctions SQL de manipulation de date 70 DS - langage SQL 71 Exercices corrigés de langage SQL
Introduction à l'intelligence artificielle
Introduction à la théorie des jeux
Préparation aux concours
72 Réseau de distribution d'eau 73 Arbre d'expression arithmétique 74 Exploration d'une grotte souterraine

Opérations élémentaires et modèles de coût

Définition des opérations élémentaires

On appelle opérations élémentaires les opérations suivantes :

  • Un accès mémoire pour lire ou écrire la valeur d'une variable ou d'une case d'un tableau ;
  • Une opération arithmétique entre entiers ou réels telle que l'addition, soustraction, multiplication, division ou calcul du reste d'une division entière ;
  • Une comparaison entre deux entiers ou réels.

  Exemple

L'instruction \(c = a + b\) nécessite les quatre opérations élémentaires suivantes :

  • Un accès mémoire pour la lecture de la valeur de a,
  • Un accès mémoire pour la lecture de la valeur de b,
  • Une addition de a et b,
  • Un accès mémoire pour l'écriture de la nouvelle valeur de c.

Pourquoi définir des opérations élémentaires ?

Nous voulons souvent raisonner sur le temps d'exécution d'une manière qui ne dépend que de l'algorithme et de son entrée. Ceci peut être réalisé en choisissant une opération élémentaire, que l'algorithme effectue à plusieurs reprises, et en définissant la complexité temporelle \(T(n)\) comme le nombre de ces opérations que l'algorithme effectue étant donné un jeu de données de longueur n.

En général, une opération élémentaire doit avoir deux propriétés :

  • Aucune autre opération ne peut être effectuée plus fréquemment au fur et à mesure que la taille de l'entrée augmente.
  • Le temps nécessaire à l'exécution d'une opération élémentaire doit être constant : il ne doit pas augmenter au fur et à mesure que la taille de l'entrée augmente. C'est ce que l'on appelle le coût unitaire.

Coût unitaire vs coût en bits

Le coût unitaire et le coût en bits sont deux fonctions de coût différentes utilisées pour calculer la complexité en termes de l'espace et du temps.

Coût unitaire

Le coût unitaire est utilisé dans un modèle simplifié où un nombre, de n'importe quelle taille, tient dans une case (ou cellule) de mémoire et où les opérations arithmétiques standard prennent un temps constant.

Coût en bits

Avec un coût en bits, nous prenons en compte que les calculs avec de plus grands nombres peuvent être plus coûteux.

Remarque Le coût unitaire fonctionne souvent bien dans la pratique car les processeurs modernes peuvent effectuer des calculs sur des nombres entiers 64 bits et à virgule flottante en temps constant.

Exemple de coût unitaire

   
Addition de nombres Python
def addition(x, y):  # x et y sont des valeurs numériques
    return x + y

Dans cet exemple simple, il est judicieux d'utiliser le coût unitaire et de dire que la fonction s'exécute en temps constant.

Exemple de coût en bits

   
Concaténation de chaînes Python
def concatener(x, y):  # x et y sont des chaines de caractères ou tableaux
    return x + y

Ici, ce serait une erreur d'utiliser le coût unitaire pour l'opération + : pour concaténer deux chaînes de caractères, il faut allouer une nouvelle mémoire et copier les caractères.

Dans ce cas, il est préférable d'utiliser le coût en bits pour l'opération + :

  • La longueur des chaînes est utilisée pour mesurer la taille de l'entrée,
  • Et nous disons que la fonction fonctionne en temps \(\Theta(|x| + |y|)\).
Remarque Notez que nous utilisons toujours les coûts unitaires pour les opérations sur les caractères. Cela est parfaitement logique car les caractères peuvent être représentés par de petits entiers de taille fixe.

Comparaison des deux modèles

CritèreCoût unitaireCoût en bits
PrincipeChaque opération élémentaire a un coût constantLe coût dépend de la taille des données manipulées
Utilisation typiqueNombres entiers, réels, booléensChaînes de caractères, grands nombres, tableaux
ComplexitéComptage du nombre d'opérationsComptage proportionnel à la taille des données
ExempleAddition de deux entiers : \(O(1)\)Concaténation de chaînes : \(O(|x| + |y|)\)

Autres exemples illustratifs

  Exemple 1 : Calcul de la somme d'un tableau

   
Somme d'un tableau Python
def somme_tableau(T):
    s = 0
    for x in T:
        s = s + x
    return s

Analyse de complexité :

  • Opération élémentaire choisie : l'addition
  • Nombre d'additions : \(n\) (où \(n\) est la taille du tableau)
  • Complexité : \(O(n)\)

  Exemple 2 : Recherche d'un élément dans un tableau

   
Recherche linéaire Python
def recherche(T, x):
    for i in range(len(T)):
        if T[i] == x:
            return i
    return -1

Analyse de complexité :

  • Opération élémentaire choisie : la comparaison
  • Nombre de comparaisons : au plus \(n\)
  • Complexité : \(O(n)\)
Points clés à retenir
  • Les opérations élémentaires sont les briques de base pour mesurer la complexité (accès mémoire, opérations arithmétiques, comparaisons).
  • Le coût unitaire suppose que chaque opération élémentaire prend un temps constant, quel que soit l'opérande.
  • Le coût en bits prend en compte la taille des données (utile pour les chaînes, grands nombres, etc.).
  • Le choix du modèle de coût dépend du type de données manipulées par l'algorithme.
  • La complexité temporelle \(T(n)\) est exprimée en nombre d'opérations élémentaires (coût unitaire) ou en fonction de la taille des données (coût en bits).

Sortie
// La sortie apparaîtra ici…
Prêt · Ctrl+Entrée pour exécuter
Complexité Opération élémentaire Coût unitaire Coût en bits Modèle de coût Complexité temporelle Temps constant

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.