Tableaux multidimensionnels et déréférencement

Lucas Levrel

16/06/2009 à 11:19

Merci d'avoir pris le temps de faire cette réponse détaillée ! On va
bientôt converger...

Le 15 juin 2009, Antoine Leca a écrit :

> Donc quand je demande si « table[i] existe en mémoire », je suis
> trop succinct, car ça peut vouloir dire :
> 1) est-ce que la valeur de table[i] est une adresse qui existe
> ou
> 2) est-ce que l'objet table[i] est stocké en mémoire

Voilà. Moi, je ne vois que la seconde forme ; la première ne me vient
pas à l'esprit. Entre autres parce qu'une expression qui a pour type
int[N] n'est pas pour moi un pointeur ou une adresse, mais un objet.

Oui ! Voilà d'où vient mon problème de communication ! J'ai toujours
interprété l'objet table[i] de type int[4] comme un pointeur (vers
table[i][0]), dont le type sert au compilateur à faire l'arithmétique
correcte (genre table[i]+1 pointe vers adresse(table[i][0])+sizeof(int)).
Quand je parle de table[i] je ne pense absolument pas au tableau de 4 int
et à ce qu'il contient.

>> Par ailleurs, le pointeur est lui-même un objet, et comme tout objet
>> possède son adresse propre.
>
> C'est bien de ça que je parlais.

¿¿¿Bzzz??? Là tu m'as complètement perdu...

Hihi (mieux vaut en rire). Je voulais dire : je parlais bien de « le
pointeur est un objet ». Je ne voulais pas dire : « l'adresse dont je
parle est l'adresse propre de l'objet pointeur ». Ouf.

l'hypothétique adresse où se trouve l'hypothétique pointeur (qui pour
moi n'existe pas, je l'appelerai virtuel).

Ça y est, on a convergé ! Le pointeur vers l'objet table[i] (ledit
pointeur qui contient adresse(table[i][0])) est virtuel.

(Tu comprends maintenant pourquoi dans ma formulation erronée, où table[i]
est le pointeur lui-même, ça donnait « table[i] existe-t-il en mémoire ».)

Euh... Je dois avoir loupé quelque chose...
Pour moi, un tableau dynamique ne désigne pas un tableau de pointeurs
vers des tableaux (éventuellement disjoints en mémoire, et de taille
allouées éventuellement distinctes), mais plutôt un tableau homogène
d'un seul bloc alloué dynamiquement (par malloc()).

En fait ce que je veux dire, c'est que je dois allouer dynamiquement de
la mémoire pour stocker des données indexées. Peu m'importe la méthode, et
j'ai donc deux possibilités :
- allouer un gros bloc m×n et gérer l'indexation avec
« element(i,j)=n*i+j »
- allouer un tableau de pointeurs (*)[m], puis m tableaux de taille n.

Par ailleurs, dans la formulation
int table[3][4];
il n'y a que 12 int, et pas de tableaux de pointeurs;

... les pointeurs sont virtuels.

> table[i] == &(table[i][0])
> Non ?

Mais pour moi, les deux sont des objets (tableaux de 4 int) ; qui en
plus d'une adresse ont un type, et dont la valeur sont des quadruplets.

Même &(table[i][0]) est de type int[4] ? J'en apprends des choses, je
croyais que c'était juste l'adresse de table[i][0], qu'on pourrait par
exemple affecter à tout pointeur int *, sans warning.

Évidemment, avec ces conventions, tu ne dois pas comprendre la plupart
de mes remarques car je n'arrive pas à entrer dans ton formalisme.
Je m'en excuse.

Y'a pas de mal ! Et vu que je me suis formé sur le tas, on ne peut pas
vraiment parler de « formalisme » pour les représentations que je me suis
forgées.

Non, le compilateur ne réserve pas de zones mémoire pour ces pointeurs,
ils restent virtuels.

(OK, dans les détails, il est possible que dans certaines expressions
complexes le compilateur soit obligé de créer des variables temporaires,
normalement en pile, pour stocker ces pointeurs lors du calcul d'une
expression plus large. Donc il y aura réservation d'espace "auto".

OK, c'est logique.

Impossible de répondre à cette question en général.

OK pour l'exemple de la matrice triangulaire. Je vais spécifier un peu
plus mon problème :
1) mes données sont denses et « rectangulaires » (pas besoin de lignes de
longueur variable),
2) supposons que les données sont contiguës, allouées par un
malloc(m*n*sizeof(float)), à l'adresse float *data.

