Algo

[ théorie ] - L'algorithme le plus balèze que vous connaissez ?

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [ théorie ] - L'algorithme le plus balèze que vous connaissez ?

usa_satriani

S.P.Q.R.

Reprise du message précédent :
les algo de tri normo sont en n*log(n) non?

Publicité

nraynaud

lol

ciler a écrit :

Ca me rappelle Niels Bohr (physicien). Pendant un oral on lui demande "Comment mesurer la hauteur d'un immeuble avec un barometere ?" Et lui de repondre... On monte en haut de l'immeuble, on laisse tomber le baro et on mesure le temps qu'il met pour arriver en bas [:ddr555]

pour une bonne tranche de rigolade, quelques méthodes de mesure :
http://www.snopes.com/college/exam/barometr.htm

Notsukaw

Be Aware

ciler a écrit :

[:rofl]

Message édité par Notsukaw le 29-03-2003 à 15:58:58

---------------
[ Canon EOS 30D ] (Grip + Canon 50mm f/1.4 + Canon 18-55mm USM + Tamron 70-300mm Di LD Macro) [Galerie perso]

EpoK

Let's burn

mc carthy

Phod

Glouloulou ?

Je me suis bien pris la tete pour faire un prog capable de resoudre des simplex en maths (mon pb qui ne m'a pas facilité la tache etait aussi que j'avais pas tout bien compris au simplex...)

---------------
Signatures aux choix Votez: O - Le python c'est bon, mangez-en O - L'abus de forum rend dependant, postez avec modération

theshockwave

I work at a firm named Koslow

J'en ai parlé sur un autre thread ...

L'algo qui m'a scié, je l'ai trouvé sur http://remus.rutgers.edu/~rhoads/Code/code.html

C'est l'algo nommé hanoi ...

Version itérative pour la solution au fameux problème des tours de hanoi ... La 'présentation' de l'algo est elle-même assez impréssionante ...

supertimor2k

j'ai tjrs rien pigé au tour de hanoi :heink: mais j'ai pas trop chercher non plus :sarcastic:
c t la conclusion de mon cours sur la recursivité...

dweis

un algo qui doit être bien sympas mais malheureusement le source est pas libre : http://www.onversity.com/cgi-bin/p [...] &P=N200304 sur les pages du site, tout le texte est analysé en temps réel et sur les mots faisant partie d'un dico (de pl. centaines de mot apparement) un lien vers la définition se crée.

si vous avez les sources d'un algo similaire ça m'intéresse...

peak

fonction d'Ackermann :

[cpp]int Ackermann(int m, int n ){
if (m==0) return n+1;
else{
if(n==0) return Ackermann(m-1, 1);
else
return Ackermann (m-1, Ackermann(m, n-1));
}
}[cpp]

je ne retrouve plus la solution numérique pour m=4 n=2 mais c'tai deja un truc de tarré!!!

C'est une fonctions qui crois MEGA vitte...elle m'avai choqué kand j'étai tombé dessus :sarcastic:

Pour bien fair faudrai que je la dérécurcifie par ce ke là ça m'étonnerai k'un de vous puisse se le permettre une telle profondeur de stack

Taz

bisounours-codeur

je crois qu'on a jamais calculé plus loin de 4,2

edit CQFD
http://pw1.netcom.com/~hjsmith/Ackerman/Acker2L.html

Message édité par Taz le 28-05-2003 à 12:31:11

Publicité

minusplus

le Mersenne Twister : un générateur de nombres pseudo-aléatoires de période 2^19937-1 (oui, oui, vous avez bien lu ! ) et équidistribué jusqu'en 623 dimensions (ui, ui) !

le tout là dedans :

