Examen 1 - Algorithmique Flashcards

1
Q

2 grands types d’algorithme de recherche

A

Recherche linéaire (glouton)
Recherche dichotomique (diviser pour régner)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Quelle condition doit-on respecter avant de procéder à une recherche
dichotomique ?

A

Trier tableau/liste

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

C’est un critère de performance très important !

A

le nombre de comparaisons effectuées

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Algorithmes de tri lent

A

 Tri par sélection
 Tri par insertion
 Tri à bulles
 Etc.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Algorithmes de tri rapides

A

 Tri fusion
 Tri rapide
 Etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

On utilise le mot « complexité » algorithmique pour désigner…

A

l’efficacité d’un algorithme et non le fait qu’il comporte une
implémentation complexe (ou compliquée)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Il existe 2 sortes des complexités algorithmiques :

A

1) De temps
2) D’espace

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

expliquer complexité de temps

A

Nombre d’opérations élémentaires effectuées par un
algorithme

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

expliquer complexité d’espace

A

Nombre d’espace physique (essentiellement de la mémoire)
occupé par l’algorithme

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

la complexité est relative à notre contexte Exemple : Sur une plateforme qui offre peu de mémoire, les
algorithmes seront plus complexes que s’ils roulent sur des
plateformes offrant de grande possibilités physiques.

A

Solution : Utiliser un algorithme moins gourmand en espace
mémoire mais plus complexe (plus long) en temps !

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Opérations élémentaires à surveiller pour complexité temps :

A

 Comparaison
 Affectation
 Opérations arithmétiques

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Tri par sélection

A

Étapes de l’algorithme

Initialisation : La liste entière est considérée comme non triée.
Recherche du minimum :
    Parcourir la partie non triée pour trouver l'élément le plus petit.
    Mémoriser l'indice de cet élément.
Échange :
    Échanger le plus petit élément trouvé avec le premier élément de la partie non triée.
Mise à jour :
    Agrandir la partie triée en incluant le nouvel élément échangé.
    Réduire la partie non triée en conséquence.
Répétition :
    Répéter les étapes 2 à 4 jusqu'à ce que toute la liste soit triée. Avantages :

Simple à comprendre et à implémenter
Performant pour de petites listes
Nombre d'échanges limité (au maximum n-1)

Inconvénients :

Inefficace pour de grandes collections de données
Toujours en O(n²), même si la liste est déjà triée
Non stable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

On dénote la complexité d’un algorithme avec le symbole…

A

“O”
O(n 2 ) Complexité quadratique
O(n) Complexité linéaire
O(n*log(n)) Complexité linéarithmique
O(log(n)) Complexité logarithmique

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Tri-Fusion

A

Le tri fusion fonctionne en trois étapes principales :

Diviser : Séparer la liste en deux moitiés à peu près égales.
Régner : Trier récursivement chaque moitié.
Combiner : Fusionner les deux moitiés triées en une seule liste triée.

Algorithme détaillé

Si la liste contient 0 ou 1 élément, elle est déjà triée. Sinon :
Diviser la liste en deux sous-listes de tailles égales (ou presque).
Appliquer récursivement le tri fusion sur chaque sous-liste.
Fusionner les deux sous-listes triées pour obtenir la liste finale triée.

Étape de fusion
La fusion est l’étape clé qui donne son efficacité à l’algorithme :

Comparer les éléments en tête de chaque sous-liste.
Sélectionner le plus petit et l'ajouter à la liste fusionnée.
Répéter jusqu'à ce que tous les éléments soient traités. O(n log n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Algorithmes de recherche

A

Recherche séquentielle / linéaire (glouton)

Parcourt les éléments un par un jusqu'à trouver celui recherché
Complexité : O(n) dans le pire cas
Simple à implémenter mais inefficace sur de grandes collections O(n) Complexité linéaire

Recherche dichotomique

S'applique sur des données triées
Divise l'espace de recherche par 2 à chaque étape
Complexité : O(log n)
Très efficace sur de grandes collections triées O(log(n)) Complexité logarithmique
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Bubble sort

A

Algorithme détaillé

Parcourir la liste du premier au dernier élément.
Pour chaque paire d'éléments adjacents (i, i+1) :
    Si l'élément i est plus grand que l'élément i+1, les échanger.
Répéter les étapes 1 et 2 jusqu'à ce qu'aucun échange ne soit effectué lors d'un parcours complet.

Complexité

Temporelle : O(n²) dans le pire et le cas moyen, O(n) dans le meilleur cas (liste déjà triée)
17
Q

Tri rapide

A

Algorithme détaillé

Choisir un élément pivot dans la liste (souvent le dernier élément).
Partitionner la liste :
    Placer tous les éléments inférieurs au pivot à sa gauche.
    Placer tous les éléments supérieurs au pivot à sa droite.
Récursivement appliquer les étapes 1 et 2 aux sous-listes à gauche et à droite du pivot. Optimisations courantes

Choix du pivot : utiliser la médiane de trois éléments (premier, milieu, dernier) pour éviter le pire cas sur des listes déjà triées.
18
Q

qu’est ce qui impact complexité algorithme ?

A

le nb de comparaisons, affectations et opérations mathématiques

19
Q
A