Algorithme

[inviteeb9e3975]

Je suis éleve de Terminale désirant me lancer dans l'informatique l'année prochaine.Ce sujet est pour moi assez flou.Peut-on en gros m'expliquer ce qu'est l'algorithme?
-----

[invitebe0cd90e]

On ne dit pas "l'algorithme" mais "un algorithme", il y en a plusieurs

En gros, un algorithme c'est une methode pour resoudre un probleme, decrite de maniere tres precise etape par etape.

Autrement dit, c'est une sorte de liste d'instruction que tu peux suivre mecaniquement, sans reflechir, pour aboutir a la resolution d'un probleme. Comme les ordinateurs ne "comprennent" pas ce qu'ils font, avoir un algorithme est la premiere etape pour "expliquer" a la machine ce que tu veux lui faire faire. La seconde etape est de traduire l'algo dans un langage comprehensible par l'ordinateur.

[inviteeb9e3975]

Merci beaucoup. Ta réponse était claire

[acx01b]

salut
un bon exemple d'algorithmes : les algorithmes sur les graphes (en gros graphe = labyrinthe)
- fonction capable de compter le nombre de noeuds du graphe,
- trouver le plus court chemin entre A et B dans un graphe
- ...

si tu veux savoir à quoi correspond la programmation et l'algorithmie, commence à regarder des cours de langage C, par exemple sur lesiteduzero,
attention les pointeurs ce n'est pas facile à comprendre tout seul !

[A voir en vidéo sur Futura]

[invitebe0cd90e]

Hum, je pense qu'il y a des exemple d'algorithmes plus simples que ceux ci, et des langages plus abordables

[sebsheep]

Ce que tu voulais dire je pense est : "Quest-ce que l'algorithmique?", et l'algorithmique est la science qui traite des algorthimes définis comme au message #2.

Et tu connais déjà un algo, celui d'Euclide pour calculer le pgcd (sisi, tu as fait ça en 3eme, souviens toi ).

Je plussoie le site du zéro pour apprendre à programmer, te montrer ce que c'est avant de te lancer dedans et éviter de découvrir au mois de novembre que c'est pas du tout pour toi (ça arrive assez souvent).

[invitebe0cd90e]

Et tu connais déjà un algo, celui d'Euclide pour calculer le pgcd (sisi, tu as fait ça en 3eme, souviens toi ).

C'est en effet l'un des exemples "non triviaux" les plus simples, et il prouve accessoirement que le concept d'algo preexiste largement a l'informatique.

Un autre exemple que tu connais deja : la methode de resolution des equations polynomiales du second degré. C'est un algorithme puisque c'est une methode qui marche toujours et que tu peux "appliquer sans reflechir" : tu as une formule qui te donne le discriminant, puis suivant son signe plusieurs cas se presentent, et pour chacun de ces cas il ya une procedure mecanique qui te permet d'ecrire la ou les solutions.

[sebsheep]

Un autre exemple que tu connais deja : la methode de resolution des equations polynomiales du second degré. C'est un algorithme puisque c'est une methode qui marche toujours et que tu peux "appliquer sans reflechir" : tu as une formule qui te donne le discriminant, puis suivant son signe plusieurs cas se presentent, et pour chacun de ces cas il ya une procedure mecanique qui te permet d'ecrire la ou les solutions.

Ce qui est malheureusement la façon de faire des maths jusqu'en Terminale et voir mm apres ... appliquer une méthode sans se poser de questions, évidement c'est ch*** et pas motivant, mais là je digresse ...

[acx01b]

ta réponse est intéressante jobherzt mais je reste sur ma position, s'il veut faire des études d'info, autant qu'il voit tout de suite si ça l'intéresse ou pas => faire un peu de C et de graphes est une bonne option s'il ne sait pas quoi regarder d'ici septembre

[invitebe0cd90e]

ta réponse est intéressante jobherzt mais je reste sur ma position, s'il veut faire des études d'info, autant qu'il voit tout de suite si ça l'intéresse ou pas => faire un peu de C et de graphes est une bonne option s'il ne sait pas quoi regarder d'ici septembre

J'admet pour les graphes, parce que ca a l'avantage d'etre assez visuel et intuitif, meme si le debut "classique" c'est plutot quelques trucs basiques (genre equation du second degré, justement) puis algos de tris. Pour travailler sur des graphes il faut deja les implementer, ce qui n'est pas si evident au debut.

Mais pour le langage, meme si perso je fais plutot du C++, pour se faire une idée je penserai plutot au python par exemple.

[prgasp77]

Bonjour tout le monde.
Si je puis me permettre, une bonne façon de commencer est d'apprendre un pseudo-code laxiste sur la syntaxe afin de ne pas avoir des erreurs de compil et de linker dès le début :d.