J'ai deux options :
a) j'accède directement à l'élément (i,j) par data[i*n+j],
b) je crée float *rows[m], que j'initialise par rows[i]Úta+i*n, puis
j'accède à l'élément (i,j) par (rows[i])[j].

Pour chaque accès, en a) il y a une multiplication, une addition, une
arithmétique de pointeur ; en b) il y a 2 arithmétiques de pointeur et un
déréférencement. Est-ce que l'une des méthodes est connue pour être plus
rapide à l'éxécution ?

Un autre exemple où l'allocation par morceau peut être moins efficace :
si l'allocateur mémoire fabrique des morceaux juste d'une taille
multiple d'une page, et si tu traverses la matrice dans l'autre sens : à
un instant donné tu vas donc manipuler des lignes mémoire qui ont toutes
par le même motif d'adresse xx234yy0 (par exemple), et tu peux (pouvais)
alors engorger une petite partie du TLB...
La manière habituelle d'optimiser ce genre de contrainte est d'allouer
une taille d'éléments légèrement supérieure qui ne soit pas multiple de
la taille de page, mais là cela ne va pas fonctionner à cause de
l'allocateur.

Rien compris :-)

> ~> xycc
> bash: xycc: command not found

Pardon.

C'était une blague ;-)

>>> Tous les types du C existent-ils ?

les informations de type sont (normalement) rangées dans le fichier
objet produit sous forme d'informations symboliques destinées à
l'éventuel débogage.

OK !

En fait, je voulais savoir si tu voulais faire référence à l'ensemble de
tous les types possible du langage C,
ou bien si tu voulais faire référence à l'ensemble des types que le
compilateur a construit au cours de l'analyse
ou si tu faisais référence aux types explicitement utilisés,

Aucun des trois ! Je me suis mal exprimé, j'aurais dû demander : n'importe
quel type du C est-il représentable en assembleur ?

--
LL

Merci d'avoir pris le temps de faire cette réponse détaillée ! On va
bientôt converger...

Le 15 juin 2009, Antoine Leca a écrit :

> Donc quand je demande si « table[i] existe en mémoire », je suis
> trop succinct, car ça peut vouloir dire :
> 1) est-ce que la valeur de table[i] est une adresse qui existe
> ou
> 2) est-ce que l'objet table[i] est stocké en mémoire

Voilà. Moi, je ne vois que la seconde forme ; la première ne me vient
pas à l'esprit. Entre autres parce qu'une expression qui a pour type
int[N] n'est pas pour moi un pointeur ou une adresse, mais un objet.

Oui ! Voilà d'où vient mon problème de communication ! J'ai toujours
interprété l'objet table[i] de type int[4] comme un pointeur (vers
table[i][0]), dont le type sert au compilateur à faire l'arithmétique
correcte (genre table[i]+1 pointe vers adresse(table[i][0])+sizeof(int)).
Quand je parle de table[i] je ne pense absolument pas au tableau de 4 int
et à ce qu'il contient.

>> Par ailleurs, le pointeur est lui-même un objet, et comme tout objet
>> possède son adresse propre.
>
> C'est bien de ça que je parlais.

¿¿¿Bzzz??? Là tu m'as complètement perdu...

Hihi (mieux vaut en rire). Je voulais dire : je parlais bien de « le
pointeur est un objet ». Je ne voulais pas dire : « l'adresse dont je
parle est l'adresse propre de l'objet pointeur ». Ouf.

l'hypothétique adresse où se trouve l'hypothétique pointeur (qui pour
moi n'existe pas, je l'appelerai virtuel).

Ça y est, on a convergé ! Le pointeur vers l'objet table[i] (ledit
pointeur qui contient adresse(table[i][0])) est virtuel.

(Tu comprends maintenant pourquoi dans ma formulation erronée, où table[i]
est le pointeur lui-même, ça donnait « table[i] existe-t-il en mémoire ».)

Euh... Je dois avoir loupé quelque chose...
Pour moi, un tableau dynamique ne désigne pas un tableau de pointeurs
vers des tableaux (éventuellement disjoints en mémoire, et de taille
allouées éventuellement distinctes), mais plutôt un tableau homogène
d'un seul bloc alloué dynamiquement (par malloc()).

En fait ce que je veux dire, c'est que je dois allouer dynamiquement de
la mémoire pour stocker des données indexées. Peu m'importe la méthode, et
j'ai donc deux possibilités :
- allouer un gros bloc m×n et gérer l'indexation avec
« element(i,j)=n*i+j »
- allouer un tableau de pointeurs (*)[m], puis m tableaux de taille n.