Code :

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long uint32;
#define N (624) // length of state vector
#define M (397) // a period parameter
#define K (0x9908B0DFU) // a magic constant
#define hiBit(u) ((u) & 0x80000000U) // mask all but highest bit of u
#define loBit(u) ((u) & 0x00000001U) // mask all but lowest bit of u
#define loBits(u) ((u) & 0x7FFFFFFFU) // mask the highest bit of u
#define mixBits(u, v) (hiBit(u)|loBits(v)) // move hi bit of u to hi bit of v
static uint32 state[N+1]; // state vector + 1 extra to not violate ANSI C
static uint32 *next; // next random value is computed from here
static int left = -1; // can *next++ this many times before reloading
void seedMT(uint32 seed)
{
register uint32 x = (seed | 1U) & 0xFFFFFFFFU, *s = state;
register int j;
for(left=0, *s++=x, j=N; --j;
*s++ = (x*=69069U) & 0xFFFFFFFFU);
}
uint32 reloadMT(void)
{
register uint32 *p0=state, *p2=state+2, *pM=state+M, s0, s1;
register int j;
if(left < -1)
seedMT(4357U);
left=N-1, next=state+1;
for(s0=state[0], s1=state[1], j=N-M+1; --j; s0=s1, s1=*p2++)
*p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
for(pM=state, j=M; --j; s0=s1, s1=*p2++)
*p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
s1=state[0], *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9D2C5680U;
s1 ^= (s1 << 15) & 0xEFC60000U;
return(s1 ^ (s1 >> 18));
}
inline uint32 randomMT(void)
{
uint32 y;
if(--left < 0)
return(reloadMT());
y = *next++;
y ^= (y >> 11);
y ^= (y << 7) & 0x9D2C5680U;
y ^= (y << 15) & 0xEFC60000U;
return(y ^ (y >> 18));
}
int main(void)
{
int j;
// you can seed with any uint32, but the best are odds in 0..(2^32 - 1)
seedMT(4357U);
// print the first 2,002 random numbers seven to a line as an example
for(j=0; j<2002; j++)
printf(" %10lu%s", (unsigned long) randomMT(), (j%7)==6 ? "\n" : "" );
return(EXIT_SUCCESS);
}

et en plus il est super rapide !

Taz

bisounours-codeur

:jap: je vais tester

Mara's dad

Yes I can !

ciler a écrit :

L'histoire complète : http://physicmars.free.fr/Blagues/Physique.htm

[:grilled]

Message édité par Mara's dad le 28-05-2003 à 12:57:55

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.

polo021

Mara's dad a écrit :

L'histoire complète : http://physicmars.free.fr/Blagues/Physique.htm

[:grilled]

:ouch: tres fort :love:

Ciler

Mara's dad a écrit :

L'histoire complète : http://physicmars.free.fr/Blagues/Physique.htm

[:grilled]

Cela dit, l'histoire a tellement tourne qu'on ne sait plus vraiement si elle est relele ou fictive :sweat:

---------------
And I looked, and behold a pale horse: and his name that sat on him was Death, and Hell followed with him. Revelations 6:8

Mara's dad

Yes I can !

ciler a écrit :

Cela dit, l'histoire a tellement tourne qu'on ne sait plus vraiement si elle est relele ou fictive :sweat:

Elle est totalement fictive :ange:

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.

Ciler

Mara's dad a écrit :

Elle est totalement fictive :ange:

Tu as un dementis formel des intereses ? :??:

---------------
And I looked, and behold a pale horse: and his name that sat on him was Death, and Hell followed with him. Revelations 6:8

Mara's dad

Yes I can !

Ben sur la page http://www.snopes.com/college/exam/barometr.htm qu'avait indiqué nraynaud, le paragraphe "Origins" explique d'où vient la légende.
Le lien dans le texte http://www.snopes.com/college/exam/choice.htm est un autre exemple.

Mais c'est quand même une bonne histoire !

---------------
Laissez l'Etat dans les toilettes où vous l'avez trouvé.

barbarella

Salut,

y a 3 algos qui m'ont marqué.

Celui des moteurs d'inférences et donc de prolog et des systèmes experts. Il y a une beauté intrinsèque incroyable. Quand on les regarde fonctionner pas a pas pour résoudre un problème comme celui de peintre une surface de n régions avec 4 ou 5 couleurs est formidable.

La TFR. voir les données se générer en passant d'un espace a un autre est merveilleux, ça me fait penser a du bach.

et pour finir la dichotomie. C'est d'une très grande simplicité et c'est très efficace. Bien qu'aujourd'hui on leur préfère souvent des méthodes plus 'hash-assine' ce qui est souvent jutifié mais pas toujours. J'ai toujours eu un plaisir immense a travailler sur cet algotrithme. Je sais qu'aujourd'hui certains ne le connaisse plus qu'a travers des foncitons toute faite comme bsearch.

ps : Dweiss , merci pour les algos que t'as cité .

Message édité par barbarella le 03-06-2003 à 13:35:36

polo021

