Catégories
Matrices Permutations Programmation Représentations

Rangement de matrices carrées dans une table à une dimension

Introduction

De façon classique, pour linéariser une matrice de n x n, on utilise une formule telle que :

indice(x, y) x + y * n

et inversement, coordonnées(i) { i mod n, i div n }

Avec mod : le modulo, et div la division entière, qui utilise le fait que la division euclidienne est une bijection entre les entiers positifs ou nuls et les couples d’entiers positifs ou nuls.

Par exemple, pour matrice de 3 x 3, les indices dans la table linéaire peuvent être :

Figure 1

Tout dépend des choix, ligne/colonnes, sens droite/gauche, haut bas, etc. Mais cela dépend essentiellement de la taille de la matrice :

Figure 2

Pour la taille 4 x 4, avec les mêmes choix d’orientation, seules 3 cases gardent la même place.

Le problème est donc : si la matrice grandit la version linéaire de la matrice est à recalculer.

Proposition

Figure 3

Dans le cas de matrices carrées pouvant être amenée à grandir, par exemple si celles-ci représentent les matrices d’incidence de graphes auxquels on ajoute de nouveaux sommets, je propose une numérotation « incrémentale » ne changeant pas les indices si la matrice croît.

Numérotation triangulaire

Figure 4

La numérotation triangulaire est une bijection possible, mais elle laisse des trous. Par exemple dans la matrice de 2 x 2, l’indice 3 n’est pas utilisé, et c’est de pire en pire en augmentant la taille.

Méthode de rangement

On propose de générer les indices en partant d’un carré de 1, puis en ajoutant une ‘couche’ de 2n + 1 éléments à chaque incrémentation de n. Les couches sont représentées par les couleurs dans la figure 3.

Nommons indices, les indices i de la forme linéaire, et coordonnées les couples (x, y) donnant la position dans la forme matricielle.

On s’arrange pour que :

1/ Si les coordonnées x et y varient de 0 à n – 1, alors les indices i correspondants varient de 0 à n² -1.

2/ Le plus grand indice dans un carré de n corresponde au plus grand couple de coordonnées.

Donc, les indices des éléments de la diagonale principale, de coordonnées (x, y) avec x === y, valent (x + 1)² – 1. Ce qui donne la suite : 0, 3, 8, 15…

3/ On garantit que si x et y sont tous deux inférieurs à n, l’indice de (x, y) sera inférieur à .

4/ Et enfin, on garantit que tous les indices déterminés au niveau du carré de n seront toujours valables dans un carré de n+1, et récursivement en partant de n = 1.

Notation

Il faut choisir une orientation pour représenter les figures, la voici :

Figure 5

Les lignes sont numérotées x et les colonnes y. Le gnomon du carré est décomposé en trois parties : la diagonale de surface 1, notée avec son indice n² – 1, la partie rouge avec y = n – 1 qu’on peut nommer le gnomon de y, et le gnomon de x, en vert, avec x = n – 1.

Implémentation

Sous forme de fonctions :

function index(x, y) {
	if (x === y) {
		return (x + 1) * (x + 1) - 1;
	}
	// retrouver le plus petit carré contenant (x, y)
	n = Math.max(x, y);
	if (x > y) {
		// on est dans le gnomon de x
		return n * n + 2 * y;
	}
	// sinon, y > x
	return n * n + 1 + 2 * x;
}

function coordonnées(i) {
	// retrouver n
	let r = Math.sqrt(i + 1);
	if (Number.isInteger(r)) {
		// on est sur la diagonale
		return { x: r - 1, y: r - 1 };
	}
	let n = Math.floor(r);
	let k = i - n * n;
	if (k & 1) {
		// impair : gnomon de y
		return { x: (k - 1) / 2, y: n};
	}
	// pair : gnomon de x
	return { x: n, y: k / 2};
}

Si on préfère on peut aussi utiliser une mémo-fonction pour établir les correspondances. On doit choisir entre temps de calcul ou utilisation de mémoire selon les cas.

function index(x, y) {
	if (x === y) {
		// on est dans la diagonale 
		return (x + 1) * (x + 1) - 1;
	}
	if (x > y) {
		// on est dans le gnomon de x
		return x * x + 2 * y;
	}
	// sinon, y > x, on est dans le gnomon de y
	return y * y + 1 + 2 * x;
}

