# Présentation 05/02
###### tags: `présentation`
[TOC]
## Introduction (salsa)
On utilise souvent les graphes dans notre vie sans s’en rendre compte, comme pour faire un plan de table, dessiner une figure géométrique.
Nous aborderons la notion de graphe et plus précisément les graphes orientés. Mais avant cela nous allons revenir quelques années auparavant pour découvrir quelques trois grandes personnalités importantes qui furent la source mère de cette pensée.
### Personnages importants

### Euler
Le père de la théorie des graphes se prénomme Leonhard Euler. Né en 1707 à Bâle en Suisse, il décède en 1783. Il fut mathématicien et physicien.
Le premier article scientifique moderne sur la théorie des graphes fut écrit par Leonhard Euler, présenté à l’académie de Saint-Pétersbourg en 1735, et publié en 1741.
Il traitait du cas des sept ponts de Königsberg :
- Le principe est simple. C’est d'effectuer un chemin en passant par chacune des arêtes. Ce qu’on appelle aujourd’hui un chemin eulérien, et de cycle eulérien si l’on revient à l'arête de départ.
- Ainsi il pose sa théorie, qui est la suivante : “pour que l’on puisse passer par chacun des ces arcs, il faudrait que ces sommets aient un nombre d’arêtes entrantes et sortante pair.” Il est considéré comme le père de cette science car il est le premier à y apporter un regard mathématique.
### Al-Adli (Hugo)

Al-Adli fut un joueur d’echec et théoricien arabe du IXème siècle.
Il s’intéressa au problème suivant : “Peut on, avec un cavalier, passer par chacune des cases d’un échiquier ?”
Ce qui sera un problème souvent étudié aussi au XVIIIème siècle.

### Arthur Cayley
Mathématicien britannique de la fin du XIXème siècle. Il travaillera sur le sujet des arbres en théorie des graphes : C’est un type de graphes particuliers, car acyclique. On ne peut pas faire demi tour sans faire le chemin inverse.
Prenons le cas d’un arbre de 1 à 4 sommets : Une autre problématique souvent étudiée est celle de la coloration de graphe.
Le but étant de déterminer le nombre de couleur qu’il faudra pour colorier chacun des sommets sans que deux sommets voisins aient la même couleur.
Ce problème fut énoncé par Francs Guthrie qui voulait savoir si on pouvait colorier toutes cartes avec seulement 4 couleurs. De nombreuses questions sont régulièrement soulevé dans ce domaine.

### Rappels théoriques (Amandine)
#### Mais que signifie le terme graphe ?
- Un graphe est un ensemble d’objets appelés sommets qui sont mis en relation. Il existe plusieurs types
de graphes, ceux qui nous intéressent ici sont les graphes orientés.

- Dans un graphe orienté les sommets sont reliés entre eux par des arcs, de manière asymétrique, ce qui signifie que ces arcs ne sont empruntables que dans un seul sens. Les arcs arrivant vers un sommet sont appelé Arcs Entrants et les arcs sortants d’un sommet et dirigés vers un autre sont appelés Arcs Sortants.
Un graphe orienté est représenté sous forme de diagramme où des ensembles de points représentant les sommets sont joints entre eux par des flèches.
- Dans un graphe nous avons le concept de sous graphe partiel qui est un sous-ensemble de sommets d’un graphe nommé G. C’est-à-dire un nouveau graphe formé de certains sommets sélectionnés, des arcs reliant ces sommets, ainsi que d’arcs qui sont également choisis.

Nous pouvons voir différentes notions qui interagissent avec un graphe orienté :
- Une matrice est un tableau de nombres utilisé en algèbre linéaire sur laquelle des opérations peuvent
être réalisées.
- Pour un graphe de N sommets, une matrice d’adjacence est une matrice de taille N*N dans laquelle sont listés, sommet par sommet, les arcs sortants de ceux-ci. Si aucun arc ne sort d’un sommet, sa valeur sera mise à 0, et à 1 dans le cas contraire. Une matrice d’adjacence est unique à chaque graphe.

- Le terme de voisins est peu utilisé dans le cas de graphes orientés, on parle alors de prédécesseurs ou successeurs. Les prédécesseurs d’un sommet A sont les sommets depuis lesquels les arcs entrant de A partent. Les successeurs de ce même sommet sont ceux vers lesquels les arcs sortants de A sont dirigés.

