Algorithmie, ca ressemble a koi ?

Recherche :

Dernière réponse
Sujet : Algorithmie, ca ressemble a koi ?
matafan	Un algorithme, c'est une succession d'opérations qui permettrons systématiquement de résoudre un "problème" particulier. On parle généralement d'algorithmes en informatique, mais ça peut s'appliquer à n'importe quoi. En mathématiques par exemple on peut parler d'algorithmes, même si l'on utilise pas d'ordinateur (par exemple "l'agorithme d'Euclide" pour trouver le PGCD de deux entiers). L'algorithmique, c'est la science des algorithmes. Rapporté à l'informatique, c'est l'étude des "méthodes" qui permettent de résoudre certaines classes de problèmes. L'algorithmique étudie la façon de résoudre un problème (par exemple trier un tableau, avec éventuellement des hypothèses concernant les données à trier), sans se soucier du langage utilisé. En gros l'algorithme c'est l'idée, que l'on peut ensuite implémenter dans un langage quelconque. Il n'y a pas une façon de décrire un algorithme. Tu peux le faire en français de façon très informelle, tu peux faire du pseudo-code comme plus haut (avec des "tant que machin"...), tu peux aussi le faire dans un langage particulier. Mais tu peux tout aussi bien faire un dessin, des diagrammes de séquence...

Dernière réponse

Sujet : Algorithmie, ca ressemble a koi ?

matafan

Un algorithme, c'est une succession d'opérations qui permettrons systématiquement de résoudre un "problème" particulier. On parle généralement d'algorithmes en informatique, mais ça peut s'appliquer à n'importe quoi. En mathématiques par exemple on peut parler d'algorithmes, même si l'on utilise pas d'ordinateur (par exemple "l'agorithme d'Euclide" pour trouver le PGCD de deux entiers).

L'algorithmique, c'est la science des algorithmes. Rapporté à l'informatique, c'est l'étude des "méthodes" qui permettent de résoudre certaines classes de problèmes. L'algorithmique étudie la façon de résoudre un problème (par exemple trier un tableau, avec éventuellement des hypothèses concernant les données à trier), sans se soucier du langage utilisé. En gros l'algorithme c'est l'idée, que l'on peut ensuite implémenter dans un langage quelconque.

Il n'y a pas une façon de décrire un algorithme. Tu peux le faire en français de façon très informelle, tu peux faire du pseudo-code comme plus haut (avec des "tant que machin"...), tu peux aussi le faire dans un langage particulier. Mais tu peux tout aussi bien faire un dessin, des diagrammes de séquence...

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

matafan

Jubijub

pis faut se méfier : l'algo c un mode de raisonnement...mais certains truc que tu définis en algo se codent pas...

exemple tt con :

x réel
afficher "entrez la valeur de x"
lire x

en dbase par exemple, ca se codera comme ca :
accept"entrez la valeur de x" to x

tu définie pas que x est réel, car accept ne remplit que des variable de type réel...de même, une seule instruction permet de faire 2 opérations...

tt les langages ont l'équivalent du input, qui permet d'afficher un texte et de remplir une variable avec une entrée clavier...

ben en algo, ca existe pas :
écrire "[texte]"
lire [variable]

--> input [texte],[variable]

gfive

LeGreg : ça me rapelle mes cours d'algo de première année! !arg! :D
Sinon, je suis d'accrod avec toi, en ce qui concerne la différence pratique/théorie... Ce que je voulais dire, c'est que limiter l'algo à la partie "application" à des cas pratique, c dommage, pasque la thérorie pure est vachement intéressante, et en plus, c'est ça que max.evans risque de rencontrer.. (enfin, ça dépend de l'école, je pense, mais en tout cas, là où j'étais, on a fait la théorie et la mise en pratique.)

LeGreg

youdontcare a écrit a écrit :

o(k*n) pour le radix, où k = 4 pour trier un dword / float32 avec du bytesort.
mais, n'a t-on pas justement prouvé que le meilleur tri était en o(ln(n)*n) ? :D