Par ailleurs, dans la formulation
int table[3][4];
il n'y a que 12 int, et pas de tableaux de pointeurs;

... les pointeurs sont virtuels.

> table[i] == &(table[i][0])
> Non ?

Mais pour moi, les deux sont des objets (tableaux de 4 int) ; qui en
plus d'une adresse ont un type, et dont la valeur sont des quadruplets.

Même &(table[i][0]) est de type int[4] ? J'en apprends des choses, je
croyais que c'était juste l'adresse de table[i][0], qu'on pourrait par
exemple affecter à tout pointeur int *, sans warning.

Évidemment, avec ces conventions, tu ne dois pas comprendre la plupart
de mes remarques car je n'arrive pas à entrer dans ton formalisme.
Je m'en excuse.

Y'a pas de mal ! Et vu que je me suis formé sur le tas, on ne peut pas
vraiment parler de « formalisme » pour les représentations que je me suis
forgées.

Non, le compilateur ne réserve pas de zones mémoire pour ces pointeurs,
ils restent virtuels.

(OK, dans les détails, il est possible que dans certaines expressions
complexes le compilateur soit obligé de créer des variables temporaires,
normalement en pile, pour stocker ces pointeurs lors du calcul d'une
expression plus large. Donc il y aura réservation d'espace "auto".

OK, c'est logique.

Impossible de répondre à cette question en général.

OK pour l'exemple de la matrice triangulaire. Je vais spécifier un peu
plus mon problème :
1) mes données sont denses et « rectangulaires » (pas besoin de lignes de
longueur variable),
2) supposons que les données sont contiguës, allouées par un
malloc(m*n*sizeof(float)), à l'adresse float *data.

J'ai deux options :
a) j'accède directement à l'élément (i,j) par data[i*n+j],
b) je crée float *rows[m], que j'initialise par rows[i]Úta+i*n, puis
j'accède à l'élément (i,j) par (rows[i])[j].

Pour chaque accès, en a) il y a une multiplication, une addition, une
arithmétique de pointeur ; en b) il y a 2 arithmétiques de pointeur et un
déréférencement. Est-ce que l'une des méthodes est connue pour être plus
rapide à l'éxécution ?

Un autre exemple où l'allocation par morceau peut être moins efficace :
si l'allocateur mémoire fabrique des morceaux juste d'une taille
multiple d'une page, et si tu traverses la matrice dans l'autre sens : à
un instant donné tu vas donc manipuler des lignes mémoire qui ont toutes
par le même motif d'adresse xx234yy0 (par exemple), et tu peux (pouvais)
alors engorger une petite partie du TLB...
La manière habituelle d'optimiser ce genre de contrainte est d'allouer
une taille d'éléments légèrement supérieure qui ne soit pas multiple de
la taille de page, mais là cela ne va pas fonctionner à cause de
l'allocateur.

Rien compris :-)

> ~> xycc
> bash: xycc: command not found

Pardon.

C'était une blague ;-)

>>> Tous les types du C existent-ils ?

les informations de type sont (normalement) rangées dans le fichier
objet produit sous forme d'informations symboliques destinées à
l'éventuel débogage.

OK !

En fait, je voulais savoir si tu voulais faire référence à l'ensemble de
tous les types possible du langage C,
ou bien si tu voulais faire référence à l'ensemble des types que le
compilateur a construit au cours de l'analyse
ou si tu faisais référence aux types explicitement utilisés,

Aucun des trois ! Je me suis mal exprimé, j'aurais dû demander : n'importe
quel type du C est-il représentable en assembleur ?

--
LL

Vous avez filtré cet utilisateur ! Consultez son message

Merci d'avoir pris le temps de faire cette réponse détaillée ! On va
bientôt converger...

Le 15 juin 2009, Antoine Leca a écrit :

> Donc quand je demande si « table[i] existe en mémoire », je suis
> trop succinct, car ça peut vouloir dire :
> 1) est-ce que la valeur de table[i] est une adresse qui existe
> ou
> 2) est-ce que l'objet table[i] est stocké en mémoire

Voilà. Moi, je ne vois que la seconde forme ; la première ne me vient
pas à l'esprit. Entre autres parce qu'une expression qui a pour type
int[N] n'est pas pour moi un pointeur ou une adresse, mais un objet.

