DS dInformatique n 1 — 16 novembre 2013
16 nov. 2013 2) Ecrire le code Python correspondant à cet algorithme. Page 2. 2. PCSI — Devoir surveillé d'Informatique n01 — 16 novembre 2013.
PCSI - Lycée Henri Wallon Devoir Surveillé dInformatique Pour
PCSI - Lycée Henri Wallon. Devoir Surveillé d'Informatique Pour Tous no 3. Durée : 1 heure 30. Ce sujet comporte 4 pages d'énoncé.
DS 1 dinformatique Lisez attentivement les consignes ci-dessous
PCSI 3. Lycée Sainte-Geneviève. 2020/2021. Samedi 11 janvier 2020. DS 1 d'informatique. 2 heures. Lisez attentivement les consignes ci-dessous.
DS n o III Informatique
DS n o III Informatique lycée A. Brizeux. M.Roger 2019-2020. Durée : 1h. Les calculatrices sont interdites. Exercice 1.
Sujets et corrigés des DS de mathématiques et dinformatique
107. BCPST1A lycée Hoche 2014-2015. 2 sur 109. Sébastien Godillon. Page 3. DS n o. 1 de mathématiques durée : 3 heures. Exercice 1. Dans un haras un test
SII PSI cahier de texte informatique
Programme d'informatique PCSI PSI · nouveaux programme à partir de septembre 2021 en PCSI septembre 2022 en PSI DS informatique : le devoir porte.
Lycée Champollion PCSI-1 2017-2018 Planning prévisionnel des
Les DS de chimie du semestre 1 sont communs avec les PCSI-1 et 3. Les DS d'informatique de français et d'allemand LV1 seront programmés "au fil de ...
Devoir Surveillé 1 dInformatique
Devoir Surveillé 1 d'Informatique. MPSI 1 & 2 du Lycée International de Valbonne. Informatique. • Durée : 4 heures. • L'usage de tout dispositif
PCSI Chapitre 10 Informatique 2016-2017 1/6
CHAPITRE 10 : RÉSOLUTION NUMÉRIQUE D'ÉQUATIONS SUR LES RÉELS. Dans de nombreuses situations en calcul scientifique la détermination d'une solution
TP dinformatique évalué Consignes
PCSI 3. Lycée Sainte-Geneviève. 2020/2021. Vendredi 27 novembre 2020. TP d'informatique évalué. 1 heure. Consignes. • La clarté du code sera prise en compte
Informatique PCSI - AlloSchool
16 déc 2017 · Informatique PCSI Cours Exercices corrigés Examens - AlloSchool Votre école sur internet
[PDF] DS n o III Informatique - CPGE Brizeux
DS n o III Informatique lycée A Brizeux M Roger 2019-2020 Durée : 1h Les calculatrices sont interdites Exercice 1
Lycée Henri Poincaré PCSI 1 et 2 année 2022-2023
Cours d'informatique pré-réforme pour vos révisions · I_01 pdf : fonctions · I_02 pdf : listes et str · I_03 pdf : for et while
[PDF] Cours dInformatique pour Tous
Ces notes de cours sont issues du cours d'informatique commune (IPT) subi par les élèves du lycée Masséna des classes de première année MPSI (831)
[PDF] PCSI 2018-2019 Informatique - DS n°7 1h Téléphones et
PCSI 2018-2019 Informatique - DS n°7 1h Téléphones et documents interdits sur la table Les exercices sont indépendants les uns des autres Consignes
[PDF] Devoir dinformatique no 1 (2 heures)
Lycée Marceau MPSI 2014/2015 Le lundi 17 novembre 2014 Devoir d'informatique no 1 (2 heures) Ce devoir est constitué de plusieurs petits exercices
[PDF] Version numérique pour la préparation des cours dinformatique en
Version numérique pour la préparation des cours d'informatique en CPGE à partir du manuel : “Cette version électronique du manuel est diffusée pour aider à la
[PDF] TP dinformatique PCSI - Free
TP d'informatique PCSI http://alexandre boisseau free fr/Prive/WWW/InfoPCSI/tp1 pdf PCSI 1 et enregistrer la page dans les signets ;
[PDF] Devoir Surveillé 1 dInformatique
MPSI 1 2 du Lycée International de Valbonne Informatique • Durée : 4 heures • L'usage de tout dispositif électronique (calculatrice téléphone portable
Documents à télécharger - Informatique PCSI - Cahier de Prépa
Informatique PCSI (2 documents) 1er avril (2 documents) 25 mars ( pdf 08/11/2020 61 ko) interro 1 20 21 ( pdf 12/11/2020 54 ko) interro 2 20 21 pcsi2
?La clarté et la lisibilité de la copie sont des qualités essentielles. Toute copie sale, peu claire ou à
la rédaction approximative serapénalisée. Numérotez vos feuilles doubles et indiquez votre nom
sur chacune d"entre elles.Première feuille Autres feuilles La première page de la copiedoit laisser un cadre de 5cm. Votre copie doit comporter une marge d"au moins 3cm. Toute copie ne respectant pas ces spécifications perdra des points.?Un problème, ou un exercice à plusieurs questions, n"est pas un grand chelem, et il est approprié
en l"absence de réponse à une question de supposer les résultats et de passer à la suivante.Ne
vous arrêtez pas à la première question dont vous n"avez pas la réponse !Aucune copie ne sera pénalisée pour avoir tenté un début de réponse.?S"il vous semble qu"une erreur s"est glissée dans un énoncé, justifiez-vous et poursuivez l"exercice
mutatis mutandis, c"est-à-direen changeant ce qui doit être changé.Les trois parties sontindépendantes.
Les trois exercices visent à proposer des algorithmes efficaces pour effectuer des tâches élémentaires qui sont
des briques de bases pour résoudre de nombreux problèmes. Plus précisément, nous nous attachons à extraire les
éléments maximum/minimum d"un tableau (Problème 1), la plus longue chaîne d"un tableau (Problème 2) et à trier
les éléments d"un tableau (Problème 3). Chacune des parties tire parti du paradigme "diviser pour régner".
Dans chacun des exercices, nous utilisons les fonctions CAML suivantes: min!int!int!intetmax!int!int!intAlgorithme 1.
let min a b = ifa < bthena elseb;;Algorithme 2. let max a b = ifa > bthena elseb;;11 Recherche d"extrema dans un tableau
Dans ce problème, nous considérons des tableaux dont les éléments sont des entiers naturels. C"est-à-dire, pour
tout tableauTde longueurn2N,T?(i)2Npour tout?6i < n.Le but de l"exercice est de proposer un algorithme efficace qui, étant donné un tableauT, renvoie le maximum
et le miminum contenus dans le tableau. Plus précisément, étant donné un tableauTde longueurn, l"algorithme
doit retourner la paire d"entiers(minT?MaxT) = (????6iProuver que le nombre de comparaisons réalisées par l"algorithmeextr(T)proposé à la question
précédente, est équivalent à?n, avecnla longueur deT.Question 2Question 2 SoientTun tableau de longueurn2N,?6a6b < n. Considérons l"algorithme suivant:Algorithme 3.
Let rec extr2 T a b=
ifa==bthen(T?(a)?T?(a)) else ifa==b-?then ifT?(a)< T?(b)then(T?(a)?T?(b))else(T?(b)?T?(a)) else letm= (a+b)=?in let(x?y) =extr2 T a m in let(u?v) =extr2 T m+1 b in(???x u? ???b v);;Que calcule l"algorithme précédent ? Prouvez qu"il termine et qu"il est correct
(on supposera que?6a6b < n).Question 3Question 3 Soitx=b-aet posonsuxle nombre de comparaisons réalisées lors de l"appel deextr2 T a b. Exprimer la relation de récurrence satisfaite par(ux)x>?.Question 4Question 4 Donner explicitement l"expression de(ux)x>?lorsquex=?p. On poseravp=u?ppour toutp>?et on étudiera la suite(vp+?)p>?.Question 5Question 5Donner un algorithme, plus efficace de celui de la question 1, qui calcule(minT?maxT).Question 6Question 6
2 Plus grande sous-séquence d"un tableau
Le but de ce problème est d"étudier différents algorithmes pour calculer le maximum des sommes d"éléments con-
sécutifs d"un tableau donné d"entiers relatifs. Plus précisément, soitTun tableau denéléments à valeur dansZ. 2Pour tout?6a6b < n, on notet(a?b) =bX
k=aT?(k). On cherche la plus grande somme de ce type. C"est-à-dire, on cherche à calculerS(T) =????6a6bAlgorithme 4.
LetSomMax?T=
letn=vect_length T in letsMax=refT?(?)in fora=?ton-?do forb=aton-?do letm=refT?(a)in fork=a+?tobdom:=!m+T?(k)done; sMax:=???m !sMax done; done;!sumMax;;Calculer le nombre d"itérations de l"opération "m:=!m+T?(k)". En déduire l"ordre de grandeur
de la complexité de l"algorithmeSomMax?en fonction de la longueurnde son entrée.Question 7Question 7
2.2 Première amélioration
On se propose de supprimer l"une des boucles "for" imbriquées de la fonctionSomMax?. Pour cela, on peut mettre
la variablesMaxà jour au fur et à mesure du calcul dest(a?b) =bXk=aT?(k)pourafixé etbvariant deaàn-?.En suivant la suggestion ci-dessus, écrire en CAML la fonctionSomMax?qui prend en entrée
un tableauTet renvoieS(T). Prouver que le nombre d"additions réalisées parSomMax?est (n?).Question 8Question 82.3 Version Récursive
SoitTun tableau de longueurnet soitk6n. On noteS(T?k) =????6a6bS(T). Calculer l"ordre de grandeur du nombre d"additions réalisées parSomMax?.Question 10Question 10
32.4 Diviser pour régner
SoitTun tableau de longueurnet soit?6a6b < n.
Posonstaux(a?b) =???a6x6y6bt(x?y). C"est-à-dire,taux(a?b)est le maximum des sommes d"éléments
consécutifs compris entre les indicesaetbdeT. Soita6m6b. On pose finalementtjoin(a?m?b) =???a6x6m6y6bt(x?y). C"est-à-dire,taux(a?b)est lemaximum des sommes d"éléments consécutifs compris entre les indicesaetbdeTet contenant l"élément d"indice
m.Soita6m < b. Exprimertaux(a?b)en fonction detaux(a?m),taux(m+??b)et t join(a?m?b).Question 11Question 11 Écrire en CAML une fonctionJunction(T?a?m?b)qui prend en entrée un tableauTde longueur net trois entiers?6a6m6b < net calculetjoin(a?m?b)avec un nombre d"additions de l"ordre deb-a.Question 12Question 12 Dans la suite on pourra admettre le résultat de la question précédente. Écrire en CAML une fonction récursiveSumAux(T?a?b)qui prend en entrée un tableauTde longueurnet deux entiers?6a6b < net calculetaux(a?b).Question 13Question 13 En déduire en CAML une fonction récursiveSomMax?qui prend en entrée un tableauTet calculeS(T).Question 14Question 14 Soitunle nombre d"additions réalisées par la fonctionSomMax?appliquée à un tableau delongueurn. Exprimer la relation de récurrence satisfaite par(un)n>?. Conclusion ?Question 15Question 15
2.5 Programmation dynamique
Dans cette section, nous étudions un algorithme encore plus efficace. SoitTun tableau de longueurnet soitk6n. Rappelons queS(T?k) =????6a6b3 Tri rapide et complexité en moyenne
Rappeler brievement (pas plus de 5 lignes) le principe de l"algorithme de tri-fusion et donner sa complexité (sans preuve).Question 18Question 18 4Dans ce problème, nous nous intéressons à un autre algorithme de tri, appeléTri rapide(quick sorten anglais).
On rappelle que, étant donné un tableau d"entiers, le but est de renvoyer un tableau avec les mêmes éléments,
ordonnés dans l"ordre croissant.Le principe du quick sort est de partitionner le tableau à trier (s"il a au moins deux éléments) en trois sous-
tableaux, le premier comprenant tous les éléments inférieurs ou égaux à un élément (l"élément pivot), le deuxième
ne contenant qu"un seul élément (l"élément pivot) et le troisième contenant tous les éléments supérieurs ou égaux à
l"élément pivot. Puis on réappliquerécursivementle quick sort sur les premier et troisième sous-tableau (l"élément
pivot, lui, est à sa place définitive).On considère tout d"abord la fonctionpivot, décrite ci-dessous, qui prend en entrée un tableauTde longueurn
et deux entiers?6a6b < n.Algorithme 5.
let recpivotT a b= ifa==bthena else letaux=T?(a+?)in ifT?(a)> auxthenT?(a+?) T?(a);T?(a) aux;pivotT(a+?)b Quelle est la valeur deTaprès l"exécution de cette fonction ?Question 19Question 19 Quel est le nombre de comparaisons d"entiers réalisées parpivotT a b ?Question 20Question 20Algorithme 6.
let recquickSortT= letn=vect_lengthTin let recquickAuxT a b= ifa==bthenT else leti=pivotT a b inquickAux(quickAuxT a i) i+1 b;; inquickAuxT 0(n-?);;SoitT= [???????n].Quel est le nombre de comparaisons d"entiers réalisées parquickSortT ? Justifiez.Question 21Question 21
D"après la question précédente, il existe des "mauvais" tableaux pour lesquels l"algorithme quickSort se comporte
"mal": sa complexité est quadratique en la longueur du tableau.Dans le pire cas, l"algorithme de tri-fusion est donc meilleur que quickSort. Cependant, nous allons voir que
quickSort est efficace "en moyenne".Dans la suite on considère des tableaux qui correspondent auxpermutationsde[j??nj]. C"est-à-dire, un tableau
de longueurncontient des éléments, deux-à-deux distincts, dans[j??nj]. Soitnl"ensemble de ces tableaux.Calculer le cardinal den.Question 22Question 22
SoitT2nun tableau. On noteC(T)le nombre de comparaisons d"entiers réalisées parquickSortT.Jusqu"à présent, on s"intéressait à la complexité en pire cas, c"est-à-dire au???T2nC(T)(le tableau qui nécessite
le plus de comparaisons). 5 Le but de cet exercice est de calculer la complexité en moyenne définie parCn=?jnjXT2nC(T).
Pour cela, pour tout?6k6n, soitknnl"ensemble des tableaux dont le premier élément est l"entierk.Prouver quejknj=jnj=n.Question 23Question 23
Finalement, soitCn(k) =?jknjX
T2knC(T)la complexité en moyenne dequickSortdans l"ensemblekn.Prouver queCn=?n X ?6k6nC n(k).Question 24Question 24 Prouver queCn(k) =n-?+Cn(k-?) +Cn(n-k).Question 25Question 25En déduire queCn=n-?+?n
X ?6kCnn+?=?Hn+?+O(?).
indice: calculer d"abord(n+?)Cn+?-nCnpour prouver queCn+?n+?=Cnn+?+?n+?-?n+?Question 27Question 27Conclusion ?Question 28Question 28
6quotesdbs_dbs35.pdfusesText_40[PDF] exercices corrigés fonctions usuelles mpsi
[PDF] cours mpsi
[PDF] alain troesch
[PDF] ds physique mpsi louis le grand
[PDF] principe de conservation de l'énergie première s exercices
[PDF] controle energie mecanique 1ere s
[PDF] diagramme simplifié des niveaux d'énergie de l'atome de sodium
[PDF] le polonium 210 corrigé
[PDF] devoir seconde physique
[PDF] fonctions second degré controle
[PDF] exercice extraction liquide liquide
[PDF] controle physique seconde extraction
[PDF] exercice miscibilité 5eme
[PDF] exercice sur l'extraction par solvant