On peut faire au mieux un algorithme de tri dont le cas le pire
prendra un temps en Theta(ln(n)*n) (dire qu'il est en 'petit' o donne beaucoup moins d'info qu'en grand Theta, donc on n'utilise jamais la notation petit o en algorithmie).

C'est a dire qu'il prendra dans tous ses cas les pires un temps entre k1*ln(n)*n et k2*ln(n)*n pour trier un ensemble de n entiers tous differents.

Le "tous differents" a une importance parce qu'on peut arriver
a des algorithmes plus efficaces lorsque le nombre de valeurs prises par les elements a trier est lui-meme borne.
Mais c'est reduire l'algorithme de tri a un sous-ensemble
ou son cas le pire peut etre reduit.
cas du bytesort: tu ne peux pas construire d'histogrammes si les valeurs prises sont toutes differentes, ou alors l'histogramme est aussi grand que ton ensemble d'elements a trier.

Le probleme c'est que ca ne te dit pas quel algorithme utiliser en fait.. tu peux exclure d'emblee tous les tris qui prennent
un minimum asymptotique de n*n operations, d'ailleurs je crois que s'il y en avait un tout le monde l'a oublie.
Par contre, le tri fusion prend un temps en Theta(n*log(n)) dans son cas le pire.
Mais dans beaucoup de cas, on lui prefere un tri QuickSort
qui a un cas le pire en Theta(n*n).
incroyable non? En fait pas tant que ca, le quick sort prend en moyenne un temps en Theta(n*log(n)) (je ne te sors pas la demonstration mais ca se fait par recurrence) et est dans beaucoup de cas, plus rapide que le tri fusion.

La valeur des k est tres importante dans tous les cas pour
departager deux algorithmes dont la complexite parait
semblable, ainsi que l'utilisation memoire ou encore
le temps de pretraitement, ou d'autres contraintes
externes mais l'etude algorithmique sur un projet
"pratique" doit inclure toutes les contraintes du projet
sinon ca n'a pas de sens.

A+
LEGREG

[jfdsdjhfuetppo]--Message édité par legreg--[/jfdsdjhfuetppo]

Max Evans

Lol oki, encore merchi pour tous ces renseignements ! :jap:

youdontcare

>> Houlalala, kes ke ca ve dire ???

o() est juste le standard pour noter la complexité de l'algo que tu utilises.

par ex, trier un tableau de n entrées : o(n) = tu fais n opérations pour trier ton tableau.
o(k*n) = tu fais k*n opérations pour trier ton tableau.

o(ln(n)*n) = tu fais _en moyenne_ ln(n)*n opérations pour trier ton tableau.

>> Donc, si g bien compris, kand on fe un prog, y a un moment ou on va etre coincé et se sert de l'algo pour decomposer le pb, et le resoudre ?

en général c'est bien d'avoir une idée de comment tu vas t'y prendre _avant_ d'écrire le code :D mais là on sort de l'algorithmiquee pure, qui est d'après mon petit larousse :

algorithmique : science des algorithmes.

algorithme : suite finie d'opérations élémentaires constituant un schéma de calcul ou de résolution d'un problème.

Max Evans

youdontcare a écrit a écrit :

o(k*n) pour le radix, où k = 4 pour trier un dword / float32 avec du bytesort.

mais, n'a t-on pas justement prouvé que le meilleur tri était en o(ln(n)*n) ? :D

Houlalala, kes ke ca ve dire ??? :) :)
Donc, si g bien compris, kand on fe un prog, y a un moment ou on va etre coincé et se sert de l'algo pour decomposer le pb, et le resoudre ? :)

youdontcare

gfive a écrit a écrit :

que le meilleur alogo de tri a une complexité de...Medre, je sais plus! :D

o(k*n) pour le radix, où k = 4 pour trier un dword / float32 avec du bytesort.

mais, n'a t-on pas justement prouvé que le meilleur tri était en o(ln(n)*n) ? :D

