Algorithmique

Programmation
#1

Bonjour tous le monde, ben voilà suite au topic “J’aimerais apprendre la programmation” (avec 2 m ça va mieux) je lance le même topic mais pour l’algo.

En fait j’ai des lacunes à ce niveau là et je souhaiterais les combler mais j’aimerais partir du début, histoire d’avoir les bonnes bases. Donc, si vous avez quelques notions que ce soit à ce sujet n’hésitez pas à venir en discuter ici. L’objectif pourrait être à terme de lancer par exemple un petit exercice et on posterait les réponses ça permettrait d’avoir des résolutions différentes à confronter.

Enfin sinon, il y a toujours les bouquins mais je trouve cela moins fun, plus chiant et plus difficile à appréhender qu’en communauté comme ça. Même si bien sûr ça reste incontournable donc si vous connaissez des références dans l’algo tenez moi informé :wink:

#2

Je cite mon message précédent :

[quote]
Une des références sur la programmation : The Art of Computer Programming [1].

[1] http://www.amazon.fr/Art-Computer-Programming-Volumes-Boxed/dp/0201485419[/quote]
Actuellement, il est composé de 3 volumes :

  • Volume 1, Fundamental Algorithms
  • Volume 2, Seminumerical Algorithms
  • Volume 3, Sorting and Searching

C’est peut-être moins fun, mais tellement plus instructif. Après avoir lu et compris tout ça, tu seras bien préparé pour affronter toute sorte de problème algorithmique.

#3

J’imagine que tu connais l’introduction à l’algorithmique ?

#4

Qu’est ce que tu entends par étudier l’algorithmique? Ça consiste en fait en plusieurs choses:

  • Une partie théorique:
  • Démonstration qu’un algorithme fait bien ce que tu veux, c’est très mathématique, liée à la notion d’invariant de boucle et souvent fait de manière intuive dès qu’on sait programmer (Se rappeler que si un charpentier n’a aucune idée de ce qu’est la tangente d’un angle, il ne sait jamais trompé pour que la ferme de 10m qu’il fabrique soit juste à 2-3mm près lors de l’assemblage sur site, ni sur le nombre de tuiles).
    Exemple pour illustrer:

let max lst = let rec boucle m l = match l with | [] -> m | a::suite -> (boucle (if a>m then a else m) suite) in boucle (hd lst) (tl lst);;
L’invariant de boucle est la description exacte et précise des arguments de la boucle (c’est pour ça entre autres que la programmation fonctionnelle est très rigoureuse). Ici c’est «Au début de la kième boucle, l est constituée des (n-k) élements de lst, m est le maximum de k premiers éléments de lst (où n est la longueur de lst). C’est invariant de boucle est vrai par induction, l’algorithme fonctionne.
N’importe qui ayant programmé finit par faire ce genre de raisonnement sur ces programmes (sans le formaliser à ce point).

  • Complexité: Evaluer la complexité d’un algorithme, c’est la partie la plus importante: Il faut définir ce qui est la taille des données, ce qui mesure le travail effectué et la relation entre les deux. La taille de la sortie peut être importante car dans ce cas, ce qui valide l’efficacité de l’algorithme est le rapport complexité/taille la sortie.
    Cette partie là n’est pas toujours simple, nécessite des Maths ou peut se faire de manière intuitive. Exemple: difgférence d’efficacité entre

et

let rec puissance x n = if (n=1) then x else let y = (puissance x (n/2)) in if (n mod 2) = 1 then (produit (produit y y) x) else produit y y;;

  • Une partie pratique:
    Les algorithmes classiques et comment se ramener à ces algorithmes: Programmer c’est organiser les données et faire des fonctions sur ces données. La programmation objet est l’aboutissement logique de ça (où la structure de données contient aussi les méthodes agissant sur ces données). On se fonde sur un type d’organisation (Liste, Arbre, Graphe, …) et on peut utiliser des algorithmes connus et efficaces sur ces structures.

Après tu as aussi des parties spécialisées (algorithmes dans le cryptage, dans le calcul numérique, génétiques, etc)

#5

Je n’arrive définitivement pas à lire du Caml.
Je sais pas vraiment pourquoi.

Trop habitué à la syntaxe du C qui est reprise ou très inspiré dans un nombre phénoménale de langage. :confused:

#6

Ce sont des fonctions, sans doute tu cherches ce que ça fait alors qu’il faut chercher ce que ça vaut, c’est ça qui te gène… (sinon ton argument rappelle ceux qui soutiennent Windows et son interface :smiley: mais c’est juste une remarque :slightly_smiling:)

#7

