Introduction à la programmation avec R
gilles.hunault "at" univ-angers.fr
Cours 7 - Programmation soutenue
Table des matières cliquable
1. Structure de données classiques des autres langages
2. Problèmes demandant des compétences techniques en algorithmique
3. Problèmes de grande taille (big data)
Exercices : énoncés solutions [Retour à la page principale du cours]1. Structure de données classiques des autres langages
Lorsqu'on suit des cours de programmation, on apprend des techniques classiques et des modèles de résolution de problèmes, nommés en anglais Design Patterns. On apprend aussi à utiliser des structures de données adaptées, comme les piles, les queues, les files, les graphes (dont les arbres), les listes chainées, les tableaux associatifs... Il faut donc de nombreuses heures de cours et de pratique avant de maitriser la programmation. Les cours présentés ici ne peuvent prétendre se substituer à ces enseignements traditionnels, tout au plus sensibiliser à l'importance de ces concepts via quelques exemples choisis.
On trouvera donc dans les exercices de ce cours des graphes, des arbres et des tableaux associatifs à titre d'illustration.
Il faut noter aussi que l'utilisation de R est souvent liée à des calculs statistiques, discipline qui a ses propres structures comme les séries chronologiques, les variables ordinales, les matrices de distances, les arbres de classification hiérarchique... et ses propres méthodes comme le modèle linéaire, les intervalles de confiance...
2. Problèmes demandant des compétences techniques en algorithmique
Voici un problème qui a l'air presque anodin : quelle la plus grande sous-chaine de caractères répétée dans une chaine de caractères ? Attention : il ne s'agit pas de trouver la lettre la plus souvent utilisée, mais une sous-chaine. Pour un texte "littéraire", avec des avec des "vrais" mots, c'est facile à faire et rapide. Voir par exemple le site analexies. Mais pour une séquence d'ADN comme celle de Pseudomonas putida GB-1 (soit un peu plus de 6 millions de lettres), comment faire ?
C'est grâce à l'étude de structures de données adaptées comme celle de tableau des suffixes que le problème se résoud de façon « assez rapide » (quelques dizaines de secondes sur un ordinateur récent un peu puissant, pour Pseudomonas putida GB-1). Il est clair qu'une structure comme celle-là ne s'invente pas en pensant dix minutes au problème. C'est pourquoi il y a un moment où savoir programmer dans un langage ne suffit plus : il faut aussi savoir inventer des algorithmes, connaitre les algorithmes classiques et les structures de données associées. Voici deux références pour progresser dans ce domaine :
Algorithmique et Programmation JAVA : un polycopié en français de polytechnique (version locale) ;
Algorithms : une grande référence anglaise sur les algorithmes.
Pour R, on pourra consulter le package PST.
3. Problèmes de grande taille (big data)
Lorsque les données sont très importantes (disons quelques dizaines de giga octets ou tera octets), ce qui est souvent le cas en bioinformatique, en [méta]génomique, de nouvelles difficultés surgissent : il n'est plus possible de charger les données en mémoire, ou seulement partiellement, les calculs ne peuvent plus s'exécuter sur un seul ordinateur et il faut recourir à un cluster ou à une grid de calculateurs...
La programmation en "grande dimension" (autre nom du big data) nécessite des approches algorithmiques différentes de la programmation classique. Ce sujet est beaucoup trop technique pour pouvoir être abordé dans un cours comme celui-ci qui est une petite introduction à la programmation classique, mais il est bon de savoir qu'il existe des solutions, par exemple Revolution R, qu'on y parle Hadoop et autres map/reduce ou map/filter/reduce, de la programmation fonctionnelle.
On pourra lire sur ce sujet la page wiki RHadoop alors qu'en français deux sites incontournables sont celui de L. THIBAULT et celui de E. RAKOTOMALALA.
4. Problèmes de grande ampleur (big computing)
Contrairement à un problème de grande taille, un problème de grande ampleur peut avoir des données de taille «raisonnable» mais leur traitement nécessite des capacités gigantesques. Un exemple classique est la détermination (calcul ?) de sous-séquences répétées à ne pas confondre avec le calcul de sous-chaines répétées (qui, lui, se traite «assez facilement»). Dans les phrases un bateau qui va sur l'eau et mon ami est en bateau, la chaine eau est une sous-chaine répétée. Dans les phrases mon papa est dans un bateau et pour mon tonton, il y a un souci, la sous-séquence notée mon*un, qui signifie le mot mon suivi quelque part du mot un, est une sous-séquence répétée. Ce genre de problème est classique lorsqu'on s'intéresse aux séquences d'ADN ou d'acides aminés.
Là encore, la programmation en "grande complexité" (autre nom pour dire grande ampleur) nécessite des approches algorithmiques différentes de la programmation classique. Ce sujet est beaucoup trop technique pour pouvoir être abordé dans un cours comme celui-ci qui est une petite introduction à la programmation classique, mais il est bon de savoir qu'il n'existe pas toujours des solutions exactes et qu'on doit alors se contenter de résultats approchés, d'approximations souvent issues d'heuristiques voire de métaheuristiques...
5. La récursivité
Programmer, c'est écrire des programmes. De nombreux programmes utilisent des fonctions. Il y a parfois des façons "naturelles" ou "élégantes" de traiter un problème. Par exemple, voici une méthode de tri :
Pour trier une liste de valeurs par ordre décroissant, il suffit de trouver le plus grand élément de la liste, de l'afficher, puis de l'enlever de la liste et de trier la liste restante par ordre décroissant, jusqu'à ce qu'il n'y ait plus de valeurs à trier.
Cette définition du tri qui fait référence à son propre tri se nomme un appel récursif. Ecrire des fonctions récursives, savoir quand les utiliser et comment s'en passer ou comment les convertir en fonctions non récursives (lorsque c'est concrètement faisable) est une partie non négligeable de l'algorithmique traditionnelle. Pour aller plus loin dans ce sujet, on pourra consulter le cours d'algorithmique de F. Vivien, chapitre 3 (version locale) et la définition de la fonction d'Ackermann qui est, en principe, dérécursivable...
Exercices : énoncés solutions [Retour à la page principale du cours]
Retour à la page principale de (gH)