Oui ! Voilà d'où vient mon problème de communication ! J'ai toujours
interprété l'objet table[i] de type int[4] comme un pointeur (vers
table[i][0]), dont le type sert au compilateur à faire l'arithmétique
correcte (genre table[i]+1 pointe vers adresse(table[i][0])+sizeof(int)).
Quand je parle de table[i] je ne pense absolument pas au tableau de 4 int
et à ce qu'il contient.

>> Par ailleurs, le pointeur est lui-même un objet, et comme tout objet
>> possède son adresse propre.
>
> C'est bien de ça que je parlais.

¿¿¿Bzzz??? Là tu m'as complètement perdu...

Hihi (mieux vaut en rire). Je voulais dire : je parlais bien de « le
pointeur est un objet ». Je ne voulais pas dire : « l'adresse dont je
parle est l'adresse propre de l'objet pointeur ». Ouf.

l'hypothétique adresse où se trouve l'hypothétique pointeur (qui pour
moi n'existe pas, je l'appelerai virtuel).

Ça y est, on a convergé ! Le pointeur vers l'objet table[i] (ledit
pointeur qui contient adresse(table[i][0])) est virtuel.

(Tu comprends maintenant pourquoi dans ma formulation erronée, où table[i]
est le pointeur lui-même, ça donnait « table[i] existe-t-il en mémoire ».)

Euh... Je dois avoir loupé quelque chose...
Pour moi, un tableau dynamique ne désigne pas un tableau de pointeurs
vers des tableaux (éventuellement disjoints en mémoire, et de taille
allouées éventuellement distinctes), mais plutôt un tableau homogène
d'un seul bloc alloué dynamiquement (par malloc()).

En fait ce que je veux dire, c'est que je dois allouer dynamiquement de
la mémoire pour stocker des données indexées. Peu m'importe la méthode, et
j'ai donc deux possibilités :
- allouer un gros bloc m×n et gérer l'indexation avec
« element(i,j)=n*i+j »
- allouer un tableau de pointeurs (*)[m], puis m tableaux de taille n.

Par ailleurs, dans la formulation
int table[3][4];
il n'y a que 12 int, et pas de tableaux de pointeurs;

... les pointeurs sont virtuels.

> table[i] == &(table[i][0])
> Non ?

Mais pour moi, les deux sont des objets (tableaux de 4 int) ; qui en
plus d'une adresse ont un type, et dont la valeur sont des quadruplets.

Même &(table[i][0]) est de type int[4] ? J'en apprends des choses, je
croyais que c'était juste l'adresse de table[i][0], qu'on pourrait par
exemple affecter à tout pointeur int *, sans warning.

Évidemment, avec ces conventions, tu ne dois pas comprendre la plupart
de mes remarques car je n'arrive pas à entrer dans ton formalisme.
Je m'en excuse.

Y'a pas de mal ! Et vu que je me suis formé sur le tas, on ne peut pas
vraiment parler de « formalisme » pour les représentations que je me suis
forgées.

Non, le compilateur ne réserve pas de zones mémoire pour ces pointeurs,
ils restent virtuels.

(OK, dans les détails, il est possible que dans certaines expressions
complexes le compilateur soit obligé de créer des variables temporaires,
normalement en pile, pour stocker ces pointeurs lors du calcul d'une
expression plus large. Donc il y aura réservation d'espace "auto".

OK, c'est logique.

Impossible de répondre à cette question en général.

OK pour l'exemple de la matrice triangulaire. Je vais spécifier un peu
plus mon problème :
1) mes données sont denses et « rectangulaires » (pas besoin de lignes de
longueur variable),
2) supposons que les données sont contiguës, allouées par un
malloc(m*n*sizeof(float)), à l'adresse float *data.

J'ai deux options :
a) j'accède directement à l'élément (i,j) par data[i*n+j],
b) je crée float *rows[m], que j'initialise par rows[i]Úta+i*n, puis
j'accède à l'élément (i,j) par (rows[i])[j].

Pour chaque accès, en a) il y a une multiplication, une addition, une
arithmétique de pointeur ; en b) il y a 2 arithmétiques de pointeur et un
déréférencement. Est-ce que l'une des méthodes est connue pour être plus
rapide à l'éxécution ?

