Format MIDI et musique algorithmique

Magazine
Marque
GNU/Linux Magazine
Numéro
198
Mois de parution
novembre 2016
Domaines


Résumé

Avec le format MIDI, vous pouvez mêler les plaisirs de la composition musicale et de la programmation. Dans ce second article, nous allons explorer quelques aspects de la composition algorithmique.


Body

 

Dans ce second article consacré au format MIDI, nous utilisons notre programme en C pour composer un canon à trois voix avec une basse continue, à partir du début du canon de Pachelbel puis nous explorons la musique stochastique en parcourant aléatoirement une gamme de blues. C'est également l'occasion de découvrir l'usage des percussions dans le format MIDI.

Lors du précédent article [1], nous avions écrit un programme en C permettant de créer des fichiers au format MIDI (Musical Instrument Digital Interface). Nous allons maintenant l’utiliser pour explorer d’une part les possibilités offertes par MIDI et d’autre part certains liens pouvant exister entre musique et algorithmique. Une partition musicale comporte en effet des instructions (notes, nuances, etc.), des répétitions et des branchements conditionnels. Il s'agit donc d'un algorithme.

Les fichiers sources sont disponibles sur le dépôt GitHub du magazine. Rappelons que le fichier midi. ccontient toutes les procédures et fonctions qui seront utilisées par les différents exemples développés dans cet article. Pourles fichiers .mid et .mp3 des exemples sont disponibles sur mon site [2], ainsi que quelques bonus.

1. Canon de Pachelbel

1.1 Introduction

Afin de vous donner envie de vous lancer dans la programmation MIDI et d'aller jusqu'au bout de cet article, il me faut de l'artillerie lourde. Le canon de Pachelbel devrait faire l'affaire [3]. Nous allons donc nous faire la main avec les premières mesures de ce canon en ré majeur composé vers 1700. Il est composé d'une basse continue et obstinée qui répète huit noires. Au bout de deux mesures, un premier violon commence à jouer un thème composé de seize noires. Un deuxième violon commence ce même thème deux mesures plus loin, puis un troisième violon encore deux mesures plus loin. C'est ce que l'on appelle un canon à trois voix (voir figure 1), procédé simple, à la structure algorithmique limpide, mais du plus bel effet !

 

Format_MIDI_et_musique_algorithmique_figure_01

 

Fig. 1. Partition de notre fichier MIDI obtenue avec le logiciel Rosegarden.

Je vous rappelle que la première piste d'un fichier MIDI contient normalement les métadonnées. Et dans la procédure ecrire_piste1(), nous allons fixer un tempo de 60 (noires par minute), c'est-à-dire qu'une noire durera un million de micro-secondes (ligne 7) :

03: #include "midi.c"
04: 
05: void ecrire_piste1(FILE *fichier) {   
06:     unsigned long marque = MIDI_ecrire_en_tete_piste(fichier) ;
07:     MIDI_tempo(fichier, 1000000) ;   
08:     MIDI_fin_de_la_piste(fichier) ;
09:     ecrire_taille_finale_piste(fichier, marque) ;    
10: }

1.2 Basse continue

Définissons tout d'abord la piste de la basse obstinée. Ligne 15, nous mettons un effet de réverbération moyen puisque le niveau est de 64 alors que le maximum possible est de 127. Ligne 16, nous choisissons l'instrument General Midi 48 (String Ensemble 1) parmi les 128 disponibles [4]. Rappelons que la numérotation informatique des instruments commence à zéro. Nous définissons ensuite un tableau d'octets basse[] qui contient les numéros MIDI des huit notes à répéter [5] (la première, 50, est un ré2). La boucle sur i écrit les huit noires dans le fichier, avec un volume sonore moyen 64. La boucle sur j répète trente fois ces huit notes (ces deux mesures). Je vous l'ai dit qu'elle était obstinée, cette basse !

