Algorithmique & programmation en langage C - vol.1

Il exécute les instructions de l'algorithme les unes à la suite des autres. Page 8. 6. I - Algorithmes instructions et langages informatiques. 2)

Algorithmique Structures de données

Les structures de données séquentielles (tableaux) ;. Les structures de données linéaires (liste chaînées) ;. Les arbres ;. Les graphes. Page 4. Structures

cours-python.pdf

22 mar. 2018 10.7 Conversion d'une liste de chaînes de caractères en une chaîne de ... L'apprentissage d'un langage informatique comme Python va ...

Algorithmique & programmation en langage C - vol.2 - Archive

14 juil. 2015 Faculté d'ingénierie et de technologie – Génie informatique. Algorithmique et programmation. Damien Berthet & Vincent Labatut. TP 06 chaînes ...

livre-algorithmes EXo7.pdf

Arithmétique – Algorithmes récursifs . PREMIERS PAS AVEC Python 2 ... entier une liste

Python au lycée - tome 1

L'informatique accompagne à merveille les mathématiques ! L'ordinateur devient indispensable Chaînes de caractères – Analyse d'un texte. 41. 7. Listes I.

SUJET + CORRIGE

Les indentations des fonctions écrites en Python Liste doublement chainée ... (b) (2 points) Écrire un algorithme existeInvOuOppConsecutifs(T) o`u T est ...

Algorithmique & programmation en langage C - vol.1 - Archive

1 fév. 2019 IMPLÉMENTATION PAR LISTE CHAÎNÉE. ... 14 Listes simplement chaînées ... En informatique on s'intéresse surtout à la base 2 (décomposition.

Algorithmes de tris

Dans la pratique ces algorithmes seront illustrés en Python par le tri d'une liste à valeurs numériques. Remarque. Il existe des algorithmes qui

Exercices corrigés

2010 – 2011. Informatique Scientifique version 2.2. Python 3. Exercices corrigés 2. Écrire une fonction cube qui retourne le cube de son argument.

>G A/, +2H@yRRdeRRN ?iiTb,ff?HXb+B2M+2f+2H@yRRdeRRNpk am#KBii2/ QM R 62# kyRN

Bb KmHiB@/Bb+BTHBM`v QT2M ++2bb

`+?Bp2 7Q` i?2 /2TQbBi M/ /Bbb2KBMiBQM Q7 b+B@

2MiB}+ `2b2`+? /Q+mK2Mib- r?2i?2` i?2v `2 Tm#@

HBb?2/ Q` MQiX h?2 /Q+mK2Mib Kv +QK2 7`QK

i2+?BM; M/ `2b2`+? BMbiBimiBQMb BM 6`M+2 Q` #`Q/- Q` 7`QK Tm#HB+ Q` T`Bpi2 `2b2`+? +2Mi2`bX /2biBMû2 m /ûT¬i 2i ¨ H /BzmbBQM /2 /Q+mK2Mib b+B2MiB}[m2b /2 MBp2m `2+?2`+?2- Tm#HBûb Qm MQM-

Tm#HB+b Qm T`BpûbX

.Bbi`B#mi2/ mM/2` *`2iBp2 *QKKQMbii`B#miBQM @ LQM*QKK2`+BH @ a?`2HBF2% 9Xy

