Forum de mathématiques - Bibm@th.net

fabricen26

Membre

Inscription : 25-11-2009

Messages : 47

Nombre de ramsey

Salut a vous

j'ai un projet celui d’écrire un programme en matlab ou en c++ qui pour 2 entiers n,k m'affiche R(n,k) si cela existe ou ses bornes
par exemple R(3,4)=9
n=5 k=5   42<R(5,5)<49
et je n'arrive pas a démarrer

Merci de me donner quelques indications  pour arriver a réaliser ce projet

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombre de ramsey

Bonjour,

J'aurais bien voulu essayer, mais :
1. Je ne connaissais pas ces "nombres de Ramsey", ni donc la manière de les calculer
2. J'ai trouvé  ici  ceci :

Le théorème de Ramsey

Le théorème de Ramsey est l'inégalité [tex]R(m,n) \leq R(m-1,n) + R(m,n-1[/tex]) qui montre en particulier que ces nombres sont bien définis. Les premiers termes sont plutôt facile à calculer, cependant la plupart d'entre eux restent encore inconnus !
Le plus petit de ces nombres et qui restent inconnus à l'heure actuelle est [tex]R(5,5)[/tex]. Les autres sont donnés dans le tableau suivant :

 \ n |  1    2    3    4    5
m \ |  
----|----------------------------
1   |  1    1    1    1    1
2   |  1    2    3    4    5
3   |  1    3    6    9   14
4   |  1    4    9   18   25
5   |  1    5   14   25   ?

qui ne m'apprend pas à calculer l' encadrement...
Si je sais faire ça "à la main" (je vais y réfléchir, mais si tu m'expliques ça on gagnera du temps), écrire un prog ne devrait pas être difficile.

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombre de ramsey

Re,

J'ai trouvé autre chose, là cette fois :

(...)Selon le combinatoriste W. Gowers, qui a reçu la médaille Field en 1998, une amélioration des inégalités

[tex]2^{\frac k 2}<  R(k) < 2^{2k}[/tex]

serait de grande importance, non pas tant pour ses conséquences directes que parce que de nouvelles méthodes
devraient être dégagées et mises en œuvre. (...)

J'avais pensé que k ici valait m+n dans l'écriture R(m,n), et j'ai vu que c'était inexact.
Par contre, en examinant le tableau je constate que R(m,n) = R(n,m).
Donc qu'est-ce que k ?

Question programmation.
1. Je créerais un tableau (ou matrice carrée si tu veux) de dimension 5 x 5 où les m et désigneraient lignes et colonnes, dans lequel je rentrerais les valeurs connues.
2. Je demanderais ensuite à l'utilisateur de rentrer m et n, avec contrôle d'erreurs : pas de nombres décimaux, pas de nombres négatifs... pas autre chose que des entiers naturels.
3. Ensuite toutes vérifications faites, je monterais une structure conditionnelle du type
    SI m <6 ET n < 6
         SI m =5 ET n = 5
                calcul encadrement + affichage
         SINON
                lecture R[m,n] et affichage
    SINON
           calcul encadrement + affichage

Petite question
Si j'en crois ce que j'ai lu du théorème Ramsey, alors [tex]R(5,5)\leq R(4,5)+R(5,4)[/tex]
soit [tex]R(5,5)\leq 50[/tex], pourquoi écris-tu donc R(5,5) <49 ?

@+

jdec

Invité

Re : Nombre de ramsey

Bonjour,

Vous allez vous lancer dans les algorithmes probabilistes ?

Anecdote sur les nombres de Ramsey :
Paul Erdos disait : "Imaginez une force extraterrestre, vigoureuse et plus puissante que nous qui atterrit et demande la valeur de R(5, 5) où sinon ils détruiront notre planète. Dans ce cas, nous devrions regrouper l'ensemble des ordinateurs et tous nos mathématiciens pour trouver la valeur. Mais supposons, par contre, qu'ils demandent la valeur R(6, 6), nous devrions alors tenter de détruire les extraterrestres."

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombre de ramsey

Bonjour,

Amusant...
Mais ça ne répond pas à mon questionnement !

@+

tibo

Membre expert

Inscription : 23-01-2008

Messages : 1 097

Re : Nombre de ramsey

Bonjour,

Je ne connaissaient pas les nombre de Ramsey non plus.
Je viens de me renseigner dessus (Wikipedia donne une explication succincte mais assez claire pour appréhender ces nombres).
Ca a l'air vraiment très intéressant, je vais me pencher dessus.

Mais je serais toujours étonné par la capacité qu'ont certaines personnes à inventer des théories aussi ...étranges et farfelues.
Là on pourrait la résumer en "Quelle est la taille minimum d'un truc pour qu'il y ait un machin?"

fabricen26

Membre

Inscription : 25-11-2009

Messages : 47

Re : Nombre de ramsey

Bonjour

Tibo ces nombres sont tres étranges et cette theorie est vraiment magique!!!

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Nombre de ramsey

Bonjour,

A mon tour, Fabricen26, je t'ai posé des questions, peux-tu y répondre s'il te plaît ?

Merci

@+

fabricen26

Membre

Inscription : 25-11-2009

Messages : 47

Re : Nombre de ramsey

Bonjour
Navre pour le retard Yoshi
dans les nombres de ramsey R(k)=R(k k). En ce concerne la majoration tu as bien raison d'applique le theoreme de Ramsey qui donne R(5,5)≤50 on a pu réduire cette majoration et avoir R(5,5)≤49 tu pourra ici voir le tableau http://www.emis.de/journals/EJC/Surveys/ds1.pdf page 4