13: void ecrire_piste_basse(FILE *fichier) {
14:     unsigned long marque = MIDI_ecrire_en_tete_piste(fichier) ;
15:     MIDI_Control_Change(fichier, 0, reverb, 64) ;
16:     MIDI_Program_Change(fichier, 0, 48) ;
17:     
18:     unsigned char basse[8] = {50, 45, 47, 42, 43, 38, 43, 45} ;   
19:     for(int j = 1 ; j <= 30 ; j = j + 1) {
20:         for(int i = 0 ; i < 8 ; i = i + 1){
21:             Note_unique_avec_duree(fichier, 0, basse[i], 64, noire) ;
22:         }
23:     }
24:     MIDI_fin_de_la_piste(fichier) ;
25:     ecrire_taille_finale_piste(fichier, marque) ;    
26: }

1.3 Canon à trois voix

La procédure ecrire_pistes_canon() ci-dessous va créer les trois pistes (voix) du canon, numérotées ici 3, 4 et 5. La ligne 36 permet de décaler le démarrage de chaque voix de huit noires par rapport à la précédente, en écrivant une note avec un volume sonore nul (il s’agit donc d’une pause). Les seize notes du thème sont stockées dans le tableau theme[]. La première note, 78, est un fa#4. La boucle sur i, la plus interne, écrit le thème. La boucle sur j va écrire ce thème quinze fois sur chaque piste mais, petit raffinement, pour donner plus d’ampleur à notre morceau sans trop d’effort, la ligne 38 va permettre de changer d’instrument à chaque fois, en puisant dans une liste d’instruments MIDI bien choisis stockés dans le tableau instrument[]. On commencera donc par les instruments 40, 41 et 42 (violon, alto et violoncelle), puis on glissera progressivement vers les autres instruments. La boucle sur piste s’occupe bien sûr de créer les trois voix.

29: void ecrire_pistes_canon(FILE *fichier) {
30:     unsigned char instrument[17] = {40, 41, 42, 44, 45, 48, 49, 51, 52, 89, 90, 91, 92, 94, 95, 99, 100} ;
31:     unsigned char theme[16] = {78, 76, 74, 73, 71, 69, 71, 73, 74, 73, 71, 69, 67, 66, 67, 64} ;
32:     
33:     for(int piste = 3 ; piste <= 5 ; piste = piste + 1) {
34:         unsigned long marque = MIDI_ecrire_en_tete_piste(fichier) ;
35:         MIDI_Control_Change(fichier, piste, reverb, 64) ;    
36:         Note_unique_avec_duree(fichier, piste, 0, 0, 8*noire*(piste - 2)) ;   
37:         for(int j = 0 ; j < 15 ; j = j + 1) {
38:             MIDI_Program_Change(fichier, piste, instrument[(piste - 3) + j]) ;
39:             for(int i = 0 ; i < 16 ; i = i + 1){
40:                 Note_unique_avec_duree(fichier, piste, theme [i], 64, noire) ;
41:             }
42:         }        
43:         MIDI_fin_de_la_piste(fichier) ;
44:         ecrire_taille_finale_piste(fichier, marque) ;           
45:     }
46: }

Dans le programme principal, nous indiquons ligne 50 que le fichier MIDI comportera cinq pistes (une pour les métadonnées, une pour la basse obstinée et trois pour le canon) :

48: int main(void) {
49:     FILE *fichier_midi = fopen("canon.mid", "wb") ;
50:     MIDI_ecrire_en_tete(fichier_midi, 1, 5, noire) ;
51:     ecrire_piste1(fichier_midi) ;
52:     ecrire_piste_basse(fichier_midi) ;
53:     ecrire_pistes_canon(fichier_midi) ;
54:     fclose(fichier_midi) ;  
55: }

1.4 Music Non Stop !