Chercher un petit cours sur le net sur le pseudo-code (j'en posterai un d'ici quelques jours si tu n'as pas trouvé), et commencer des exercices simples (résolution d'équation du second degré, calcul de pgcd/ppcm, conversion secondes en h/m/s, calculs de statistiques), puis un peu plus complexes (tris, algo récursifs ...) et enfin avec des choses intéressantes (recherche de solution dans un arbre/ un graphe, calcul du plus cours chemin ...)

Une fois cela fait, tu pourra apprendre le C (très bon langage pour débuter, il permet d'avoir dès le début une manière stricte de penser programmation, pour ensuite apprendre d'autres langages un peu moins formels). Tu pourra alors traduire tes algorithmes de pseudo-code en C, et tu pourra admirer la magie de ton travail.

Note : un point important à comprendre avant de se lancer dans l'algorithme, c'est l'affectation de valeur à une variable. Si le code suivant te semble barbare, renseigne toi un peu sur ce principe.

Exemple de pseudo code : calculer à près.

Commentaire
début
	Nous savons que l'intégrale de Riemann est la somme d'une série :
	int[0,1->10](f(x)dx) = lim[n->+oo] (10-0,1)/n * sum[k : 0->n-1](f(0,1 + k(10-0,1)/n))
	
	L'erreur commise est, en fonction de n, majaurée par (10-0,1)/n * | f(0,1) - f(10 - (10-0,1)/n) |
	donc majaurée par (10-0,1)/n * |f(0,1) - f(10)|
fin

Fonction f(x) : réel
début
   retourner e^(-x)/x^3
fin

algorithme calcul_intégral
variables
   intégrale : réel
   erreur : réel
   erreur_max : réel
   n : entier
   k : entier
début
   // Initialisation
   intégrale <- 0
   erreur <- 1
   erreur_max <- 9.9*(f(0.1)-f(10))
   n <- 1

   // Calcul de la précision nécessaire
   Tant que précision >= 0.01 faire
      n <- n*2
      précision <- précision_max / n
   fin tant que

   // Nous avons notre n tel que précision <= 0.01, nous calculons donc la somme de la série
   Pour k allant de 0 à n-1 faire
      intégrale <- intégrale + f(0.1 + k*(10-0.1)/n)
   fin pour
   intégrale <- intégrale*(10-0.1)/n

   // Affichage du résultat
   Ecrire("Le résultat est : ")
   Ecrire(intégrale)
fin

La lecture est assez intuitive, ainsi si je montre ceci à un lycéen de seconde, s'il est assez rigoureux il pourra effectuer le calcul. Mais une fois un problème résolu sous forme d'algo, il est plus facile de traduire cela dans un langage de programmation et de laisser le soin à la machine d'effectuer les calculs. Tu peux remarquer que les deux codes sont semblables. (While = tant que, For = pour ...)

Exemple simple d'implémentation en C

/*
	Ce programme calcule l'intégrale de 0,1 à 10 de f(x) = exp(-x)/(x^3)
	à 1E-02 près.
*/

#include <stdio.h>
#include <math.h>

/*
	Nous savons que l'intégrale de Riemann est la somme d'une série :
	int[0,1->10](f(x)dx) = lim[n->+oo] (10-0,1)/n * sum[k : 0->n-1](f(0,1 + k(10-0,1)/n))
	
	L'erreur commise est, en fonction de n, majaurée par (10-0,1)/n * | f(0,1) - f(10 - (10-0,1)/n) |
	donc majaurée par (10-0,1)/n * |f(0,1) - f(10)|
*/

double f(double x); // cf, analyse

void main()
{
	double Integrale = 0;
	double Epsilon = 1;
	const double ConstEps = 9.9 * ( f(0.1)-f(10) );
	int n = 1, k; // cf, analyse
	
	while(Epsilon >= 0.01)
	{
		n *= 2; // Mieux vaut plus que moins, cela accelère le calcul (ne complexifie pas tellement le calcule de Integral)
		Epsilon = ConstEps / n;
	}
	
	// Nous avons notre n tel que Epsilon < 1E-02, nous calculons donc la somme de la série
	for(k=0; k<=n-1; k++)
		Integrale += f(0.1 + k*(10-0.1)/n);
	Integrale *= (10-0.1)/n;
	
	// Il nous suffit d'afficher le résultat
	printf("L'integrale de 0,1 a 10 de exp(-x)/(x^3) est : %f\n", Integrale);
	return;
}


double f(double x)
{
	return exp(-x)/pow(x, 3);
}

Bonne chance à toi (tu verra l'algo c'est génial, la prog un peu moins).

[sebsheep]

