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
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
Base 2 Jeux Mathématiques Numération

Balance de Roberval pour apprendre les bases de numération

2020 en Base 3
Image extraite de l’atelier

Cet article présente une simulation de balance de Roberval pour apprendre les bases de numération de position.

Il suffit de cliquer sur les poids pour équilibrer la balance. Une fois l’équilibre atteint, le nombre de billes est écrit sous le plateau de gauche dans la base choisie.

La documentation complète est dans la page d’expérience. Cliquez sur l’image pour démarrer.

Catégories
Animation Instrument interactif Jeux Musique Pavages

Ian Snyder’s five stringed instrument

Un jeu d’enfant, l’instrument concocté par Ian Snyder est très simple et intuitif.

Un élastique et 6 punaises délimitent 5 cordes vibrantes.

La longueur des cordes correspond (à une transformation près) à la hauteur du son : comme en vrai, plus la corde est longue plus le son est grave et inversement, plus la corde est courte plus le son correspondant est aigu.

Pour faire sonner une corde, il suffit de l’attraper à la souris, de tirer dessus et de la relâcher. L’intensité du son produit est corrélé à la traction effectuée avant de relâcher : plus on tire, plus le son est fort.

En haut à gauche, le bouton « tuning » permet d’accorder l’instrument selon plusieurs gammes :

Un bout de commentaire dans le code correspondant :

// all – [1,1,1,1,1,1,1,1,1,1,1,1]
// penta – [1,0,1,0,1,0,0,1,0,1,0,0]
// hexa – [1,0,1,0,1,0,1,0,1,0,1,0]
// hepta – [1,0,1,0,1,1,0,1,0,1,0,1]
// octa – [1,1,0,1,1,0,1,1,0,1,1,0]
/* A BC D EF G
000000000000
1-1-1-1-1-1- > whole
–11–11–11 > augmented
11-1-1-1-1– > prometheus
-1-1–1-111- > blues
> 1–1-1-11-1- > diatonic
*/

Le code en vrai dans la fonction tuneMode() :

switch (tuning) {
		case 1:
		scale = [1,1,1,1,1,1,1,1,1,1,1,1];
		str = "12 tone";
		break;
		
		case 2:
		scale = [1,1,0,1,1,0,1,1,0,1,1,0];
		str = "8 tone";
		break;
		
		case 3:
		scale = [1,0,1,0,1,1,0,1,0,1,0,1];
		str = "7 tone";
		break;
		
		case 4:
		scale = [1,0,1,0,1,0,1,0,1,0,1,0];
		str = "6 tone (whole)";
		break;
		
		case 5:
		scale = [1,1,0,0,1,1,0,0,1,1,0,0];
		str = "6 tone (augmented)";
		break;
		
		case 6:
		scale = [1,1,0,1,0,1,0,1,0,1,0,0];
		str = "6 tone (prometheus)";
		break;
		
		case 7:
		scale = [0,1,0,1,0,0,1,0,1,1,1,0];
		str = "6 tone (blues)";
		break;
		
		case 8:
		scale = [1,0,0,1,0,1,0,1,1,0,1,0];
		str = "6 tone (diatonic)";
		break;
		
		case 9:
		scale = [1,0,1,0,1,0,0,1,0,1,0,0];
		str = "5 tone";
		break;
	}

On est toujours basé sur une échelle en 12 demi-tons, à moins de mettre le « tuning » à OFF.

On peut changer le timbre utilisé : il suffit de choisir le fichier d’échantillons à utiliser (en wav, mp3, etc…) disponible sur sa machine.

Par exemple, un son de corde de violoncelle : téléchargez

https://www.cyclonium.com/atelier/sons/Cello.wav

Ou encore un son produit par SoundPotatoes :

https://www.cyclonium.com/atelier/sons/Potato20200828_7b.mp3

Vous avez remarqué que les mouvements effectués à la souris sont répétés automatiquement, à intervalle de temps réguliers. En bas à gauche le bouton : SWARM permet de régler les répétitions des mouvements. Pas de répétition, ou 2, 4, 8, 16, 32 et 64 répétitions (tiens ! des puissances de deux).

Les répétitions des mouvements concernent là la fois le jeu sur les cordes et le déplacement des punaises.

Enfin, le bouton « Snapping » en haut à gauche montre que Ian s’est également intéressé aux grilles hexagonales. Si le « Snapping » est actif, les positions des punaises sont ajustées à la grille.

 

ianiselsewhere.com/fivestrings/(ouvre un nouvel onglet)

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
Animation Géométrie

Sur le thème du théorème de Varignon

Animation dans un canevas (canvas) 2D de Quadrilatères quelconques, avec la mise en valeur des parallélogrammes issus des milieux des segments des quadrilatères.

CHARGEMENT DE LA PAGE

Voir aussi :

L’animation interactive Quadrilatères de Varignon

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