M02 : Complexité -- cours 7 - Cours 7 -- Introduction et ...

Michel Van Caneghem [e-mail]

Description

M02 : Complexité -- cours 7
Cours 7 -- Introduction et rappels mathématiques
Michel V an Caneghem
[e-mail]
Octobre 2008
(C) 2008 Michel V an Caneghem () M02 : Complexité #7 Octobre 2008 1 / 32Objectifs du cours complet
L'objectif de cette UE est de vous présenter divers aspects de la
"complexité" des programmes. Cette UE se compose de :
✍ 6 cours et 6 TD (JFM) : P et NP exam noté 7/20 ;
✍ 6 cours et 6 TD (MVC) : Complexité théorique et expérimentale
d'algorithmes exam noté 5/20 ;
✍ 2 Devoirs à faire par binôme noté 8/20 .
(C) 2008 Michel V an Caneghem () M02 : Complexité #7 Octobre 2008 2 / 32Objectifs de cette partie du cours
La partie Complexité théorique et expérimentale, a pour but :
D'étudier les outils mathématiques nécessaires à l'analyse des
performances d'un algorithme.
De montrer comment améliorer les performances des algorithmes
faciles.
Il y aura deux devoirs à rendre qui vont compter , le premier pour 4
points, le second pour 4 points. Ces devoirs sont à faire au plus par
groupes de deux élèves. Chaque devoir mélange à la fois la pratique et
un peu de théorie et correspond environ à 10h de travail ( Remarque : On
compte 30h de travail étudiant pour 1 crédit : cela représente, les
cours, les TD, les TP et le travail personnel ). De manière générale, il
faut faire un petit programme (le langage recommandé est java 6 et je
vous conseille d'utiliser Eclipse) et rendre un document écrit.
Salles de TP réservées le Mardi et le V endredi ...

Sujets

• cours
• mathématiques
• mathématique

Informations

• Publié par: Anja
• Nombre de lectures: 274
• Langue: Français

Extrait

02)C(aVCnnage80iMhcle:Complexhem()M02erbo8002#étitcO7

Octobre 2008

321/

Cours 7 -- Introduction et rappels mathématiques

Michel Van Caneghem [e-mail]

M02 : Complexité -- cours 7

7Octité#2008obre

Objectifs du cours complet

L'objectif de cette UE est de vous présenter divers aspects de la "complexité" des programmes. Cette UE se compose de : 6 cours et 6 TD (JFM) : P et NP exam noté 7/20 ; 6 cours et 6 TD (MVC) : Complexité théorique et expérimentale d'algorithmes exam noté 5/20; 2 Devoirs à faire par binôme noté 8/20.

/223 - - - 20C)(plex:Com)M02hem(nageaVCnhcle80iM

Il y aura deux devoirs à rendre qui vont compter, le premier pour 4 points, le second pour 4 points. Ces devoirs sont à faire au plus par groupes de deux élèves. Chaque devoir mélange à la fois la pratique et un peu de théorie et correspond environ à 10h de travail (Remarque : On compte 30h de travail étudiant pour 1 crédit : cela représente, les cours, les TD, les TP et le travail personnel). De manière générale, il faut faire un petit programme (le langage recommandé est java 6 et je vous conseille d'utiliser Eclipse) et rendre un document écrit. Salles de TP réservées le Mardi et le Vendredi après-midi

De montrer comment améliorer les performances des algorithmes faciles.

La partie Complexité théorique et expérimentale, a pour but :

D'étudier les outils mathématiques nécessaires à l'analyse des performances d'un algorithme.

Objectifs de cette partie du cours

323/0820reobiM80lehc(02)Cti#éO7tcC:molpxehem()M02VanCaneg

C:molpxeti#éO7tcVanCaneghem()M02

eCUMEest la plate-forme d'apprentissage en ligne (e-learning en anglais) de l'Université de la Méditerranée, basée sur Moodle(http ://fr.wikipedia.org/wiki/Moodle) sous licence open source. Elle permet la création de communauté d'apprenants autour de contenus pédagogiques.

Connectez-vous sur l'ENT (http ://ent.univmed.fr)et choisissez le coursM02 : Complexité, vous devez être déjà inscrit.

Authentifiez vous et activez votre email de l'Université (redirection) [Vous devez votre photo, c'est plus pratique pour moi]

Consultez les activités Devoir pour rendre les devoirs

reob0820324/

Montrer la page

N'hésitez pas à utiliser le forum, si vous avez des questions d'intérêt général.

Utilisation d'eCUME

(C)2008Michel

plex:Com7Octité#0280boer

Le Devoir 1 - première partie

1) Un premier moyen consiste à trier ce fichier et prendre l'élément du milieu. Selon voustemps cela va prendre sur votrecombien de ordinateur ?

2) En fait il existe de meilleures méthodes (linéaires). Recherchez sur internet ces méthodes (Wikipedia) et dites moi laquelle vous choisiriez en expliquant pourquoi ? Vous programmerez 3 méthodes dans la seconde partie du devoir.