Un autre exemple où l'allocation par morceau peut être moins efficace :
si l'allocateur mémoire fabrique des morceaux juste d'une taille
multiple d'une page, et si tu traverses la matrice dans l'autre sens : à
un instant donné tu vas donc manipuler des lignes mémoire qui ont toutes
par le même motif d'adresse xx234yy0 (par exemple), et tu peux (pouvais)
alors engorger une petite partie du TLB...
La manière habituelle d'optimiser ce genre de contrainte est d'allouer
une taille d'éléments légèrement supérieure qui ne soit pas multiple de
la taille de page, mais là cela ne va pas fonctionner à cause de
l'allocateur.

Rien compris :-)

> ~> xycc
> bash: xycc: command not found

Pardon.

C'était une blague ;-)

>>> Tous les types du C existent-ils ?

les informations de type sont (normalement) rangées dans le fichier
objet produit sous forme d'informations symboliques destinées à
l'éventuel débogage.

OK !

En fait, je voulais savoir si tu voulais faire référence à l'ensemble de
tous les types possible du langage C,
ou bien si tu voulais faire référence à l'ensemble des types que le
compilateur a construit au cours de l'analyse
ou si tu faisais référence aux types explicitement utilisés,

Aucun des trois ! Je me suis mal exprimé, j'aurais dû demander : n'importe
quel type du C est-il représentable en assembleur ?

--
LL

Lucas Levrel

16/06/2009 à 11:30

Le 15 juin 2009, Antoine Leca a écrit :

> Jean-Claude Arbaut nous a appris qu'en C99 on pouvait faire
> double get(int n, int p, double t[n][p], int i, int j){return t[i][j];}

Et c'est un VLA (tableau à longueur variable) de VLA, et rien ne dit que
les perfs des VLAs sont les mêmes que celles des tableaux à taille fixe.

On doit probablement trouver des implémentations où les VLAs sont
implémentés comme des objets C++ avec méthodes virtuelles etc., et un
ordre de grandeur de performance différent.

Peux-tu m'en dire plus ? Tu fais peut-être référence à des objets tableaux
qui vérifient que l'index demandé ne sort pas des limites allouées ?

--
LL

Antoine Leca

16/06/2009 à 13:05

Le 15/06/2009 20:22, ld écrivit :

C'était pour donner une image intuitive à Antoine.

Merci. Mais comme je l'écrivis, j'avais bien compris, et j'ai la réponse
à la remarque parfaitement HS que j'ai faite en passant, même si je ne
suis pas donné la peine de reprendre la totalité des arguments des uns
et des autres sur un sujet dont je continue de considérer qu'il n'a pas
sa place sur ce forum.

Antoine

Antoine Leca

16/06/2009 à 13:16

Le 16/06/2009 9:30, Lucas Levrel écrivit :

Le 15 juin 2009, Antoine Leca a écrit :

Jean-Claude Arbaut nous a appris qu'en C99 on pouvait faire
double get(int n, int p, double t[n][p], int i, int j){return t[i][j];}

Et c'est un VLA (tableau à longueur variable) de VLA, et rien ne dit que
les perfs des VLAs sont les mêmes que celles des tableaux à taille fixe.

On doit probablement trouver des implémentations où les VLAs sont
implémentés comme des objets C++ avec méthodes virtuelles etc., et un
ordre de grandeur de performance différent.

Peux-tu m'en dire plus ?

Sur ? Le mot « probablement » dans la phrase ci-dessus est un indice que
indique qu'en fait, je n'ai pas d'exemple concret sous la main...

Tu fais peut-être référence à des objets tableaux
qui vérifient que l'index demandé ne sort pas des limites allouées ?

C'est théoriquement possible.
En fait, c'est probablement ce qui est implémenté dans un compilateur
qui saurait mixer C et Ada (où le langage requiert que le système
vérifie les indices par rapport aux limites à chaque utilisation).

Et cela me paraîtrait une fonctionnalité intéressante pour un
compilateur C (largement plus que les _s).

Mais je ne pratique pas suffisament les compilos C99 pour avoir un
exemple pratique sous la main.

Antoine

espie

16/06/2009 à 14:56

In article ,
ld wrote:

dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer
(discret vs continu).

Tiens, je n'avais pas fait gaffe, mais ce paragraphe est totalement faux.
La denombrabilite a tout a voir avec le nombre d'elements de l'ensemble, ou
plus exactement la possibilite d'etablir une bijection entre l'ensemble et N
(avec ou sans axiome du choix, pour les puristes... et avec ou sans tiers
exclu pour les fans de logique intuitioniste).