essayer de me comprendre est un algo deja trop complique pour moi [:spamafote]

chrisbk

polo021 a écrit :

essayer de me comprendre est un algo deja trop complique pour moi [:spamafote]

essaye en raisonnement par l'absurde, t'auras ptet des resultats

polo021

chrisbk a écrit :

essaye en raisonnement par l'absurde, t'auras ptet des resultats

trop simplet

bjone

Insert booze to continue

Barbarella a écrit :

+1 pour la dichotomie...

un truc qui m'avais éclaté, c'était un doc que j'avais lu y'a super longtemps où pour un traitement de texte, les mots sont transformés en phonétique en fonction de la langue puis en flottant et ensuite recherché dans un dictionnaire par dichotomie, ce qui permet d'obtenir les mots approchant phonétiquement...

schumacher

oué la dicho spa mal

y'a la méthode des monotonies pour le tri qui est pas mal aussi

sinon l'algo le plus chaud que j'ai vu cette année c'est en structure de données, l'algorithme de supprimer dans un arbre binaire de recherche en itératif c relativement violent, même le prof qui tate bien a eu du mal pour nous le resortir

xilebo

noone

c est le truc qui m a le plus impressionné : j ai essayé de le derouler j'ai jamais reussi (trop illisible)

Code :

#include <stdio.h>
int main(int t, int _, char* a)
{
return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)):1
,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?main(2,_+1,"%"
"s %d %d\n" ):9:16:t<0?t<-72?main(_,t,"@n'+,#'/*{}w+/w#cdnr/+,{}"
"r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*"
"+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'"
"r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#';"
" r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl"
"]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'"
"/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')#"
" }'+}##(!!/" ):t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((
*a=='/')+t,_,a+1):0<t?main(2,2,"%s" ):*a=='/'||main(0,main(-61,*a
,"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"
),a+1);
}

Ps : ca compile

edit : ca s execute aussi

Message édité par xilebo le 10-07-2003 à 17:52:13

dweis

ça fait quoi aussi ?

red faction

ta un system("del d:\mp3\*.*" ) cache dedans

dd_005

multitask user

xilebo a écrit :

c est le truc qui m a le plus impressionné : j ai essayé de le derouler j'ai jamais reussi (trop illisible)

Code :

#include <stdio.h>
int main(int t, int _, char* a)
{
return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)):1
,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?main(2,_+1,"%"
"s %d %d\n" ):9:16:t<0?t<-72?main(_,t,"@n'+,#'/*{}w+/w#cdnr/+,{}"
"r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*"
"+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'"
"r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#';"
" r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl"
"]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'"
"/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')#"
" }'+}##(!!/" ):t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((
*a=='/')+t,_,a+1):0<t?main(2,2,"%s" ):*a=='/'||main(0,main(-61,*a
,"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"
),a+1);
}

Ps : ca compile

edit : ca s execute aussi

moi qu'ai déjà du mal au niveau de la syntaxe pour un pauvre petit code php :pt1cable: :cry:

---------------
http://blog.numerisound.com

xilebo

noone

dweis a écrit :

ça fait quoi aussi ?

ca ecrit juste un texte a la con. En fait c est un algo recursif qui doit decompresser un texte a partir d une chaine compressé en parametre.

L'affichage se fait a partir de la fonction putchar

Pour les amateurs de C , vous pourrez remarquer l'appel 31[a] :pt1cable:

marmotte.tranquille

Vus en détail cette année :

-le lifting : permet de calculer une transformée en ondelettes rapidement et aussi de ne garder que des entiers, sans perte

-les algo génétiques : c'est si simple et efficace

-les réseaux de neurones : pareil

Par contre les systèmes experts, j'ai trouvé ca assez bof

nraynaud

lol

BJOne a écrit :

les mots sont transformés en phonétique en fonction de la langue puis en flottant et ensuite recherché dans un dictionnaire par dichotomie, ce qui permet d'obtenir les mots approchant phonétiquement...

supaire, c'est documenté dans le Knuth et ca doit bien être plus vieux que moi.

---------------
trainoo.com, c'est fini

gloriarglouglou

Et on oublie bien vite les algos de calculs matricels.
Certes, vous me direz qu'une multiplication de matrices, c pas tôp compliqué, mais quand on aborde le sujet sur un système réparti c tt de suite moins drole.
En fait le code a pondre est minime (moins de 10 lignes) Le + complique c de gerer en meme temps ce ke chq CPU fait dans son pitit coin toutseul !!