/52320C)(elchMi08genaCnaV20M)(meh

A rendre sur eCUME sous forme d'un fichier .pdf avant le Lundi 3 Novembre, 9h50 (Vous devrez me préciser la composition du binôme) après c'est impossible-- Vous devez répondre, en 2 pages (max), aux2 questions suivantes : On cherche a trouver le salaire médian des français (24 000 000 de salariés). Je n'ai pas ce fichier, mais on va le tirer au hasard ! (entiers).

/680

Les supports disponibles

23

MP3Cette année, je vais enregistrer le cours (audio) -- cela sera lisible sur un baladeur ;

iTunesEn gros cela va être un podcast -- le son plus les images des transparents -- pour lire sur un iPod ;

SMILCe sont des vieux cours (6 ans) qui avaient été enregistrés en video -- lire en streaming avec Real Player ;

Video.zipLa même chose que précédement, mais téléchargeable.

PDFr | PDF | MP3 | iTunes | SMIL | Video.zip

PDFrcours réduit, peut être imprimé 2Le fichier Pdf du pages/feuille ;

PDFLe fichier Pdf du cours ;

C)(naCnaVlehciM8002ompl02:Cm()Megheer02tcbo#éO7xeti

Introduction to Computational Molecular Biologyde Joao Meidanis, Joao Carlos Setubal (52,17 e )

Algorithms in C (existe en Java) : Fundamentals, Data Structures, Sorting, Searchingde Robert Sedgewick (74,64 e )

The Art of Computer Programmingde Donald Ervin Knuth (150,32 e ) -- 3 volumes -1969 ! ! !.

En fait il y a beaucoup d'informations sur Internet et ces livres ne sont pas indispensables. Je vous conseille wikipedia (attention selon la langue, ce n'est pas le même texte), ainsi que les cours ayant le même sujet dans des universités étrangères.

et les nombreux livres sur l'algorithmique....

20C:molpxeti#é 6 O7ctobre20087/32

Quelques Livres

6 6 6 ()C0280iMhcelVanCaneghem()M

0280/823O7tcboerplexité#)M02:Comgena(mehlehcCnaV20C)Mi08(

Le but est d'exprimer les performances d'un programme, en quantité de mémoire et en temps d'exécution, à l'aide de fonctions qui dépendent de la taille des données. Notion de limites : quandnestgrand. Relations de récurrences. Notions de combinatoire. Eléments de théorie des graphes.

Quelques rappels mathématiques

8002erbotcO7#éti

La notion de récurrenceest nécessaire pour analyser le comportement d'un programme récursif. Il faut penser que nous n'avons pas besoin de connaitre exactement la solution de la récurrence, mais seulement sa limite.

On cherche à prévoir le temps que va mettre un programme pour résoudre un problème (ou la mémoire nécessaire). Ce temps va dépendre du volume de données traité. Les ordinateurs calculent vite, mais on leur en demande de plus en plus !

La notion de limitesert a estimer le temps d'un programme quand le volume de donnée est grand : cela n'est pas la peine de rentrer dans le calcul exact, il faut seulement une estimation grossière (pas facile cependant !).

Pourquoi des mathématiques ?

329/nageaVCnhcle80iMplex:Com)M02hem((20C)

1! C:moM)20ti#élpxeVanCchelhem(aneg( ) iM8002)C013/0280boerO7tc

x 2 = o ( x 5 ) sinx = o ( x ) 14:709 p x = o ( x /2 + 7 cosx ) 23 logx = o ( x 0:002

x!1 lim g f ( ( x x =0 ) )

2

Il faut comparer les taux d'accroissement de différentes fonctions qui mesurent les performances d'un programme. Notation ``o'' :On dit quef ( x ) = o ( g ( x ) pourxsi

Ce qui veut dire quefcroit plus lentement quegquandxest très grand. Par exemple :

imiLset

) ) ndeirmfoneauonSi:latipôH'ledelgè 1 eiméntére ) eganm(he02)Mom:C02)CiM80lehcCnaV x = O ( x ) sinx = O ( s R ni

(1)

11/32008

La notationoest plus précise queO, maisOest plus facile à calculer et suffisant. Par exemple :

/1 alors :

0 ( x lim f ( x ) = lim f x!1 g ( x ) x1! g 0 ( x

x > x 0 ) f ( x )< kg ( x

2

Limites (2)

sifetgsont dérivables (voir wikipedia). Notation ``O'' :On dit quef ( x ) = O ( g ( x ) s'il existeketx 0 tels que :

ti#élpxeboerO7tc