Fractronique

Android Studio: An IDE built for Android | Android Developers Blog

2013-05-16T14:22:00.001+02:00

Android Studio: An IDE built for Android | Android Developers Blog

Dieu, la vrai sagesse

2008-09-27T14:45:00.023+02:00

La fonction d’ACKERMANN

La théorie de la récursivité ou Théorie de la calculabilité, est une notion appartenant à la fois à la logique mathématique et à l’informatique théorique. Cette notion, du moins sa formalisation, est née vers les années 1930, période riche en découvertes mathématiques ; elle permet notamment de trouver, algorithmiquement, une fonction calculable, et par conséquent de juger des limites de nos ordinateurs (computer = calculateur) sur certains algorithmes. Une fonction récursive étant une fonction qui peut s’exprimer en s’utilisant elle-même.

Exemple : la fonction factorielle : n!=n×(n-1)!
On utilise le terme factorielle « ! » des deux cotés de l’égalité).

La fonction d’ACKERMANN, à l’instar de la suite de Fibonacci qui croit de manière exponentielle, est une fonction récursive à très forte croissance (c’est là un excellent euphémisme), définie initialement en 1928 par le mathématicien Wilhelm Ackermann (29 mars 1896 à Herscheid - 24 décembre 1962 à Lüdenscheid), alors étudiant sous la direction du célèbre David HILBERT (23 janvier 1862 à Königsberg, Prusse-Orientale - 14 février 1943 à Göttingen, Allemagne), incontestablement l’un des plus grands mathématiciens du siècle dernier. Cette fonction fut initialement définie avec 3 valeurs en entrée :

C’est ensuite le mathématicien Ròzsa Péter qui donna à la fonction d’Ackermann sa forme que nous connaissons et utilisons actuellement : elle prend seulement 2 valeurs en entrée.

On montre de manière récurrente la définition suivante de la fonction :

A(m,n)= 2↑(m-2)(n + 3)- 3

On peut voir ici l’utilisation des puissances itérées de Knuth (« ↑ »).

Il est facile de coder cette fonction en C, c’est ce que je vous propose de faire à présent :

--------------------------------------------------------------------------------------------
#include stdio.h // N'oubliez pas les crochets que j'ai du enlever

main ()
{
/**
C’est dans le programme principal (main) que sera testée
notre fonction ackermann(…)
=========================================
*/

int ackermann (int, int) // Il faut bien sûr déclarer
// la fonction avant de l’utiliser.
Sa définition est faite plus bas.

int m,n;

printf ("Donnez m et n :\t");
scanf ("%d,%d", &m, &n) ;
printf("\n");
printf ("ackermann (%d,%d)= %d", m, n, ackermann(m,n) );
printf("\n");

/**
Dans cette partie, on définit la fonction, donc ce qu’elle devra faire
avec les paramètres mis en entrée
Attention : entrer des valeurs négative n’est pas correcte
*/

int ackermann (int m, int n)
{
if (m<0) style="font-weight: bold; color: rgb(0, 0, 153);">else if (m==0) return (n+1) ;
else if (n==0) return ( ackermann(m-1,1) ) ;
else return ackermann ( m-1, ackermann(m,n-1) ) ;
}
}

-------------------------------------------------------------------------------------------------
Exemple d’exécution :

Donnez m et n : 2,3
ackermann (2,3)= 9

Attention, la fonction d’Ackermann croît très vite, évitez donc d’utiliser de trop grandes valeurs . À titre d’exemple : A(4,2) contient 19729 chiffres, c’est quand même énorme !

Face à La conjecture de Syracuse

2008-09-23T22:11:00.013+02:00