ta réponse est intéressante jobherzt mais je reste sur ma position, s'il veut faire des études d'info, autant qu'il voit tout de suite si ça l'intéresse ou pas => faire un peu de C et de graphes est une bonne option s'il ne sait pas quoi regarder d'ici septembre

Autant sur le C je suis d'accord, autant sur les graphes, c'est un peu dur pour commencer je trouver (surtout en C, pour faire ça bien faut maitriser les pointeurs itou). Calculer une intégrale comme l'a proposé prgasp me paraît plus adapter pour commencer (quand on est en terminale S et qu'on sait parfaitement ce que c'est, sinon, aucun interet!).

Enfin bref, ce topic dévie déjà ... Tino découvre ici la joie d'être geek : débattre passionnement sur des sujets dont tout le monde (à part les geeks bien sur) se fiche et n'y comprend rien, de toute façon. Et évidement, tout le monde a raison et possède le meilleur avis qui existe sur la question. En gros, sans le savoir/vouloir, tu as lancé un troll (assez récurent au passage) : par quel langage commencer la programmation? (alors que tu ne poses même pas la question au début ...)

Et pour rajouter du troll au troll déjà bien velu :

Bonne chance à toi (tu verra l'algo c'est génial, la prog un peu moins).

Tout l'inverse pour moi : algo : utilise un langage que personne utilise, sous une forme totalement différente de vrais langages ce qui n'habitue pas trop au code.

Moi j'ai commencé directement à coder comme un gros bourin, pour commencer et faire afficher la table de 10, pas besoin de s'emmerder avec un papier ; ça c'est pour des trucs plus compliqués. Parce que quand on est débutant, quel bonheur de voir notre programme qui fonctionne pour de vrai sur la machine (tu admettras qu'un bout de papier sur le quel est griffoné des symboles mystique n'est pas bien glamour).

[prgasp77]

Et pour rajouter du troll au troll déjà bien velu :



Tout l'inverse pour moi : algo : utilise un langage que personne utilise, sous une forme totalement différente de vrais langages ce qui n'habitue pas trop au code.

Moi j'ai commencé directement à coder comme un gros bourin, pour commencer et faire afficher la table de 10, pas besoin de s'emmerder avec un papier ; ça c'est pour des trucs plus compliqués. Parce que quand on est débutant, quel bonheur de voir notre programme qui fonctionne pour de vrai sur la machine (tu admettras qu'un bout de papier sur le quel est griffoné des symboles mystique n'est pas bien glamour).

Mince, je suis découvert !
J'ai moi aussi commencé à programmer directement. J'ai commencé sur mon magnifique Genius 6000 à l'âge de 10 ans, et en basic avec pour instructeur mon papa qui trouvait amusant de me piquer mon jouet parce que ça lui rappelait le bon vieux temps (du basic tout-ça).
Mais je me suis rendu compte au fil du temps que je préfère les maths à l'informatique, du coup je préfère l'algo à la prog ... c'est cohérent.

Et pour donner un dernier coup de pinceau à ce troll, coder sous windows c'est comme faire apprécier du Chopin (Oui, j'aime pas Mozart) à un chien (nettement inférieur au chat tout le monde le sait). Passez sous Linux (et particulièrement Débian parce que c'est la meilleur distrib', sans Emacs préinstallé qui sert à rien puisqu'il y a vi).

Bonne soirée.

[sebsheep]

Et pour donner un dernier coup de pinceau à ce troll, coder sous windows c'est comme faire apprécier du Chopin (Oui, j'aime pas Mozart) à un chien (nettement inférieur au chat tout le monde le sait). Passez sous Linux (et particulièrement Débian parce que c'est la meilleur distrib', sans Emacs préinstallé qui sert à rien puisqu'il y a vi).

Bonne soirée.

Je suis d'accord avec toi, coder sous windows et Mozart, c'est pas top (quoi que chez Mozart, y a des choses que j'aprécie).

Par contre je suis horripilé de voir que tu puisse mettre en doute la supériorité d'Emacs et de Mandriva, qui est la meilleure distrib'.

Pour les chiens et chat, ils sont de toute façon nettement inférieurs aux trolls ...

PS : faire commencer la prog' à son gamin de 10 ans, et voilà ce que ca devient plus tard : un mathématicien ... mefiez vous papas geeks, vous êtes en train de produire des erreurs de la nature

[prgasp77]

PS : faire commencer la prog' à son gamin de 10 ans, et voilà ce que ca devient plus tard : un mathématicien ... mefiez vous papas geeks, vous êtes en train de produire des erreurs de la nature

Mouarf'
Pour info, et pour ne pas l'incriminer, c'est moi qui voulait voir ce qu'il faisait. Selon ma famille, ma période "Pourquoi ..?" a duré très longtemps et était extrêmement intense.