Information Calcul et Communication : [5pt] Présentation ...Jamila Sam & Jean-Cédric Chappelier Calcul de la note I La note ﬁnale du semestre, N, est calculée comme suit : N =

Présentation ducours

Qu’est-ce qu’unalgorithme?

Annexe :Environnementde travail

c©EPFL 2019-20Jamila Sam& Jean-Cédric Chappelier

Information Calcul et Communication :

Présentation générale

Jamila Sam

Laboratoire d’Intelligence ArtificielleFaculté I&C

ICC (partie programmation) – Cours 1 : Présentation du cours – 1 / 52





Plan

I Présenter le cours :

I Objectifs (« Quoi? »)

I Administration (« Comment? »)

I Introduire la programmation : notion d’algorithme

I Présenter l’environnement de travail pour la partie pratique


Présentation ducoursNotes et examens




Structure générale du cours ICC

INFORMATIQUE

PROGRAMMATION

Théorie Pratique

Partie théorique −→ Barbara JobstmannPartie pratique −→ Jamila Sam

I Cours obligatoire pour les étudiants du 1er semestre de lasection des Sciences de la Vie.

I Connaissances supposées acquises : aucune






Objectifs de la partie théorique

I Présenter l’informatique en tant que discipline scientifiqueI Exposer ses fondements conceptuelsI Développer la pensée algorithmique

+ « Computational thinking »I Expliquer les bases de fonctionnement du monde numériqueI Sensibiliser à la sécurité dans ce monde numérique

+ D’avantage lors du cours de vendredi !






Objectifs de la partie pratique

La programmation n’est qu’une partie de l’informatique mais unepartie importante et une discipline en tant que telle.Buts de la partie pratique :

1. Apprendre à programmersavoir les bases et connaître correctement au moins unlangage

+ pratique sur le langage C++

2. Appréhender par la pratique certaines des problématiquesconceptuelles vues dans la partie théorique

3. Savoir comment utiliser un ordinateur (sous Linux) dans lecadre du développement de programmes






Organisation de la partie théorique

Langue : AnglaisMoyens :

Concepts introduits lors de cours magistrauxex-cathedra

+ Vendredi 915–1100

mis en pratique, de manière guidée, lors deséances d’exercices sur papier

+ Vendredi 1515–1600






Organisation de la partie pratique

Langue : FrançaisMoyens :

Concepts introduits ou complémenté lors de coursmagistraux ex-cathedra

+ Jeudi 1015–1100

mis en pratique, de manière guidée, lors deséances d’exercices sur machines

+ Jeudi 1715–1900

Compléments en lignes : vidéos et quizzes(disponibles pour 8 semaines du cours).






Équipe

Barbara Jobstmann (Théorie) Jamila Sam (Programmation)

Alexandre Coudray David Aksun Ruofan Zhou Etienne Bamas

(Programmation) (Programmation) (Théorie) (Théorie)






Équipe (2)

De nombreux assistants étudiants apportent un soutienindispensable à ce cours :

I 10 assistants-étudiants (théorie)

I 12 assistants-étudiants (pratique)

+ Certains travaillent pour les deux parties, mais pas tous !

La liste complète est disponible sur le site Moodle du cours :

https://moodle.epfl.ch/course/view.php?id=15751






Accès au matériel du cours

I Logistique (salles, horaires, forums) : site Moodle du cours

https://moodle.epfl.ch/course/view.php?id=15751

I Planning et contenu des séances :

https://iccsv.epfl.ch/

+ aussi accessible via Moodle






Interaction avec les enseignants

Plusieurs moyens pour contacter les enseignants, assistants etétudiants-assistants pour poser des questions sur le cours ou lesexercices :

I Durant les séances d’exercices :

+ c’est le moyen le plus direct, et généralement le plus efficace.

I Par l’intermédiaire du forum (dans site Moodle)

+ moyen idéal pour diffuser la connaissance

N’hésitez pas à en faire usage !

I par email aux assistants :

+ mais pour les cas généraux, préférez le forum.