En mathématiques, on appelle conjecture une assertion qui a été supposé vraie, mais qui n’a cependant jamais été démontrée comme vrai, ni même réfutée. Parmi les conjectures les plus célèbres on pourrait citer :
## Le problème P=NP (un des 7 problèmes mathématiques du millénaire)
## La conjecture des nombres parfaits
## Le célèbre « Dernier Théorème de Fermat », démontré en 1995 par le mathématicien anglais Andrew WILES
## L’hypothèse de Riemann, qui fait aussi parti des 7 problèmes du Millénaire classé par le Clay Mathematics Institut
## La conjecture de Syracuse ou encore « problème 3X+1»
## ….On pourrait en citer bien d’autres, il en existe un tas.
On va s’intéresser ici à la conjecture de Syracuse, qui a été conçue vers les années 1928 par le mathématicien allemand Lothar Collatz (6 juillet 1910, Arnsberg, Westphalie — 26 septembre 1990, Varna, Bulgarie). D’ailleurs la conjecture de Syracuse s’appelle également « Conjecture de Collatz ». Le raisonnement proposé par Collatz est assez simple (A priori) : prenez un nombre quelconque dans l’ensemble des entiers naturels non nuls , ensuite faites le raisonnement suivant :
--> Si ce nombre est pair, alors on le divise par 2
--> Sinon (donc s’il est impaire), on le multiple par 3 et on ajoute 1 au résultat de la multiplication .
On répète les opérations avec les valeurs qu’on obtient. On obtient alors une suite de nombres nommée Suite de Syracuse

Exemple : On prend le nombre 17
Il est impair on le multiplie donc par 3 et on ajoute 1, soit :
17×3+1 =52,
52 est un nombre paire (divisible par 2). On applique la première règle
52÷2=26
26 est un nombre paire (divisible par 2). On applique la première règle
26÷2=13
13 est un nombre impaire (non divisible par 2). On applique la seconde règle :
13×3+1=40
…
On obtient finalement la suite S(n) d’éléments :
17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,…
On se retrouve finalement avec un cycle dit « Triviale » composée des chiffres : 1,4 et 2
La conjecture de Syracuse énonce qu’en prenant n’importe quel nombre de l’ensemble on obtient toujours ce cycle dit Triviale, autrement dit, prenez n’importe quel entier naturel, appliquer le raisonnement précédent et vous tomberez toujours sur le chiffre 1.
Mais malgré la simplicité de cet énoncé, la conjecture de Syracuse a mise à l’épreuve de Brillants mathématicien. Aujourd’hui elle est évaluée à 1 million de dollars, c’est pas rien pour une hypothèse qui paraît aussi évidente.
On défini la suite de Syracuse comme une de manière récurrente, c’est-à-dire comme d’une suite dont la valeur des éléments dépend d’une valeur initiale, soit le nombre que l’on a en entrée de fonction :

Avec u0=N, la valeur initiale

Je vous propose à présent de coder ce résultat dans le langage de Programmation Matlab, que j’affectionne particulièrement pour sa grande souplesse.

-----------------------------------------------------------------------------------------------

%Auteur : Charles Morpheus

%Fichier :Syracuse_for_testit.m

% ======================

% |Conjecture de Syracuse|

% ======================

%==========================================================================

% Ce programme permet de tester la conjecture de Syracuse dans un certain

% intervalle qu'il est nécessaire de spécifier dès le début du programme...

%==========================================================================

clc; %% On supprime tout ce qui est à l'écran

disp('Nous allons vérifier la conjecture de Syracuse')

a=input('borne inférieure : ');

b=input('borne supérieure : ');

disp('=============================================')

for n=a:b

disp(['TEST DU NOMBRE ' int2str(n)]) %% On Affiche la valeur du "n"

while true %% correspondant à chaque fois

if n==1

disp('---> OK !')

break

else

if mod(n,2)==0 %% n est pair

n=n/2;

else

n=3*n+1; %% n est impair

end

disp(['La conjecture de Syracuse est donc vraie pour les nombres de ' int2str(a) ' à ' int2str(b)])

Un imprime-écran du résultat à l’exécution (en appuyant sur F5 à partir du source)

Voici un bon site pour tester cette conjecture directement en ligne :
Algorithme de Collatz

2008-09-17T16:26:00.003+02:00

Marre de voir personne sur ton blog ? tout ça c'est fini, "OVER !"....Maintenant ya
-- BoosterBlog --
Hey ! tu veux quoi en plus ;)