C’est un constat d’échec de ma part et pas un dénigrement du caml (on m’a toujours dis du bien des langages fonctionnels).

#8

As tu vu du Lisp??? Jettes un oeil sur les sources d’emacs:

[code](defgroup calculator nil
"Simple Emacs calculator."
:prefix “calculator”
:version “21.1”
:group 'tools
:group 'convenience)

(defcustom calculator-electric-mode nil
"*Run `calculator’ electrically, in the echo area.
Electric mode saves some place but changes the way you interact with the
calculator."
:type 'boolean
:group 'calculator)

(defcustom calculator-use-menu t
"*Make `calculator’ create a menu.
Note that this requires easymenu. Must be set before loading."
:type 'boolean
:group 'calculator)

(defcustom calculator-bind-escape nil
"*If non-nil, set escape to exit the calculator."
:type 'boolean
:group 'calculator)

(defcustom calculator-unary-style 'postfix
"*Value is either 'prefix or 'postfix.
This determines the default behavior of unary operators."
:type '(choice (const prefix) (const postfix))
:group 'calculator)

[/code]

#9

Ca dépend du lisp, l’elisp ouai j’ai un peu vu. J’ai tenté en vain de déclarer une fonction.
Les autres lisp non.

#10

Je ne connais pas le brainfuck, mais à part la polonaise inversée et le prolog, je n’ai rien trouvé d’aussi peu naturel pour moi que le lisp.
Quelle horreur. Et pourtant, j’en ai bouffé (scheme, elisp, lelisp). J’ai même fait une interface graphique en scheme pour un moteur de calcul formel à l’époque.
C’est clair, c’est pas comme ça que je parle.

#11

On voit que tu n’as pas fait du Forth :slightly_smiling:

#12

Pour faire simple j’ai quelques fois des soucis de raisonnements et n’arrive pas à concevoir une appli optimisée du premier coup (quelques fois je pond des solutions alambiqué mais fonctionnelle alors qu’il y a plus simple) donc pour des applis complexe je peux le comprendre mais pour des choses simples j’aimerais avoir un peu plus de connaissance théorique pour le faire plus aisément. Et ce n’est qu’une étape car il me faut aussi des cours de méthodologie donc j’essaie de combiner les 2 pour m’améliorer :wink:

Et il faut bien commencer quelque part :smiley:

Merci pour vos remarques, je dois encore commander quelques livres mais ca se fera :wink: je ne me contenterais pas du net :smiley:

#13

Je ne suis pas un super développeur qui pond toujours des codes ultra optimisés mais il y a une chose qui m’a beaucoup aidé : la prog sur micro contrôleur.
Notamment quand je bossais sur les téléphones : à l’époque on avait pas des grosses machines comme maintenant il fallait tout faire rentrer dans une petite brouette C51.
Cela m’a donné des automatismes de programmation qui me servent encore.

#14

Un lien intéressant : http://www.catonmat.net/blog/category/introduction-to-algorithms/page/3/

#15

ah tiens, c’est une des plus marrantes curiosités que j’ai rencontrées dans mon cours d’algo moi :stuck_out_tongue:

ca c’est la biblio d’un cours d’algo que j’ai eu:

#16

En Français, un poly de 220 pages, introduction à l’algo et bases de la prog:

catalogue.polytechnique.fr/site.php?id=78
catalogue.polytechnique.fr/site. … fileid=414
enseignement.polytechnique.f … ue/INF421/

#17

Bonjour,

Je pense que si tu veux acquérir de bonnes méthodes de programmation, le cursus que j’ai suivi dans mon école est pas mal. Je te le décris et les autres pourront dire ce qu’ils en pensent :

- 1er: Apprentissage des bases de l’algorithmie. 2 ouvrage majeurs:
* Jacques Courtin, Irène Kowarski (1994) Initiation à l’algorithmique et aux structure de données, Volume 1, Dunod, 349 pages.
* Jacques Courtin, Irène Kowarski (1994) Initiation à l’algorithmique et aux structure de données, Volume 2, Dunod, 481 pages.
(envoie un MP si tu est intéressé par des manuels, poly et exos)

  • 2e: Apprentissage de l’ADA, langage extrêmement stricte et typé concordant bien avec l’algo. C’est surtout un langage utilisé dans l’aéronautique et l’embarqué ==>> utile simplement pour acquérir des bonnes méthode stricte de programmation.
    (envoie un MP si tu est intéressé par des manuels, poly et exos)

  • 3e: Apprentissage du C (programmation classique), programmation plus souple et pérmissive…
    (envoie un MP si tu est intéressé par des manuels, poly et exos)

  • 4e: Apprentissage PHP4 (programmation classique), programmation très souple et très permissive…
    (envoie un MP si tu est intéressé par des manuels, poly et exos)
    (Fin de 1er Année)

(2e Année)

  • 5e : Apprentissage C++ ( POO ) , découverte d’un nouveaux style de programmation!
    … ensuite JAVA , PHP5 etc… le reste tu trouvera ton bonheur sur le WEB.

Je n’ai pas parlé du SQL, des bases de données car je crois que ce n’est pas ton objectif.
Je n’ai pas parlé du génie logiciel, et de la modélisation car je crois que ce n’est pas ton objectif.

Je pense que ce cheminement permet d’acquérir de bonne méthode de programmation, surtout au début avec algo + ADA.
Beaucoup de gens critiqueront cela, je rappel qu’à l’ENSIMAG, les étudiants en première année suivent un cursus similaire ( au début du moins algo, ada…)

#18

Je bosse juste en face d’ENSIMAG :slightly_smiling: Un collègue qui y fait ses études m’expliquait que certains étudiants comprenaient rien à la compilation après un semestre.

Je ne crois pas en un parcourt type qui soit parfait. Ça dépend de celui qui suit la formation.

#19

(Ces étudiants dont tu parle n’ont peutètre pas validé leur 1er semestre!)
Et je suis d’accord avec toi, j’ai juste présenté un parcourt d’apprentissage que j’ai trouvé plutot pas mal et logique… Surtout au niveau méthode/Algo et c’est pour cela que j’ai voulu en parlé ici. Après un débat est possible mais il n’a pas sa place sur ce topic je pense.

#20

[quote=“thomasp”]Bonjour,

Je pense que si tu veux acquérir de bonnes méthodes de programmation, le cursus que j’ai suivi dans mon école est pas mal. Je te le décris et les autres pourront dire ce qu’ils en pensent :

- 1er: Apprentissage des bases de l’algorithmie. 2 ouvrage majeurs:
* Jacques Courtin, Irène Kowarski (1994) Initiation à l’algorithmique et aux structure de données, Volume 1, Dunod, 349 pages.
* Jacques Courtin, Irène Kowarski (1994) Initiation à l’algorithmique et aux structure de données, Volume 2, Dunod, 481 pages.
(envoie un MP si tu est intéressé par des manuels, poly et exos)
[/quote]Merci bien c’est des ouvrages intéressants je jetterais un oeil[quote=“thomasp”]

  • 2e: Apprentissage de l’ADA, langage extrêmement stricte et typé concordant bien avec l’algo. C’est surtout un langage utilisé dans l’aéronautique et l’embarqué ==>> utile simplement pour acquérir des bonnes méthode stricte de programmation.
    (envoie un MP si tu est intéressé par des manuels, poly et exos)
    [/quote]Je ne connais pas ce langage mais si ça permet de coller assez fidèlement à l’algo pourquoi pas[quote=“thomasp”]
  • 3e: Apprentissage du C (programmation classique), programmation plus souple et pérmissive…
    (envoie un MP si tu est intéressé par des manuels, poly et exos)
    [/quote]En C non pas trop besoin de cours j’en fais pas suffisamment pour cela et le peu que je fais je le fais propre :smiley:[quote=“thomasp”]
  • 4e: Apprentissage PHP4 (programmation classique), programmation très souple et très permissive…
    (envoie un MP si tu est intéressé par des manuels, poly et exos)
    (Fin de 1er Année)
    [/quote]php4 non merci c’est bon je pense que ca peux aller à ce niveau là :wink:[quote=“thomasp”]
    (2e Année)
  • 5e : Apprentissage C++ ( POO ) , découverte d’un nouveaux style de programmation!
    … ensuite JAVA , PHP5 etc… le reste tu trouvera ton bonheur sur le WEB.
    [/quote]PHP5 là aussi je pense que ça va je me débrouille :smiley:[quote=“thomasp”]
    Je n’ai pas parlé du SQL, des bases de données car je crois que ce n’est pas ton objectif.
    Je n’ai pas parlé du génie logiciel, et de la modélisation car je crois que ce n’est pas ton objectif.

Je pense que ce cheminement permet d’acquérir de bonne méthode de programmation, surtout au début avec algo + ADA.
Beaucoup de gens critiqueront cela, je rappel qu’à l’ENSIMAG, les étudiants en première année suivent un cursus similaire ( au début du moins algo, ada…)[/quote]Pour le reste tu as raison ce n’est pas mes objectifs principaux mais avoir de bonnes notions dans ces domaines peut être intéressant.