Les contacts personnels avec les enseignants (email,téléphone ou visites) devront être strictement réser-vés aux cas personnels et/ou urgents !






Support de coursTout le matériel est accessible via le site Web du cours :

I Transparentsparfois enrichis de notes techniques (mini-références)détaillant certains concepts évoqués pendant le cours, enparticulier les éléments du langage C++également parfois des références complémentaires(bibliographiques et/où hyperliens Internet)

I Énoncé des exercicesdisponibles sur le site Web en fin de semaine.

I Corrigé des exercicesdisponibles sur le site Web en fin de semaine suivante.

I Pour la partie pratique : Vidéos et quizzesofferts par le cours massif en ligne (MOOC) associé au cours(voir plus loin)






Livre? (1)

Pour la partie théorique, le livre suivant est recommandé :

Sous la direction de André Schiper, PPUR, 2016(prix etudiant 35 CHF)






Livres? (2)

Le matériel du MOOC, les transparents et divers supports du siteWeb devraient constituer une documentation suffisante pour lapartie programmation !

Si vous souhaitez la compléter, les ouvrages suivants sontégalement recommandés pour la partie pratique :

Marylène Micheloud & Medard RiederProgrammation orientée objets en C++– une approche évolutive, PPUR, 1997.

Il est disponible pour un prix avoisinant les 43 CHF.






Livres? (2)

Le matériel du MOOC, les transparents et divers supports du siteWeb devraient constituer une documentation suffisante pour lapartie programmation !

Si vous souhaitez la compléter, les ouvrages suivants sontégalement recommandés pour la partie pratique :

J.-C. Chappelier & F. SeydouxC++ par la pratique –recueil d’exercices corrigés et aide-mémoire,PPUR, 3ème édition. Empruntable en versionélectronique auprès de la bibliothèque

Il est disponible pour un prix avoisinant les 50 CHF.






Couplage au MOOC (1)

MOOC d’initiation à la programmation en C++ :

www.coursera.org/learn/initiation-programmation-cpp/

Notre cours dispose de ses propres séries d’exercices et detransparents de complément

+ Sur-ensemble du MOOC

Matériel MOOC utilisé :1. Vidéos2. Quizzes3. Devoirs (mais ne comptent pas)

+ à utiliser pour se préparer aux tests







I Avant le cours : visionner les vidéos, faire les quizzes etcomprendre certains exercices de niveau 0

I Cours ex-cathedra : résumé et approfondissements+ seulement une heure

I Exercices : mise en pratique

I Certificats (payants) : en aucun cas obligatoires pour cecours







Charge de travail pour la partie pratique :

I 45 mn de cours ex-cathedra : récapitulation etapprofondissements ;

I 1h45 d’exercices en salle de TP : mise en pratique ;

I environ 3h30 heures de travail à la maison :

I 1h30-1h45 sur les vidéos de la semaine suivante

I 0 :15-0 :30 sur les quizzes de la semaine suivante

I environ 1 :30 heures pour commencer à préparer la séried’exercices de la semaine en cours, finaliser celle de lasemaine passée.






Notes et examens

Les épreuves de contrôle continu seront les suivantes :

I Mid-term (théorie) individuel, 1h45

I Série notée (pratique) individuel, 1h15

I Examen écrit final (théorie + pratique) individuel, 1h45






Calcul de la note

I La note finale du semestre, N, est calculée comme suit :

N = (3∗NserieNotee+3∗Nmidtermtheorie+4∗Nexamen)10

I Les notes intermédiaires ne sont pas arrondies.

I Les cours ICC et programmation II sont indépendants. Lamoyenne arrondie de chaque cours est transmise au SAC àla fin de chaque semestre.






Notes et examensMid-term théorie

Objectif : vérifier la maîtrise des concepts exposés dans la partiethéorique du cours

Examen écrit (documentation non autorisée)

Réalisé individuellement

Le mid-term sur la théorie aura lieu le :

Vendredi 25 Octobre






Notes et examensSérie notée