AMi2`MiBQMH GB+2Mb2

H;Q`Bi?KB[m2 T`Q;`KKiBQM 2M HM;;2 * @ pQHXR

hQ +Bi2 i?Bb p2`bBQM, .KB2M "2`i?2i- oBM+2Mi G#imiX H;Q`Bi?KB[m2 T`Q;`KKiBQM 2M HM;;2 * @ pQHXR, amTTQ`ib /2 +Qm`b oQHmK2 R Sû`BQ/2 kyy8@kyR9X GB+2M+2X H;Q`Bi?KB[m2 2i S`Q;`KKiBQM- AbiM#mH- hm`[mB2X kyR9- TTXkjkX +2H@yRRdeRRNpk

Université Galatasaray

Algorithmique &

programmation en langage C

Damien Berthet & Vincent Labatut

Notes de cours

Supports de cours Volume 1

Période 2005-2014

Damien Berthet & Vincent Labatut 2005-2014

Ce document est sous licence Creative Commons Attribution - - 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 Üniversitesi

Mühendislik ve Teknoloji Fakültesi

version 0.9Turquie 1/0/201 Supports de cours vol.1 Période 2005-2014 3/232

SOMMAIRE ................................................................................................................................................ 3

CONVENTIONS ........................................................................................................................................... 8

1 INTRODUCTION .................................................................................................................................. 9

1.1 DÉFINITIONS ........................................................................................................................................ 9

1.2 PRÉSENTATION DU LANGAGE C ............................................................................................................. 14

2 TYPES DE DONNÉES .......................................................................................................................... 23

2.1 REPRÉSENTATION DE L'INFORMATION ..................................................................................................... 23

2.2 NOMBRES ENTIERS ............................................................................................................................. 25

2.3 NOMBRES RÉELS ................................................................................................................................ 31

2.4 CARACTÈRES ...................................................................................................................................... 37

2.5 IMAGES ............................................................................................................................................ 39

3 VARIABLES ET CONSTANTES LITTÉRALES........................................................................................... 44

3.1 CONSTANTES LITTÉRALES...................................................................................................................... 44

3.2 VARIABLES ........................................................................................................................................ 46

4 EXPRESSIONS ET OPÉRATEURS ......................................................................................................... 51

4.1 EXPRESSIONS ..................................................................................................................................... 51

4.2 OPÉRATEURS ..................................................................................................................................... 52

4.3 CONVERSIONS ................................................................................................................................... 56

5 CONDITIONS ET BOUCLES ................................................................................................................. 59

5.1 INSTRUCTIONS DE TEST ........................................................................................................................ 59

5.2 INSTRUCTIONS DE RÉPÉTITION ............................................................................................................... 64

5.3 ANALYSE D'UN PROGRAMME ................................................................................................................ 68

6 TABLEAUX ........................................................................................................................................ 74

6.1 DÉFINITION ....................................................................................................................................... 74

6.2 MÉMOIRE ......................................................................................................................................... 75

6.3 MANIPULATION ................................................................................................................................. 76

6.4 CHAÎNES DE CARACTÈRES ..................................................................................................................... 77

6.5 TABLEAUX MULTIDIMENSIONNELS .......................................................................................................... 79

6.6 EXERCICES ......................................................................................................................................... 80

7 FONCTIONS....................................................................................................................................... 82

7.1 PRÉSENTATION .................................................................................................................................. 82

7.2 PASSAGE DES PARAMÈTRES .................................................................................................................. 87

7.3 TABLEAUX ......................................................................................................................................... 91

7.4 EXERCICES ......................................................................................................................................... 93

8 TYPES PERSONNALISÉS ..................................................................................................................... 95

8.1 GÉNÉRALITÉS ..................................................................................................................................... 95

8.2 STRUCTURES ..................................................................................................................................... 96

8.3 UNIONS .......................................................................................................................................... 101

8.4 ÉNUMÉRATIONS ............................................................................................................................... 102

8.5 NOMMAGE DE TYPES ........................................................................................................................ 104

9 CLASSES DE MÉMORISATION .......................................................................................................... 106

9.1 PERSISTANCE D'UNE VARIABLE ............................................................................................................ 106

9.2 DÉCLARATIONS LOCALES .................................................................................................................... 106

9.3 DÉCLARATIONS GLOBALES .................................................................................................................. 109

9.4 FONCTIONS ..................................................................................................................................... 109

10 POINTEURS

10.1 PRÉSENTATION

10.2 ARITH

10.3 POINTEURS ET TABLEAUX

11 ALLOCATION DYNAMIQUE

11.1 PRÉSENTATION

11.2 ALLOCATION SIMPLE

11.3 AUTRES FONCTIONS

11.4 EXERCICES

12 FICHIERS

12.1 STRUCTURE FILE

12.2 OUV/FERMETURE

12.3 LECTURE/ÉCRITURE NON-FORMATÉES EN MODE CA

12.4 LECTURE/ÉCRITURE NON-FORMATÉES EN MODE CH

12.5 LECTURE/ÉCRITURE FORMATÉES

12.6 LECTURE/ÉCRITURE PAR BLOC

12.7 EXERCICES

13 FONCTIO

13.1 PRÉSENTATION

13.2 TYPES DE RÉCURSIVITÉ

13.3 ARBRE DES APPELS

13.4 STRUCTURE D'UNE FONCTION RÉCURSI

13.5 COMPARAISON ITÉRATIF/RÉCURSIF

13.6 EXERCICES

14 LISTES CHAÎNÉES

14.1 PRÉ

14.2 LISTES SIMPLEMENT CHA

14.3 LISTES DOUBLEMENT CHA

15 PILES DE DONNÉES

15.1 PRÉ

15.2 TYPE ABSTRAIT

15.3 IMPLÉMENTATION PAR TA

15.4 IMPLÉMENTATION PAR LI

16 FILES DE DONNÉES

16.1 PRÉSENTATION

16.2 TYPE ABSTRAIT

16.3 IMPLÉMENTATION SIMPLE

16.4 IMPLÉMENTATION CIRCUL

16.5 IMPLÉMENTATION PAR LI

17 COMPLEXITÉ ALGORITHM

17.1 INTRODUCTION À LA COM

17.2 CALCUL DE COMPLEXITÉ

17.3 ALGORITHMES RÉCURSIFS

18 ALGORITHMES DE TRI

18.1 PRÉSENTATION

18.2 TRI À BULLES

18.3 TRI PAR SÉLECTION

18.4 TRI PAR INSERTION

Supports de cours vol.1 Période 2005-2014 5/232 18.5 TRI FUSION...................................................................................................................................... 208

18.4 TRI RAPIDE ...................................................................................................................................... 212

ARBRES ........................................................................................................................................... 215

19.1 DÉFINITIONS .................................................................................................................................... 215

19.2 ARBRES BINAIRES ............................................................................................................................. 218

19.3 ARBRES BINAIRES DE RECHERCHE ......................................................................................................... 223

Supports de cours vol.1 Période 2005-2014 6/232 Ce document constitue le support de cours écrit pour différents enseignements

2) et de leurs corrigés (volume 3).

