Très bon article: Essences de la programmation [Oliv. Durin]

par **Napoléon** Jeu 25 Oct - 23:06

Un très bon article rédigé par
Olivier Durin

Cliquer ici pour lire l'article
Essences de la programmation

study

Aperçu sur la table des matières:

1 Introduction
1.1 Encore un livre d’algorithmique ?
1.2 Mais à qui s’adresse ce livre ?
1.3 Que peut-on bien y trouver ?
1.4 Comment le lire ?
1.5 Pourquoi tant de questions ?
2 Formalismes et méthodes
2.1 Conception descendante
2.1.1 Le zen dans l’art du tir à l’arc
2.1.2 Des pyramides et des arbres
2.1.3 Le développement champignon
2.1.4 La programmation à la demande
2.1.5 Revenons sur terre
2.2 Type de données abstrait
2.2.1 Le plus rigoureux possible ?
2.2.1.1 Les entiers naturels
2.2.1.2 Les entiers naturels munis de + et de –
2.2.1.3 Les listes dans la version la plus simple
2.2.1.4 Des listes aux piles et aux files
2.2.1.4.1 LIFO
2.2.1.4.2 FIFO
2.2.2 Un peu de souplesse !
2.2.3 En langage naturel !
2.2.4 Jusqu’où doit-on aller ?
3 Programmation
3.1 Introduction
3.1.1 Clarté ou efficacité
3.1.1.1 Y a-t-il un langage universel dans la salle ?
3.1.1.2 Langages utilisés
3.1.1.2.1 Lisp (lelisp de l’INRIA)
3.1.1.2.2 Pascal et C
3.1.1.2.3 Java
3.1.1.3 Nomenclature
3.1.1.4 Indentation
3.1.2 Prototypage
3.1.3 Le coût de la mise au point
3.1.3.1 Au niveau stratégique
3.1.3.2 Au niveau tactique
3.1.4 Des modules
3.2 La récursivité
3.2.1 Le concept
3.2.1.1 Le théorème de la récurrence
3.2.1.2 Amorcer la pompe
3.2.1.3 Lancer la mécanique
3.2.2 Méthodes pratiques
3.2.2.1 Jamais de cas particulier
3.2.2.2 Programmer « optimiste »
3.2.3 Modèles de fonctions récursives
3.2.3.1 Le modèle non terminal
3.2.3.2 Le modèle terminal
3.2.3.3 Deux fonctions mutuellement récursives
4 Les grandes familles d’optimisations
4.1 L’optimisation de l’algorithme
4.1.1 Rapprocher l’information de la racine
4.1.1.1 Des listes aux arbres
4.1.1.2 Des arbres aux tables de hachage
4.1.2 Factoriser les calculs : les mémofonctions, la cache
4.1.3 Faire les calculs à l’avance
4.1.4 Eviter les calculs inutiles
4.1.4.1 Evaluation à la demande
4.1.4.2 Petits effets de bord
4.1.4.2.1 Mais que sont donc ces fameux « effets de bord » ?
4.1.4.2.2 Comment s’en servir ?
4.1.4.2.3 L’exemple du plus grand rectangle blanc
4.1.4.2.4 Distance entre deux mots
4.1.4.2.5 Optimisation αβ dans l’algorithme Min Max
4.1.4.3 Violents effets de bord
4.2 L’optimisation de code
4.2.1 Cas des fonctions récursives terminales
4.2.2 Autres cas : les mains dans le cambouis
4.2.2.1 Le parcours d’arbre
4.2.2.2 Retour sur le plus grand rectangle blanc
4.3 La complexité
4.3.1 En temps et en taille
4.3.2 Réduire l’ordre de grandeur de la complexité
4.3.2.1 Est-ce toujours utile ?
4.3.2.2 A quel prix ?
5 Quelques grandes familles d’algorithmes
5.1 Rechercher l’information
5.1.1 Rechercher de manière linéaire
5.1.1.1 Dans des listes
5.1.1.2 Dans des listes triées
5.1.1.3 Quelques algorithmes de tri, juste pour rire
5.1.1.3.1 Le tri rapide (Quicksort)
5.1.1.3.2 Le tri interclassement monotone
5.1.2 La recherche arborescente
5.1.2.1 Les arbres binaires
5.1.2.2 Rajoutons la relation d’ordre
5.1.3 Le hachage
5.1.3.1 Avant de partir
5.1.3.2 Une injection de E dans N
5.1.3.3 Une surjection de E sur [0 , T[
5.1.3.4 Boum ! Une collision
5.1.3.4.1 Une liste de clefs
5.1.3.4.2 Une solution simple, le « linear probing »
5.1.3.4.3 Une famille de tables de tailles croissantes
5.1.3.5 Tout un univers d’applications possibles
5.2 Reconnaître l’information
5.2.1 Parenthèse sur l’unification
5.2.2 Reconnaissance d’un motif dans un texte
5.2.2.1 Soyons naïfs ! (en n x p)
5.2.2.2 Plus fort : L’automate KMP (en n)
5.2.2.2.1 Utiliser l’automate
5.2.2.2.2 Construire l’automate
5.2.2.3 Terrifiant : Boyer - Moore (en n / p)
5.2.3 Les arbres de décision
5.3 Divers autres problèmes
5.3.1 La simulation
5.3.2 Les jeux et l’aide à la décision
6 Représenter l’information
6.1 Modéliser n’importe quoi
6.1.1 Union d’intervalles
6.2 Adapter sa représentation
6.2.1 Combinaisons
6.2.2 Polynômes
6.2.2.1 Addition
6.2.2.2 Multiplication
6.2.3 Retour sur les arbres binaires de recherche
6.2.3.1 Rééquilibrage automatique
6.3 Ne représenter que ce qui est utile, sans redondance
6.3.1 Le complémentaire de nos unions d’intervalles
6.3.2 La représentation des nombres et des polynômes
6.4 Visualiser les données
6.4.1 Listes
6.4.2 Arbres binaires
6.4.3 Arbres quelconques, graphes
6.5 La précision et la tolérance d’erreur (numérique)
6.5.1 Représentation approximative
6.5.1.1 Perte du morphisme pour les entiers
6.5.1.2 Les rationnels décimaux en binaire
6.5.1.3 Représenter plus ou moins des réels
6.5.1.3.1 Virgules fixes
6.5.1.3.2 Virgules flottantes
6.5.2 Gérer l’erreur
6.5.2.1 Situons le problème
6.5.2.2 Estimons l’erreur
6.5.2.3 Alors, en pratique, comment calcule-t-on un sinus ?
7 Techniques de développement moderne, l’Extreme
Programming
7.1 Petites équipes et échéances courtes
7.2 L’ambassadeur des utilisateurs
7.3 Des scénarios d’utilisation plutôt qu’un cahier des charges préliminaire
7.4 Validation des programmes
7.4.1 Le passage du prototype à l’application réelle
7.4.2 Preuve de programme versus tests pratiques
7.4.3 Tests automatiques et tests manuels
7.4.4 Le cahier des charges final et la recette
7.5 La gestion de version

Très bon article: Essences de la programmation [Oliv. Durin] 848511

Très bon article: Essences de la programmation [Oliv. Durin] 848511