Objectif : vérifier la maîtrise des concepts du langage C++exposés en cours.

Séance d’exercices, à l’issue de laquelle le travail réalisé estenvoyé par courrier électronique aux assistants responsables.

Réalisée individuellement

Documentation autorisée

La série notée aura lieu le :

Jeudi 21 Novembre






Notes et examensExamen final

Le semestre sera clôturé par un examen écrit portant sur lecontenu du cours et les séances d’exercices, aussi bien pour lapartie théorique que pratique.

Réalisé individuellement

Documentation autorisée

Date :

Vendredi 20 Décembre






Qu’est-ce que la programmation?

«PROGRAMME» :Conception :quelles notes en-chainer? Exécution : tourner la

manivelleRésultat : mélodie

Réalisation : percerles trous aux bonsendroits






Algorithme?

+ solution calculatoire/mécanique/itérative/... à un problème

”Spécification d’un schéma de calcul sous forme d’une suited’opérations élémentaires obéissant à un enchaînementdéterminé”

[Encyclopedia Universalis]

AlgorithmeI suite finie de règles à appliquer,I dans un ordre déterminé,I à un nombre fini de données,I se terminant (i.e., arriver, en un nombre fini d’étapes, à un

résultat, et ce quelque soit les données traitées).






Algorithme

Un algorithme est un moyen pour un humain de représenter larésolution par calcul d’un problème à une autre personnephysique (humain) ou virtuelle (calculateur) ; un algorithme est :

I séquentiel si ses opérations s’exécutent en séquence,I parallèle si certaines de ses opérations s’exécutent en

parallèle,I réparti si certaines de ses opérations s’exécutent sur

plusieurs machines.






Toute une théorie

Formalisation : dans les années (19)30 par des mathématiciens :Gödel, Turing, Church, Post, ...

+ fonctions "calculables" et machines de Turing : abstractionmathématique des notions de traitement (suite d’opérationsélémentaires), de problème et d’algorithme.

+ la partie théorique du cours a pour but de vous en donner unaperçu !






Algorithmes et données

« Voulez-vous danser? » : premier algorithme :

Voulez−vousdanser?

Choisir une

personne

ouiSuccess story

non

Données :

I PersonneI Ensemble de N

personnes

+ Il n’est pas garanti que l’algorithme puisse se terminer !






Algorithmes et données

« Voulez-vous danser? » : deuxième algorithme :

Choisir la

personne i

Voulez−vous

danser?

i = i+1

i > N

i=1

Hopeless

non

oui

non oui

Success story Données :

I PersonneI Ensemble

ordonné de Npersonnes

I les données sont structuréesI l’algorithme se termine nécessairement

(au pire N essais successifs)I . . . mais il n’est pas sûr qu’il soit le plus efficace possible !






Conception d’un programmeConcrètement, concevoir un programme c’est décomposer latâche à automatiser sous la forme :I d’une séquence d’instructions (traitements)I et de données permettant une mise en oeuvre efficace et

correcte des traitements.

traitements données

influencent

opèrent sur

Formalisation des traitements : algorithmes

+ distinguer formellement les bons traitements des mauvais

Formalisation des données : structures de données (abstraites)

+ distinguer formellement les bonnes structures de donnéesdes mauvaises






Algorithmes – objectifs

On attend d’un algorithme qu’il :I se termine,I produise un résultat correct,I pour toute donnée d’entrée valable.

+ Il n’y a (mal)heureusement aucune recette pour produire unalgorithme !






Difficulté de l’Informatique

Un programme doit être valable pour toute une gamme d’entrées !

+ Impossible de vérifier par des essais : on ne pourra jamaistester tous les cas.

Vérification par preuves mathématiques.

Importance du travail soigneux et mûrement réfléchi !






Algorithme 6= Programme

Un algorithme est indépendant du langage de programmationdans lequel on va l’exprimer et de l’ordinateur utilisé pourl’exécuter

C’est une description abstraite des étapes conduisant à la solutiond’un problème.

Algorithme = partie conceptuelle d’un programme(indépendante du langage)