Equation de degré n=1,2,3 à une variable

2007-07-23T05:27:00.003+02:00

Introduction
Une équation dite du second degré est une équation qui admet formule générale :

ax²+bx+c=0 a,b, et c étant des coefficients complexes tels que a#0. L'inconnue x est un nombre complexe, en tout évidence.

Origines

Le problèmes des équations du second degré existe déjà chez les babyloniens, les égyptiens et les grecs. Ce n'est qu'au IXe siècle que le mathématicien Iranien musulman AL-KHWARIZMI fort de l'apport grec ,découvre une méthode de résolution de ces équations particulières. Les équations du second degré son les premières équations résolues; les équations mathématiques sont inventées en même temps que l'algèbre par ce même savant, véritable génie du calcul. L'algèbre n'utilisait cependant aucun symbole jusqu'à la Renaissance qui marque l'entrée du savant français VIETE François.

Resolution d'une équation du second degré : forme canonique et
discriminant

On part de l'équation initiale pour aboutir à une forme dite canonique, soit :
ax²+bx+c =a (x²+x*b/a +c/a)
=a [(x+b/2a)²-(b/2a)²+c/a]
=a [(x+b/2a)²-b²/4a² +c/a]
=a [(x+b/2a)²-(b²-4ac)/4a²] // Forme Canonique du trinome du second degré

On appelle le discriminant la valeur Δ = b² − 4ac
C'est à partir de cette valeur ( le discriminant) que nous discuterons des solutions de notre équation.
Si Δ >0

Notre équation admet deux solutions réels :

x1= (-b-sqrt( Δ ))/2
sqrt: racine carrée
x2=(-b+sqrt( Δ ))/2

si Δ = 0

Notre équation admet dans ce cas une solution double :
x1=x2=x= -b/2a

Si Δ < 0
Alors, l'équation admet deux solutions complexes qui sont :

x1=(-b-i sqrt(Δ ))/2
sqrt: racine carrée
x2=(-b+i sqrt(Δ ))/2

Exemples
Resolvons cette équation

(E1): x²+3x-4x=0

Δ = 3² - 4*1*(-4) = 9+16=25 >0; Il ya donc deux solutions réelles

x1= (-3-5)/2= -4
x2= (-3+5)/2= 1
d'ou S={1, -4}

On aurait pu utiliser le fait qu'il y est une solution évidente, ici 1 .
Or :
x1 +x2 = -b/a et x1*x2=c/a

En utilisant la dernière relation, on a : -1*x2=c/a=-4, donc x2=4

Voici un programme en Matlab permettant des équations de degré 1 à 3....Il faut simplement spécifier le degré dès le début du programme.

-------------------------------------------------------------------------------------------------

%Auteur : Charles S.

%Fichier: SolveEqua.m'

%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

% Ce programme permet la résolution d'équations linéaires de degré n=1,2,3

%dont les solutions sont dans l'ensemble des nombres complexes C. La réso

%lution des équations de degré 1 et 2 se fait de façon classique (On utili-

% se des méthodes élémentaires) et pour des équations de degrés 3 , on uti-

%lisera une méthode particulière ,dite méthode de Cardan-Tartaglia. Il en

%existe bien d'autres, mais je me limiterai à celle-ci....

%NB: Le programme se lance en appuyant sur F5....Enjoy it!

%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

clear all;

clc;

deg=input('Degré de l''équation : ');

%**************************************************************************

%On effectue le premier test --> degré 1

%**************************************************************************

if deg==1

disp('Nous allons résoudre des équations du type : Ax+B=0 , avec A et B réels')

disp('***********************************************************************')

A=input('Valeur de A : ');

B=input('Valeur de B : ');

if A==1

disp(['L''équation x+' num2str(B) ' =0 admet pour solution :']);

else

disp(['L''équation ' num2str(A) 'x+' num2str(B) ' =0 admet pour solution :']);

end

disp([' x= ' num2str(-B/A)]);

end

%**************************************************************************

%Si le premier n'est pas ton choix, on passe au second --> degré 2

