Défis informatiques

  • Initiateur de la discussion Initiateur de la discussion Waroc
  • Date de début Date de début
I: Generate and Test
-------------------------------

On genere chaque combinaison possible, puis on verifie
pour chaque combinaison si les dames ne se menacent pas
respectivement.

Pour chaque ligne i, Xi represente la colonne ou placer la dame.
Ou, dit autrement, chaque dame est placee aux coordonnees (i,Xi).

Code: 
eight_queens([X1,X2,X3,X4,X5,X6,X7,X8]) :-
    permutation([X1,X2,X3,X4,X5,X6,X7,X8], [1,2,3,4,5,6,7,8]),
    safe([X1,X2,X3,X4,X5,X6,X7,X8]).

Pour generer les permutations:

Code: 
permutation([],[]).
permutation([X|Xs], Ls) :-
    delete(X,Ls,Rs),
    permutation(Xs,Rs).

delete(X,[X|Xs],Xs).
delete(X,[Y|Ys],[Y|Rs]) :-
    delete(X,Ys,Rs).

Pour verifier que les dames ne se menacent pas:

Code: 
safe([]).
safe([X|Xs]) :-
    noattack(X,Xs),
    safe(Xs).

Les dames ne se menacent pas, si elles sont sur des colonnes
differentes (elles sont avec la representation d'une liste [X1,...,X8]
forcement sur des lignes differentes), et si elles ne sont pas sur
des diagonales:

Code: 
noattack(X,Xs) :-
    noattack(X,Xs,1).

noattack(X,[],Nb).
noattack(X,[Y|Ys],Nb) :-
    X =\= Y - Nb,
    X =\= Y + Nb,
    Nb1 is Nb + 1,
    noattack(X,Ys,Nb1).

On peut aussi utiliser une strategie de backtracking classique au lieu de
Generate and Test:

Code: 
eight_queens(X) :-
    queens(X,[],[1,2,3,4,5,6,7,8]).

queens([],Placed,[]).
queens([X|Xs],Placed,Values) :-
    delete(X,Values,New_values),
    noattack(X,Placed),
    queens(Xs,[X|Placed],New_values).

(La suite plus bas)
 
II. Constrain and Generate:
--------------------------------------

On quitte le standard Prolog ici en utilisant la bibliotheque clpfd:

Code: 
:- use_module(library(clpfd)).

queens(N, L, Lab, Const) :-
    length(L, N),
    domain(L, 1, N),
    safe(L, Const),
    labeling(Lab, L).

safe([], _Const).
safe([X|L], Const) :-
     noattack(L, X, 1, Const),
     safe(L, Const).

noattack([], _, _, _Const).
noattack([Y|L], X, I, Const) :-
     diff(Const, X, Y, I),
     I1 is I + 1,
     noattack(L, X, I1, Const).

Pour le predicat diff/4 restant:

Code: 
diff(clpfd, X, Y, I) :-
    X #\= Y,
    X #\= Y+I,
    X+I #\= Y.

Exercice: paufiner cette ebauche pour que ca fonctionne avec SWI-Prolog.

Une solution plus complete ici.
 
farid_h a dit:
Okay @Kuzan, je precise:

Resoudre le probleme des 8 (ou N) dames en Prolog, en utilisant:

1. generate and test
2. constrain and generate.

Sans Google. Je suggere SWI-Prolog comme systeme de developpement.

Il faut etre en mesure d'expliquer exactement le code et l'algorithme.
Cliquez pour agrandir...
Ca serai plus drole de trouver la solution avec le plus petit bout de code
On s'en fou de la lisibilité faut que ça marche c'est tout :D
 
Kuzan a dit:
Ca serai plus drole de trouver la solution avec le plus petit bout de code
On s'en fou de la lisibilité faut que ça marche c'est tout :D
Cliquez pour agrandir...
Ce qui est amusant avec Prolog, c'est qu'on a pas besoin de coder le depth first search; c'est Prolog qui s'en occupe. Il suffit de definir logiquement le but a atteindre et les contraintes a respecter.

Okay, Prolog est un langage tres inhabituel et non-conventionnel. C'est pas imperatif, c'est pas (purement) fonctionnel, c'est une langue declarative. Un peu comme VHDL et autres langues descriptives.
 
Avec la vague Big Data, l’exploitation des données en entreprise est devenu une véritable source d’avantage concurrentiel. En tant que responsable de la valorisation de ces données, le profil de data-scientist est une perle rare. D’après McKinsey, il en manquerait déjà près de 200 000 aux Etats-Unis seulement, et ce chiffre pourrait dépasser le million d’ici 2017. Si les formations Big Data « officielles » commencent à voir le jour en France, les MOOCs sont aujourd’hui le moyen privilégié par beaucoup pour s’auto-former à la Data-Science. - See more at: http://www.data-business.fr/guide-m...-devenir-data-scientist/#sthash.DfuS5aWg.dpuf
 