Le fait d'avoir un successeur, c'est deja une structure algebrique, et c'est
une propriete totalement differente. Je peux parfaitement te fabriquer une
structure sur R qui fait que tout element aura un successeur (l'operation
triviale d'ajouter 1 marche parfaitement, et en gros on obtient N x [0,1], avec
N dote de son successeur habituel, et [0,1[ dote de la topologie triviale ou
tout point est isole). Elle n'aura evidemment aucun rapport
avec la topologie usuelle de R (mais on parle de l'ensemble et de sa
cardinalite) et ca ne le rendra pas denombrable pour autant...

Jean-Marc Bourguet

16/06/2009 à 18:45

Antoine Leca writes:

Tu fais peut-être référence à des objets tableaux
qui vérifient que l'index demandé ne sort pas des limites allouées ?

C'est théoriquement possible.

Il y a eu un compilateur C++ (celui de Centerline) qui faisait ce genre de
chose, je suppose qu'il avait un mode "compilateur C". A ma connaissance,
ils ont fait faillite.

Gcc a (eu?) quelque chose du genre, peut-être uniquement dans une branche.
Et leur passe de propagation d'intervalle utilisée dans le compilateur --
avec des effets parfois plus ou moins surprenants -- devrait en théorie
permettre de supprimer des vérifications car prouvable statiquement.

En fait, c'est probablement ce qui est implémenté dans un compilateur
qui saurait mixer C et Ada (où le langage requiert que le système
vérifie les indices par rapport aux limites à chaque utilisation).

Pas nécessairement. (Et en utilisant le système de type comme de coutume
en Ada, une passe comme la propagation d'intervalle de gcc devrait encore
être plus efficace).

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Manuel Pégourié-Gonnard

16/06/2009 à 20:29

[Cross-post fclc + fsm, suivi fsm]

Suite à une réflexion sur l'ensemble des types du langage C qui est
infini, on en vient à parler de dénombrabilité, sujet qui semble prêter
à quelques confusions.

Marc Espie scripsit:

In article
,
ld wrote:
dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer
(discret vs continu).

Tiens, je n'avais pas fait gaffe, mais ce paragraphe est totalement
faux. La denombrabilite a tout a voir avec le nombre d'elements de
l'ensemble, ou plus exactement la possibilite d'etablir une bijection
entre l'ensemble et N (avec ou sans axiome du choix, pour les
puristes... et avec ou sans tiers exclu pour les fans de logique
intuitioniste).

Toutafé d'accord jusque là (d'ailleurs j'avais dit la même chose il y a
deux messages).

Le fait d'avoir un successeur, c'est deja une structure algebrique, et
c'est une propriete totalement differente.

Alors là par contre, pas entièrement.

Je peux parfaitement te
fabriquer une structure sur R qui fait que tout element aura un
successeur

Bien sûr, mais si en plus tu veux une opération successeur qui ait
certaines propriétés, ça ne sera pas possible. Plus précisément, si E
est un ensemble muni d'une application succ E -> E et d'un élément e tel
que la plus petite partie de E qui contienne e et qui soit stable par
succ soit E, alors E est en bijection avec l'ensemble des entiers
naturels N.

Comme quoi, l'existence d'une structure algébrique particulière n'a pas
rien à voir avec le cardinal de l'ensemble sous-jacent...

Pour en revenir à ce que disait Laurent :

dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer

Là où il y a peut-être une confusion, c'est qu'être dénombrable ça veut
dire qu'il existe une bijection avec N, donc un notion de successeur
ayant la propriété énoncée ci-dessus, pas que cette notion de successeur
est donnée de façon naturelle. Pour revenir à l'ensemble des types du C,
bien sûr qu'il n'y a pas de notion « naturelle » (et encore moins
sémantique) de successeur d'un type, ça n'empêche pas cet ensemble
d'être dénombrable. (On peut dire la même chose de Q.)

(discret vs continu).

Je l'ai déjà dit sur fclc, je le répète sur fsm, je pense qu'on devrait
réserver les mots discret et continu à la topologie. Appelons un chat un
chat, quand on peut dire « fini ou dénombrable » (ce qui est clair et
non ambigu) je ne vois pas de raison de dire « discret », pas plus que de
dire « continu » pour dire « infini non dénombrable ».

Certes il y a des expressions classiques qui utilisent cette
terminologie (« hyptohèse du continu ») mais je trouve que ça
embrouille inutilement de sortir ça à toutes les sauces.

--
Manuel Pégourié-Gonnard Institut de mathématiques de Jussieu
http://weblog.elzevir.fr/ http://people.math.jussieu.fr/~mpg/