Programme = implémentation (i.e., réalisation) de l’algorithme,dans un langage de programmation et sur un système particulier.

+ Premier programme au cours prochain






Lien entre les parties théorique et pratique

I L’écriture de programmes est indissociable de la conceptiond’algorithmes.

I Certains exercices de la partie pratique vous permettrontd’expérimenter plus concrètement des problématiquesconceptuellement abordées dans la partie théorique :

I Ecriture d’algorithmes simples

I Mise en pratique de techniques de résolution algorithmiques(récursion, dichotomie)

I Théorie de la complexité






Pour préparer le prochain cours

I Vidéos et quiz du MOOC semaine 1 :I Introduction [09 :55]I Variables [18 :08]I Variables : lecture/écriture [13 :43]I Expressions [14 :50]

+ A échelonner sur plusieurs jours pour éviter l’« overdose »

I Le prochain cours :I Jeudi 10h15 à 11h (résumé et compléments)




Annexe :Environnementde travailSystèmed’exploitation

Shell

Système de fichiers

Editeurs et EDI


Aspects logiciels d’un ordinateur

Pour fonctionner, un ordinateur doit pouvoir interagir avecl’environnement :

I comprendre, c’est-à-dire ici traiter, les informations luiprovenant (clic de souris, touche clavier, . . . )

I produire des sorties (sons, image écran, . . . )

Cela se fait grâce à des programmes (ou « logiciels ») dont leplus fondamental, est le système d’exploitation.

Le système d’exploitation est responsable de la gestion desinteractions entre l’unité centrale et ses périphériques,Exemples : MacOS X, Linux, Solaris, Windows...





Shell


Editeurs et EDI


Catégories de Logiciels

logiciels d’application traitement de tâches spécifiques auxutilisateurstraitements de textes, tableurs, logiciels de comptabilité, CAO, ....

logiciels utilitaires servant au développement des applicationsassembleurs, compilateurs, dévermineurs, gestionnaires de versions,

gestionnaires de fenêtres, librairies d’outils, ...

logiciels systèmes regroupés dans le système d’exploitation+ présents au cœur de l’ordinateur, ces logiciels sont à labase de toute exploitation, coordonnant les tâchesessentielles à la bonne marche du matériel.





Shell


Editeurs et EDI


Système d’exploitation

matériel

applications / services

gestionnaire de fenêtres

système d’exploitationinterpréteur d

e commandes

...

(Windows)

(MacOS)

(DOS)

Linux

OpenBSD

FreeBSD

Solaris





Shell


Editeurs et EDI


Interaction avec LinuxComment interagir avec votre système d’exploitation?

+ avec un interpréteur de commande (« shell »)

matériel

applications / services

gestionnaire de fenêtres

interpréteur de commandes

système d’exploitation

Parmi les shells Unix les plus utilisés, citons : Bourne [Again] shell (sh et bash), Cshell (csh), Z shell (zsh), et celui présent par défaut sur les comptes du cours,l’Enhanced C shell (tcsh). ICC (partie programmation) – Cours 1 : Présentation du cours – 37 / 52




Shell


Editeurs et EDI


Interpréteur de commandes (1)

Pour interagir avec l’utilisateur, un système informatique doitdisposer au minimum d’un interpréteur de commandes(« shell »)

Contrairement à d’autres architectures moins modulaires, l’interpréteur decommandes (ainsi que le gestionnaire de fenêtres) des systèmes de typeUNIX est un composant externe au SE.Ne faisant pas directement partie du système, ils peuvent être changés àsouhait.

Le shell attend les ordres que l’utilisateur transmet par le biais del’interface, décode et décompose ces ordres en actionsélémentaires, et finalement réalise ces actions en interagissantavec le système d’exploitation.

Parmi les shells Unix les plus utilisés, citons : Bourne [Again] shell (sh etbash), C shell (csh), Z shell (zsh), et celui présent par défaut sur lescomptes du cours, l’Enhanced C shell (tcsh).





Shell


