Analyse en algorithmique

Bonjour,

J’ai déjà des notions de bases en algorithmique que j’ai apprises a la fac cette année, cependant le programme ne contenait pas de partie sur les preuves de programmes.

J’entends pas la le fait de verifier/prouver qu’un algorithme est bon, qu’il se termine, qu’une boucle se termine, etc. J’ai cru comprendre que ça faisait pourtant partit des bases de l’algo, de l’analyse en gros.

Par contre on eu une partie sur la complexité, mais la encore très rapidement, clairement pas assez a mon goût, en fait, j’aimerais vraiment me mettre à niveau en analyse algorithmique, la mathématique nécessaire pour ça en tout cas. C’est-à-dire apprendre les méthodes pour calculer la complexité d’un quelconque, et être capable de prouver/verifier.

En général, pour calculer des complexités, on manipule souvent des indices sommatoire et il y a toute une algèbre et propriétés autour de ça que je ne connais pas et n’ai pas apprise.

(quand, je dis quelconque, c’est évidemment de niveau licence/master quoi, des trucs faisable)

Si vous avez des cours, livres, conseils a donner, je suis preneur. Faut que je fasse beaucoup d’exercices, je pense.

Salut,

Tu trouveras en partie ton bonheur par ici : https://en.wikipedia.org/wiki/Category:Formal_methods (connaitre le bon terme aide )

En partie effectivement, merci !

Hum, ce que tu veux c’est prouver la validité de ton algorithme ou connaître les méthodes utilisées pour prouver la validité d’un algorithme ?

J’ai pas bien compris ce que tu recherches.

Il me semble que c’est apprendre de manière générale l’algorithmique.

Alors moi qui me lance dedans pour participer au Google Code Jam dans un an, je m’y suis pas mal intéressé. J’ai la chance d’avoir un accès permanent à ce livre qui est clairement la bible. Ceci dit tu ne connaitras pas tout encore, loin de là. Mais avec ce livre bien compris voire maîtrisé tu as les bases les plus solides possibles (tu vas apprendre comment concevoir un algo, prouver qu’il est juste, calculer sa complexité… mais aussi construire des structures de données). La suite sera essentiellement de la pratique. Ce qui manque principalement c’est la programmation concurrente et les algorithmes d’apprentissages qui ne sont pas ou peu abordé dans ce livre. Et bien entendu le livre n’aborde pas tout les algorithmes spécifiques à certains domaines comme l’analyse d’image.

Ensuite tu as cette réponse sur Quora qui a le mérite d’être assez complète avec beaucoup de lien et d’explication. Par contre c’est en anglais.

Je te met en garde rapidement puisque j’ai fait cette erreur, il faut absolument que tu codes tes algos. Quand on te parle de tri insertion, quick sort… Tu connais peut être le fonctionnement des algorithmes mais il faut vraiment apprendre à les coder et chercher à le faire de manière optimale et y passer du temps. Je te conseil même de les coder dans différents langages assez éloigné (selon ton temps et tes connaissances) : Python (parce qu’il est haut niveau et pour commencer c’est plus simple), C (pour les pointeurs / pointeurs de fonctions notamment) ou Rust (je ne connais pas mais c’est un bon langage bas niveau), C++ (pour la STL et les templates) et un langage fonctionnel (en général on apprend Caml à la fac mais tu peux changer vers Lisp ou Haskell ou autre).

C’est long de faire tout ça et tu vas devoir apprendre pleins de nouveau langages. Certains vont peut être me répondre que c’est pas une bonne idée parce que dans chaque langage tu feras des bêtises. Le but n’est pas du tout d’apprendre à maîtriser les langages cités mais d’avoir des approches différentes de tes algorithmes et d’apprendre à utiliser différents concepts (un arbre en Python est très différent en C) pour être le plus flexible et complet possible.

Sinon, par curiosité, tu es à quel niveau d’étude ?

Le site possède aussi un tutoriel sur frama-C qui est un soft développé par des chercheurs qui permet de prouver correct des programmes écrits en C. Les méthodes formelles demandent cependant en général un bon background en maths/logique. Si par hasard tu as d’autres questions, je pourrais y répondre car mon domaine de recherche est la preuve formelle qui est un sous-domaine des méthodes formelles.

Bon je HS un peu par rapport a mon sujet du coup, mais j’en profite, perso, je suis intéressé par les domaines théorie des langages, langages formels, etc. Mais c’est trop vaste et inconnu pour moi pour avoir des questions a poser. Les méthodes formelles ont forcément un lien avec la théorie des langages ? Sous domaine ou sûr ?

Le plus simple, je pense, c’est que tu me racontes ce que tu fais et dans quel domaine de l’informatique théorique ça intervient, j’ai besoin de trier un peu le nuage d’infos que je trouve sur le net pour savoir ce qui pourrait vraiment me plaire et aller lire sur le sujet. Et c’est aussi pour ça que j’ai du mal a exprimer clairement ce que je veux apprendre par rapport au thread

Je suis nouveau sur le site/forum.