Bien sûr on peut simplifier la fonction index comme ci-dessus. On n’est pas obligés de calculer n.

x\y

0

1

2

3

4

5

6

7

8

9

10

0

0

2

5

10

17

26

37

50

65

82

101

1

1

3

7

12

19

28

39

52

67

84

103

2

4

6

8

14

21

30

41

54

69

86

105

3

9

11

13

15

23

32

43

56

71

88

107

4

16

18

20

22

24

34

45

58

73

90

109

5

25

27

29

31

33

35

47

60

75

92

111

6

36

38

40

42

44

46

48

62

77

94

113

7

49

51

53

55

57

59

61

63

79

96

115

8

64

66

68

70

72

74

76

78

80

98

117

9

81

83

85

87

89

91

93

95

97

99

119

10

100

102

104

106

108

110

112

114

116

118

120

Tableau 1 : Les index placés à leur coordonnées pour n = 11.

 

Catégories
Graphisme Musique Programmation Synthèse sonore

Sonographe parallèle

Pour les nostalgiques de Phonogramme et Sonographe, je vous présente une page web permettant de dessiner des sons, de les écouter et les enregistrer.

https://www.cyclonium.com/atelier/synthese/sonographeParallele.html

C’est une préfiguration de ce que pourrait être un ‘SoundPaint’ dans une page web. Pour l’instant, c’est une maquette, en développement, mais elle permet déjà de dessiner et écouter, quasiment en temps réel.

En fait, il faut environ 2 secondes pour calculer 30 secondes de son, grâce à notre bibliothèque de calcul parallèle basée sur WebGL (Paradigma).

La touche F12 remplace la documentation, il faut juste lire le code.

Sonographe parallèle
https://www.cyclonium.com/atelier/synthese/sonographeParallele.html

Catégories
Mathématiques Nombres Programmation

Représentation de Rationnels à partir des BigInt

Une page d’expérimentation sur les fractions, représentées par un couple de grands entiers, maintenant accessibles en JavaScript sous le nom de BigInt.

 

https://www.cyclonium.com/atelier/nombres/fromTheBigInt.html

Catégories
Animation Graphisme Jeux Programmation

Constellations de Ian Snyder

Constellations est un jeu, un puzzle, inventé par Ian Snyder et programmé par lui-même en HTML 5 dans un « canvas » 2D.

Il s’agit de résoudre les puzzles en manipulant des élastiques accrochés à des punaises : pour le faire il suffit de reproduire le schéma linéaire des tensions, accroches et croisements proposé en haut de l’écran.

Le niveau que vous avez atteint est stocké dans le « localStorage » du navigateur de sorte que si vous revenez sur la page, les puzzles résolus ne seront proposés qu’en utilisant le bouton « back » en bas à gauche. Le bouton « skip » permet d’abandonner un puzzle pour s’attaquer au suivant.