Editeurs et EDI


Interpréteur de commandes (2)

Depuis un interpréteur de commandes vous aurez la possibilitéde :I lancer des programmes (par exemple un navigateur web,

commande firefox)I exécuter des commandes Unix (on peut aussi regrouper

plusieurs commandes dans un fichier alors appelé script).I définir des variables d’environnement,I renommer ou définir de nouvelles commandes (alias), etc...

La plupart des interpréteurs offrent également des facilitésd’édition comme le rappel des commandes précédentes(historique des commandes), la complétion (complète le nom dufichier lorsqu’il n’y a plus d’ambiguïté), la correction en cas decommande invalide, ...





Shell


Editeurs et EDI


La commande man

man permet d’accèder à l’aide du sytème (« page de manuel »)

Utilisations :man nomman section nomExemples : man tcsh man ls man man

Les man-pages sont organisées en différentes sections :1 commandes et programmes2 appels systèmes (noyau)3 bibliothèques logicielles4 fichiers spéciaux (/dev)

5 formats de fichiers6 jeux7 divers8 administration système

Comparer :man printf et man 3 printfman time et man 2 timeman man et man 7 man

man -a nom pour avoir toutes les man-pages portant sur ce nom.(’q’ pour quitter une manpage et passer à la suivante)





Shell


Editeurs et EDI



Le concept de fichiers est une structure adaptée aux mémoiresde masse permettant de regrouper des données.

Un fichier c’est une collection ordonnée de données,représentant une entité pour l’utilisateur.

Le système d’exploitation va donner corps au concept defichiers, c’est-à-dire les gérer : les créer, détruire, modifier, lire, etoffrir la possibilité de les désigner par des noms.

Dans le cas de systèmes multi-utilisateurs, il faut de plus assurerla confidentialité de ces fichiers, en protégant leur contenu duregard des autres utilisateurs.





Shell


Editeurs et EDI


Structuration d’un système de fichiers

Grand nombre de fichiers

+ fournir un moyen pour organiser ces fichiers

+ concept de répertoire (directory)

Un répertoire est une collection (généralement non ordonnée) defichiers ou de répertoires (alors appelés sous-répertoires).Ils permettent d’organiser l’ensemble des fichiers dans unestructure arborescente

= un répertoire

= un fichier





Shell


Editeurs et EDI


Structuration d’un système de fichiers (2)

En plus de la notion de répertoire, la plupart des systèmespermettent également de définir des liens symboliques vers desfichiers ou des répertoires (« soft links » avec UNIX, ou« raccourcis » dans d’autres systèmes), qui permettent de définirdes alias (i.e., autres noms)+ permet d’assouplir la structure d’arbre





Shell


Editeurs et EDI


Nommage des fichiers : absolu et relatifOn appelle « chemin » la succession des répertoires conduisantà un fichier, à partir d’un endroit donné dans l’arborescence.

Pour désigner un fichier, il est possible de procéder de deuxmanières :I à l’aide d’un chemin absolu : on prend comme convention un

parcours de l’arbre partant de la racineDans le cas de plusieurs arbres (« forêt »), le nom du lecteurest tout d’abord spécifié (i.e. on désigne la racine de l’arbre).

home

tmp

julie

marc

cours a

/

/home/julie/cours/a

I à l’aide d’un chemin relatif : c’est la succession desrépertoires à traverser, à partir d’un autre répertoire del’arborescence

../julie/cours/a

cours/a

home

tmp

julie

marc

cours a

/





Shell


Editeurs et EDI


Nommage des fichiers (2)

Le répertoire parent d’un sous-répertoire est désigné par ..,tandis que le répertoire lui-même est désigné par .

Là il y a un point et là deux

Exemples de noms de fichiers (« chemins ») :/home/prof/Work/cours/Info1/introduction2.tex

../images/paysages.gif

../../../toutlahaut.ps.gz

Sous UNIX/Linux, le délimiteur entre nom de répertoire et nom defichier dans les chemins est la barre oblique « slash » : /

