Recherche:

Ah bon ? lol. Je trouve qu'un million de dollars c'est pas assez payé pour celui qui demontrerait NP egal ou different de P !!



Tout a fait, il faut juste faire attention au cout de la...

Dans le cas du probleme de fredschmidt, on est d'accord que l'algo Pseudocode est plutot bien adapté et simple.

Mais je pense qu'il faut tout de meme preciser, que lister les configurations...

Bonjour,

tout d'abord je tiens a preciser que le probleme de bin packing 1D n'est pas le meme probleme que celui du sac a dos 1D (meme s'il existe un lien forte entre ces deux problemes)!!!
En...

C'est clairement un probleme de bin packing en 1 dimension. Suivant l'echelle de temps que tu veux laisser au programme (plutot de l'ordre de la milliseconde, seconde, minute... ?) et du nombre de...

+1 :ccool:
pour une fois (ou plutot les rares fois) qu'un probleme de la "realite" est suffisament simple pour etre mis sous forme de systemes lineaire et qui plus est avec seulement deux...

L'algorithme supreme qui bat tous les autres algorithmes sur toutes les instances de problemes possibles... ca n'existe pas (ca se saurait sinon). Dans ton cas, si j'ai bien compris tu as identifié...

Bonjour,

je pense que ce que Alp veut dire c'est que le probleme que tu poses ne porte pas sur les algorithmes eux meme (un algorithme n'est pas le code source, c'est une méthode pour resoudre ton...

Bonjour,

alors si on chipote comme ca (meme si sur le fond je suis d'accord avec millie pour dire qu'une complexité lineaire ne veut rien dire si on ne dit pas en quel parametre), on devrait...

En fait, la matiere que tu aborderas a la fac fera certainement le lien entre automates, grammaires et langages.

Une grammaire definira un langage lequel sera représenté par un automate a etat...

Bonjour a tous,

je pense que deja on est imcapable de dire si un probleme requiert de l'intelligence ou pas pour etre resolu car l'intelligence reste a definir (du moins de facon plus formelle)....

Bonjour,

est ce que ta liste peut contenir n'importe quel entier ou bien tu connais le maximum qu'elle puisse avoir ??

Si oui et que ce maximum n'est pas "trop grand" alors il y a un moyen...

Ok donc c'est dejà plus clair (enfin pour moi).
Le problème de vouloir utiliser des algos dejà existant c'est que tu as une contrainte que je n'ai pas vu souvent qui est de ne pas avoir de trou dans...

Ton problème est assez spécifique et donc peut être il serait interessant d'utiliser sa spécificité pour améliorer des algos déjà existants qui traitent le cas général (cas ou l'on a des rectangles...

Bonjour,

saches que ce probleme est NP-Difficile, c'est à dire qu'il n'existe pas d'algorithme (connu) polynomial pour le résoudre (que des algorithmes exponentiels).
Dans ton cas, à quel...

Moi j'aurais plutot dis qu'un formalisme est un langage particulier servant à décrire mathématiquement un objet (graphe,...) qui lui meme est censé représenté un type de connaissance alors que la...

il faut savoir aussi que la facon dont est ecrit l'algo peut influer enormement sur la preuve. Deux algo semantiquement equivalents mais syntaxiquement differents peuvent avoir des preuves...

Il est vrai qu'en pratique c'est impossible. Toutefois, je pense que dans son cas, c'est un exercice de devoir démontrer que son algo est correct.

Non dans cet algo c'est bien a=B*Q+R l'invariant mais la ya 2 parametres qui changent dans la boucle, c'est R et Q et ils changent de sorte a garder a=B*Q+R vrai.

Alors que dans l'invariant que tu...

Bon deja, le fait de mettre un Si plutot que Tant Que, c'est bien mieux (je sais pas si c'est juste par rapport au calcul que tu veux faire mais au moins t'as plus de boucle infinie...).

Ca...

Oui mais imagine tu rentre dans la boucle Tant Que, dans cette boucle, seuls r et c sont modifiés donc le test d<>1 sera toujours vrai et tu n'en sortira jamais !!! Le seul endroit ou d est modifié...

Bon, dejà pour etre clair, est ce que c'est :

r=(a^(t+1))/2 mod p
ou bien
r=a^((t+1)/2) mod p

pour savoir si le 2 est dans la puissance ou c'est le tout sur 2 ?

Ensuite ou se termine ta...

Si t'arrives vraiment pas a voir, montre nous ton algo, dis nous ce que tu pense etre un invariant.

Salut,

a noter que ton invariant de boucle est une propriété qui doit etre vraie à 4 endroits :

- Avant de rentrer dans la boucle
- Au début de la boucle
- A la fin de la boucle...

Salut,

ta configuration initiale :
(11, 13, 10, 1, 4, 12, 2, 15, 6, 0, 5, 9, 3, 7, 8, 14)

permutations pour arriver à la solution :

(11, 13, 10, 1, 4, 12, 2, 15, 6, 14, 5, 9, 3, 7, 8, 0)...

et puis à préciser que la profondeur n'est pas le seul critère à prendre en compte, il y a aussi le facteur de branchement, c'est-à-dire combien de coups possibles à chaque fois? (pour le puissance...