Introduction à l'économétrie
Introduction à l'économétrie
Introduction à l'économétrie
Introduction à l'économétrie
INTRODUCTION AUX METHODES ECONOMETRIQUES
ECO 4272 : Introduction `a l'´Econométrie Introduction au cours
Méthodes Econométries
Bases de Données introduction
Introduction aux Bases de Données
Introduction aux Bases de données

Next PDF List

Introduction à l"InformatiqueBernard BoigelotUniversité de Liège2021Table des matièresAvant-propos vii1 Les ordinateurs, les algorithmes et les programmes 11.

1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.1. 1) Qu"est-ce qu"un ordinateur? . . . . . . . . . . . . . . . . . . . . . . . .1 1.1. 2) Une petite histoire de l"informatique . . . . . . . . . . . . . . . . . . . .4 1. 2) L"algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.2. 1) La notion d"algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.2. 2) Exemples de problèmes algorithmiques . . . . . . . . . . . . . . . . . .8 1. 3) La programmation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 1.3. 1) L"implémentation d"un algorithme . . . . . . . . . . . . . . . . . . . . .12 1.3. 2) Les langages de programmation . . . . . . . . . . . . . . . . . . . . . .13 1.3. 3) Un premier programme . . . . . . . . . . . . . . . . . . . . . . . . . . .14 1.3. 4) La compilation et l"exécution d"un programme . . . . . . . . . . . . . .19 1. 4) Quelques considérations théoriques . . . . . . . . . . . . . . . . . . . . . . . .20 1.4. 1) Les ressources consommées . . . . . . . . . . . . . . . . . . . . . . . .20 1.4. 2) Les limitations de l"informatique . . . . . . . . . . . . . . . . . . . . . .21 1.

5) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 i2 Les bases du langage C 232.

1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 2. 2) Les variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24 2.2. 1) Les types de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 2.2. 2) La déclaration des variables . . . . . . . . . . . . . . . . . . . . . . . .28 2.2. 3) La portée d"une déclaration . . . . . . . . . . . . . . . . . . . . . . . .29 2. 3) Les expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 2.3. 1) Les opérateurs arithmétiques . . . . . . . . . . . . . . . . . . . . . . . .31 2.3. 2) Les opérateurs de comparaison . . . . . . . . . . . . . . . . . . . . . . .32 2.3. 3) Les opérateurs booléens . . . . . . . . . . . . . . . . . . . . . . . . . .33 2.3. 4) Les opérateurs d"aectation . . . . . . . . . . . . . . . . . . . . . . . .34 2.3. 5) Les opérateurs d"incrément et de décrément . . . . . . . . . . . . . . . .35 2.3. 6) L"opérateur virgule . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36 2.3. 7) La conversion de type . . . . . . . . . . . . . . . . . . . . . . . . . . .37 2.3. 8) Les expressions conditionnelles . . . . . . . . . . . . . . . . . . . . . .38 2. 4) Les instructions de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 2.4. 1) Le choix conditionnel binaire . . . . . . . . . . . . . . . . . . . . . . .39 2.4. 2) Le choix conditionnel multiple . . . . . . . . . . . . . . . . . . . . . . .43 2.4. 3) Les instructions de boucle . . . . . . . . . . . . . . . . . . . . . . . . .46 2.4. 4) Les instructions de rupture de séquence . . . . . . . . . . . . . . . . . .51 2. 5) Les commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52 2.

6) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53 3 Quelques notions d"algorithmique 573.

1) La recherche de nombres parfaits . . . . . . . . . . . . . . . . . . . . . . . . . .57 ii3.1. 1) Première solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .58 3.1. 2) Deuxième solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59 3.1. 3) Troisième solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60 3.1. 4) Comparaison des performances . . . . . . . . . . . . . . . . . . . . . .63 3. 2) La complexité en temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64 3.2. 1) Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65 3.2. 2) La notation "grand-O" . . . . . . . . . . . . . . . . . . . . . . . . . . .65 3.2. 3) Les classes de complexité . . . . . . . . . . . . . . . . . . . . . . . . .68 3.2. 4) Application aux programmes de recherche de nombres parfaits . . . . . .69 3. 3) L"analyse d"un programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72 3.3. 1) Les triplets de Hoare . . . . . . . . . . . . . . . . . . . . . . . . . . . .73 3.3. 2) Les invariants de boucle . . . . . . . . . . . . . . . . . . . . . . . . . .76 3.3. 3) Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77 3.3. 4) La terminaison d"un programme . . . . . . . . . . . . . . . . . . . . . .85 3.

4) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87 4 Les fonctions et les procédures 884.

1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88 4. 2) La programmation des fonctions . . . . . . . . . . . . . . . . . . . . . . . . . .89 4.2. 1) La définition d"une fonction . . . . . . . . . . . . . . . . . . . . . . . .89 4.2. 2) Les paramètres d"une fonction . . . . . . . . . . . . . . . . . . . . . . .93 4.2. 3) La déclaration d"une fonction . . . . . . . . . . . . . . . . . . . . . . .93 4.2. 4) L"invocation d"une fonction . . . . . . . . . . . . . . . . . . . . . . . .95 4.2. 5) Les notions d"interface et d"implémentation . . . . . . . . . . . . . . . .96 4.

3) La récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98 iii4.3.

1) Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98 4.3. 2) La complexité en espace . . . . . . . . . . . . . . . . . . . . . . . . . .100 4.3. 3) La terminaison d"une fonction récursive . . . . . . . . . . . . . . . . . .101 4.3. 4) Application : les tours de Hanoï . . . . . . . . . . . . . . . . . . . . . .103 4. 4) Les variables globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .109 4.4. 1) Définition et déclaration . . . . . . . . . . . . . . . . . . . . . . . . . .110 4.4. 2) Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111 4. 5) Les macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115 4. 6) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .117 4.6.

1) Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .117 4.6.2 Énoncés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118 5 Les tableaux et les chaînes de caractères 1235.

1) Les vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123 5.1. 1) La définition et l"utilisation des vecteurs . . . . . . . . . . . . . . . . . .123 5.1. 2) Application : le crible d"Ératosthène . . . . . . . . . . . . . . . . . . . .125 5. 2) Le passage de tableaux à une fonction . . . . . . . . . . . . . . . . . . . . . . .128 5.2. 1) Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128 5.2. 2) Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128 5.2. 3) L"arithmétique sur les pointeurs . . . . . . . . . . . . . . . . . . . . . .130 5. 3) Le tri d"un vecteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131 5.3. 1) Le tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132 5.3. 2) Le tri par fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .134 5. 4) Les chaînes de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .140 5.4. 1) Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .141 iv5.4. 2) Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .143 5. 5) Les tableaux multidimensionnels . . . . . . . . . . . . . . . . . . . . . . . . . .145 5.5. 1) Définition et utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . .145 5.5. 2) Le passage d"un tableau multidimensionnel à une fonction . . . . . . . .146 5.5. 3) Application : bibliothèque de transformations géométriques . . . . . . .147 5.

6) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .151 6 Les structures et les pointeurs 1556.

1) Les données structurées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155 6.1. 1) La définition d"un type de données structuré . . . . . . . . . . . . . . . .156 6.1. 2) L"utilisation des données structurées . . . . . . . . . . . . . . . . . . . .158 6.1. 3) Application : manipulation de nombres complexes . . . . . . . . . . . .161 6. 2) Les pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .161 6.2. 1) Le passage d"arguments par variable . . . . . . . . . . . . . . . . . . . .161 6.2. 2) Les pointeurs en langage C . . . . . . . . . . . . . . . . . . . . . . . . .164 6.2. 3) Les pointeurs vers des données structurées . . . . . . . . . . . . . . . .167 6.2. 4) Les pointeurs et les tableaux . . . . . . . . . . . . . . . . . . . . . . . .170 6. 3) L"allocation dynamique de mémoire . . . . . . . . . . . . . . . . . . . . . . . .172 6.3. 1) Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172 6.3. 2) La copie de blocs en mémoire . . . . . . . . . . . . . . . . . . . . . . .174 6.3. 3) Application : retournement d"une séquence de valeurs . . . . . . . . . .175 6.3. 4) L"allocation dynamique de tableaux . . . . . . . . . . . . . . . . . . . .179 6. 4) Les paramètres demain. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .186 6.

5) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .187 7 Les piles et les files 192v7.

1) Les structures de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192 7. 2) Les piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .193 7.2. 1) Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .193 7.2. 2) Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .193 7.2. 3) Implémentation à l"aide d"un vecteur . . . . . . . . . . . . . . . . . . .194 7.2. 4) Application : appariement de parenthèses . . . . . . . . . . . . . . . . .199 7.2. 5) Implémentation à l"aide d"une liste liée . . . . . . . . . . . . . . . . . .203 7. 3) Les files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .204 7.3. 1) Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .204 7.3. 2) Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .204 7.3. 3) Implémentation à l"aide d"un vecteur . . . . . . . . . . . . . . . . . . .208 7.3. 4) Implémentation à l"aide d"une liste liée . . . . . . . . . . . . . . . . . .214 7.

4) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .218 viAvant-proposLes ordinateurs sont devenus des objets indispensables de la vie quotidienne.

Nous en dé-pendons pour nous informer, nous divertir, communiquer et travailler.

En plus de cela, il existedes ordinateurs moins directement visibles employés comme composants essentiels de disposi-tifs plus complexes; par exemple, une voiture moderne en comprend plusieurs dizaines.

De nosjours, la plupart des ingénieurs, quelle que soit leur discipline, sont amenés à devoir réaliser ougérer des développements informatiques.Ce cours a pour objectif d"apprendre à utiliser un ordinateur pour résoudre des problèmes.

Ilcomprend une introduction à l"algorithmique, qui étudie comment passer d"un problème à uneprocédure eective permettant de le résoudre, et à laprogrammation, qui vise à exprimer unetelle procédure sous la forme d"unprogrammepouvant être exécuté par un ordinateur.

Dans cecours, la programmation est introduite à l"aide du langage de programmation C, qui a l"avantaged"être simple, très utilisé, et de permettre d"introduire aisément des concepts et des mécanismespossédant une portée plus générale.Ces notes de cours sont structurées de la façon suivante :-Le chapitre 1 introduit la matière du cours, en commençant par une brèv ehistoire de l"informatique et en définissant les notions d"algorithme et de programme.-Le chapitre 2 décrit les bases du lang ageC, en fournissant su samment d"éléments pourpouvoir commencer à rédiger des programmes simples.-Le chapitre 3 est consacré à l"algorithmique.

Il introduit un problème élémentaire (la re- cherche de nombres parfaits), et discute de la façon de le résoudre en développant dessolutions de plus en plus élaborées.

Des mécanismes permettant de comparer les per-formances des solutions obtenues et de prouver rigoureusement que ces dernières sontcorrectes sont également introduits.-Le chapitre 4 définit le concept de fonction.

Celui-ci permet de structurer un programme en une combinaison de fragments plus simples, et de réutiliser facilement des solutionsdéveloppées pour des sous-problèmes.

Ce chapitre présente ensuite le mécanisme d"exé-cution récursive d"une fonction, qui permet de résoudre élégamment certains problèmesviialgorithmiques.-Le chapitre 5 décrit les éléments du lang ageC liés à la manipulation de tableaux et de chaînes de caractères, et illustre leur utilisation dans le cadre de deux problèmes algorith-miques : le calcul de nombres premiers et le tri d"un ensemble de valeurs.-Le chapitre 6 aborde la représentation de données structurées, et introduit la notion fon- damentale de pointeur.

Il présente également les mécanismes permettant d"allouer dyna-miquement de la mémoire pour accommoder des données de taille variable.-Le chapitre 7 étudie deux structures de données importantes : les piles et les files, et discute de leurs implémentations possibles.

Le fait qu"une même structure puisse êtreimplémentée de diérentes façons est un mécanisme essentiel au développement de pro-grammes possédant de bonnes propriétés de modularité.Chacun de ces chapitres se termine par une série d"exercices, servant en partie de base auxséances de travaux pratiques.Ce cours ne constitue qu"une première étape dans l"apprentissage de l"algorithmique et de laprogrammation; sa matière est destinée à être approfondie et complétée par d"autres enseigne-ments.

En particulier, les cours deStructures de données et algorithmeset deCompléments deprogrammationcontinuent l"apprentissage de l"algorithmique et de la programmation.Object-oriented programmingetProgrammation fonctionnelleexplorent d"autres paradigmes de pro-grammation qui complètent celui introduit dans ce cours.Organisation des ordinateurss"inté-resse quant à lui aux principes de fonctionnement des machines capables d"exécuter les pro-grammes tels que ceux développés dans ce cours; il s"agit d"un sujet qui est ensuite approfondidansComputation structures.

Cette liste de cours n"est pas exhaustive.viiiChapitre 1Les ordinateurs, les algorithmes et lesprogrammes1.

1) IntroductionDans ce cours, nous allons apprendre à programmer un ordinateur.

Avant de pouvoir expli-quer ce que cela signifie exactement, la première étape est de définir précisément ce que l"onentend par "ordinateur".1.1.

1) Qu"est-ce qu"un ordinateur?Si l"on demande à plusieurs personnes prises au hasard d"expliquer ce qu"est un ordinateur,il est probable que la plupart d"entre elles vont évoquer le PC (Personal Computer, ordinateurpersonnel) qu"elles utilisent pour naviguer sur Internet, jouer à des jeux ou consulter leur courrierélectronique.

Une autre forme d"ordinateur que nous connaissons tous est bien sûr lesmartphonedont nous dépendons pour nous divertir et communiquer.

Certaines personnes vont sans douteaussi mentionner les grands systèmes informatiques que l"on trouve par exemple dans le siègecentral des banques, chargés de gérer les données financières relatives à un ensemble de comptes.Un autre exemple d"ordinateurs est donné par ceux qui sont chargés de résoudre des problèmesscientifiques, par exemple simuler le comportement de l"atmosphère en vue de prévoir la météo.À côté de ces types d"ordinateurs qui sont connus du grand public, il exist