Salut à tous, ça faisait un moment que je m´intéressais à ce domaine des maths/informatique, à savoir la preuve qu´un algorithme donné est juste/unique/le plus rapide etc.
Et cette année le prof d´algo a titillé ma curiosité, et du coup j´ai très envie de savoir si quand j´écris un algorithme, il est juste, sans savoir à passer par la phase coding. Seulement je me doute bien qu´il faut des notions en maths que je suis loin d´avoir acquises et j´aurai voulu vous demander si vous saviez ce qu´il fallait que j´apprenne en théories mathématiques avant de m´attaquer à ces démonstrations algorithmiques.

Merci à tous, bonne journée

Ah la preuve d´algorithme. le seul domaine interessant de l´informatique (snif, snif ca sent le troll ).

Prouver qu´un algorithme est juste est souvent pas tres difficile. On s´interesse aux propriétés qui sont vrai dans notre algorithme.
par exemple si on cherche la plus grande valeure d´un tableau d´entier positif. l´algorithme suivant fonctionne:

entier max = 0
indice i = 0
tant que i est inferieur a taille du tableau T - 1
i = i + 1
si max < T[i] alors max = T[i]

tu peux prouver (par récurence) qu´a la fin d´un tour de boucle, max est supérieur ou égal a toute les valeures de T dont les indices sont inférieur a i. Ceci est la post condition de ta boucle.
Il se trouve que la post condition est aussi la précondition mais il y a des jours ou c´est plus compliqué.

Pour prouver l´unicité d´un algorithme, ca je ne sais pas faire. Il faut voir exactement ce qu´il entends par la. Il n´y a pas de probleme pour lesquels il n´y a qu´un seul algorithme.

Pour montrer que c´est le plus rapide. Tu utilises des bornes inférieurs sur les temps de calcul de ton algorithme. Par exemple, dans l´exemple du minimum, tu ne peux pas assurer a 100% que ta valeur est correcte sans avoir considéré chaque element de ton tableau. Si ton tableau est de taille N, tu es obligé de faire au moins N opérations. Ton algorithme a une complexité temporelle qui apartient a O(N). Tu en déduis que ton algorithme est le plus rapide possible (a un facteur constant pres).

Il y a bien sur des cas plus compliqué pour lesquels les preuves sont egalement plus compliqué. Par exemple, on peut montrer qu´un tri basé sur des comparaisons doit faire au minimum N log (N) comparaisons. Ainsi un tri qui fait de l´ordre de N log(N) comparaison est dit optimal.

J´ai pu emprunter un bouquin super intéressant à la BU : "Structures de données et algorithmes", où j´ai pu avoir un aperçu du calcul de complexité, même si je m´emmêle un peu avec.
Donc en gros je n´ai pas vraiment besoin d´avoir un niveau license en maths pour pouvoir m´adonner à ce domaine (que je trouve passionnant, soit dit en passant ^^) ?

Sinon j´ai encore un peu de mal avec cette "complexité temporelle", ça veut dire quoi exactement ? Que je raisonne en minutes, en secondes ou en heures, la complexité temporelle reste la même ?

Ces questions sont traiter en licence premiere annee d´informatique. Elles sont parfaitement compréhensible.

quand on parle de complexité temporelle, on cherche a donner une estimation de la progression du temps de calcul quand on augmente la taille des donnees. Je dis estimation, parceque l´on fait des calculs au pire cas sur un modele un peu simpliste.

Quand on dit qu´un algorithme a une complexité dans O(n), on veut dire que si sur 1Mo, ca prenait 1 minute, alors sur 2Mo, ca devrait prendre de l´ordre de 2 minutes. la progression du temps de calcul est linéaire dans la taille des données.

Si l´algorithme a une complexité dans O(n^2), alors si sur 1Mo ca prend 1 minute, alors sur 2Mo ca devrait prendre 2^2 = 4 minutes.

oui effectivement, on fait abstraction de l´unité temporelle.
Peu importe, on connait son evolution.
Générallement d´ailleurs, le coup qu´on trouve est proche d´une unité en [temps de quelques instructions machine] puisqu´on evalue le temps de chaque ligne, puis on regarde le nombre d´execution de cette ligne.
Mais le truc c´est qu´une ligne de code d´un langage de haut niveau (entendre par la meme le c++, de haut niveau par rapport à l´assembleur), se traduit en plusieurs lignes d´asm.
Donc du coup on a une fonction dont l´unité serait proche de [temps de QUELQUES instructions machines].

Mais en fait on s´en fiche royallement, ce qui nous interesse vraimment c´est l´évovlution du temps d´execution en fonction de l´évolution de la taille des données, exactement comme l´a expliqué Godrik.

Il faut aussi savoir qu´on ragarde cette compléxité indépendamment de la machine sur laquelle on implémente , et indépendamment du langage utilisé.
Cela est bien sur une approximation car des langages de très haut niveau (comme caml ou haskell par exemple), une fois compilés et traduit en asm peuvent avoir pas mal changés (à cause notamment de la forte abstraction de ces langages, qui coute un peu plus cher en asm, car a la base moins basé sur le fonctionnement de la machine).

je conseil à l´auteur de ce topic de se renseigner sur les algos de tri principaux (fusion, insertion, tri à bulles...) : le code est simple et tu verra comment dans la pratique ces codes sont évalués en terme de performance.
Je crois d´ailleurs que Godrik a fait un papier la dessus, va voir sur sa carte de visite. Sur le net tu trouveras bcp de doc la dessus aussi. (un bouquin d´algo te donnera aussi bcp d´info sympa)

Voila !

Merci beaucoup, je commence à saisir le truc. Justement, dans le bouquin que j´ai emprunté, il y a une cinquantaine de pages traitant des diverses méthodes de tri, je vais donc m´y pencher le plus tôt possible

Qu´ est ce qu´ un algorithme unique ?

Je n´en sais rien, ce sont des questions que je me pose, si ça n´existe pas, tant mieux, ça me fera moins de boulot xD