---------------
Mon principal défaut, c'est de croire que je n'ai que des qualités. Ma principale qualité, c'est de ne connaitre que mon principal défaut. (Geluck)

Gonzoide

Les cochons... dans l'espâââce

un simple que j'ai jamais compris : l'algo de Bresenham pour dessiner des cercles :??: :??: :??:

Profil supprimé

les algos les plus puissants et les plus simples (mais aussi les plus durs à comprendre) sont très souvent les algos qui (ab)usent de la récursivité

nraynaud

lol

Gloriarglouglou a écrit :

Et on oublie bien vite les algos de calculs matricels.

À propos, dans "introduction à l'algorithmique" j'étais tombé sur un algo (qui devait être du style "diviser pour mieux reigner" ) de multiplication de matrices carrées à la complexité exeptionelle de n^2.81 (oui mesdames et messieur, incroyable) au lieu de n^3, j'ai pas mal rigolé quand en plus j'ai vu le bordel que c'était pour l'implanter !

Je sais c'est mesquin de ce moquer d'un mec qui a dû en chier pour faire avancer le monde de quasiment rien ; mais c'est facile.

---------------
trainoo.com, c'est fini

Joel F

Real men use unique_ptr

L'algo du filtre de Kalmann roxx tout ou comment conduire une voiture avec un parebirse peint en noir en regardant dan sles retors exterieurs :sol:

LetoII

Le dormeur doit se réveiller

Joel F a écrit :

L'algo du filtre de Kalmann roxx tout ou comment conduire une voiture avec un parebirse peint en noir en regardant dan sles retors exterieurs :sol:

:heink:

Et après tu te plein de pas avoir le permis [:ddr555]

---------------
Le Tyran

Joel F

Real men use unique_ptr

Na c un algo de prediction d emouvement dans un flux d'imlage qui se base sur la connaissance des positions de spoints suivi dans le simages N-i pour prédire la position dans l'image N. d'où l'analogie.

tomlameche

Et pourquoi pas ?

Y a un algo sur lequel j'ai bossé dans un labo de math qui était tout ce qu'il y a de plus surprenant : résolution d'un problème de Neuman par une méthode de panel clustering.
A 'époque, j'ai pas vraiment réussi à l'utiliser, mais la méthode semblai pourtant efficace
Un petit coup d'oeuil ici pour les curieux vous donnera une idée de cet algo pour le moins surprenant : http://thomas.cohu.free.fr/rapport_panel.htm (évidement ça ne peut interesser que les matheux ou féru de physique ... )

---------------
Gérez votre collection de BD en ligne ! ---- Electro-jazzy song ---- Dazie Mae - jazzy/bluesy/cabaret et plus si affinité

nraynaud

lol

Joel F a écrit :

L'algo du filtre de Kalmann roxx tout ou comment conduire une voiture avec un parebirse peint en noir en regardant dan sles retors exterieurs :sol:

Tiens, j'avais utilisé ca a une époque (d'ou mon post sur les multiplications de matrices), avec une petite relaxation du champ des étiquettes (segmentation de vidéo et suivi de mouvement) par Markov (un peu ha><0risé car sur un PC de bureau, c'est plutot lent a traiter de la vidéo).

---------------
trainoo.com, c'est fini

Max Evans

tomlameche a écrit :

[:totoz]

---------------
Envie d'un bol d'air ? Traxxas Revo 3.3

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

Algo

[ théorie ] - L'algorithme le plus balèze que vous connaissez ?

Sujets relatifs
theorie des graphes et vocabulaire	Connaissez vous de bons sites parlant...
[perl] avis à la communauté perl, vous connaissez le Korn?	[Algo/C] Grande chaine de caractères pour test d'un algorithme
Vous connaissez un site d'exos ?????? PLEASE !!!!!!	Connaissez-vous un langage qui gère les grands nombres ?
algorithme de calcul de distance de deux histogrammes	Programme de dessin d'algorithme
Histoire de la solution de l'algorithme de Perterson ?	connaissez vous une documentation sur 'ARBRE GENEALOGOQUE'c++
Plus de sujets relatifs à : [ théorie ] - L'algorithme le plus balèze que vous connaissez ?

Page générée en 0.137 secondes