### Exemples d'utilisations (Alexandre)
Le système de graphe orienté est retrouvé dans plusieurs applications, par exemple :
- La planification d’une chaîne logistique de production :
Un acheminement du produit selon son point de départ au stockage puis à la livraison. Ceci inclut la gestion de plusieurs type de flux comme le flux physique ( transport de matières ), flux financier et le flux d'informations (échange de données).
- Le réseaux de transport :
Le skieur : un trajet optimisé d’un skieur, selon son point départ et le point d’arrivé voulu. En prenant en compte le souhait des couleurs des pistes, les pistes fermés et à risque. Tout cela selon la carte de station.
Les transports ferroviaires : insertion de la position de départ ainsi que la destination, pour rechercher ainsi un chemin optimal.

Dans ce genre d’application, une base de données orientée graphe est importante. Ceci est un type de base de donnée utilisant la théorie des graphes pour stocker, et interroger des relations. Plus théoriquement, c’est un système de stockage capable de fournir une adjacence entre éléments voisins.
L’orientation d’un graphe est primordiale dans ce genre d’application, car on ne peut faire un parcours dans les deux sens.

### Description du Sujet (Camille)
L’interface de notre projet doit donc permettre à un utilisateur de créer des graphes orientés à la main ou bien par matrice d'adjacence. Il sera égalemment possible de demander à l’application de créer un nombre de graphes aléatoires. Les arcs et sommets de chaque graphe auront un nom et une valeur ainsi que, pour les sommets, des coordonnés en plus.

Des sous-graphes partiels pourront être créés par l’utilisateur au moyen d’une sélection de sommets. Ce dernier pourra également modifier les graphes créés ainsi que les sous-graphes sélectionnés en ajoutant, supprimant ou déplaçant des sommets et liaisons. De plus, un graphe pourra prendre la valeur d’un sous-graphe. Tous les graphes seront représentés dans le code sous forme de matrice d’adjacence, nous permettant notamment d’identifier les voisins de chaque sommet.

## Planning (Sébastien)
La plannification du projet est effectué à l'aide de l'outils Gantt Project, elle se fait au travers de plusieurs diagrammes tels que le diagramme des tâches et le diagramme des ressources.
Le diagramme de Gantt apporte la clarté, une vue d'ensemble simplifiée, une information sur la performance, une amélioration de la gestion du temps et une flexibilité.
Le planning peut être amené à changer afin de spécifier des tâche, ajouter des tâches, affecter des ressources à une tâches. Dans notre cas le planning s'étale du 29 Janvier 2020 au 11 Mars 2020. Il sera étoffé par la suite avec les autres sections comme le rendu du cahier des charges, les spécifications du projet, le compte rendu et enfin la soutenance et la démonstration.

- Diagramme des tâches
Ce diagramme est très complets, en effet il permet d'organiser les différentes tâches d'un projet en fonction de leurs dates de début et de fin. Certaines tâches peuvent être éventuellement superposées et d'autres sont précédées par certaines, cela implique que les des tâches ne sont pas censées débuter avant que la ou les tâches précédentes soient finies.
Le diagramme de la partie cahier des charges est décomposé en 6 sous parties qui représentes les sous parties du modèle Volere, les présentations du mercredi matin sont toujours précédées par le travail de la semaine.

- Diagramme des ressources
Ce diagramme de gestion de ressources permet de visualiser les ressources humaines attachées à différentes tâches, si certaines ressources sont sous employées ou bien si elles sont attribuées à plusieurs tâches à la fois.

- Diagramme de PERT ou PDM (Méthode de diagramme des prédécesseurs)
Ce diagramme identifie les chemins critiques, c'est à dire qu'il identifie le temps de réalisations estimé le plus long, il calcul donc la temps de fin au plus tard, fin au plus tôt. Il est la plupart du temps constitué de quatre éléments:
- Le nom de la tâche
- La date de début de la tâche
- La date de fin de la tâche
- La durée de la tâche

### Semaine du 30 janvier au 5 février (Slide)

- Planning
- Recherches
- Méthodologie

### Semaine du 6 au 12 février

- Objet du projet
- Définition des clients et des parties prenantes
- Utilisateurs finaux du produit

### Semaine du 13 au 19 février

- Contraintes obligatoires
- Conventions de normes et définition
- Organigramme
- Faits et hypothèses déterminants

### Semaine du 20 au 26 février

- Périmètres de l'oeuvre
- Périmètre de l'ouvrage
- Exigences sur les fonctions et les données

### Semaine du 27 février au 5 mars

