[PDF] [PDF] Cours de lalgorithmique et programmation: Licence SMI- S2

View - Download [PDF] Cours de lalgorithmique et programmation: Licence SMI- S2

Previous PDF

Next PDF

Université Mohammed V

Faculté des Sciences

/LFHQFH60,-6$FFUpGLWDWLRQ - <(/%(1$1,

Année de production : 2014

2

2014/2015Algo1 /SMI1

FRXUV G·$OJRULPOPLTXH 1

1ère année SMI

GpSMUPHPHQP G·HQIRUPMPLTXH

Université Mohammed V

elbenani@hotmail.com

2014/2015Algo1 /SMI2

Objectif du cours

YObjectifs:Apprendre les conceptsde basede

l'algorithmique.et la résolutionde problèmeset écrire les algorithmes correspondants.Étudier les procédureset les fonctionsqui permettent de structurer et de réutiliser les algorithmes.Avoir une première notion de performancedes algorithmes utilisés.

Plan du cours

Y Y Y

YChap4: Les instructions conditionnelles

YChap5: Les instructions itératives (les boucles)

YChap6: Les tableaux

YChap7: Les fonctions et les procédures

YChap8: La récursivité

Y

YChap10: Les algorithmes de recherche et tri

2014/2015Algo1 /SMI3

3

Galerie de portraits

2014/2015Algo1 /SMI4

Mathématicien anglais, il publie en 1854 les Lois de la pensée. Dans ce livre, il décrit comment toute la logique peut être définie par un principe simple: le binaire.

George BOOLE

(1815-1864) John

Von NEUMANN

(1903-1957) L'un des personnages clés des débuts de l'informatique. Il publia de nombreux articles sur l'algèbre et la mécanique quantique avant de se consacrer à la construction d'ordinateurs et à la modélisation mathématique de la réaction en chaîne de la bombe A. Ses "machines IAS" sont à l'origine de "l'Architecture Von NEUMANN", c'est à dire celle des ordinateurs tels que nous les connaissons.

Galerie de portraits

2014/2015Algo1 /SMI5

Cette américaine, mobilisée comme auxiliaire dans la marine américaine fut affectée aux travaux de programmation et d'exploitation de l'ENIAC. Puis, devenue une grande spécialise de la programmation des ordinateurs, elle sera l'une des principales créatrices du

COBOL.

Grace Murray

HOPPER

(1906 -1992) Mathématicien anglais, maître-assistant à Cambridge dès 23 ans. Il a conçu en 1936 une machine logiquecapable de résoudre tous les problèmes que l'on peut formuler en termes d'algorithmes. Pendant la guerre, il participera à la réalisation de la Bombe, première machine électromécanique de décryptage des messages codés avec l'Enigma

Allemande.

Alan TURING

(1912 -1954)

Galerie de portraits

2014/2015Algo1 /SMI6

Cet ingénieur des laboratoires Bell, est l'auteur du langage C. En 1973, avec K.THOMPSON, il réécrira dans ce nouveau langage le système d'exploitation UNIX.

Dennis

RITCHIE

(1941) C'est l'un des pères de l'Internet. Encore étudiant de l'université de Los Angeles, il fut l'un des auteurs du protocole TCP/IPet développa avec une équipe de chercheurs les premiers outils utilisant ce mode de communication. Il est aujourd'hui président de l'Internet Society qui surveille les nouveaux standards d'Internet.

Vinton G.

CERF (1943 -) 4

Galerie de portraits

2014/2015Algo1 /SMI7

Objet.Bjarne

STROUSTRUP

(1950 -)

James Gosling

(1955 -) portablessurplusieurssystèmes.

Galerie de portraits

2014/2015Algo1 /SMI8

Ancien président (et fondateur avec P.ALLEN) de Microsoft. Cette société est à l'origine du MS-DOS, de

Windows, du Basic-Microsoftpuis de Visual Basic.

Bill GATES

(1951 -)

Steve JOBS

(1955 -2011) fondateurs de la société Apple. Après son éviction d'Apple S. JOBS créera la société Nextavant d'être rappelé pour redresser Apple.

Galerie de portraits

2014/2015Algo1 /SMI9

Richard

STALLMAN

(1953 -) Fondateur du projet GNU, lancé en 1984pour développer le systèmed'exploitationlibreGNUet donner ainsi aux utilisateurs des ordinateurs la liberté de coopérer et de contrôler les logiciels qu'ils utilisent. Il est également le créateur (entre autres) de l'éditeur Emacset du compilateur gcc. Finlandais d'origine, il a construit en 1991 un nouveau système d'exploitation de type UNIX appelé Linux. Ayant choisi de le diffuser suivant le principe des logiciels libres, Linus TORVALDS ne retire aucune royaltie de son travail sur le noyau Linux.

LinusTORVALDS

(1969 -) 5

Galerie de portraits

2014/2015Algo1 /SMI10

Larry Page

(1973 -)

Sergey Brin

(1973 -)

Créateurs du moteur de recherche Google.

Ces deux jeunes brillants nord-américains ont

lancé leur moteur de recherche en 1999.

Ce mot vient du terme "googol" qui désigne un

chiffre, un 1 suivi de 100 zéros, traduisant l'exhaustivité du moteur de recherche.

Mark Zuckerberg

(1984 -)

Créateur de Facebook

C'est en 2004 que la première version de

Facebookvoit le jour pour mettre en relation les

étudiants de Harvard.

Pourquoi un cours

G·MOJRULPOPLTXH

YPour proposer à la "machine» un travail à notre place. YProblème: expliquer à la machine comment elle doit le faire.

YBesoins: savoir expliqueret formaliserson problèmeConcevoiret écriredes algorithmes(séquence

qui décritcomment résoudreun problème particulier).

2014/2015Algo1 /SMI11

Les algorithmes sont anciens !

YLes algorithmes ne sont pas nés avec

ƒpour calculer le PGCDde

deux entiers est vieux de plus de 2000 ans ! présents dans la Chineancienne. (Par exemple, pour extraire des racinescarréesà partir de divisions effectuées sur une "surface à calculer»).

2014/2015Algo1 /SMI12

6

Les origines de

O·MOJRULPOPLTXH

YMohammed Al-Khwarizmi (780 -850)

YMathématicien, géographe, astrologueet astronome musulman arabe dontles écrits ont permis l'introduction de l'algèbreen Europe.

Y"algorithme»est lié au nom -

Khwarizmi.

Ce savant arabe a publié plusieurs méthodespour le calcul effectif de racineséquationdu seconddegréet grâce à lui les chiffresarabesont pu se diffuser en occident.

2014/2015Algo1 /SMI13

Algorithme

YSavoirexpliquercomment faire un travail sans la moindre ambiguïté.

YUn algorithme: est une suitefinie

applique à un nombre finide donnéesdans un ordreprécis pour arriver à un résultat.

Y: un travail de programmationayant

une visionuniverselle:Un algorithmene dépend pas du langagedans lequel il est implanté,ni de la machine qui va exécuter le programme correspondant.

2014/2015Algo1 /SMI14

2014/2015Algo1 /SMI15

Algorithmique

Ydésigne la disciplinequi étudie

les algorithmeset leurs applicationsen informatique

YUne bonneconnaissance de

exactset efficaces 7

2014/2015Algo1 /SMI16

3URSULpPpV G·XQ MOJRULPOPH

YUn algorithme doit:

avoir un nombre, avoir un par étape, se terminer après un nombre fini, fournir un résultat.

YChaque opération doit être:

définierigoureusementet sans ambiguïté effective, c.-à-d. réalisablepar une machine YLe comportement d'un algorithme est déterministe.

IHV 3 pPMSHV G·XQ MOJRULPOPH

Les entrées(les données du problème)Le traitementLes sorties

YLes entrées : repérerles données

nécessairesà la résolutiondu problème. YLe traitement : déterminertoutes les étapes des traitementsà faire et donc des "instructions" à développerpour arriver aux résultats.

2014/2015Algo1 /SMI17

IHV 3 pPMSHV G·XQ MOJRULPOPH

YLes sorties : les résultats obtenus peuvent

être affichésimpriméssur

papier, ou bien encore conservésdans un fichier.

2014/2015Algo1 /SMI18

8 ([HPSOH G·MOJRULPOPH UHŃHPPH GH ŃXLVLQH

2014/2015Algo1 /SMI19

([HPSOH G·XQ MOJRULPOPH

YOn se donne deux points A et B du plan.

1. Tracer le cerclede centreA passant par B.

2. Tracer le cerclede centre Bpassant parA.

3. Nommer Cet Dles points de ces cercles.

YConstruire le polygone ADBC.

YCet algorithmedécrit la constructionlosangedont une diagonaleest [AB].

YLes entréessont : les points A et B.

YLe traitementde la construction est décrit dans les phases1. 2. et 3.

YLa sortieest : le polygone ADBC.

2014/2015Algo1 /SMI20

Algorithme de calcul

Y

2014/2015Algo1 /SMI21

9

Génie logiciel

YDéfinition: le génie logiciel regroupeles scienceset les technologiesqui permettent la productionet la maintenancede logicielsde qualité

YLe cycle de vie regroupeles étapesde

productiondu logiciel, ainsi que leur ordonnancement.

2014/2015Algo1 /SMI22

Les étapes de développement

du logiciel

2014/2015Algo1 /SMI23

Les étapes de développement

du logiciel

Y1) Analysedes besoins: que fait le système ?On définit les fonctionnalitésdu systèmeà développer.

Y2) conception : comment faire le système ?décompositiondu système en modules logicielset matériel. Y3) Implémentation (codage): Réalisation des programmes dans un langage de programmation

2014/2015Algo1 /SMI24

10

Les étapes de développement

du logiciel Y4) tests unitaires : effectuer les tests de chaque composant du logiciel en vue de son intégration. Y5) intégration : Intégration des modules et test de tout le système

Y6) Livraison et maintenance: Livraisondu produit finalà l'utilisateur,Le suivi, les modifications, les améliorationsaprès

livraison.

2014/2015Algo1 /SMI25

Modèles de développement

YObjectifs: Organiserles différentes phasesdu cycle de vie pour

l'obtention d'un logicielfiable, adaptable et efficace.Guiderle développeurdans ses activitéstechniquesFournirdes moyenspour gérerle développementet la

maintenance(ressources, délais, avancement, etc.). YIl existeplusieurs typesde modèles: en cascade, en V,

2014/2015Algo1 /SMI26

Modèle en cascade

2014/2015Algo1 /SMI27

11

Modèle en V

2014/2015Algo1 /SMI28

Modèle en spirale

2014/2015Algo1 /SMI29

Les langages de programmation

YLe langage de programmationest l'intermédiaireentre l'humain (anglais)et la machine(binaire). YIl existe des milliersde langagesde niveau élevé, pour tous les goûtset toutes les applications.

YQuelques uns des plus connus: C, C++, Java, PHP

2014/2015Algo1 /SMI30

12

Les langages de programmation

YHaut niveau : proche de , vocabulaire et syntaxe

plus richesAssembleurLangage machine

YBas niveau : proche de la machine, instructions

élémentaires

2014/2015Algo1 /SMI31

Compilation et interpréteur

YCompilation: permet de traduirele codesourcedu

programme vers le langage natif (objet)de la machine(ou parfois vers du codeintermédiaire).

YInterpréteur: permet de traduireet chaque

instruction du programme. Ce mécanisme est utilisé pour le passageprogrammeprécompiléà un pseudo-code (cas de Java).quotesdbs_dbs29.pdfusesText_35

[PDF] Examen d 'informatique (Algorithmique)

[PDF] Recueil d 'Examens (1997 - 2009) Analyse Numérique - lamsin

[PDF] Cours offerts Examens de reprise sans cours Frais et - CSDM

[PDF] Architecture des ordinateurs Corrigé de l 'examen

[PDF] Le baccalauréat 2016 - Session de juin - Ministère de l 'Éducation

[PDF] 2

[PDF] Corrigé Examen Final Bases de Données (2010/2011) - essai

[PDF] Épreuve d 'économie familiale - Classe de troisieme

[PDF] Correction du QCM - Dunod

[PDF] Planning des Examens du S2 (2016/2017) : 2 année 11h00 - FSNV

[PDF] Examen bureautique

[PDF] ROYAUME DU MAROC

[PDF] NOTICE CAP PE session 2016 - Académie de Nantes

[PDF] Corrigé examen CAPACITÉ TRANSPORT - Capaplus

[PDF] Examen clinique