%**************************************************************************

if deg==2

disp('Nous allons résoudre des équations du type : Ax²+Bx+C=0, avec A,B,C réels et A non nul')

disp('**************************************************************************************')

A=input('Valeur de A : ');

if A==0

disp('Désolé, mais A doit être non nul. Veuillez recommencer svp')

return;

else

B=input('Valeur de B : ');

C=input('Valeur de C : ');

if (A==1&&B==1)

disp(['Il s''agit donc de résoudre : x²+x+' num2str(C) '=0'])

elseif (A==1)&&(B~=0)

disp(['Il s''agit donc de résoudre : x²+' num2str(B) 'x+' num2str(C) '=0'])

else

disp(['Il s''agit donc de résoudre : ' num2str(A) 'x²+' num2str(B) 'x+' num2str(C) '=0'])

end

disc=B*B-4*A*C;

%Tests sur la valeur du discriminant....

%=======================================

if disc>0

x1=(-B-sqrt(disc))/2*A;

x2=(-B+sqrt(disc))/2*A;

disp(['Cette équation admet deux solutions réeles : x1= ' num2str(x1) ' et x2= ' num2str(x2)])

end

if disc==0

x_d=-B/2*A;

disp(['Cette équation admet une solution double : x1=x2= ' num2str(x_d)])

end

if disc<0

disp('Cette équation admet deux solutions complexes : ')

disp(['x1=' num2str(-B/2*A) '-' num2str(sqrt(-disc)/2*A) 'i et x2= ' num2str(-B/2*A) '+' num2str(sqrt(-disc)/2*A) 'i'])

end

%**************************************************************************

%Si le deuxième n'est pas votre choix, on passe au troisième --> degré 3

%**************************************************************************

if deg==3

disp('Nous allons résoudre des équations de la forme Ax^3+Bx^2+Cx+D=0')

A=input('Valeur de A : ');

B=input('Valeur de B : ');

C=input('Valeur de C : ');

D=input('Valeur de D : ');

%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

%--*--*--*--> NB : Il faut connaître (ou pas nécessairement) la méthode de

%Cardan-Tartaglia pour comprendre la suite du programme. Cette méthode

%permet en effet la résolution des équations de degrés 3 de la forme :

% x^3+px+q=0....On généralise ensuite cette méthode de résolution à des

% équations de la forme Ax^3+Bx^2+Cx+D=0 en posant x=z-B/3*A

%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

p=-(B/3*A)^2+C/A;

temp00=(2*B*B)/(A^2)-(9*C/A);

q=(B/27*A)*temp00+D/A;

disc3=q.^2+(4*p.^3)/27;

sqrt3=1/3;

temp0=B/(3*A);

if (B<0)&&(c<0)&&(d<0)

disp(['L''equation: ' num2str(A) 'x^3 ' num2str(B) 'x^2 ' num2str(C) 'x' num2str(D) '=0 possède 3 solutions :'] )

else

disp(['L''equation: ' num2str(A) 'x^3 ' num2str(B) 'x^2 ' num2str(C) 'x + (' num2str(D) ') =0 possède 3 solutions :'] )

end

disp('==================================================================')

%Tests sur la valeur du discriminant....

%=======================================

if disc3>0

disp('disc >0')

u=((-q+sqrt(disc3))/2).^sqrt3;

v=((-q-sqrt(disc3))/2).^sqrt3;

z1=u+v;

disp(['- une solution réelle: x1= ' num2str(z1-temp0)])

disp(['- deux solutions complexes : x2=' num2str(-z1/2-temp0) '+' num2str((sqrt(3)*(u-v))/2) 'i et x3= ' num2str(z1/2-temp0) '-' num2str((-sqrt(3)*(v-u))/2) 'i' ])

end

if disc3==0

z1=(3*q)/p;

z2=(-3*q)/(2*p);

disp('disc =0')

disp('Nous avons deux solutions réelles :')

disp(['-Une simple : x1= ' num2str(z1-temp0)])

disp(['-Une double : x1=x2= ' num2str(z2-temp0)])

