Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université Galatasaray Faculté d’ingénierie et de technologie Algorithmique & p

Université Galatasaray Faculté d’ingénierie et de technologie Algorithmique & programmation en langage C Damien Berthet & Vincent Labatut Sujets de travaux pratiques Supports de cours – Volume 2 Période 2005-2014 Damien Berthet & Vincent Labatut 2005-2014 © Damien Berthet & Vincent Labatut 2005-2014 Ce document est sous licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International. Pour accéder à une copie de cette licence, merci de vous rendre à l'adresse suivante : http://creativecommons.org/licenses/by-nc-sa/4.0/ Galatasaray Universitesi Mühendislik ve Teknoloji Fakültesi Çırağan Cad. No:36 Ortaköy 34349, İstanbul version 1 Turquie 23/07/2014 Sommaire SOMMAIRE 1 INFORMATIONS PRATIQUES 1.1 CONVENTIONS 1.2 ACCÈS AUX RESSOURCES 2 INSTALLATION ET CONFIGURATION 2.1 JAVA 2.1.1 Windows 2.1.2 Linux 2.1.3 Vérification 2.2 ECLIPSE 2.2.1 Installation 2.2.2 Utilisation 2.3 CDT 2.3.1 Compilateur C 2.3.2 C/C++ Development Tooling 2.3.3 Test de l’installation 2.3.4 Problèmes possibles 2.4 SDL 2.4.1 Installation 2.4.2 Configuration 2.4.3 Test de l’installation 2.4.4 Problèmes possibles 3 UTILISATION EN TP 3.1 RÈGLES CONCERNANT LES TP 3.1.1 Nommage 3.1.2 Programmation 3.1.3 Texte 3.1.4 Remise du travail 3.2 CRÉATION D’UN PROJET 3.2.1 Nom du projet 3.2.2 Structure du projet 3.2.3 Importation de fichiers 3.3 BIBLIOTHÈQUE MATHÉMATIQUE 3.4 COMPILATION 3.5 EXÉCUTION 3.5.1 Dans Eclipse 3.5.2 Hors d’Eclipse 3.6 DÉBOGAGE 3.6.1 Perspective de débogage 3.6.2 Contrôle de l’exécution 3.6.3 Accès à la mémoire 4 SUJETS DE TP 01 ENTRÉES-SORTIES 02 TYPES SIMPLES 03 VARIABLES & OPÉRATEURS 04 INSTRUCTIONS DE CONTRÔLE 05 CRIBLE D'ÉRATHOSTÈNE 06 CHAÎNES DE CARACTÈRES 07 TABLEAUX MULTIDIMENSIONNELS 08 DIAGRAMMES TEXTUELS 09 INTRODUCTION À LA SDL 10 MODIFICATION DES COULEURS 11 PASSAGE DE PARAMÈTRES 12 ALGORITHME DE BRESENHAM 13 HISTOGRAMME DES COULEURS 14 PROPRIÉTÉS ARITHMÉTIQUES 15 ALGORITHMES POUR L'ARITHMÉTIQUE 16 BIBLIOTHÈQUE CHAÎNE 17 DÉCOMPOSITION D'UNE PERMUTATION 18 NOMBRES BINAIRES 19 ALGORITHME DE JOHNSON 20 MANIPULATION DE DATES 21 CARRÉS LATINS 22 REPRÉSENTATION D'UNE PROMOTION 23 PARTITION D'UN ENTIER 24 ROTATION D'UN CARRÉ 25 ZOOM D'UNE IMAGE 26 AUTOMATES FINIS 27 CHAMPIONNAT DE FOOTBALL 28 FLOUTAGE D'UNE IMAGE 29 FLOUS AVANCÉS 30 GESTION D'UN LEXIQUE 31 ALLOCATION DYNAMIQUE 32 GÉNÉRATEUR PSEUDO-ALÉATOIRE 33 NOMBRES HEXADÉCIMAUX 34 AGENDA TÉLÉPHONIQUE 35 FICHIERS ET ARGUMENTS DE PROGRAMME 36 DIAPORAMA 37 STOCK D'UNE LIBRAIRIE 38 AUTOMATES CELLULAIRES 39 FONCTIONS RÉCURSIVES 40 APPROXIMATIONS NUMÉRIQUES 41 FIGURES FRACTALES 42 LISTES CHAÎNÉES 43 DISQUES & GUIRLANDES 44 LISTES DE CARACTÈRES 45 TAPIS DE SIERPIŃSKI 46 SUITE DE SYRACUSE 47 ENVELOPPE D'UN NUAGE DE POINTS 48 MARCHES DE GRAHAM & JARVIS 49 ANALYSE D'EXPRESSIONS 50 CONVERSION D'EXPRESSIONS 51 DÉTECTION DE PALINDROMES 52 TOURS DE HANOÏ 53 REMPLISSAGE DE FORMES 54 PARCOURS D'UN LABYRINTHE 55 GÉNÉRATION D'UN LABYRINTHE 56 TRI PAR DÉNOMBREMENT 57 TRI COCKTAIL 58 REPRÉSENTATION DES TRIS 59 TRIS SUR LISTES 60 REPRÉSENTATION DE L'ADN 61 NOMBRES DE GRANDE TAILLE 62 TABLE DE SYMBOLES 63 PLUS LONGUE SOUS-SÉQUENCE COMMUNE 64 ARBRES BINAIRES Ce document regroupe 64 sujets de travaux pratiques (TP) et d’examen, écrits pour différents enseignements d’algorithmique et de programmation en langage C donnés à la Faculté d’ingénierie de l’Université Galatasaray (Istanbul, Turquie), entre 2005 et 2014. Il s’agit du deuxième volume d’une série de 3 documents, comprenant également le support de cours (volume 1) et un recueil des corrigés de ces sujets (volume 3). Les sujets d’examen ont été retravaillés pour prendre la forme de sujets de TP. Les 64 sujets proposés ont été ordonnés de manière à correspondre à la progression des concepts parallèlement étudiés en cours (cf. le volume 1). En ce qui concerne les concepts les plus simples, il est difficile de sortir des exercices assez classiques, d’autant plus que les étudiants ne disposent à ce moment-là du cours que d’un bagage technique très réduit. Cependant, nous avons tenté d’aborder des thèmes plus originaux dans les sujets venant plus tard. Nous nous sommes particulièrement attachés à proposer des exercices basés sur une approche graphique de l’algorithmique, grâce à l’utilisation de la bibliothèque SDL1 (Simple DirectMedia Layer). Le volume horaire d’un (ou même de deux) cours classique(s) ne permet bien entendu pas d’effectuer tous les TP proposés ici. Il faut remarquer que si certains sujets introduisent un concept nouveau, d’autres, au contraire, se concentrent sur l’approfondissement d’une ou plusieurs notions déjà utilisées. L’idée est plutôt, pour l’enseignant, de disposer d’un assortiment d’exercices divers, dans lequel il peut choisir ce dont il a besoin, en fonction des étudiants, de la progression effective et des objectifs de son cours. Pour les étudiants, il s’agit de proposer des exercices pouvant offrir une vision alternative à celle donnée dans le cours suivi, ou bien d’approfondir certains points vus en cours. Malgré tout le soin apporté à la rédaction de ces sujets, il est probable que des erreurs s’y soient glissées. Merci de nous contacter afin de nous indiquer tout problème détecté dans ce document. Il faut également remarquer qu’il s’agit de TP donnés dans le cadre d’un cours d’introduction, aussi les notions abordées le sont parfois de façon simplifiée et/ou incomplète. Le reste du document est organisé de la façon suivante. Nous présentons d’abord les conventions adoptées dans les sujets. Puis, nous décrivons les outils utilisés au cours des TP, à savoir GCC2 pour la compilation, Eclipse3 pour l’environnement de programmation, et la SDL pour la manipulation des graphismes. Nous expliquons comment les installer et donnons les rudiments de leur utilisation. Nous donnons ensuite une liste synthétique des sujets, en précisant notamment comment ils utilisent les différentes notions vues en cours. Enfin, le cœur du document est constitué des sujets de TP eux-mêmes. Damien Berthet & Vincent Labatut le 7 juillet 2014 1 https://www.libsdl.org/ 2 http://gcc.gnu.org/ 3 http://www.eclipse.org/ Supports de cours vol.2 – Période 2005-2014 Sujets de travaux pratiques 1 Informations pratiques 1.1 Conventions Afin de faciliter la compréhension des sujets, certaines conventions de mise en forme sont systématiquement employées dans les trois volumes. Tout d’abord, les identificateurs (noms de fonctions, variables, constantes, etc.) sont indiqués en utilisant la police Courier. La plupart des exercices consistent à écrire une fonction implémentant un traitement demandé. Nous essayons, dans la mesure du possible, de toujours donner un exemple de ce traitement. Quand celui-ci implique une interaction avec l’utilisateur (affichage ou saisie), le contenu de la console est représenté en utilisant Courier sur fond bleu. Lorsque l’utilisateur doit saisir des valeurs, celles-ci sont surlignées en jaune. Entrez une valeur : 12 Vous avez entré la valeur 12. Lorsque du code source est cité, nous employons un fond rouge. Si une partie du code source en particulier doit être désignée, elle est surlignée en vert. int ma_function(int x) { int une_variable_notable; ... 1.2 Accès aux ressources Certains sujets nécessitent d’utiliser/compléter des bibliothèques, ou bien d’accéder à des images. Ces données additionnelles sont disponibles à partir de la page du cours sur Kikencere4. La remise du travail se fait également sur Kikencere. 4 http://kikencere.gsu.edu.tr/ Supports de cours vol.2 – Période 2005-2014 Sujets de travaux pratiques 2 Installation et configuration Dans cette section, nous expliquons brièvement comment installer et configurer les différents outils utilisés en TP, à savoir :  L’environnement d’exécution de Java, qui est nécessaire pour utiliser Eclipse ;  Le logiciel Eclipse, qui sera notre environnement de programmation ;  Un compilateur capable de traiter des programmes écrits en langage C ;  La bibliothèque SDL que nous utiliserons pour dessiner à l’écran. Notez que tous ces outils sont libres d’utilisation, et multiplateforme. Ils sont disponibles au moins pour les systèmes Windows, Unix/Linux et Apple. Cependant, dans nos explications, nous ne traitons que les deux premiers. Chaque étape décrite ici suppose que l’étape précédente a été réalisée avec succès. Inutile de passer à l’étape suivante tant que l’étape courante n’est pas validée. Par exemple, ne tentez pas d’installer Eclipse tant que vous ne réussissez pas à faire fonctionner Java d’abord. Supports de cours vol.2 – Période 2005-2014 Sujets de travaux pratiques 2.1 Java Java est à la fois un langage de programmation et un environnement d’exécution, développés par Sun Microsystems à partir de 1995, puis Oracle depuis 2010. Le langage est orienté objet, et l’environnement d’exécution permet de créer des programmes de façon relativement indépendante de la plateforme. 2.1.1 Windows  Allez sur le site de Sun Microsystems consacré à Java : http://java.sun.com/javase/downloads/index.jsp  Téléchargez le dernier JDK (Java Standard Edition Development Kit) version SE (Standard Edition) pour Windows.  Installez le JDK en exécutant le programme que vous venez de télécharger.  On notera dorénavant <Java> le dossier d’installation du JDK. 2.1.2 Linux  La plupart du temps, Java est déjà installé sous Linux (cela dépend de la distribution que vous utilisez).  Vérifiez que : o C’est bien le JDK entier qui est installé, et non pas seulement le JRE (Java Runtime Environment). o Il s’agit bien de la dernière version disponible du JDK.  Dans le cas contraire, vous devez installer le dernier JDK.  Remarque : vous aurez généralement besoin d’être connecté en tant qu’administrateur.  La procédure d’installation dépend de la distribution Linux que vous utilisez : o Ubuntu : vous pouvez utiliser le gestionnaire de packages Synaptic. o Fedora : vous pouvez utiliser le gestionnaire de packages Yellow Dog.  uploads/s3/ algorithmique-amp-programmation-en-langage-c-vol-2-sujets.pdf