Aller au menu - Aller au contenu

Une classe d'algorithme non naïfs : diviser pour régner

Pour accéder à cette section
Connectez-vous !
connexion_rpx
Page 1 
Pseudo Commentaire
Page 1 
Hors ligne rga # Posté le 16/09/2008 à 14:00:51
Because you're mine...
Avatar

 bon tuto sur les algorithmes.
j'ai juste vu cette erreur de frappe :
Code : Autre
1

quand on double la quantité de données à traiter, l'algorithme fait une opéartion de plus.

ce ne serait pas plutôt "opération" ?
Avant de poster, regardez les tutos :lol: ... Les réponses à nos questions y sont souvent. ;)
Sinon, pensez à marquer vos sujets en résolu dès que c'est le cas.
 
Hors ligne NeeL # Posté le 16/09/2008 à 16:54:17
#k3v1n5 PownZ
Avatar

Études : Exia.Cesi, Ecole Supérieure d'Informatique du Cesi

 Bon tuto ,
Une petite erreur pas bien grave :

"Imaginons que l'on commence par proposer 50. Quelque soit la réponse du Sphinx, on peut éliminer 50 possibilités :

* si c'est plus que 50, la solution est entre 51 et 100.
* si c'est moins, la solution est entre 1 et 49. "
Si c'est plus ou moins elle peut pas inclure 50 :D
Voila , merci encore pour ce bon tuto :)
http://deepneel.eu/ Portfolio ;)
 
Hors ligne noluz # Posté le 17/09/2008 à 12:56:15

Juste une question, sur le graphique, pourquoi \log2(2*10^4) \approx 5 o_O ? Pour log10 je veux bien, mais là c'est en base 2. Y'a pas eu une erreur de tracé :-° ?

Édit : iPoulet, le préposé aux graphiques, me dit que "on s'en branle, ça varie que d'une constante multiplicative". Je suis bien d'accord, mais là ça colle pas avec le texte quoi. Après, vous faites ce que vous voulez :) ça donne l'allure d'un graphe de logarithme au moins.
Hors ligne F_D_V # Posté le 17/09/2008 à 13:31:22

Études : INSA Rennes

 très bon tuto, très clair et bien expliqué!!
Hors ligne souls killer # Posté le 20/09/2008 à 16:40:03
Groupe : aigris
Avatar
Groupe : Bannis
Flux RSS
close

Ville : Chevilly-larue
Pays : France métropolitaine
Études : Université Paris XII

 Toujours aussi clair et concis, bravo.

Cependant, j'ai vu quelques erreurs de syntaxe mineures qui apporteraient à être corrigées :

Citation
Si f(m) est positif, on peut en déduire que la solution est comprise dans l'intervalle ; sinon, elle se trouve dans l'intervalle .

J'ai l'impression qu'il manque soit un mot, soit qu'il y a un contre-sens...

Autre chose : lorsque tu définis des puissances de nombre suivis de signes de ponctuation, tu places parfois la ponctuation avec son exposant. Je m'explique : lorsque tu écris (par exemple) "x3, blabla" ; tu places ta virgule avec le 3. A mon avis, elle devrait plutôt être avec le texte normal...
La ligne droite est le plus long chemin d'un point à un autre. — Théorème mathématique shadok.
Mon blog (un peu mort depuis quelques mois) | Twitter

Discutez en direct avec les membres du site.
 
Hors ligne funduk # Posté le 27/10/2008 à 20:30:46
Avatar

 Très bon tuto, comme les précédents.
Qu'est-ce que tu as contre les carottes ?
Hors ligne jerome41 # Posté le 17/01/2009 à 22:56:09
vive le rock
Avatar

Études : EPFL

 Salut
bon tuto mais il y a une toute petite erreur dans les exemples, tu as mis f(x) = (x^2)-2 puis tu en deduis x = (racine de deux) mais tu as omis la possibilite x = (-racine de deux) sauf erreur de ma part
" Les hommes naissent bien dans l'égalité, mais ils n'y sauraient demeurer. "
Montesquieu
 