Après compilation et exécution, vous pouvez utiliser le logiciel TiMidity++ (paquet timidity dans le cas d'une distribution Ubuntu) [6] pour le jouer :

$ gcc canon. c

$ ./a.out

$ timidity canon.mid

Mais pour un meilleur rendu, je vous conseille fortement d'utiliser la fonte sonoreFluid R3 General MIDI soundfont disponible dans le paquet fluid-soundfont-gm (142 Mio) sous Ubuntu, d'autant plus que certains instruments n'existent pas dans la fonte par défaut :

$ timidity canon.mid -x "soundfont /usr/share/sounds/sf2/FluidR3_GM.sf2"

Si vous avez un instrument avec une entrée MIDI, vous pouvez bien sûr envoyer le flux dessus avec la commande ci-dessous (en supposant que votre instrument soit sur le port MIDI 20) :

$ aplaymidi -p 20 canon.mid

Je vous renvoie pour plus de détails sur ce point au hors-série n°29 « Musique & Son » de Linux Pratique [7].

Pas mal pour un fichier MIDI de 8902 octets ! Attention, ces 4'30" de musique peuvent devenir obsédantes... Cette durée me fait penser que pour vous reposer le cerveau et les oreilles, vous pourrez ensuite réfléchir à un algorithme pour jouer les trois mouvements du morceau « 4'33" » de John Cage :-).

1.5 Variations

Dans les trois voix de notre canon, les deuxième et troisième sont des imitations strictes de la première. Mais une imitation peut également être par exemple rétrogradée (dite à l'écrevisse), c'est-à-dire que le thème est joué de la fin vers le début, en miroir (on inverse le mouvement vertical de la mélodie), transposée (par exemple à la quinte), etc. Dans la pratique, l'effet n'est pas toujours heureux (apparition de dissonances plus ou moins marquées) et nécessite de la recherche. Je vous propose de remplacer la ligne 40 de notre programme par la structure de choix suivante :

01: switch(piste) {
02:     case 3:
03:         Note_unique_avec_duree(fichier, piste, theme[i], 64, noire) ;
04:         break ;
05:     case 4:
06:         Note_unique_avec_duree(fichier, piste, theme[15-i], 64, noire) ;     
07:         break ;
08:     case 5:
09:         if (i%2 == 0) Note_unique_avec_duree(fichier, piste, theme[i], 64, 2*noire) ;                        

10: }

La deuxième voix est une imitation à l'écrevisse (15-i). La troisième ne joue qu'une note sur deux mais pendant la durée d'une blanche (deux noires). Le résultat me semble plutôt heureux.

2. Blues stochastique

2.1 Introduction

Les premières expérimentations consistant à faire composer de la musique par un ordinateur datent des années 50. En 1957, L.A. Hiller et L.M. Isaacson utilisent l’ordinateur ILLIAC 1 de l’Université de l’Illinois pour composer la « suite Illiac », quatuor à cordes en quatre mouvements, chaque mouvement correspondant à une expérimentation différente [8, 9, 10]. Cette pièce combine l’utilisation de nombres pseudo-aléatoires et de règles diverses.

Dans le système MIDI, nous disposons de 128 notes numérotées de   (do -2) à 127 (sol 8), sur plus de dix octaves. Nous pourrions bien sûr tirer des notes au hasard parmi ces valeurs, mais l’on imagine assez bien le résultat. Nous allons plutôt tenter de créer quelque chose pouvant être considéré comme une mélodie. Pour rester simple, on peut considérer qu’une mélodie est une suite de notes plus ou moins proches les unes des autres qui montent et qui descendent dans des intervalles assez limités (en général une ou deux octaves). L’idée vient donc d’effectuer une marche au hasard en utilisant une méthode Monte-Carlo : on part d’une note, on tire un nombre au hasard entre   et 1, s’il est supérieur à 0,5 on passe à la note au-dessus, sinon à la note en dessous.

2.2 I've got the blues

Si l’on utilise la numérotation MIDI, nous parcourrons alors des gammes chromatiques : do, do#, ré, ré#, mi, fa, fa#, sol, sol#, la, la#, si, etc.Nous sommes alors dans la musique dite dodécaphonique, développée par Arnold Schönberg au début du XXe siècle, puisque ces douze notes sont sur un pied d’égalité : chacune aura la même probabilité d’être jouée. Nous aurions pu nous lancer dans la musique sérielle, mais nous allons ici rester dans la musique tonale. La première chose que nous allons faire est donc de définir un tableau gammes[] qui contiendra un sous-ensemble des 128 notes MIDI composé d'une gamme commençant par la note   (c'est un do) et répétée aux octaves supérieures. La plupart des gammes couramment utilisées comportent entre cinq et sept notes : ce nombre variable sera stocké dans nb_notes. Ligne 22, nous commençons à remplir le tableau avec les notes de notre gamme sur une octave. Il s'agit ici d'une gamme de blues (six notes) : {0, 3, 5, 6, 7, 10} soit do, ré#, fa, fa#, sol, la#. La boucle « Faire Tant Que » et sa boucle « Pour » interne sont chargées de répéter cette gamme aux octaves supérieures tout en veillant à ne pas dépasser la note MIDI 127. La variable jmax contiendra l'indice de la dernière note entrée dans le tableau.

13: void ecrire_piste2(FILE *fichier) {
14:     double p, delta ;
15:     
16:     unsigned long marque = MIDI_ecrire_en_tete_piste(fichier) ;
17:     MIDI_Control_Change(fichier, 0, reverb, 64) ;
18:     MIDI_Control_Change(fichier, 0, 1, 40) ;    // modulation
19:     MIDI_Program_Change(fichier, 0, 30) ;
20: 
21:     const int nb_notes = 6 ;
22:     unsigned char gammes[128] = {0, 3, 5, 6, 7, 10} ;  // Blues
23:     int jmax = nb_notes - 1 ;
24:     int octave = 1 ;
25:     bool continuer = true ;
26:     do {
27:         for(int j=0 ; j <= nb_notes-1 ; j = j+1){    
28:             if (gammes[j] + octave*12 <= 127) {
29:                 jmax = octave*nb_notes + j ;
30:                 gammes[jmax] = gammes[j] + octave*12 ;
31:             }
32:             else continuer = false ;
33:         }
34:         octave = octave + 1 ;
35:     } while (continuer) ;

L'instrument utilisé (30) est une guitare avec distorsion. Ligne 18, le Control Change1 correspond à la molette de modulation d'un clavier musical, qui commande par défaut le vibrato [11].

2.3 Marche au hasard et tonique

La deuxième partie de la procédure ecrire_piste2() va consister à créer une mélodie en parcourant nos gammes au hasard. La fonction srand(time(NULL))permet de modifier la graine du générateur de nombres pseudo-aléatoires avec l'horloge de l'ordinateur afin d'obtenir une mélodie différente à chaque fois.

Nous partons d'un do (24e note de notre gamme) de durée noireblues (les constantes seront définies plus loin) avec un volume 40. Nous tirons ensuite un nombre pseudo-aléatoire p entre   et 1 en utilisant la fonction rand() qui renvoie un entier entre   et RAND_MAX. Le test lignes 46-51 utilise la valeur de p pour déterminer si on passe à la note au-dessus ou en dessous dans notre gamme, ou si on rejoue la même note (avec une probabilité 0.1). On veille bien sûr à ne pas dépasser les limites du tableau gammes[]. On tire ensuite un autre nombre pseudo-aléatoire pour déterminer la durée de la note (lignes 53-55), pour donner un peu de rythme. Notre blues comporte en tout deux cents notes (constante longueur).

37:     srand(time(NULL));
38:     unsigned char duree = noireblues ;
39:     const unsigned char tonique = 24 ;  // do
40:     unsigned char note = tonique ;
41:     for(int i=1 ; i <= longueur ; i = i+1){
42:         Note_unique_avec_duree(fichier, 0, gammes[note], 40, duree) ;    
43:         
44:         p = rand() / ((double)RAND_MAX) ;
45:         delta = ((gammes[note] - gammes[tonique]) / 12.0) * 0.45 ;
46:         if (p >= 0.55+delta) {
47:             if (note < jmax) note = note + 1 ;
48:         }
49:         else if (p >= 0.1) {
50:             if (note > 0) note = note - 1 ;
51:         }
52:         
53:         p = rand() / ((double)RAND_MAX) ;
54:         if (p >= 0.75) duree = noireblues ;
55:         else duree = noireblues / 4 ;
56:     }
57:     MIDI_fin_de_la_piste(fichier) ;
58:     ecrire_taille_finale_piste(fichier, marque) ;    
59: }

Mais à quoi sert la variable delta ? Si nous nous contentions d'un test if (p>=0.5), la marche au hasard pourrait nous éloigner arbitrairement dans les graves ou les aiguës. La valeur absolue de delta est d'autant plus grande que nous nous éloignons de notre note de départ, la tonique. Nous créons ainsi une sorte de force de rappel vers notre tonique qui nous empêche de nous en éloigner de plus d'une octave (douze demi-tons).

2.4 Percussions

 

Format_MIDI_et_musique_algorithmique_figure_02

 

Fig. 2. Un rythme de blues./

Nous allons ajouter une piste avec le rythme de blues de la figure 2 [12]. Rappelons que MIDI réserve son 10e canal (le 9 si la numérotation commence à  ) aux percussions, d'où la déclaration dans le fichier midi. c de la constante percu. Dans ce canal, il n'y a pas d'instrument à définir, chaque percussion correspondant en fait à un numéro de note allant de 35 (grosse caisse) à 81 (triangle) [4], ce qui correspond à un classement de la plus grave à la plus aiguë. Nous n'utilisons pas notre procédure Note_unique_avec_duree()car nous allons devoir jouer ici une à trois notes simultanément et donc gérer à la main les événements MIDI Note On et Note Off pour chaque note, en n'oubliant pas d'inclure un delta_time nul à chaque fois. Les percussions utilisées sont : 35 (Acoustic Bass Drum, grosse caisse), 38 (Acoustic Snare, caisse claire) et 42 (Closed Hi-Hat, charleston fermé). Les volumes sonores ont été choisis différents pour chaque type de percussion.

Une des caractéristiques des rythmes de blues est l'usage de triolets (groupes de trois notes valant une noire). La durée de chaque coup de charleston sera donc noireblues/3 (raison pour laquelle il est important que noireblues soit un entier multiple de trois). L'opérateur modulo % nous est bien utile pour déterminer pour quelles valeurs de i il faut taper sur la grosse caisse ou la caisse claire :

61: void ecrire_piste_percu(FILE *fichier) {
62:     unsigned long marque = MIDI_ecrire_en_tete_piste(fichier) ;
63:     MIDI_Control_Change(fichier, percu, reverb, 64) ;
64: 
65:     for(int i=1 ; i <= longueur*3 ; i = i+1){
66:         MIDI_delta_time(fichier, 0) ;
67:         MIDI_Note(ON, fichier, percu, 42, 80) ; // Charleston
68:         if (i%6 == 4) {                         // Caisse claire
69:             MIDI_delta_time(fichier, 0) ;
70:             MIDI_Note(OFF, fichier, percu, 38, 92) ;
71:             MIDI_delta_time(fichier, 0) ;
72:             MIDI_Note(ON, fichier, percu, 38, 92) ;
73:         }
74:         else if ((i%6 == 1) || (i%12 == 6)) {   // Grosse caisse
75:             MIDI_delta_time(fichier, 0) ;
76:             MIDI_Note(OFF, fichier, percu, 35, 127) ;
77:             MIDI_delta_time(fichier, 0) ;
78:             MIDI_Note(ON, fichier, percu, 35, 127) ;
79:         }
80:         MIDI_delta_time(fichier, noireblues / 3) ;      
81:         MIDI_Note(OFF, fichier, percu, 42, 64) ;
82:     }   
83:     MIDI_fin_de_la_piste(fichier) ;
84:     ecrire_taille_finale_piste(fichier, marque) ;    
85: }

N'oubliez pas de définir les constantes noireblues et longueur au début du fichier blues. c :

01: #include "midi. c"
02: #include "time.h"
03: #define noireblues 120
04: #define longueur   200

Et de définir le tempo suivant dans la procédure ecrire_piste1() :

08:     MIDI_tempo(fichier, 1000000) ;   

Enfin, n'oubliez pas de modifier la fonction main() en indiquant qu'il y a trois pistes dans notre fichier MIDI : ecrire_piste1(), ecrire_piste2() et ecrire_piste_percu().

2.5 Autres explorations

Pour changer d'ambiance, vous pouvez, après avoir désactivé la procédure ecrire_piste_percu(), utiliser d'autres gammes [13] :

- une gamme par ton, utilisée en particulier par Debussy : {0, 2, 4, 6, 8, 10} ;

- une gamme pentatonique, pour une ambiance asiatique : {1, 3, 6, 8, 10} (les touches noires d'un piano). Utilisez le Koto, instrument 107 ;

- une gamme majeure : {0, 2, 4, 5, 7, 9, 11} ;

- une gamme mineure harmonique : {9, 11, 12, 14, 16, 17, 20, 21}.

Il faudra également trouver l'instrument le plus en adéquation avec l'ambiance recherchée.

Conclusion et perspectives

Nous avons vu à l'aide de deux exemples comment il était possible d'utiliser le format MIDI pour créer de petites compositions musicales. Dans l'exemple du canon, il s'agissait de répéter des motifs musicaux à l'aide de boucles. Dans l'exemple du blues, nous avons abordé d'une part la musique stochastique et d'autre part l'utilisation des percussions MIDI.

Terminons par quelques idées de travaux pratiques. Le format MIDI faisant correspondre à chaque note un entier, on peut s'amuser à créer des motifs musicaux à partir des codes ASCII de chaînes de caractères, de la même façon que Jean-Sébastien Bach et Dimitri Chostakovitch utilisaient dans leurs œuvres leurs motifs BACH et DSCH en se basant sur la notation musicale anglo-saxonne. On peut également transposer en notes (ou en rythmes) des nombres premiers, des suites mathématiques (Fibonacci, Syracuse, ...), les chiffres de Pi, etc. Et pourquoi pas, s'aventurer en canon dans les rencontres du troisième type : 67, 69, 65, 53, 60.

Références

[1MAGNIN V., «Format MIDI : composez en C ! », GNU/Linux Magazine n°196, septembre 2016.

[2Fichiers musicaux de l'article : http://magnin.plil.net/spip.php?article132

[3Le canon de Pachelbel : https://fr.wikipedia.org/wiki/Canon_de_Pachelbel

[4Liste des instruments General MIDI : https://www.midi.org/specifications/item/gm-level-1-sound-set

[5Numérotation MIDI des notes : https://upload.wikimedia.org/wikipedia/commons/3/36/NoteNamesFrequenciesAndMidiNumbers_V3.svg

[6Lecteur MIDI Timidity++ :http://timidity.sourceforge.net/

[7MAGNIN V., « Avec MIDI, lancez-vous dans la musique assistée par ordinateur », Linux PratiqueHS n°29, p. 36-47.

[8FICHET L., « Les théories scientifiques de la musique aux XIXe et XXe siècles », Vrin, 1996, ISBN 978-2-7116-4284-7.

[9ANDREATTA M., « Musique algorithmique », 2009 : http://articles.ircam.fr/textes/Andreatta11b/index.pdf

[10Suite Illiac : https://en.wikipedia.org/wiki/Illiac_Suite

[11Control Change Messages : https://www.midi.org/specifications/item/table-3-control-change-messages-data-bytes-2

[12Un rythme de blues : http://blog-batteur-debutant.fr/rythme-blues-batterie/

[13Liste des gammes et modes : https://fr.wikipedia.org/wiki/Liste_des_gammes_et_modes

 



Articles qui pourraient vous intéresser...

Et si on déchiffrait la machine Enigma...

Magazine
Marque
GNU/Linux Magazine
Numéro
235
Mois de parution
mars 2020
Domaines
Résumé

La machine Enigma fut utilisée par les Allemands, pendant la Seconde Guerre mondiale, pour chiffrer des messages secrets. Alan Turing est connu pour avoir fortement contribué à la compréhension du fonctionnement du chiffrement de cette machine. Dans cet article, je vais présenter le modèle M3 de la machine Enigma et proposer une simulation de cette machine utilisant le langage Python.

Informatique quantique : l’empire des chats morts-vivants

Magazine
Marque
GNU/Linux Magazine
Numéro
233
Mois de parution
janvier 2020
Domaines
Résumé

Le célèbre paradoxe du chat, à la fois vivant et mort, expérience de pensée due à Erwin Schrödinger en 1935 [1], est très certainement la « bizarrerie » la plus connue, mais aussi la plus perturbante de la mécanique quantique. Elle avait pour but d’illustrer simplement les paradoxes de la mécanique quantique, à une époque où elle n’était pas encore acceptée par les scientifiques. Pour comprendre le passage du monde quantique (la boîte n’est pas ouverte et contient un chat mort-vivant) au monde classique (la boîte est ouverte et le chat est soit mort soit vivant), nous allons présenter les problèmes de cohérence et de mesure. Partons donc à la chasse aux chats morts-vivants.

Les filtres de Bloom : un peu de bruit pour beaucoup [1] !

Magazine
Marque
GNU/Linux Magazine
Numéro
231
Mois de parution
novembre 2019
Domaines
Résumé

Avec l’explosion des données (un fichier de logs, par exemple), chercher une information particulière déjà connue devient une tâche complexe. Or depuis 1970, il existe une technique particulièrement puissante qui permet de résoudre très efficacement ce problème : les filtres de Bloom. Cet article propose de les explorer et de montrer comment les implémenter.

Graphes géants creux : comment définir le centre du Web

Magazine
Marque
MISC
HS n°
Numéro
18
Mois de parution
novembre 2018
Domaines
Résumé

Les graphes, composés de sommets et d’arêtes sont des objets communs en mathématiques (et indispensables) en informatique. Lorsqu’on veut manipuler des graphes de plusieurs centaines de millions de sommets, voire de plusieurs milliards de sommets, comme le graphe du web (ou un sous-ensemble) ou le graphe de certains réseaux sociaux, les choses se compliquent singulièrement : la plupart des algorithmes « académiques » se heurtent au « mur » de la complexité en temps (voire en espace), que nous appellerons le mur du « Big Data ». Tout algorithme dont la complexité est de l’ordre de O(n³) ou même de l’ordre de O(n²) est en fait inutilisable en pratique (ou très coûteux) dès lors que n, le nombre de sommets, dépasse (disons) le milliard. Il faut alors suivre d’autres stratégies. Il faut par exemple accepter de ne pouvoir calculer qu’une approximation même si dans certains cas, cette approximation peut en fait être la valeur exacte.

Quelques applications des Arbres Binaires à Commande Équilibrée

Magazine
Marque
GNU/Linux Magazine
Numéro
218
Mois de parution
septembre 2018
Domaines
Résumé

Les Arbres Binaires à Commande Équilibrée, ou ABCE, ont été présentés dans GLMF n°215 [1] au moyen d'une métaphore ferroviaire. Cependant, ils sont surtout utiles dans certains circuits numériques, dont ils améliorent la vitesse et la consommation, pour la plupart des technologies. Par rapport à un arbre binaire classique, le gain de performance augmente avec la taille, ce qui est un atout précieux pour concevoir des circuits intégrés par exemple.