- Exigences d'interface utilisateur
- Exigences d'utilisabilité
- Exigences de performances
- Exigences opérationnelles
- Exigences de mainteabilité et de support
- Exigences de sécurité
- Exigences culturelles, politiques et légales

### Semaine du 6 au 11 mars

- Questions ouvertes
- Solutions sur étagère
- Problèmes nouveaux
- Tâches
- Finalisation
- Risques
- Coûts
- Documentation utilisateur, formation
- Questions mises en attente
- Idées de solutions

## Organisation interne (Théo)

- **Mercredi après-midi** physiquement à la BU.
- **Mardi** soir via *discord* pour faire le point des avancées de la semaine.
- **Week end**, par plus petits groupes via Discord ou physiquement.

## Méthodologie de travail

Dans un premier temps nous avons fait des recherches sur les différentes méthodologies de travail existantes pour la réalisation d'un projet. Les deux plus grosses méthodologies que nous avons trouvés sont :

- La méthode classique, dite en cascade
- La méthode agile

Nous avons choisis la 1ère car la méthode agile ne nous as pas semblé adapté à l'organisation du travail imposée.

### Recherche sur le cahier des charges Volere
Nous avons trouvé un modèle de cahier des charges sur le site *volere.co.uk*.

#### Definir la stratégie d'élaboration du cahier des charges (Guillaume)
Se calquer, après adaptation, sur le modèle du cahier des charges volère.

#### Déterminer les techniques de gestion des exigences
Gestion des exigences par fiche (diapo 10 du modèle).
Toutes les fiches d'exigences seraient stockées en interne et seule les plus importante serait présente dans le cahier des charges.

#### Grille de cadrage (Switch Guillaume/Théo)

- Qui est à l’origine de la demande ? (Théo)
La professeure : Kloul Leila (Guillaume)
- Qu’est-ce qui motive la demande ? (Guillaume)
La demande est motivée par le cadre universitaire et nous avons choisis ce sujet car les graphes touchent de très nombreux domaines et sont très utilisés dans l'industrie car cela permet de modéliser toutes sortes de problèmes et les relations entre les elements du problème. (Théo)

- Que veut-on obtenir ? (Théo)
Un package facilement réutilisable pour tout type d'application contenant des graphes dont le formalisme peut être soit une matrice d'adjacence soit un listing des voisins (prédécesseur(s)/successeur(s). (Guillaume)
- Comment saura-t-on que l’objectif est atteint ?(Définir les métriques)(Guillaume)
L'objectif sera atteint lorsque le package répondra positif aux test techniques que nous définirons.(Théo)
- Quels sont les bénéfices attendus ?(Théo)
Permettre de manipuler aisèment les graphes orientés et avoir package relativement simple à installer et utiliser.(Guillaume)
- Qui va l'utiliser/exploiter ?(Guillaume)
Son exploitation tout comme son utilisation vont être, dans un premier temps, très limité à cause du cadre qui est celui d'un projet de fin d'étude. Puis potentielement plus tard par nous si d'autres projets personnels ou professionnels nous mènent à manipuler des graphes orientés.(Théo)
- Que veut-on inclure, exclure, avec quelles contraintes ?(Théo)
Contraintes : puissance du CPU et possiblement la mémoire vive.
Inclure : Des fonctions de manipulations de graphes simple (ajout/suppression d'un noeud/arête, création de plusieurs graphes),
Exclure : Graphes trop grand ???(Guillaume)

- Quelles fonctions veut-on décrire ?(Guillaume)
1. un mécanisme de création d’un nombre arbitraire de graphes
2. des primitives de manipulations sur le graphe global
3. des procédures de gestion de la séléction de sommets
4. des primitives de manipulations de graphes restreints(Théo)

- Quel est l’objectif du cahier des charges ?(Théo)
Il a pour objectif de présenter le sujet de notre projet et sa problématique ainsi que la façon dont nous allons répondre à la problématique.(Guillaume)
- Quel est la portée du système ?(Guillaume)
Sa portée première est le cercle universitaire mais elle pourrait par la suite servir à d'autres ou à nous même.
- Qui a interêt à quoi ? Avec quels pouvoirs ?
Notre interêt pour ce projet est l'expérience qu'il nous apportera. Nous avons le pouvoir de déterminer la manière de réaliser le projet. Et la professeure a le pouvoir d'orienter le projet.

### Les outils utilisés
- Discord : Pour les réunions en vocal
- Git/Github : Pour le partage de fichiers
- Gantt Project : Pour créer un diagramme de Gantt et gérer le planning.
- Hackmd : Pour rédiger les documents à plusieurs.