[Cross-post fclc + fsm, suivi fsm]

Suite à une réflexion sur l'ensemble des types du langage C qui est
infini, on en vient à parler de dénombrabilité, sujet qui semble prêter
à quelques confusions.

Marc Espie scripsit:

In article
<9629865c-0e4d-474e-95c3-76942f98d2e5@s12g2000yqi.googlegroups.com>,
ld <Laurent.Deniau@gmail.com> wrote:

dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer
(discret vs continu).

Tiens, je n'avais pas fait gaffe, mais ce paragraphe est totalement
faux. La denombrabilite a tout a voir avec le nombre d'elements de
l'ensemble, ou plus exactement la possibilite d'etablir une bijection
entre l'ensemble et N (avec ou sans axiome du choix, pour les
puristes... et avec ou sans tiers exclu pour les fans de logique
intuitioniste).

Toutafé d'accord jusque là (d'ailleurs j'avais dit la même chose il y a
deux messages).

Le fait d'avoir un successeur, c'est deja une structure algebrique, et
c'est une propriete totalement differente.

Alors là par contre, pas entièrement.

Je peux parfaitement te
fabriquer une structure sur R qui fait que tout element aura un
successeur

Bien sûr, mais si en plus tu veux une opération successeur qui ait
certaines propriétés, ça ne sera pas possible. Plus précisément, si E
est un ensemble muni d'une application succ E -> E et d'un élément e tel
que la plus petite partie de E qui contienne e et qui soit stable par
succ soit E, alors E est en bijection avec l'ensemble des entiers
naturels N.

Comme quoi, l'existence d'une structure algébrique particulière n'a pas
rien à voir avec le cardinal de l'ensemble sous-jacent...

Pour en revenir à ce que disait Laurent :

dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer

Là où il y a peut-être une confusion, c'est qu'être dénombrable ça veut
dire qu'il existe une bijection avec N, donc un notion de successeur
ayant la propriété énoncée ci-dessus, pas que cette notion de successeur
est donnée de façon naturelle. Pour revenir à l'ensemble des types du C,
bien sûr qu'il n'y a pas de notion « naturelle » (et encore moins
sémantique) de successeur d'un type, ça n'empêche pas cet ensemble
d'être dénombrable. (On peut dire la même chose de Q.)

(discret vs continu).

Je l'ai déjà dit sur fclc, je le répète sur fsm, je pense qu'on devrait
réserver les mots discret et continu à la topologie. Appelons un chat un
chat, quand on peut dire « fini ou dénombrable » (ce qui est clair et
non ambigu) je ne vois pas de raison de dire « discret », pas plus que de
dire « continu » pour dire « infini non dénombrable ».

Certes il y a des expressions classiques qui utilisent cette
terminologie (« hyptohèse du continu ») mais je trouve que ça
embrouille inutilement de sortir ça à toutes les sauces.

--
Manuel Pégourié-Gonnard Institut de mathématiques de Jussieu
http://weblog.elzevir.fr/ http://people.math.jussieu.fr/~mpg/

Vous avez filtré cet utilisateur ! Consultez son message

[Cross-post fclc + fsm, suivi fsm]

Suite à une réflexion sur l'ensemble des types du langage C qui est
infini, on en vient à parler de dénombrabilité, sujet qui semble prêter
à quelques confusions.

Marc Espie scripsit:

In article
,
ld wrote:
dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer
(discret vs continu).

Tiens, je n'avais pas fait gaffe, mais ce paragraphe est totalement
faux. La denombrabilite a tout a voir avec le nombre d'elements de
l'ensemble, ou plus exactement la possibilite d'etablir une bijection
entre l'ensemble et N (avec ou sans axiome du choix, pour les
puristes... et avec ou sans tiers exclu pour les fans de logique
intuitioniste).

Toutafé d'accord jusque là (d'ailleurs j'avais dit la même chose il y a
deux messages).

Le fait d'avoir un successeur, c'est deja une structure algebrique, et
c'est une propriete totalement differente.

Alors là par contre, pas entièrement.

Je peux parfaitement te
fabriquer une structure sur R qui fait que tout element aura un
successeur

Bien sûr, mais si en plus tu veux une opération successeur qui ait
certaines propriétés, ça ne sera pas possible. Plus précisément, si E
est un ensemble muni d'une application succ E -> E et d'un élément e tel
que la plus petite partie de E qui contienne e et qui soit stable par
succ soit E, alors E est en bijection avec l'ensemble des entiers
naturels N.

