Algorithme_pseudocode_paradigme.md 2.35 KB
Newer Older
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
1
#### Algorithmes
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
2

Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
3
4
  - Présentation succinte des aglorithmes
  - N'est pas une présentation exhaustive
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
5

Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
6
7
8
note: Mireille

Dans cette partie, nous ne détaillons que les procédures qui modifient
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
9
10
le modèle et ne présentons aucun algorithme lié aux fonctions permettant de
passer d'une représentation des données à une autre.
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
11

12

Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
13
---
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
14

Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
15
#### Recherche des chemins de longueur 3
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
16

Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
17
18
19
20
21
22
23
  - choix d'un point de départ `start`
  - initialisation d'une liste de liste qui contiendra les chemins de longueur 3 en
  ajoutant le point de départ à toutes les listes.
  - choix, pour chacune des listes un deuxième point de «passage» dans le
  parcours du graphe.
  - Tant qu'il reste des indices à remplir
    - on ajoute un élément non encore ajouté.
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
24

25
26
---

27
#### Tous les chemins de longueur 3
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
28

29
30
  - On applique la procédure précédente à tous les points de départs
  potentiels.
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
31

32
33
34
---

#### Chercher les cycles parmi les chemins de longueur 3
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
35

36
37
  - On parcourt la liste des chemins et on regarde si ce sont le dernier
  point est le même que le premier.
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
38

39
40
41
42
---

#### On cherche les élèves sans «demande»

43
44
  - Le problème ici est celui de la recherche «inverse» des clefs possédant
  une certaine valeur.
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
45

46
  - Autre méthode : on peut également exploiter la matrice d'adjacence
47

48
49
50
51
52
note: c'est même la recherche inverse des clefs n'étant pas dans l'ensemble
image.

---

53
#### Recherche des «binômes» qui se sont mutuellement choisis
54

55
56
  - Exploitation de la matrice d'adjacence (Symétrie par rapport à la
      diagonale de la matrice)
57

58
59
60
61
62
63
note: on n'est pas obligé de passer par une matrice

---

#### Simplification du graphe

64
65
66
67
68
69
70
  - on supprime les élèves qui sont dans des cycles de longueur 3
  - À partir d'une liste de binômes, on les compléte avec des
  élèves sans «demande»
    - On constitue ainsi de nouveaux groupes de 3.
    - On supprime ces groupe du graphe
  - On cherche tous les chemins de longueurs 3 réalisables dans le graphe
  simplifié
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
71
  - On termine du mieux que l'on peut (force brute, hasard, autre
72
      heuristique)
73

74
75
76
note: les cycles de longueur 3 peuvent être retirés car ils forment les
groupes cherchés

77
===
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
78

79
### Paradigme de programmation
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
80
81
82

Le projet est principalement de la programmation procédurale. Une évolution 
possible serait de traitrer le sociogramme (ou les groupes) comme un objet
Vincent-Xavier JUMEL's avatar
Vincent-Xavier JUMEL committed
83
et donc passer à de la programmation orientée objet.
84
85

note: Vx