Place aux permutations ! – Blog Maths Discrètes 2021

Maintenant... Place aux permutations !!!

Quelle est la seconde appellation de l'algorithme de Heap ?

Par insertion

Bottom-up

Par sous-permutations

Qu'est ce qu'un polyèdre connexe ?

Une figure connexe ayant des faces différentes et le même degré sur ses sommets

Une figure connexe ayant les même faces et des degrés différents sur ses sommets

Une figure connexe ayant les même faces et le même degré sur ses sommets

Quelle est la formule donnant le nombre de permutations ?

exp(n)

n!

n^n

Combien de sommets possède un permutoèdre d'ordre 6 ?

36

715

720

216

Que se passe-t-il si l'ensemble S ne contient qu'un seul élément ?

Les algorithmes ne font rien

L'élément s'échange avec "lui-même"

Fin de l'exécution, le programme renvoie l'ensemble inchangé

Quelle est la différence entre l'algorithme SJT et les algorithmes de Heap et Bottom-up ?

Il n'y aucune différence.

Il y a des "pointeurs" allant à gauche et à droite.

Il utilise le principe de minimisation des échanges.

Quelle est la particularité de l'algorithme de Heap ?

Le principe de minimisation des échanges

Les échanges basés sur la parité

Les échanges alternatifs allant de gauche à droite et droite à gauche

Quelle est la complexité de l'algorithme de Bottom-up ?

O(n-1)

O(n-1!)

O(n!)

O(n^n)

Exécutez l'algorithme de Heap sur l'ensemble {7,8,9}.

{8,7,9}

{7,9,8}

{9,8,7}

{7,8,9}

{8,9,7}