Hors ligne stallaf # Posté le 20/01/2009 à 14:07:29
intuitu personae
Avatar

 Bonjour,

Dans tous les cas, si les 20% restants sont de même qualité, je dis : :magicien:
Gourou, tu deviendras...
 
Hors ligne Alp # Posté le 09/02/2009 à 09:49:07

Il aurait pu être intéressant de donner la méthode de Newton en exercice ;)
Blog (EN - nouveau) - Mes articles - FAQ C++0x - Conseils sur le C++ - La meilleure FAQ du monde - Le site du commité C++

Nouveau Le guide pour bien débuter en C++
 
Hors ligne bluestorm # Posté le 09/02/2009 à 14:28:45
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

L'étude de la complexité de la méthode de Newton n'est pas faisable dans le cadre de ce cours (qui évite les pré-requis mathématiques). De plus, les conditions de fonctionnement ne sont pas évidentes et assez lourdes à donner avec précision.

Si quelqu'un veut écrire un mini-tuto sur les recherches de racines, qu'il ne se gêne surtout pas :p
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne K-jasi # Posté le 10/03/2009 à 10:37:54
Nothing really ends...
Avatar

 C'est intéressant, mais personnellement je n'aurais pas ajouté la section pour la recherche de zéros d'une fonction.
C'est un problème de méthodes numériques tellement complexe qu'il ne tiendrait pas dans un big tuto, alors donner une méthode qui est présentée comme la seule existant (c'est en fait la plus naïve, et elle est présentée sans aucune de ses hypothèses) est beaucoup trop réducteur. De plus, pour un tuto qui se veut faire abstraction de toute notion mathématique (vu comme vous passez sur le 'log'), la présentation de ce problème ne remplit pas l'objectif (même si très simpliste).

En dehors de cela, c'est un bon tuto, avec un domaine très intéressant et vaste à couvrir. Bon courage.
Un forum gratuit, efficace, et en perpétuelle évolution:
Image utilisateur
Générateur de smileys ^^
 
Hors ligne Cygal # Posté le 10/03/2009 à 13:33:24
X-No-Archive: yes
Avatar
Flux RSS
close

  • C'est un tuto d'algorithmique, pas d'analyse numérique, on présente le point de vue "informatique" sans trop s'attarder sur le côté théorique de la chose en effet, je comprend que ça choque les puristes. Après, on en dit assez pour que ce soit clair à mon sens.
  • On s'abstrait de connaissances mathématiques certes, mais on estime que demander le niveau collège est honnête, donc on suppose que la personne qui lit sait ce qu'est une fonction. Si elle ne l'a pas encore vu en cours, ça reste une notion plutôt naturelle a priori, et elle peut toujours se renseigner rapidement. Dans le cas du log2, ça ne "s'invente pas", donc on estimé important d'en parler, oui.
  • La dichotomie n'a pas été présentée comme la meilleure, on dit justement qu'il existe d'autres méthodes qui convergent plus vite en conclusion.
Hors ligne K-jasi # Posté le 10/03/2009 à 13:57:28
Nothing really ends...
Avatar

 Il serait alors peut-être juste intéressant de rappeler les hypothèses de l'algo.
Un forum gratuit, efficace, et en perpétuelle évolution:
Image utilisateur
Générateur de smileys ^^
 
Hors ligne bluestorm # Posté le 10/03/2009 à 22:13:09
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Citation
Il existe d'autres méthodes pour rechercher les 'zéros de fonctions' (c'est-à-dire les points où les fonctions s'annulent), certaines étant encore plus efficaces dans des cas spécifiques. Cependant, la recherche dichotomique est une très bonne base parce qu'elle marche sur n'importe quelle fonction continue (si on connaît deux points dont les valeurs sont de signes opposés) et que le gain de précision est "garanti" : on sait précisément quelle approximation on aura au bout de N étapes (et c'est L/2N , où L est la longueur de l'intervalle de recherche initial).


Quelle est l'hypothèse qui manque ? Je suis prêt à insister sur le fait qu'il faut deux points aux images de signe opposé, mais il me semble que tout est là, même pour les puristes.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne lastsseldon # Posté le 10/03/2009 à 23:49:51
Avatar

Études : Paris 7 Denis Diderot

 Hum. C'est vrai qu'on a fait le choix de présenter d'une manière "intuitive" les bases mathématiques de l'algorithme, mais je pense pas qu'une énonciation du théorème des valeurs intermédiaires (ou de Bolzano ici) soit vraiment à sa place dans ce tuto... Le but était surtout de présenter la dichotomie dans un contexte différent :) . Merci pour le feedback cela dit, on rajoutera peut être un lien pour les plus curieux, la page wikipedia m'a l'air compréhensible.

http://fr.wikipedia.org/wiki/Th%C3%A9o [...] %C3%A9diaires

[gnustep,etoile,Io ,haskell, erlang ]
 
Hors ligne ledemonboiteux # Posté le 16/03/2009 à 12:00:01

Il y a une erreur :

"On constate que f(0) est négatif et que f(2) est positif. Comme notre fonction est continue, l'équation f(x) = 0 possède nécessairement une solution entre 0 et 2. En utilisant la dichotomie, on peut réduire l'intervalle et donc améliorer la qualité de l'approximation."

Il faut constater en plus que la fonction est monotone (sinon la solution n'est pas unique), sinon on peut dire la fonction possède au moins une solution dans l'intervalle.
Image utilisateur
http://www.venganza.org
 
Hors ligne bluestorm # Posté le 16/03/2009 à 18:34:35
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Je n'ai jamais parlé d'une solution unique. Ce sont des subtilités (la plupart des gens qui lisent ce tuto sont au lycée, donc ne connaissent même pas le TVI) et le texte est exact. Je ne vois pas l'intérêt d'alourdir le texte avec des précisions superflues, pour faire plaisir aux maniaques du coin.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne CyberjujuM # Posté le 25/03/2009 à 18:28:53
Keep your mind wide open...
Avatar

Études : INSA Toulouse

 Bonjour et félicitations pour cette introduction à l'algorithmique très bien expliquée.

Je viens de m'intéresser à la recherche par dichotomie et j'avais eu l'idée d'une solution similaire à celle que vous présentez dans ce tutoriel pour résoudre un exercice, c'est à dire :

Code : PHP
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
<?php
function find($mot, $dictionnaire, $begin, $end) {
    $new = floor(($begin + $end) / 2);
    $cmp = strcmp($dictionnaire[$new], $mot);
    if ($cmp == 0)
         return true;
    else if ($begin == $end)
         return false;
    else if ($cmp > 0)
         return find($mot, $dictionnaire, $begin, $new - 1);
    else
         return find($mot, $dictionnaire, $new + 1, $end);
}

// exemple :
$dictionnaire = array('chat', 'cheval', 'chien', 'grenouille');
echo find('chien', $dictionnaire, 0, sizeof($dictionnaire) - 1);
?>


Seulement cet algorithme semblait partir en boucle infinie sur certains tests. Ne comprenant pas, j'ai cherché un peu et ai finalement trouvé l'origine du problème. En effet, avec un exemple tel que celui-ci :

Code : PHP
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
<?php
function find($mot, $dictionnaire, $begin, $end) {
    $new = floor(($begin + $end) / 2);
    $cmp = strcmp($dictionnaire[$new], $mot);
    if ($cmp == 0)
         return true;
    else if ($begin == $end)
         return false;
    else if ($cmp > 0)
         return find($mot, $dictionnaire, $begin, $new - 1);
    else
         return find($mot, $dictionnaire, $new + 1, $end);
}

// exemple :
$dictionnaire = array('caribou', 'chat', 'cheval', 'chien', 'grenouille', 'pingouin');
echo find('abcd', $dictionnaire, 0, sizeof($dictionnaire) - 1);
?>


- On commence par appeler notre fonction avec $begin = 0, $end = 6-1 = 5. Le milieu est 2, et le mot correspondant "cheval" est "supérieur" au mot "abcd" que l'on cherche.
- On rappelle donc notre fonction avec $begin = 0, $end = 2-1 = 1. Le milieu est 0, et le mot correspondant "caribou" est toujours supérieur.
- On rappelle notre fonction avec $begin = 0, $end 0-1 = -1. Le milieu est -1, et... là on a un problème. Pas d'indice -1 dans notre tableau de mots, du coup le mot recherché est considéré comme "supérieur" au "rien" trouvé en indice -1, et on rappelle notre fonction avec $begin = -1+1 =0, $end = -1... et voilà notre boucle infinie !

Pour éviter ça, il faut soit faire un découpage en [début;milieu] et [milieu+1;fin], soit garder le [début;milieu-1] et [milieu+1;fin] mais tester si $begin > $end et arrêter l'algorithme le cas échéant.

Code : PHP
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
<?php
function find($mot, $dictionnaire, $begin, $end) {
    $new = floor(($begin + $end) / 2);
    $cmp = strcmp($dictionnaire[$new], $mot);
    if ($cmp == 0)
         return true;
    else if ($begin == $end)
         return false;
    else if ($cmp > 0)
         return find($mot, $dictionnaire, $begin, $new);
    else
         return find($mot, $dictionnaire, $new + 1, $end);
}

// exemple :
$dictionnaire = array('caribou', 'chat', 'cheval', 'chien', 'grenouille', 'pingouin');
echo find('abcd', $dictionnaire, 0, sizeof($dictionnaire) - 1);
?>


ou

Code : PHP
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
<?php
function find($mot, $dictionnaire, $begin, $end) {
    if ($begin > $end)
         return false;
    $new = floor(($begin + $end) / 2);
    $cmp = strcmp($dictionnaire[$new], $mot);
    if ($cmp == 0)
         return true;
    else if ($begin == $end)
         return false;
    else if ($cmp > 0)
         return find($mot, $dictionnaire, $begin, $new - 1);
    else
         return find($mot, $dictionnaire, $new + 1, $end);
}

// exemple :
$dictionnaire = array('caribou', 'chat', 'cheval', 'chien', 'grenouille', 'pingouin');
echo find('abcd', $dictionnaire, 0, sizeof($dictionnaire) - 1);
?>


Voilà :)
http://www.codelyoko.fr
http://www.m2radio.fr
http://www.blogeee.net
 
Hors ligne bluestorm # Posté le 25/03/2009 à 23:35:40
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Effectivement, un bug s'est glissé là ! J'ai testé un peu le code avant de l'envoyer, mais ces manipulations d'indices sont toujours un peu traîtres, et ça ne suffisait visiblement pas.

Merci pour l'avoir remarqué. Après avoir pesé le pour et le contre, j'ai finalement choisi une solution proche de la deuxième proposition (on retire uniquement le test if ($begin == $end) devenu inutile) :
Code : PHP
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
<?php
function find($mot, $dictionnaire, $begin, $end) {
    if ($begin > $end)
        return false;
    $new = floor(($begin + $end) / 2);
    $cmp = strcmp($dictionnaire[$new], $mot);
    if ($cmp == 0)
        return true;
    else if ($cmp > 0)
        return find($mot, $dictionnaire, $begin, $new - 1);
    else
        return find($mot, $dictionnaire, $new + 1, $end);
}
?>


J'ai fait la modification, elle sera en ligne à la prochaine publication. Merci.

Il y a bien sûr de nombreuses autres méthodes pour coder la recherche par dichotomie : ici je demande le premier indice à explorer, et le dernier (les deux étant inclus dans la zone de recherche). Il est assez courant d'exclure l'indice de fin de la zone (on appellerait donc sur (0, sizeof(...)) au lieu de (0, sizeof(...)-1), ou de donner, au lieu de l'indice de fin, la taille de la zone à explorer.
De toute façon, je trouve que l'important c'est l'idée de l'algorithme, pas tellement la mise en pratique, même s'il faut bien sûr s'efforcer de manipuler les indices de tableaux sans erreurs (surtout dans un tutoriel, qui peut éventuellement servir d'exemple; j'ai honte :p ).
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne alexises # Posté le 21/08/2010 à 00:49:37
merci m@téo pour la v3
Avatar

Études : IUT Paris

 au fait juste pour infos certes il n'y a pas de prérequis mathématique mais sa serait bien d'éviter de dire des conneries :) : tu parle du logarithme : si tu ne précise pas la base elle est définis comme de base e, l'utilisation de log prête aussi a confusion on le réserve a la base 10. précise au moins que c'est un logarithme de base 2
Image utilisateur
 
Hors ligne bluestorm # Posté le 21/08/2010 à 08:58:27
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Le paragraphe suivant répond à ta remarque :
Citation
En réalité, ils ont même fait du zèle : il n'y a pas une seule "fonction logarithme", mais plusieurs. Par exemple il y a une fonction qui ajoute une opération à chaque fois qu'on triple la taille de l'entréee : f(3*N) = f(N) + 1. C'est une autre fonction logarithme qu'on appelle "logarithme en base 3" (et la nôtre, logarithme en base 2). Mais ce n'est pas important parce qu'ils ont prouvé dans la foulée que les différentes fonctions logarithme ne diffèrent que d'une constante multiplicative (quel que soit x, log2 (x) = k * log3 (x) avec k environ 1.58549625) : en termes de complexité, elles sont donc toutes équivalentes, puisqu'en calculant la complexité on néglige les constantes multiplicatives.


Du point de vue de la complexité, toutes les fonctions logarithmes sont équivalentes. Sachant qu'en pratique la base la plus naturelle en programmation est quasi-exclusivement 2 (mais pas toujours !), je ne souhaite pas alourdir le contenu d'un tutoriel déjà bien chargé avec une notion compliquée (qu'est-ce que e ? comment est-il défini ? pourquoi ?) de plus.

L'utilisation de "log" pour désigner la base 2 (ou la base 'e', d'ailleurs) est tout à fait acceptable. La base 10 est utilisée en chimie, et ce n'est pas mon problème.

Par ailleurs, tu pourrais essayer de faire un effort sur la façon dont tu formules tes commentaires. J'apprécie les critiques constructives, et ta remarque est tout à fait justifiée, mais ce n'est pas très agréable de lire que je devrais « éviter de dire des conneries », même avec un smiley derrière.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne Arnolddu51 # Posté le 09/09/2010 à 17:37:13
<lien url="http://forum.hardwa
Avatar

Ville : Paris
Pays : France métropolitaine
Études : EFREI

 Salut,

J'ai reperé une erreur sur le tutoriel. Je ne sais pas si c'est ici que je dois poster et si ce n'est pas le cas, veuillez m'excuser.
Citation : Tutoriel
Autrement dit, si on double la taille de l'entrée (en passant de 1 à 200, ou en ayant un dictionnaire deux fois plus gros), il suffit d'effectuer une étape de plus.


1 * 2 != 200 N'est-ce pas ?
Le mode sans échec de Windows est la preuve que son mode normal est un échec !

Mes ventes sur Hardware.fr

Citation : Georges Clémenceau
Ne craignez jamais de vous faire des ennemis ; si vous n'en avez pas, c'est que vous n'avez rien fait.


Image utilisateur





 
Hors ligne JoTwo # Posté le 26/04/2011 à 18:59:14
À prononcer DJOTOU
Avatar

Ville : Bruxelles
Pays : Belgique

 Salut!
Encore une fois, c'est bien! Mais pourquoi ne pas détailler le calcul de la complexité de l'algo trouvant le zéro d'une fonction?
Vu que le nombre d'appels récursif dépend de la marge d'erreur que l'on se fixe, ce n'est pas habituel et c'est plutôt intéressant, non?
Gnarf o_O !
 
Pour accéder à cette section
Connectez-vous !
connexion_rpx