Publié le
15
décembre
2017
dans les catégories :
informatique sciences
Un graphe est un objet mathématique qui permet, notamment, de représenter une communauté et ses interactions : par exemple, un groupe de profils Facebook avec les ajouts en ami, un ensemble de villes et les routes qui les relient entre elles, un ensemble de gènes et leurs liens de régulation, ... Il s'agit dans cet article d'introduire les définitions basiques portant sur les graphes pour résoudre un problème simple : étant donné des emplois du temps scolaires dans une école, compter le nombre de salles nécessaires à réserver pour que tous les cours soient mis en place. Le problème majeur est que plusieurs cours peuvent...
Publié le
16
décembre
2017
dans les catégories :
informatique sciences
Exercices de compréhension
Exercice 1 : Dites combien vaut chi(G) (le nombre chromatique de G) quand G a trois sommets 0, 1 et 2, et trois arêtes, une reliant 0 à 1, une reliant 1 à 2, et l'autre reliant 2 à 0.
Attention : on parle ici d'arêtes, donc le graphe est non orienté. On rappelle que chi(G) est le nombre minimal de couleurs nécessaire pour qu'il existe une coloration c telle que (P) : si les sommets i et les sommets j sont...
Publié le
17
février
2018
dans les catégories :
informatique sciences
La programmation est utilisée pour résoudre des problèmes. Ces derniers amènent souvent à analyser, lire, mémoriser des données. Nombre de ces petites opérations, qui effectuent des actions simples, basiques à l'échelle d'un algorithme, sont fréquemment utilisées. Pour réduire le temps de calcul (c'est-à-dire, le temps pour rendre un résultat) et l'espace en mémoire (le nombre d'informations à stocker pour faire les calculs), il est préférable de les organiser, selon le but à atteindre, dans un objet de type structure de données. Dans la majorité des langages, ces objets sont déjà implémentés (c'est-à-dire programmés) et...
Publié le
18
février
2018
dans les catégories :
informatique sciences
Exercice de programmation
En OCaml, les listes et les tableaux sont évidemment présents, et ces deux structures sont implémentées de façon différente (contrairement à Python, par exemple). (Re)programmez les primitives de ces deux structures de données : initialisation d'un objet sans données, suppression d'un élément à une position donnée (sans erreur, donc en particulier en vérifiant que l'objet contient effectivement au moins un élément !), ajout d'un élément à une position donnée, retour de la valeur Vrai (true en OCaml) d'un élément dans l'objet...