1 (Simple DirectMedia Layer

ue. Les outils utilisés en TP (GCC23

notions abordées le sont parfois de façon simplifiée et/ou incomplète. s de 2 heures réparties

de la façon suivante : Séance Sujet abordé Sections traitées

01 Introduction 1

02 Types simples 2

03 Variables, expressions et opérateurs 3-4

04 Structures de contrôle 5

05 Tableaux 6

06 Définition de fonctions 7-7.2.1

07 Passage de paramètres 7.2.2-7.4

08 Structures et unions 8-8.3

09 Types personnalisés & classes de mémorisation 8.4-9

10 Pointeurs 10

11 Allocation dynamique de mémoire 11

12 Fichiers 12

13 Fonctions récursives 13

14 Listes simplement chaînées 14-14.2

15 Listes doublement chaînées 14.3-14.3.5

16 Piles de données 15

17 Files de données 16

18 Introduction à la complexité 17-17.1

19 Complexité d'algorithmes itératifs 17.2

20 Complexité d'algorithmes récursifs 17.3

21 Tris quadratiques 18-18.4

22 Tris log-linéaires 18.5-18.4

23 Arbres binaires 19-19.2

24 Arbres binaires de recherche 19.3

sabsent du cours magistral, et était plutôt traité lors du tout premier TP. 1https://www.libsdl.org/ 2 3

Les principales références bibliographiques utilisées pour préparer ce cours sont les

, Thomas Cormen, Charles Leiserson & Ronald Méthodologie de la programmation en C, Achille Braquelaire, Dunod, 4ème

Langage, Gerhard Willms, MicroApplication, 1996.

Ce document utilise différentes conventions, dont certaines sont aussi appliquées dans les fonctions, variables, constantes, etc.) sont indiqués en utilisant la polCourier.

Courier

Entrez une valeur

Lorsque du code source est cit

int ma_function(int x)

Concept

1 1.1 1.1.1

Le mot algorithme ème

Al Khuwarizm4rythme, ce qui explique

Algorithme

ithme Algorithmiqueensemble des méthodes permettant de définir des (dans le cadre informatique) son implém 1.1.2

Un informel, ou incomplètement

informatique) ou autres. Par opposition, une démonstration mathématique ou un formels5 comp 6 Les étapes sont représentées par des liens

Les étapes de test

Les étapes de début fin

Les étapes de traitement

Les appels à des fonctions sous) sont

4 algèbre.

5 6 entrée/sortie complexes tout en gardant un diagramme lisible. pa exemple -

Version organi

Version pseudo

debut tant fin 1.1.3 Dans notre cas, le problème à résoudre est souvent compliqué d. Cette méthode récursivement

élémentaires,

Début

Fin

Afficher "début du traitement"

Afficher "fin du traitement"

compteur <= 0

Si compteur<4

Traitement X

Incrémenter compteur

faux vrai e

Énoncé du p

o o La table traçante possède un compteur. o Elle est capabl

lever/baisser

avec la feuille de papier posée sur la table de dessin, ou au contraire

centrer

haut/bas/gauche/droite ͳ

initialiser/incrementer

o Le problème est de dessiner une croix centrée sur la feuille, et dont chaque R début 10 fin o Algorithme de niveau ૛ debut fin o Algorithme de nivea૜

On décompose aller au centre sans tracer

debutquotesdbs_dbs46.pdfusesText_46

[PDF] Algorithmique & programmation en langage C - vol.1 - Archive