farid_h a dit:
Factoriser un nombre de, disons, 100 chiffres en nombres premiers. Methode:

http://fr.wikipedia.org/wiki/Crible_quadratique

Logiciel pour long nombres:

https://gmplib.org/

@Waroc, @Nalinux?

(Bien sur qu'on peut utiliser qsieve() de Sagemath, mais c'est plus instructif de coder l'algorithme directement)
Cliquez pour agrandir...
C est méchant la.
J ai pas mal perdu le niveau en math. Mon Bac D ca date de 1986 :)
Encore un truc ou le premier problème pour moi c est de comprendre la question ...
Je connait bien Pierre de Fermat. Il est né dans la ville natale de ma grand mère et il y a sa statue en pierre devant la mairie, sur la place centrale :p
C est a 30 mètres du marchand d articles de pêche M. Arquier et du Café des Sports
C est a peu près tout ...

$ pkg rquery %e gmp
GMP is a free library for arbitrary precision arithmetic, operating
on signed integers, rational numbers, and floating point numbers.
There is no limit to the precision except the ones implied by the
available memory in the machine GMP runs on. GMP has a rich set of
functions, and the functions have a regular interface.

Je suppose que dans un langage simple comme shell ou tcl ca doit pas être adapté avec 100 chiffres :)
 
Déjà, faut arriver a compiler l exemple de la page de GMP, le truc pour calculer Pi ...

https://gmplib.org/pi-with-gmp.html

Ça fait des années que je n ai pas touché au C.
Après modif du source pour indiquer le chemin

//#include <gmp.h>
#include "/usr/local/include/gmp.h"

Ça m insultait ..
Soluce : lignes trop longues, il faut passer l option -lm au compilateur.

gcc48 -Wall -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm
 
Nalinux a dit:
Déjà, faut arriver a compiler l exemple de la page de GMP, le truc pour calculer Pi ...

https://gmplib.org/pi-with-gmp.html

Ça fait des années que je n ai pas touché au C.
Après modif du source pour indiquer le chemin

//#include <gmp.h>
#include "/usr/local/include/gmp.h"

Ça m insultait ..
Soluce : lignes trop longues, il faut passer l option -lm au compilateur.

gcc48 -Wall -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm
Cliquez pour agrandir...


Tu peux faire directement

Code: 
#include <gmp.h>

si tu dis a gcc ou trouver les include-fichiers:

Code: 
$ gcc48 -Wall -o gmp-chudnovsky -I/usr/local/include \
              -L/usr/local/lib gmp-chudnovsky.c -lgmp -lm

T'as essaye avec clang ou clang++ au lieu de gcc48?
 
Dernière édition:
farid_h a dit:
Tu peux faire directement

Code: 
#include <gmp.h>

si tu dis a gcc ou trouver les include-fichiers:

Code: 
$ gcc48 -Wall -o gmp-chudnovsky -I/usr/local/include \
              -L/usr/local/lib gmp-chudnovsky.c -lgmp -lm

T'as essaye avec clang ou clang++ au lieu de gcc48?
Cliquez pour agrandir...
C est plus propre avec -I /usr/local/include en effet :)
clang et clang++ sont pas contents, mais cpp veut bien.
C est un détail.
Trop longtemps que j ai pas touché a du C, et je n ai jamais été bon la dedans :)

Me suis penché sur le pb, et c est pas évident ... J ai pas le niveau en math :(
J ai déjà du mal a comprendre les modulo, ça va mal :)
 
Nalinux a dit:
C est plus propre avec -I /usr/local/include en effet :)
clang et clang++ sont pas contents, mais cpp veut bien.
C est un détail.
Trop longtemps que j ai pas touché a du C, et je n ai jamais été bon la dedans :)

Me suis penché sur le pb, et c est pas évident ... J ai pas le niveau en math :(
J ai déjà du mal a comprendre les modulo, ça va mal :)
Cliquez pour agrandir...
Je vais chercher un tuto la dessus...
 
Bon, pour simplifier l'exercice, on peut commencer en programmant une petite calculette pour nombres a precision illimites, c.a.d. avec gmp. Integers illimites suffisent. +, *, -, /, =, !=, <, >, et mod. Et bien sur lire et afficher ces nombres, par ex. a partir de std::string. Apres ca, on continue avec le QS.

@Nalinux, tu peux aussi utiliser le port math/cln au lieu de gmp sous FreeBSD:

http://www.freshports.org/math/cln