D’autres systèmes utilisent l’« antislash » ou « backslash » : \D:\Users\Himher\Personnal Documents\introduction2.pdf





Shell


Editeurs et EDI


Système de fichiers UNIX/Linux

Chaque utilisateur possède un répertoire personnel (« homedirectory ») dans lequel il peut placer ses fichiers personnels.C’est la racine du sous-arbre réservé spécifiquement à unutilisateur

Les noms de fichiers possèdent généralement une extension,délimitée par un .

Là aussi il y a un point

Cette extension peut être utilisée pour indiquer la nature du fichier,c’est-à-dire l’application à laquelle il est associé.Contrairement à d’autres systèmes d’exploitation, sousUNIX/Linux les fichiers peuvent avoir 0, 1 ou plusieursextension(s).

Exemples :serie1.cc : fichier de code source C++

cours-1.ps.gz

1re extension indiquant un fichier Postscript2e extension indiquant un fichier compressé avec gzip





Shell


Editeurs et EDI


Fichiers « cachés »

On distingue les fichiers/répertoires « cachés » au moyen d’uneconvention de nommage : ils sont préfixés par un .

Encore un point !

Exemple : .cshrc

Ce sont des fichiers/répertoires dont l’utilisateur n’a pas besoinexplicitement (ou pas souvent), souvent des fichiers deconfiguration.

Pour voir les fichiers/répertoires « cachés », utilisez la commandels -a





Shell


Editeurs et EDI


Fichiers et shell

Un certain nombre des fonctions du shell sont relatives ausystème de fichiers :I Navigation dans la structure des fichiers :

I répertoire courant (pwd)I modification de ce répertoire (cd = change directory),I lister le contenu d’un répertoire (ls),I copier des fichiers (cp) et les déplacer (mv),I effacer des fichiers (rm),I créer des liens (ln), etc...

Toutes les commandes soumises au shell sont interprétéesrelativement au répertoire courant.





Shell


Editeurs et EDI


Fichiers et shell (2)

Les caractères de substitution (ou expressions régulières)permettent de spécifier plusieurs fichiers en une seule formule? : remplace un seul caractère arbitraire* : remplace une séquence quelconque de caractères[ ] : remplace un seul caractère parmi ceux entre crochets.

cours-?.ps.gz cours-*

cours-1.ps.gzcours-2.ps.gz...cours-A.ps.gz

cours-1.pdfcours-1.ps.gzcours-10.ps.gzcours-2.ps.gz...cours-A.texcours-A.ps.gz





Shell


Editeurs et EDI


Caractères de substitutionExemples

ls ??? liste tous les fichiers de trois lettres du répertoirecourant

ls *.txt liste tous les fichiers du répertoire courant se ter-minant par .txt

ls *.[ch] liste tous les fichiers du répertoire courant se ter-minant par .c ou par .h

ls *.cc *.h liste tous les fichiers du répertoire courant se ter-minant par .cc ou par .h





Shell


Editeurs et EDI


Méta-caractères

*, ?, [, ] sont donc des caractères réservés (ou« méta-caractères »), en ce sens qu’ils ont un rôle particulier dansl’interpréteur de commandes.

Il en existe d’autres : | \& ; ( ) < > $ \ " ’ ~ ‘

Si on souhaite les utiliser, il faut les protéger ce qui se fait avec le« backslash » : \

Exemple :echo \\ abc \; \<affiche \ abc ; <





Shell


Editeurs et EDI


Editeurs de texte

Pour écrire et modifier des fichiers le moyen le plus naturel estd’utiliser un un éditeur de texte tels que :I EmacsI GeanyI geditI SciteI SublimeTextI notepad ou wordpad (Windows)I WinEdt (Windows)I jEdit (Windows, Mac OS X, Linux, ...)I . . .

Connaître un/des éditeur(s) de texte est absolumentindispensable !

+ La mini-référence "Environnement Unix", disponible sur le sitedu cours dédie une de ses sections à Emacs et Geany. Vousaurez aussi l’occasion de les utiliser en TP.
