Aux nouvelles
Notes du final
Vos notes à ce cours sont disponibles sous forme brute sur la page Studium. Comme je n'arrive pas à y importer vos notes lettrées, je vous ai envoyé à 22h30 un code secret qui vous permet d'identifier toutes vos notes (normalisées tel qu'indiqué dans le plan de cours: 15 points pour les exercices notés, 15 points pour chaque devoir, 25 points pour l'intra et 30 points pour le final) dans la page suivante. Prenez note qu'une permanence vous est donnée vendredi 9 janvier de 13h30 à 15h00 afin que vous puissiez passer voir votre examen final. Manifestez tout problème rencontré dans vos notes rapidement (tout ce qui concerne les exercices notés et les devoirs doit être envoyé aux démonstrateurs). À celles et ceux que je ne reverrai pas, bonne continuation et à tous, une bonne année 2015.
Devoir 2
Vous êtes plusieurs à me demander une extension pour le devoir 2, aussi la date limite à été reportée au 18 décembre (après, il sera difficile de corriger dans les temps). Bon temps des fêtes.
À propos du final
Rappel: examen final jeudi 11 décembre de 15h30 à 18h29. Vous avez été informé par courriel: l'examen se déroulera dans deux salles: G-715 (section A) et G-615 (section B) du pav. Roger Gaudry.
Vous avez le droit à 2 feuilles (US letter) de notes (recto-verso). Tout autre document est interdit. L'usage de votre ordinateur (ou téléphone intelligent) ne sera pas permi, pas plus que l'usage d'internet. La matière à l'examen porte sur tout ce que vous avez vu en cours à l'exclusion de l'introduction à la programmation fonctionnelle.
Examens passés
Les sujets des examens finaux des sessions automne 2012 et 2103 sont disponibles (voir le cours de la semaine du 1 au 5 décembre). Des exercices de ces examens seront traités en démonstration.
Exercice noté 7
Le sujet est disponible (suivre le lien travaux) et est à remettre via studium d'ici dimanche 30.
Devoir 2
Le sujet du devoir 2 est disponible (suivre le lien travaux) et est à remettre via studium le 15 décembre 2014. Le sujet sera présenté lors de la prochaine démonstration.
Exercice noté 6
Le sujet est disponible (suivre le lien travaux) et est à remettre via studium d'ici dimanche 23.
Exercice noté 5
Le sujet est disponible (suivre le lien travaux) et est à remettre via studium d'ici vendredi 14.
Interpréteur ligne de commande
L'interpréteur ligne de commande js
de SpiderMonkey a été
installé par l'équipe de support sur les machines d'enseignement. Il
vous est possible de l'invoquer en tapant js24
(ex: js24 algo-tab.js
si vous vous trouvez dans le
répertoire où se trouve algo-tab.js
). Notez que
l'interpréteur js
continue à exister, mais que les codes
que nou voyons en cours ne sont pas compatibles avec cet interpréteur.
Exercice noté 4
Le sujet est disponible sur Studium, la remise est prévue pour vendredi 7 novembre.
Changement de prof
Je donne le cours à partir de la semaine du 27 octobre 2014.
Attention: un changement de prof vient avec
des changements d'habitudes. Mes informations sont dans le lien
contacts
. N'hésitez pas à passer me voir ou à me
contacter
par email.
Exercice noté #4
Vous devez implémenter une variante du tri à bulle vu en cours où l'on
s'interesse à trier des valeurs entières en ordre décroissant et en
place, c'est-à-dire en modifiant directement le tableau passé en
argument. Le tri à bulle classique (celui vu en cours) compare en
boucle deux valeurs successives du tableau et les échange si elles ne
sont pas dans l'ordre désiré. Cela implique que de nombreux échanges
sont effectués afin de déplacer certaines valeurs à leur place. La
variante que vous devez écrire effectue plusieurs passages de
l'algorithme de tri à bulle, où chaque passage compare les valeurs du
tableau distante d'une certaine valeur n
appelé le
régime. L'idée est de commencer par un régime élevé (par exemple 11)
afin de comparer des valeurs éloignées (indice 0, 11, 22, etc.) dans
le tableau, puis de baisser progressivement le régime, pour terminer
avec un régime 1
qui correspond à l'algorithme de tri à
bulle classique (où les valeurs sucessives sont comparées).
Vous devez écrire une fonction bubbleShell
qui admet
dans cet ordre deux arguments qui sont le tableau à trier et un
tableau de régimes, c'est-à-dire, un tableau de valeurs entières
strictement décroissantes et terminant par
l'entier 1
. Votre fonction doit retourner un tableau qui
contient le nombre d'échanges effectués à chaque régime: la ieme
valeur de ce tableau correspond donc au nombre d'échanges effectués
par votre algorithme pour la ieme valeur dans le tableau de régime.
Voici deux exemples d'appels de votre fonction, ainsi que le détail des différentes étapes de l'algorithme. Dans le premier appel, les valeurs distantes de 5 commencent par être comparées et 53 échanges sont effectués. Le régime 3 est ensuite considéré et 15 échanges sont effectués; enfin le régime 1 est effectué (un tri à bulle classique), ce qui requiert 17 échanges. Un total de 85 échanges ont donc été effectués alors que le tri à bulle classique requiert 303 échanges, tel que mesuré par le second appel.
print(bubbleShell([1,3,2,5,4,6,7,8,10,41,43,49,22,13,24,40,20,9,9,10,1,13,45,25,43,12,48,47,25,7], [5,3,1])); 53,15,17 regime 5: 43,49,47,25,43,40,48,45,25,41,12,20,22,13,24,6,13,9,10,10,1,7,8,9,7,1,3,2,5,4 regime 3: 48,49,47,43,45,40,41,43,25,25,13,24,22,13,20,10,12,9,7,10,9,7,8,4,6,5,3,2,1,1 regime 1: 49,48,47,45,43,43,41,40,25,25,24,22,20,13,13,12,10,10,9,9,8,7,7,6,5,4,3,2,1,1
print(bubbleShell([1,3,2,5,4,6,7,8,10,41,43,49,22,13,24,40,20,9,9,10,1,13,45,25,43,12,48,47,25,7], [1])); 303 regime 1: 49,48,47,45,43,43,41,40,25,25,24,22,20,13,13,12,10,10,9,9,8,7,7,6,5,4,3,2,1,1
Vous devez également écrire une fonction best
qui prend
en argument un tableau ainsi qu'un tableau de tableaux de régimes et
qui retourne le tableau de régimes le meilleur, c'est-à-dire celui
entraînant le moins d'échanges pour le tableau donné en
argument. Voici un exemple non normatif
(vous pouvez afficher les choses différemment, voire ne rien afficher)
d'appel où le meilleur régime est [11,9,7,3,1]
var regimes = [[1],[5,4,3,2,1],[7,3,1],[11,9,7,3,1]]; var t = [2,4,5,7,8,2,5,8,9,12,13,2,4,56,12,5,7,23,12,24,34,56,3,6,1]; print(best(t,regimes)); 11,9,7,3,1 tri selon [ 1 ] en 184 echanges tri selon [ 5,4,3,2,1 ] en 48 echanges tri selon [ 7,3,1 ] en 63 echanges tri selon [ 11,9,7,3,1 ] en 35 echanges
Notation: Cet exercice est noté sur 6 points. Le nom du
programme à remettre est bubbleshell.js
et la remise doit
se faire par studium.