Comme quoi, l'existence d'une structure algébrique particulière n'a pas
rien à voir avec le cardinal de l'ensemble sous-jacent...

Pour en revenir à ce que disait Laurent :

dénombrable veut dire qu'on peut les compter ou autrement dit, trouver
le successeur d'un élément. Ca n'a rien à voir avec le nombre
d'éléments de l'ensemble, mais avec la possibilité de les énumérer

Là où il y a peut-être une confusion, c'est qu'être dénombrable ça veut
dire qu'il existe une bijection avec N, donc un notion de successeur
ayant la propriété énoncée ci-dessus, pas que cette notion de successeur
est donnée de façon naturelle. Pour revenir à l'ensemble des types du C,
bien sûr qu'il n'y a pas de notion « naturelle » (et encore moins
sémantique) de successeur d'un type, ça n'empêche pas cet ensemble
d'être dénombrable. (On peut dire la même chose de Q.)

(discret vs continu).

Je l'ai déjà dit sur fclc, je le répète sur fsm, je pense qu'on devrait
réserver les mots discret et continu à la topologie. Appelons un chat un
chat, quand on peut dire « fini ou dénombrable » (ce qui est clair et
non ambigu) je ne vois pas de raison de dire « discret », pas plus que de
dire « continu » pour dire « infini non dénombrable ».

Certes il y a des expressions classiques qui utilisent cette
terminologie (« hyptohèse du continu ») mais je trouve que ça
embrouille inutilement de sortir ça à toutes les sauces.

--
Manuel Pégourié-Gonnard Institut de mathématiques de Jussieu
http://weblog.elzevir.fr/ http://people.math.jussieu.fr/~mpg/

Jean-Marc Bourguet

17/06/2009 à 18:05

Antoine Leca writes:

Le 16/06/2009 16:45, Jean-Marc Bourguet écrivit :
En fait, c'est probablement ce qui est implémenté dans un compilateur
qui saurait mixer C et Ada (où le langage requiert que le système
vérifie les indices par rapport aux limites à chaque utilisation).

Pas nécessairement.

Pas nécessairement quoi ?

Du fait qu'implémenter les vérifications demandées par Ada aiderait à faire
un compilateur C qui validerait au runtime. Les règles de validités du C
sont bien différentes de celles d'Ada (en supposant qu'il n'y a pas
d'ambiguité sur ce qui est permis ou pas en C).

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Lucas Levrel

18/06/2009 à 10:06

Le 16 juin 2009, Jean-Marc Bourguet a écrit :

Gcc a (eu?) quelque chose du genre, peut-être uniquement dans une branche.

man gcc :

-fbounds-check
For front-ends that support it, generate additional code to
check that indices used to access arrays are within the
declared range. This is currently only supported by the Java
and Fortran front-ends, where this option defaults to true and
false respectively.

--
LL

candide

18/06/2009 à 23:08

Marc Espie a écrit :

Le fait d'avoir un successeur, c'est deja une structure algebrique, et c'est

Ça dépend ce que tu entends par "successeur". A mon avis, la notion de
"successeur" dans N préexiste à la définition des opérations algébriques sur N,
comme l'addition. Souvent, on définit N par la notion de successeur, de mémoire,
ça donne :

0 comme l'ensemble vide,
puis 1 comme l'ensemble {vide}
puis 2 comme 1 union {1} et donc 2={vide,{vide}}
et plus généralement le successeur de x (déjà défini) comme x+=x union {x}.

Si on a un ensemble E muni d'une relation R (autrement dit un graphe orienté),
on peut facilement définir la notion de successeur d'un élément x de E en disant
qu'il s'agit de n'importe quel élément y tel que x R y et pour lequel il
n'existe aucun élément z distinct de x ou y tel que x R z et z R y (imaginer une
arborescence par exemple : tous les éléments sauf les feuilles ont un "successeur").

N dote de son successeur habituel, et [0,1[ dote de la topologie triviale ou
tout point est isole).

"Topologie triviale" je vois pas ce que c'est (par contre topologie grossière
OK, topologie discrète OK). "Point isolé " : je vois pas ce que tu veux dire. En
topologie, quand on parle d'un point "isolé" c'est par rapport à une partie, par
exemple chaque élément de N est un point isolé de N pour la topologie usuelle sur R.

Tableaux multidimensionnels et déréférencement

10 réponses

Veuillez sélectionner un problème