Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Overview PDE PDE ODE FD FD FD FV FV FV

De
95 pages
LogoINRIA Overview 1 PDE 1-2 PDE 2 ODE 3 FD 4 FD 5 FD 6 FV 7-8 FV 8-9 FV 10 Numerical Methods for PDE: Finite Differences and Finites Volumes B. Nkonga JAD/INRIA Lectures References: Roger Peyret (NICE ESSI : 89), Tim Warburton (Boston MIT : 03-05), Pierre Charrier (Bordeaux Matmeca 96-08) B. Nkonga Lectures References: Roger Peyret (NICE ESSI : 89), Tim Warburton (Boston MIT : 03-05), Pierre Charrier (Bordeaux Matmeca 96-08) 1 / 33

  • nkonga lectures

  • scalar nonlinear

  • advection-diffusion equation

  • multi-dimensional extensions

  • references

  • finite difference


Voir plus Voir moins
Les algorithmes
Lath´eoriedelacomplexit´e:unpeudhistoir
Complexite´ Th´eoriede
avance´e-UMIN laNP-Comple´tude
Christophe
September
Christophe PAUL
PAUL
21,
2007
345 (1)
Complexit´eavanc´ee-UMIN345The´oriedelaNP-Compl´etude
Les algorithmes
Lath´eoriedelacomplexite´:unpeudhistoir
Bibliographie
A Guide to the Theory of NP-Completenes, M.R. Garey and D.S. Johnson Computational Complexity, C. Papadimitriou. Parameterized Complexity, R. Downey and M. Fellows. Invitation to Fixed-Parameter Algorithms, R. Niedermeier.
Christophe PAUL
Complexite´avanc´ee-UMIN345The´oriedelaNP-Comple´tude
Les algorithmes
1
2
3
4
Lathe´oriedelacomplexite´:unpeudhistoir
Les algorithmes Un exemple Quelles garanties ?
Lath´eoriedelacomplexite´:unpeudhistoire
La classeP Lesr´eductionspolynomiales Les certificats polynomiaux
La classeNP Quelques reductions ´
ChristophePAULComplexite´avance´e-UMIN345Th´eoriede
laNP-Compl´etude
Les algorithmes
Lathe´oriedelacomplexit´e:unpeudhistoir
Un exemple
Quelles garanties ?
AlgorithmeiWede´ri]aidepik[t Unalgorithmeoiturapn´rallosese´eerntoynmprenctaulecsul dunproble`me.Cestun´enonce´dansunlangagebiende´nidune uitedop´erationspermetttd´soudreparcalculunprobl`eme. s an e re
Lemotvientdunomdumath´ematicienAl Khuwarizmi, qui, au IXesi`ecle´ecrivitlepremierouvragesyste´matiquesurlasolution des´equationslin´eairesetquadratiques
Lalgorithmeleplusc´el`ebreestceluiquisetrouvedanslelivre7 desEeml´dilcestneuEd. Il permet de trouver leplus grand diviseur commun, ou PGCD, de deux nombres.
Christophe PAUL
Complexit´eavanc´ee-UMIN345The´oriedelaNP-Compl´etude
Les algorithmes
Lath´eoriedelacomplexit´e:unpeudhistoir
Untribizarre...[Chv`atal]
Un exemple
Quelles garanties ?
Donn´ees:σune permutation de [1,n] R´esultat permutation: uneσ0telle queσ0(1) = 1 tant queσ(1)6= 1faire Renverser l’ordre desσ´sreimertneme´le)sp(1 fin
Christophe PAUL
Complexite´avance´e-UMIN345The´oriede
laNP-Comple´tude
Les algorithmes
Lath´eoriedelacomplexite´:unpeudhistoir
Untribizarre...[Chva`tal]
Un exemple
Quelles garanties ?
D´ees:σune permutation de [1,n] onn Re´sultat: une permutationσ0telle queσ0(1) = 1 tant queσ(1)6= 1faire Renverser l’ordre desσerp)1(miers´el´ements fin
Exemple
5
1
Christophe PAUL
6
4
2
3
Complexite´avance´e-UMIN345Th´eoriede
laNP-Comple´tude
Les algorithmes
Lath´eoriedelacomplexit´e:unpeudhistoir
Untribizarre...[Chva`tal]
Un exemple
Quelles garanties ?
Donne´es:σune permutation de [1,n] Re´sultat permutation: uneσ0telle queσ0(1) = 1 tant queσ(1)6= 1faire Renverser l’ordre desσmerpsrei)1(tsemen´el´ fin
Exemple
5 2
1 4
Christophe PAUL
6 6
4 1
2 5
3 3
Complexite´avance´e-UMIN345The´oriede
laNP-Compl´etude
Les algorithmes
Lathe´oriedelacomplexit´e:unpeudhistoir
Untribizarre...[Chva`tal]
Un exemple
Quelles garanties ?
Donnees:σune permutation de [1,n] ´ Re´sultat: une permutationσ0telle queσ0(1) = 1 tant queσ(1)6= 1faire Renverser l’ordre desσeemtnsimre´sle(1)pre ´ fin
Exemple
5 2 4
1 4 2
Christophe PAUL
6 6 6
4 1 1
2 5 5
3 3 3
Complexit´eavanc´ee-UMIN345Theoriede ´
laNP-Compl´etude
Les algorithmes
Lath´eoriedelacomplexit´e:unpeudhistoir
Untribizarre...[Chv`atal]
Un exemple
Quelles garanties ?
Donne´es:σune permutation de [1,n] R´esultat: une permutationσ0telle queσ0(1) = 1 tant queσ(1)6= 1faire Renverser l’ordre desσ(1)pree´emtnsimre´sle fin
Exemple
5 2 4 1
1 4 2 6
Christophe PAUL
6 4 6 1 6 1 2 4
2 5 5 5
3 3 3 3
Complexite´avance´e-UMIN345The´oriedelaNP-Comple´tude
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin