[PDF] [PDF] Introduction à lalgorithmique et à la programmation - INSA Lyon

[PDF] Algorithmique et programmation

M1 HN – Algorithmique et programmation http://eric univ-lyon2 fr/jdarmont/ Page 1 sur 20 Définitions Algorithme Un algorithme est une suite finie et non 

[PDF] Algorithmique et Programmation - LaBRI

Fonctionnement de l'ordinateur • Dialoguer avec l'ordinateur • C'est quoi la programmation? • Algorithme • Notion de variable • Instruction d'affectation

[PDF] Introduction à lalgorithmique et à la programmation - INSA Lyon

Introduction `a l'algorithmique et `a la programmation – p 1 Algorithmique • Algorithmique : Science qui étudie l'application des algorithmes à l'informatique

[PDF] Algorithmique Programmation - limsi

24 jan 2019 · Algorithmique-Programmation I - Introduction Le cours, le poly, les TDs et TPs du semestre S'1 ont été revus par rapport au semestre S1 afn 

[PDF] Algorithmique, programmation

22 fév 2021 · Par ailleurs, le cours introduit l'écriture d'algorithmes pour préparer l'écri- ture d' un programme L'algorithme est une suite finie, séquentielle, de 

[PDF] Algorithmes et langage C - Ecole Mohammadia dingénieurs

ETAPES ET DEMARCHES DE RESOLUTION ALGORITHMIQUE LES TABLEAUX langage naturel et indépendant de tout langage de programmation

[PDF] Programmation et Algorithmique - Départements de recherche et

Le th`eme principal du cours est, du côté de la programmation, la conception et la mise en œuvre de nouveaux types Le langage Java le permet de deux façons,  

[PDF] Algorithmique - Programmation 1 Cours 1

Application: implantation d'algorithmes au moyen du langage de programmation caml → apprendre syntaxe et sémantique d'un langage ▻ Pourquoi pas 

pdf COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE - unicefr

Structures algorithmiques fondamentales: Implantation des algorithmes dans un langage de programmation Introduction au test unitaire boîte noire Algorithmes fondamentaux de recherche recherche d’un élément parcours tri

Algorithmique et programmation - Education

concevoir des algorithmes et les traduire dans un langage de programmation Les modalités de l’apprentissage correspondant peuvent être variées : travail individuel ou en groupe en salle informatique ou en salle banale au tableau ou sur papier sur tablette ou sur ordinateur

[PDF] algorithmique et programmation exercices corrigés pdf

[PDF] algorithmique et programmation pdf

[PDF] algot ikea avis

[PDF] algot ikea pdf

[PDF] ali baba séquence pédagogique

[PDF] aliasing doppler

[PDF] aliment interdit femme enceinte 1er trimestre

[PDF] aliment riche en vitamine e et zinc

[PDF] alimentation 2 ans

[PDF] alimentation 5 ans

[PDF] alimentation animale elevage

[PDF] alimentation bebe de 3 ans

[PDF] alimentation bébé mois par mois

[PDF] alimentation creche

[PDF] alimentation d'un bébé de 1 an

AntoineFRABOULET

antoine.fraboulet@insa-lyon.fr etUsages

Algorithmique

algorithmesàl'informatique l'accomplissementd'unetâche.

LePetitRobert

Pr´esentation

Introduction

Basesdel'algotithmique

Structuredesdonnées

Structuredesopérations

Quelquesméthodesdetri

Gestiondeslistes

Introduction

méthodeindépendantedelamachine résolutionstructurée

Algorithmiqueetprogrammation

1.Analyseduproblème

2.Conceptiond'unesolution:algorithmique

choixdelareprésentationdesdonnées choixdelaméthodeutilisée

3.Développement:programmation

choixdulangagedeprogrammation choixdelamachineutilisée

4.Tests

calculutilséesenalgorithmique.

QuelquesthÁemes

Tri:

Recherche:

danslamémoire.

Traitementdechaines:

compressiondefichiers,cryptographie.

QuelquesthÁemes(2)

Algorithmessurgraphes:

Algorithmesmathématiques:

entiers,despolynômes,desmatrices.

Basesdel'algorithmique

Données

variables structures tableaux pointeurs modèlesdynamiquesCalcul instructions conditions boucles fonctions récursion l'algorithmiquec'est: lechoixd'unalgorithme lechoixd'unestructurededonnées lesdeuxsontindissociables

Structuresdedonn´ees

Unalgorithmemanipuledesdonnées:

1,2,3,4...

3,1415

"bonjour"

Variable:nomd'unevaleurenmémoire

caractère entier nombreàvirgule

Structuresdedonn´ees

Variable=nomd'unespaceenmémoire

1 octetcaractère "C"

entier "X"

Structuresdedonn´ees:typesdebase

suivantes: nom taille(octets)minmax"unsigned" caractère1(8bits)128127255 short

2(16bits)327683276765535

int

4(32bits)23123112321

long

4(32bits)idemidemidem

float

4(32bits)1:1710383:4010+38

double

8(64bits)2:22103081:7910+308

Structuresdedonn´ees

structuredate=( entierjour entiermois entierannee structurerendez vous=( structuredatedate structurepersonnenom structureadresselieu

Structuresdedonn´ees

nomd'unespaceenmémoire

1 octetcaractère "C"

entier "X" jourmoisannée date "t"

Typesdebase

L'utilisationsefaitenutilisantlepoint"."

structuredate( entierjour entiermois entierannee structuredatet1,t2 t1.jour=10 t1.mois=5 t1.annee=2008 t2=t1(copiedetoutelastructure=3 variables)

Structuresdedonn´ees:tableaux

Collectionsdevariables:

Tableaux:

ensembledevariablesdemêmetype. entiert[12]tableautcontenant12entiers entierx t[6]=42modificationdu7emeélément enmémoire. estsouventnuméroté0eninformatique.

Structuresdedonn´ees:tableaux(2)

4 octets

tableau t[0]t[1]t[5] t[6] t[11]t

Basesdel'algorithmique

Structuresdedonnées

variables structures tableaux

Structuresdecontrôle

Structuresdecontrˆole

Organisationdesopérations:

Opérations:+-*/=!=...

+=:opérationsusuelles comparaisonssurlestypessimples opérateurslogiques(et,ou,négation) opérationssontrespectées

Instructionssimplesetexpressions

x=123 y=x+w*3

Ex´ecutionconditionnelle

Exécutionconditionnelle:

si[testestvrai]alors instructions sinon instructions finsi instruction

Exemple:

sia´Ex´ecutionr´ep´etitive

Bouclederépétitionfixe:

pour[ensembledevaleurs] faire instructions finpour instruction

Exemple:

pouri=0jusqu'` ai<12faire affichert[i] finpour