end

if disc3<0

disp('disc <0')

temp1=2*sqrt(-p/3);

temp2=acos(-q*0.5*sqrt(-27/(p.^3)));

z1=temp1*cos((temp2+2*pi)./3);

z2=temp1*cos((temp2+2*2*pi)./3);

z3=temp1*cos((temp2+2*3*pi)./3);

x1=z1-temp0;

x2=z2-temp0;

x3=z3-temp0;

disp('L''équation possède trois solutions réelles : ')

disp([' -x1= ' num2str(x1)])

disp([' -x2= ' num2str(x2)])

disp([' -x3= ' num2str(x2)])

end

-------------------------------------------------------------------------------------------------------------------------

Suite de Fibonacci

2007-06-30T17:39:00.002+02:00

Un corps retrouvé sans vie, étalé à terre formant l’homme de Vitruve réalisé par De VINCI. Ce homme est entouré de chiffres symboliques ; ces chiffres particuliers appartiennent à une suite très connue en mathématiques : la suite de Fibonacci

La suite de Fibonacci, du nom de celui qui l’introduit, l’italien Leonardo Pisano, plus connu sous son pseudonyme Fibonacci, est un suite d'entiers distribués de façon un peu spéciale dans N. Il présente cette suite dans un problème qu’il posa dans le liber Abaci, où il décrit la croissance d’une population de lapins.
Pour revenir en mathématiques, cette suite particulière engendre bien sur des termes : chaque terme est la somme des deux termes précédents. En considérant initialement les termes 0 et 1, on obtient les valeurs de la suite de Fibonacci dans leur ordre croissant : 0,1 ,1,2,3,5 ,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181 ,…
Soit : Fn+2=Fn+1 + Fn qui est une suite récurrente de premiers termes 0 et 1.
On montre que le rapport de deux termes consécutifs de la suite, typiquement le plus grand sur le plus petit, tends vers le nombre d’or : 1,618033988749…
Qui a de très belles propriétés que nous exploiterons sûrement dans un autre numéro.

La suite de Fibonacci intervient dans de nombreux problèmes de dénombrement Par exemple, le terme d'indice n (pour n supérieur ou égal à 2) de la suite de Fibonacci permet de dénombrer le nombre de façons de parcourir un chemin de longueur n-1 en faisant des pas de 1 ou 2. Ce problème apparaît d'ailleurs très tôt en Inde, sous le nom maatraameru (pour montagne de cadence) . Les nombres de Fibonacci ont de plus permis la résolution du dixième problème de Hilbert. Et pour finir, on peut convertir des Miles au Kilomètre grâce à la suite de Fibonacci, vu que le facteur de conversion est sensiblement égal au nombre d’or. Il suffit de considérer le nombre en Miles, par exemple 55 , et de trouver ensuite le chiffre qui suit 55 dans la suite, soit 89. Ainsi 55 miles donnent à peu près 89 kilomètres.

Sans prétendre vouloir faire de l’algorithmique linéaire, je vous propose ici un programme qui calcul et affiche les nombres de Fibonacci, ainsi qu’une valeur approchée du nombre d’or, tout cela en Java.

public static void fibonacci() {
//Affiche les n premiers nombres de Fibonacci
System.out.print("ENCHA est fier de vous présentez : Fibonacci");
System.out.println(" ;Let's go!");

double a,b,c,n,i;
double phie,fib;

Scanner clavier=new Scanner(System.in);
System.out.println("Entrez un entier naturel n différent de 0 et 1");//**0 et 1 sont les valeurs initiales de la suite
*/n=clavier.nextInt();
System.out.println("les " +n+ " premiers "+" entiers de Fibonacci sont:" );
a=0;b=1;c=1;phie=1;
for(i=1;i<=n;i++) {
c=a+b;
a=b;
b=c;
phie=(double)c/b;
System.out.println(c);

}
System.out.println();
System.out.println("De plus,le nombre d'or a pour valeur approchée:" +phie);
}
}

fractronique.blogspot.com

2007-06-22T15:38:00.001+02:00