Pour les sons, Ian Snyder utilise la bibliothèque « howler.js » (https://howlerjs.com/) développée par James Simpson. C’est dommage qu’il utilise une ancienne version de la bibliothèque, car les règles ont changé depuis 2018 : on ne peut plus utiliser l’API Audio avant que l’utilisateur n’ait interagit avec la page. Du coup, on risque de ne pas avoir de sons. (pour remédier au problème, il faut remplacer le fichier * howler.js v2.0.3 ) par le fichier * howler.js v2.2.0) Dans la console de développement sous Google Chrome (touche F12) on peut lire le message :

The AudioContext was not allowed to start. It must be resumed (or created) after a user gesture on the page. https://goo.gl/7K7WLu
setupAudioContext @ howler.js:2133

Références

Lien vers une version sonore : https://www.cyclonium.com/ianestailleurs/constellations/

Jouer à Constellations : http://ianiselsewhere.com/constellations/

Voir le site de Ian Snyder : http://iansnyder.games/

L’article de « Libération » sur le sujet : https://www.liberation.fr/futurs/2018/03/26/constellations-la-musique-de-l-elastique_1638964

Note pour les programmeurs JavaScript

À noter dans le code, au hasard des lignes, pour choisir un son au hasard parmi 9 disponibles, Ian Snyder utilise la formule compacte :

1+((Math.random()*9)|0)

au lieu d’un plus clasique 1+Math.floor(Math.random()*9)

L’explication est qu’en JavaScript, l’opérateur « | » (ou inclusif binaire) n’opère que sur des entiers. Le résultat de (Math.random()*9) est donc tronqué à sa partie entière avant de passer par le « ou » avec zéro, qui évidemment conserve les bits en l’état. L’écriture est plus courte et on évite un appel de fonction.

Catégories
Algorithmes de jeu Jeux Pavages

L’envers du Tricérata

Le document suivant explique comment le jeu de Tricérata à été inventé et programmé. Cliquez sur l’image pour lire la suite;

L'échiquier du Tricérata
Numérotation des cases

Merci de m’envoyer vos commentaires et suggestions.

Catégories
Automates Jeux Mathématiques Permutations

Croisillons

Croisillons

À partir de pièces de puzzle représentant des portions de chemins, on forme le graphe d’une permutation que l’on peut interpréter comme un automate à états fonctionnel.

La page présente une vue des permutations sous forme de puzzle, c’est une introduction aux permutations, aux automates à états et tables de multiplication par croisement de fils.
L’idée est de former les permutations et d’autres applications à l’aide de pièces de puzzle que l’on fait glisser dans l’espace de construction.

Automate de multiplication
Automate pour effectuer les multiplications et divisions des nombres par 2 en base dix, construit à partir d’une permutation.

L’automate est fonctionnel : l’utilisateur peut entrer un nombre à traiter, les liens activés sont mis en surbrillance au cours du traitement par l’automate et montre les étapes de la multiplication avec les retenues.

Pour fabriquer un automate, on réserve un nombre de fils égal au produit du nombre d’états possibles de l’automate par le nombre d’entrées.
On relie les états d’entrées en haut aux états de sortie en bas à l’aide des pièces du puzzle. Les états de sortie sont associés à la valeur à délivrer à chaque nouvelle entrée traitée.
Dans la palette d’outils, l’utilisateur a accès à des exemples préfabriqués.
Il peut modifier la structure en ajoutant ou supprimant des lignes et des colonnes.
Il peut définir le plan de travail en fonction de l’automate à construire et spécifier les entrées et sorties de son automate.
La structure ainsi construite peut être sauvée ou partagée sous forme d’URL.

Les pièces du puzzle permettent également de créer des graphes qui ne sont pas des permutations.

Catégories
Graphes programmation Logique des prédicats Mathématiques Unification

Unificateur cyclique

Cet article présente une nouvelle version de l’unificateur, permettant de traiter des clauses partagées et/ou cycliques.

Les graphes d’unifications produits peuvent également être cycliques.

CHARGEMENT DE LA PAGE

Un clic sur la bulle emmène vers la page d’expérimentation des graphes d’unification cycliques, avec les options d’occur-check et de levée d’exception sur le premier échec.

Exemple de graphe d’unification cyclique
Cyclonium
Catégories
Graphes maths Graphes programmation Programmation

Graphes en boîtes

À partir d’une simple chaîne de caractères, le système dessine un graphe dirigé, multiple, réflexif et ordonné sous forme de boîtes imbriquées les unes dans les autres.

Catégories
Graphes maths Graphes programmation Logique des prédicats Mathématiques Programmation Unification

Graphes unificateurs

graphe unificateur de f(X, g(X), h) = f(g(g(B,Z), a), g(g(X, Z)), a)
graphe unificateur de f(X, g(X), h) = f(g(g(B,Z), a), g(g(X, Z)), a)

La page d’expérimentation est une ressource pour la programmation. Le code de l’unificateur est simplifié et basé sur la bibliothèque de traitement de graphes de Cyclonium.

Documentation

Catégories
Programmation

Unification

L’unification, ou équation d’arbres est fondamentale en Intelligence artificielle. Cet article propose une page permettant de :

  • saisir des termes : constantes, variables et prédicats
  • des clauses, unifiant des variables et des termes suivant les substitutions précédentes.
  • des substitutions
  • des produits de substitutions avec éventuellement un terme final.

Et évaluer le résultat.

Les résultats sont présentés sous forme textuelle re-interprétables par l’analyseur syntaxique intégré, et sous forme graphique interactive en format SVG.

Le parseur Javascript est écrit avec l’aide de la biblothèque http://pegjs.org/

Les graphes sont générés en SVG par Cyclonium.

La méthode de calcul est inspirée de « La méthode Robinson » décrite dans Wikipédia à la page https://fr.wikipedia.org/wiki/Unification.