Documentation: http://www.ginac.de/CLN/cln.html
 
Dernière édition:
La je regarde Jacques Grimault sur Meta TV :)

Mon pb actuel n est pas un pb de programme, gmp ou un autre, c est de comprendre le problème lui même :)
La syntaxe et les outils, c est un simple détail ensuite.
 
Chaque nombre entier est ou bien un nombre premier, ou c'est un nombre compose d'un produit de nombres premiers. Par exemple, 17 est un nombre premier, mais 15 = 3*5 est un nombre compose du produit des deux nombres premiers 3 et 5.

Le probleme consiste a trouver les facteurs premiers qui composent un nombre n. Prends par exemple deux grands nombres premiers p et q et definis: n := p*q. Si tu n'as que n, comment trouver p et q? Bien sur, on peut diviser n successivement par tous les nombres premiers < n (trial division), mais si p et q sont tres grands, par exemple 45 chiffres chacuns, tu peux t'imaginer que la factorisation va durer tres longtemps.

Il y a des methodes comme le QS qui sont beaucoup plus rapides que trial division, tant que n a moins de 100 chiffres. S'il y a plus que 130 chiffres et si n a certaines proprietes supplementaires, on peut utiliser une methode plus complexe (number field sieve), mais meme la, a partir d'un certain nombre de chiffres, ce n'est plus pratique.

La difficulte de factoriser n = pq pour de tres grands n est ce qui rend des algorithmes cryptographiques comme Diffie-Hellman et RSA possible. Si c'etait facile de trouver p (et q), RSA et tous les algorithmes qui n'utilisent pas elliptic curves seraient broken. D'ou l'interet de factoriser de grands nombres dans un temps sous-exponnentiel.
 
Oué, j ai compris le principe de base pour la factorisation.
C est le truc du calcul et ranger ça dans des matrices qu il faut que je potasse.

La méthode force brute qui consisterai a trouver les nombres premiers < n et diviser pour voir si c est un multiple, j y arriverai, c est pas compliqué.
Mais c est lourd pour 100 chiffres dans le nombre :)
 
Nalinux a dit:
farid_h m a tuer.
:bizarre:
Cliquez pour agrandir...
mdr... :D

C'est pour ca que j'ai suggere de commencer avec une calculette... le reste viendra plus tard.

Bien evidament, c'est un defis et non un simple exercice. On fait en principe et en petit, ce que la NSA et autres serieux code-breakers ont fait avec des supercomputers il y a 10 ans. C'est de la veritable recherche mathematique, empirique et theorique. Maintenant, la theorie est developpee (pour ce defis), mais l'empirique fait parti du jeu.
 
madalena a dit:
salam

vous utiliser quoi pour faire des calculs sur bladi?
Cliquez pour agrandir...
Pour faire le genre de calculs dont on parle ici, on a besoin de calculettes qui fonctionnent avec des nombres de milliers de chiffres. Pour ca, on utilise des logiciels specialises en grand nombres (bignums, pour big numbers).

On peut par exemple utiliser des programmes comme Maple, Mathematica, mais ceux la ne sont pas gratuits. Gratuits sont par contre maxima, sagemath, etc... qui calculent avec ces bignums.

Si on veut programmer avec ces bignums, on peut utiliser des languages de programmation qui sont capables d'operer sur des bignums comme par ex. Common Lisp, ou on utilise des bibliotheques specialises avec des languages comme C et C++, par ex. gmp ou cln que j'ai mentionne plus haut. L'article sur le decryptage de RSA mentionne aussi la Bignum-Bibliotheque BN du programme openssl.

Il y a plein d'autres possibilites pour calculer avec ces nombres geants. ;)
 
farid_h a dit:
Pour faire le genre de calculs dont on parle ici, on a besoin de calculettes qui fonctionnent avec des nombres de milliers de chiffres. Pour ca, on utilise des logiciels specialises en grand nombres (bignums, pour big numbers).

On peut par exemple utiliser des programmes comme Maple, Mathematica, mais ceux la ne sont pas gratuits. Gratuits sont par contre maxima, sagemath, etc... qui calculent avec ces bignums.

Si on veut programmer avec ces bignums, on peut utiliser des languages de programmation qui sont capables d'operer sur des bignums comme par ex. Common Lisp, ou on utilise des bibliotheques specialises avec des languages comme C et C++, par ex. gmp ou cln que j'ai mentionne plus haut. L'article sur le decryptage de RSA mentionne aussi la Bignum-Bibliotheque BN du programme openssl.

Il y a plein d'autres possibilites pour calculer avec ces nombres geants. ;)
Cliquez pour agrandir...


salam

ok! merci..tu peux me passer les logiciel gratuit stp?^^
 
Retour
Haut