background preloader

Algorithmie

Facebook Twitter

INF411 : Les bases de la programmation et de l'algorithmique. (la page des TD) Enseignant responsable : Jean-Christophe Filliâtre Année 2017 (promotion X2016) Présentation Ce cours entend amener les élèves de niveau INF311 (Introduction à l'informatique) au niveau de fin de INF321, afin de pouvoir poursuivre le cursus d'informatique de l'École avec le cours INF421 (Conception et analyse d'algorithmes).

L'enseignement porte essentiellement sur les structures de données (listes, piles, files, arbres, graphes), sur l'algorithmique, et sur un minimum de théorie de la complexité. Ce cours est également l'occasion de se perfectionner en Java. Poly Voici le poly (version 2017) au format PDF. Code Java du poly. Pour ceux qui souhaitent aller plus loin que le poly, voici deux ouvrages recommandés : Amphis Amphi Arago, lundi 13:30-15:00. TDs Mardi, 8:00-10:00 ou 10:15-12:15. La page des TD. Enseignants : Quelques raccourcis utiles d'Eclipse : Tutorat Un tutorat a été mis en place, le vendredi de 18:00 à 20:00 en salle info 31, du bloc 3 au bloc 8.

Pale machine Archives : Quiz : 10 questions sur les algorithmes. Algorithmes, mode d’emploi. Elle s’appelle Ada, Augusta Ada King, comtesse de Lovelace, fille du célèbre poète Lord George Gordon Byron. Certains vous diront qu’elle a juste joué un rôle de représentation publique, mais ne les écoutez pas : c’est bien grâce à elle que le premier programme informatique a été écrit (cf. dossier en ligne sur DocSciences).

Elle travaille avec Charles Babbage, mathématicien, sur la « machine analytique ». Pour faire marcher cette future machine, Ada crée des « diagrammes » qui ont pour but d’expliquer comment doit procéder la machine pour arriver au résultat recherché... et ceci indépendamment de la façon dont sont réalisées ces opérations. Ce sont des « algorithmes ». Ce mot vient du nom du grand mathématicien perse Al-Khwarizmi (vers l’an 820) qui introduit en Occident la numération décimale (rapportée d’Inde) et enseigne les règles élémentaires des calculs s’y rapportant. Mais comment être sûr qu’un mode d’emploi soit rigoureusement précis ?

Gnirut : le monstre testeur. Les algorithmes de tri. Selon le dictionnaire, « trier » signifie « répartir en plusieurs classes selon certains critères ». De manière plus restrictive, le terme de « tri » en algorithmique est très souvent attaché au processus de classement d'un ensemble d'éléments dans un ordre donné. Par exemple, trier N entiers dans l'ordre croissant, ou N noms dans l'ordre alphabétique. Tout ensemble muni d'un ordre total peut fournir une suite d'éléments à trier. Il est intéressant de constater qu'intuitivement, s'il lui est donné un ensemble à trier, tout un chacun met en place des stratégies de tri différentes selon le nombre d'éléments de l'ensemble, par exemple un jeu de 52 cartes ou 200 élèves à classer dans l'ordre alphabétique. Tri par sélection, tri par propagation, tri par insertion, tri rapide, tri par fusion... ces différentes méthodes ont chacune leurs particularités... et leur niveau de performance, qui correspond à la complexité de l'algorithme.

Les méthodes présentées sont de deux types : Les ingrédients des algorithmes. 1. Des ingrédients à découvrir Quelle différence entre une machine à café et un ordinateur ? Un ordinateur peut effectuer des opérations très variées, sur des types de données très variés : des nombres, des lettres, des images, des sons, des textes, des vidéos, comme le montre le document Tout a un reflet numérique. Il peut être utilisé pour retoucher une photo, la mettre sur un blog ou un site web, la conserver dans un album... Un ordinateur est une machine polyvalente : tout ce qui s'automatise peut être programmé sur un ordinateur.

. © Dessin : Paul Gendrot Dès la sortie de l'usine, une machine à café est capable de faire le café, un aspirateur est capable d'aspirer la poussière. C'est pour cela que les ordinateurs ont besoin de programmes. Oui, mais comment fait-on pour programmer l'ordinateur ? Les documents Algorithme mode d'emploi et Demandez le programme offrent une introduction à ce sujet. Algorithme... une recette de cuisine ? De retour en cuisine Retournons dans la cuisine. 2. Qu’est-ce qu’un algorithme ? Le mot « algorithme » vient du nom du grand mathématicien persan Al Khwarizmi (vers l'an 820), qui introduisit en Occident la numération décimale (rapportée d'Inde) et enseigna les règles élémentaires des calculs s'y rapportant.

La notion d'algorithme est donc historiquement liée aux manipulations numériques, mais elle s'est progressivement développée pour porter sur des objets de plus en plus complexes, des textes, des images, des formules logiques, des objets physiques, etc. De la méthode Un algorithme, très simplement, c'est une méthode. Une façon systématique de procéder pour faire quelque chose : trier des objets, situer des villes sur une carte, multiplier deux nombres, extraire une racine carrée, chercher un mot dans le dictionnaire… Il se trouve que certaines actions mécaniques - peut-être toutes ! - se prêtent bien à la décortication. Un exemple commun est par exemple la recherche d'un mot dans le dictionnaire. Du nombre à l'information L'importance des ordinateurs. AlgoBox. AlgoBox est un logiciel libre, multi-plateforme et gratuit d'aide à l'élaboration et à l'exécution d'algorithmes dans l'esprit des nouveaux programmes de mathématiques du secondaire.

Une démonstration vidéo d'AlgoBox sur un exemple simple est disponible ici AlgoBox, c'est : une prise en main facile et rapide avec une interface en français, claire et ergonomique;un logiciel éducatif basé sur une logique pédagogique (apprentissage de l'algorithmique par structures logiques à travers un langage textuel proche du langage naturel algorithmique);un logiciel disponible gratuitement et facilement installable sur toutes les plate-formes (Windows, MacOsx, Linux);un programme conçu pour l'enseignement et qui s'adresse à l'ensemble des élèves (et pas seulement à une petite minorité);un logiciel correspondant aux instructions officielles des programmes de mathématiques du secondaire de la seconde à la terminale.

Faire une multiplication... plus vite qu’à l’école ! 1. La méthode scolaire Pour multiplier entre eux deux nombres entiers a et b, on multiplie a par chaque chiffre de b et on écrit ces produits intermédiaires en biais les uns au-dessous des autres. Ensuite, on additionne ces produits intermédiaires. Selon les pays, il existe quelques variantes dans la façon de poser les opérations, mais globalement, c'est ainsi que fonctionne la méthode scolaire de la multiplication.

Lorsque les nombres a et b sont grands, c’est-à-dire qu’ils comportent beaucoup de chiffres, alors cette méthode devient trop coûteuse en temps. Cela mérite réflexion. Pourquoi juge-t-on cette méthode trop coûteuse en temps ? Ces questions sont intéressantes pour plusieurs raisons. Mais que veut-on dire par « la méthode scolaire est trop coûteuse en temps » ? En ne considérant que ces deux opérations de base, on va comparer des algorithmes de multiplication. L'addition de grands nombres Combien d'opérations faut-il pour additionner deux nombres a et b ? 2. Il en résulte : AlgoBox. AlgoBox. Cargo-Bot pour l'apprentissage de l'algorithmique. Cargo-Bot est un jeu de Rui Viana. Cargo-Bot is a trademark of Two Lives Left, used here with their amiable permission. Adaptation en Javascript par Joe Tessler. Traduction et niveaux supplémentaires par Benjamin Wack.

Le pack de niveau Champo a été mis au point par des élèves de seconde du lycée Champollion de Grenoble. Pour toute question, suggestion, idée de niveau, écrivez-moi. Si rien d'autre que ce texte ne s'affiche, ou si vous ne voyez pas les flèches dans les carrés roses, votre navigateur n'est probablement pas à jour.Attention, sous Windows XP, il est impossible d'utiliser cette page avec Internet Explorer (pas de version suffisamment récente disponible). PluriAlgo, un logiciel d'algorithmique pluri-langages pour lycéens. PluriAlgo, un logiciel d'algorithmique pluri-langages pour lycéens Patrick Raffinat Introduction Enseignant l'algorithmique en IUT depuis de nombreuses années, je sais par expérience que ce n'est pas une chose aisée.

Je suppose donc que le faire en lycée, dans le cadre d'un programme officiel de mathématiques, rend les choses encore plus compliquées. C'est pourquoi je présente dans cet article un logiciel dont l'un des objectifs est de faciliter l'écriture d'algorithmes dans plusieurs langages pédagogiques (Javascool, Larp, Python, Algobox...) ou mathématiques (R, Xcas) utilisés en lycée. PluriAlgo [1] fait partie de la plate-forme Javascool, destinée principalement aux lycéens de l'option ISN.

Adéquation avec le programme officiel Le programme officiel de seconde indique que les élèves doivent être capables, dans le cadre d'une résolution de problèmes : Exemples Pour illustrer mes propos, je reprendrai brièvement deux des exemples développés dans la revue MathémaTICE. Conclusion. Qu'est ce qu'un algorithme ? Explication avec la recette des crêpes. Aujourd’hui, je réponds à la question de la petite Solène, qui se demande ce que peut bien être un algorithme. J'ai récemment adapté ce petit billet en vidéo avec mes comparses de Big Bang Science, en version un peu simplifiée.

N'hésitez pas à me dire ce que vous en pensez, ça me permettra de corriger certaines problèmes et d'adapter le niveau de vulgarisation pour d'éventuelles autres vidéos :) Algorithme : ce mot ne cache rien de bien méchant : un algorithme est simplement une suite d'instructions permettant de faire quelque-chose. Une recette de cuisine, par exemple, est un algorithme : une suite d'opérations simples permettant de passer des ingrédients à un plat préparé.On représente souvent l'algorithme de façon schématique, en décomposant les étapes et en les reliant par des flèches, un peu comme ci-dessous : Pour faire des crêpes, il suffit de suivre les instructions dans l'ordre.

Les conditions dans les algorithmes Les algorithmes en langage informatique fin fin. Algorithmes débutants. Cours d'Algorithmique - Christophe Darmangeat. Partie 1 Les Variables « N’attribuez jamais à la malveillance ce qui s’explique très bien par l’incompétence. » - Napoléon Bonaparte « A l’origine de toute erreur attribuée à l’ordinateur, vous trouverez au moins deux erreurs humaines.

Dont celle consistant à attribuer l’erreur à l’ordinateur. » - Anonyme Dans un programme informatique, on va avoir en permanence besoin de stocker provisoirement des valeurs. Il peut s’agir de données issues du disque dur, fournies par l’utilisateur (frappées au clavier), ou que sais-je encore. Il peut aussi s’agir de résultats obtenus par le programme, intermédiaires ou définitifs. Pour employer une image, une variable est une boîte, que le programme (l’ordinateur) va repérer par une étiquette. En réalité, dans la mémoire vive de l’ordinateur, il n’y a bien sûr pas une vraie boîte, et pas davantage de vraie étiquette collée dessus (j’avais bien prévenu que la boîte et l’étiquette, c’était une image). 2.1 Types numériques classiques 2.3 Type alphanumérique. Initiation à la notion d'algorithme - Inria. Cours d'Algorithmique - Christophe Darmangeat.

Qu’est-ce qu’un algorithme ? Introduction aux algorigrammes. Avant toute programmation, il est recommandé d'avoir une visualisation du programme qu'on va faire. Pour cela, il faut faire un algorithme ou un organigramme. Le premier a une structure linéaire comme un programme alors que le second permet de bien mieux visualiser les différents blocs du programme, les boucles, les tests. C'est ce dernier point que je vais présenter ici : les algorigrammes. Faire un organigramme est important car la programmation est un processus itératif. Le programme est parfois modifié par d'autres développeurs que ceux qui l'ont conçu. Ce schéma pourra expliquer la conception du programme aux nouveaux développeurs.

Il pourra même éclairer le concepteur lui-même sur des idées qu'il avait eu. Les modes de programmation visuelle, qui se développent de plus en plus ressemblent plus à des algorigrammes qu'à un programme. Cet article est un résumé du cours donné en II1 au département GEii de l'IUT B de l'université Lyon 1. Exemple : Calcul de la surface d? 5.1. 5.2. 5.3.