´Ex´ecutionr´ep´etitive

Bouclederépétition"tantque":

tantque[testvrai]faire instructions fintantque instruction

Exemple:

i=0 tantquei<12faire affichert[i] i=i+1 fintantque

Structuredecontrˆole:fonctions

Permetd'utiliserdesparamètres.

depuisplusieursendroits. passagedesparamètres importante lafonction

Exempledefonction

entierTrouveMaximum(entiera,entierb) f entierm(variablelocalem) siaStructured'unefonction entierTrouverMaximum(entiera,entierb) f entierm siaFonctionsr´ecursives données ensemblededonnéesàtraiterpluspetit entierf(entiern) f entierr sin=0alors r=1 sinon r=n*f(n-1) finsi renvoyerr g

Structured'unprogramme

Visibilitédesvariables

variableslocales:internesàunbloc

Ledéroulementd'unprogrammecommence

àlapremièreinstructionisolée

Basesdel'algorithmique

Structuresdedonnées

variables structures tableaux

Structuresdecontrôle

instructions conditions boucles fonctions récursion

Quelquesméthodesdetri

Tripars´election

leplacerentêtedutableau

143295

325914321495

321495

321459

Tripars´election

TriSelection(entiert[],entiertaille)

f entieri,j,min,tmp pouri=0jusqu'` ajAutrestris lesprécédentes.

à2.

unseulélément).

Triparinsertion

TriInsertion(entiert[],entiertaille)

f entieri,j,tmp pouri=0jusqu'` ai0ett[j-1]>tmpfaire t[j]=t[j-1] j=j-1 fintantque t[j]=tmp finpour g

Tribulle

TriBulle(entiert[],entiertaille)

f entieri,j,tmp pouri=taillejusqu'` ai>1aveci=i-1 faire pourj=1jusqu'` ajt[j]alors tmp=t[j-1] t[j-1]=t[j] t[j]=tmp finsi finpour finpour g

Coˆutdesalgorithmes

!Différencierleurscoûts: coûtentempsd'exécution coûtenplacemémoire nombredetransfertsmémoire tableauxparexemple).

Complexit´edesalgorithmes

Onpeutdifférencierl'analysepour

meilleurcas casmoyen pirecas

Diff´erentescomplexit´e

0 50
100
150
200
250
300
350
400

0 5 10 15 20

xlog(x)x*log(x) x*xx*x*xexp(x)

Comparaisondesordresdegrandeur

tailleduproblème/tempsd'exécution tailleduproblème:n

2242628

lnlnn022.583 lnn 1468
n

21664256

nlnn

2643842048

n 2

4256409665536

2 n

4655361.84e+191.15e+77

n!

22.09e+131.26e+898.57e+506

Algorithmiquepratique

donnéesàtraiter.

élémentsdestableaux.

Lestrisexternes

datepourdesrendezvousparexemple) ensemblesansleschangerdeplace lesdonnées.

Basesdel'algorithmique

Structuresdedonnées

variables structures tableaux pointeurs

Pointeurs

queltype entier*pi:picontientl'adressed'un entier structuredate*t:tcontientl'adresse d'unedate entieri entier*pi=&i i=3 (*pi)=4:iest´ egal` a4

ModÁelesdedonn´eesdynamiques

files... stockéesdépenddelastructure.

Cetypedestructureutilisedespointeurs

structureelmt listef intvaleur; structureelmt liste*suivant; g

Structuresdedonn´ees:liste(2)

4 octets

Liste chaînée

LL

Structuresdedonn´ees:liste(3)

4 octets

Liste chaînée

LL ajout d'un élément

Structuresdedonn´ees

Choixdemanipulationdesstructures

Listes

Piles(LastInFirstOut)

Files(FirstInFirstOut)

Structuresdedonn´ees:Piles

Pile ajoutertoujoursausommet seullesommetestvisible retirertoujoursausommet

Structuresdedonn´ees:Files

Pile ajoutertoujoursausommet seulledernierestvisible retirertoujoursàlafin onpeutgarderunpointeursurlafin pourêtreplusefficace

Structuresdedonn´ees

PileArbre

Conclusion

données variables structures tableaux pointeurs modèlesdynamiques calcul instructions conditions boucles fonctions récursion l'algorithmiquec'est: lechoixd'unalgorithme lechoixd'unestructurededonnées lesdeuxsontindissociables

Conclusion

estdominéparunpoignéed'algorithmes rendreleprogrammeentierinutilisable.

Quelqueslivres

Courtin&Kowarski,Dunod,1989

Dunod,1994

quotesdbs_dbs48.pdfusesText_48