[jfdsdjhfuetppo]--Message édité par youdontcare--[/jfdsdjhfuetppo]

gfive

Ouais, c'est un peu restrictif, de dire que l'algorithmie se résume à écrire un programme en français...Ca se rapproche plus d'une science à part entière....je dirait..que c'est la théorisation de la programmation....Ca implique des maths, des stats (pour nottament calculer la complexité des algorithmes, et pour dire q'il sera - à priori - plus efficace de faire de telle ou telle façon pour résoudre un problème (a priori, parce que évidemment, la mise en pratique peut soulever des particularités) ... Comme en maths, aussi, il y a des "théorèmes"...je m'explique : on peut démontrer (c galère, mais ça se fait), que le meilleur alogo de tri a une complexité de...Medre, je sais plus! :D mais bon, il a une complexité donnée, et on sait qu'on trouvera pas mieux, etc, etc...On peut aussi faire intervenir des math pour démontrer qu'un problème est indécidable, ce qui évite de se faire chier à chercher un algo pour le résoudre, etc, etc..

Max Evans

Oki, merci bocoup a vous tous :) :jap:

Roco

1 / tu écris un cahier des charges en français expliquant quelles sont les données dont ton programme dispose, et quel est son objectif.

2 / tu écris un algorithme, c'est-à-dire une suite d'instruction résolvant le problème .

3 / tu traduis cet algorithme en n'importe quel langage de programmation (java/C++).

4/ tu compiles ce programme, c'est-à-dire que tu le transformes en un fichier binaire (0,1) compréhensible par la machine.

massanu

Juis en IUT info

Max Evans

massanu a écrit a écrit :

bah ouais ca se compile pas l'algo lol

c pour voir tes capacité a resoudre un probleme sous forme de programme
ensuite a toi de ladapté dans le langage que tu utilise, c ca l'avantage

l'algo ca se fait sur feuille de papier et c tout

Ha oki :)
Au fait, Massanu, t'es en kelle classe ? ;)

massanu

bah ouais ca se compile pas l'algo lol

c pour voir tes capacité a resoudre un probleme sous forme de programme
ensuite a toi de ladapté dans le langage que tu utilise, c ca l'avantage

l'algo ca se fait sur feuille de papier et c tout

Max Evans

bilgetz_42 a écrit a écrit :

sur mon site:
http://www.bilgetz.fr.st/
j'explique 2-3 truc
il est moche mais fait y pas gaffe

Je viens de lire en diagonale, c bien expliqué :jap:
Mais par contre, le truc que je comprends pas, c qu'en algorithmie, on peut pas executer un programme ?
Par exemple, en Turbo Pascal, on compile le prog, et ensuite on le fe marcher ...
Mais en algo, on ecris juste, mais on peut pas faire fonctionner un programme juste en algo non ? :)

bilgetz_42

sur mon site:
http://www.bilgetz.fr.st/
j'explique 2-3 truc
il est moche mais fait y pas gaffe

Max Evans

massanu a écrit a écrit :

l'algorithmique c ecrire un programme ou une portion de code en langage humaine, en l'occurence le francais, mais avec quand meme quelques regle a respecté

exemple pour affiché les 10 premiers chiffres

POUR i allant de 0 a 9
afficher i
FinPour

tu voit le truc ?

ha c pas de la programmation pure ?
Le code POUR i allant de 0 a 9 , on ecris vraiment ca ? :)

massanu

l'algorithmique c ecrire un programme ou une portion de code en langage humaine, en l'occurence le francais, mais avec quand meme quelques regle a respecté

exemple pour affiché les 10 premiers chiffres

POUR i allant de 0 a 9
afficher i
FinPour

tu voit le truc ?

Max Evans

Hello a tous :hello:

J'aimerais rentrer ds une ecole d'informatique, et tout le monde me parle d'algorithmie ...

Mais c koi ?
Vous auriez pas un petit code sous la main pour me montrer ? :)

Merci a vous :) :jap: