Bonjour
Je vous explique ma situation , je suis en 1er année de Licence Maths/Informatique
On a commencé par étudier le caml en programmation (pour le moment je me débrouille bien dans cette matière) , mais en méthodologie universitaire mon prof m'a donné un sujet traitant un sujet que je n'ai pas étudier et que je n'étudierais pas cette année d'après ma prof de prog .
Afin de pouvoir lui rendre quelque chose de correct je me tourne vers vous en espérant trouver une aide  
 
Voilà les 4 questions posées (je tiens a préciser que je ne comprend que le C (C++) et le Caml)
 
1 Donner un algorithme "évident" permettant de trier un ensemble . Discuter la "compléxité" de cet algorithme en termes de nombre de lectures, d'écritures et de comparaisons de valeurs (par rapport a la taille de l'ensemble)
2 Proposer des algorithmes "plus efficaces" que le précédent permettant de trier un ensemble . Discuter la complexité de ces algorithmes en regard des critères précédents
3 Donner un algorithme "évident" permettant de déterminer la présence d'un élément dans un ensemble trié . Discuter la "compléxité" de cet algorithme en termes de nombre de lectures et de comparaisons de valeurs (par rapport a la taille de l'ensemble)
4 Proposer des algorithmes "plus efficaces" . Discuter la complexité de ces algorithmes en regard des critères précédents

Je poste mais j'ai pas comprise la question... http://fr.wikipedia.org/wiki/Liste_des_algorithmes
 

Bah je peux pas trop expliquer les questions ne les ayant pas compris moi même d'où ma question sur le forum

Je pense qu'il s'agit de d'étudier quelque solutions et d'en connaître leur propriété en terme de complexité.
Tu peux regarder ce doc sur la complexité algorithmique : Théorie de la complexité des algorithmes
 
Mais c'est pas partie, je ne pourrai t'avancer d'avantage, si ce n'est te dire qu'un tris à bulle et plus ou moins complexe d'un trie rapide.

C'est pas gagné :s , car en cours je n'ai vu en Caml que les tests if then else les n uplet ,les enregistrements , les récurrences et les listes
 
J'en ai parlé a ma prof de prog que ce sujet n'est pas du niveau d'un licence 1er année elle a dit qu'elle en parlerai au prof qui m'a donné ce sujet cependant je me retrouve devant ce sujet sans savoir comment m'y prendre , je souhaite aussi vous remercier pour vos réponses mais elles restent encore obscures à mes yeux, si qlq pouvait me l'expliquer de manière assez claire ca serait parfait

Salut a toi,
Bon je pense que je vais pouvoir t'aider...
Déja, c'est du niveau premiere année, pour ce qui est du petit 1° propose un tri par minimum (tu as bien du faire ca en c ? dans des tableaux) Dans deux boucles, si l'élément x est > a l'élément x+1 alors tu les inverses ect...
Pour le 2) plus difficile, la dichotomie ? ca te dit qqch ?
3) on suppose les éléments triés, une méthode est de chercher dans une boucle jusqu'a temps de trouver l'élément (regarde la nb, si c'est celui ci c'est bon sinon tu passe au suivant)
4) idem pour optimiser, la dichotomie.

Je pense que si tu part la dessus ca devrait aller

edit: pour les discussions, il faut trouver le nb maximum d'opération qui seront effectuées pour chaque algo