Quelques raccourcis :

420KH2 – Systèmes temps réel (STR)

Ceci est un petit site de support pour le cours 420-KH2-LG – Systèmes temps réel. Notez que plusieurs liens divers sont mis à votre disposition; parmi ceux-ci, soyez particulièrement attentives et attentifs à ceux portant :

Documents sous forme électronique

Cliquez sur cette cible pour le plan de cours, sous forme électronique

Détail des séances en classe

Index des séances théoriques
T00 T01 T02 T03 T04 T05 T06 T07 T08 T09 T10 T11 T12 T13 T14
Date Séance Contenu

23 janvier

L00

Au menu :

À titre de petit bonbon, s'ajoutera un mot sur les sympathiques et Ô combien expressives expressions λ.

Les cours T00 et L00 se déborderont un peu l'un sur l'autre, question de nous permettre de démarrer la session...

25 janvier

T00

Pour vous pratiquer, prenez le code suivant :

#include <iostream>
#include <algorithm>
#include <string>
#include <locale>
using namespace std;
void rendre_majuscule(string &s, const locale &loc) {
   for(string::size_type i = 0; i < s.size(); ++i)
      s[i] = toupper(s[i], loc);
}
int main() {
   enum { NMOTS = 10 };
   string mots[NMOTS];
   for (int i = 0; i < NMOTS; ++i)
      cin >> mots[i];
   const auto &loc = locale{""}; // la culture sur cet ordinateur
   for(int i = 0; i < NMOTS; ++i)
      rendre_majuscule(mots[i], loc);
   for(int i = 0; i < NMOTS; ++i)
      cout << mots[i] << endl;
}

Et modifiez-le pour qu'il :

  • Utilise un std::vector<std::string> plutôt qu'un tableau de std::string
  • Lise autant de mots que l'usager ait choisi d'en entrer. Dans vos tests, vous pourrez provoquer une erreur de lecture à la console en appuyant CTRL+Z quand vous aurez décidé que vous en avez assez. Un mot est ici une séquence de caractères délimitée à la fin par au moins un « blanc » (espace, tabulation, saut de ligne, etc.)
  • Transforme chacun des mots en son équivalent en majuscules, cette fois à l'aide d'un std::for_each() et d'un foncteur. Le constructeur du foncteur vous permettra de capturer le std::locale utilisé comme second paramètre à std::toupper()
  • Affichera chacun des mots sur une ligne distincte à l'aide de std::for_each() et d'un foncteur Afficher, inspiré de celui proposé en classe à la séance T00

Si le coeur vous en dit, essayez de faire la même chose avec des expressions λ, mais conservez une copie de sauvegarde de la version utilisant des foncteurs pour fins de discussion en classe.

Solution avec foncteurs :

#include <iostream>
#include <algorithm>
#include <string>
#include <locale>
#include <vector>
void rendre_majuscule(std::string &s, const std::locale &loc)
{
   using std::string;
   using std::toupper;
   for(string::size_type i = 0; i < s.size(); ++i)
      s[i] = toupper(s[i], loc);
}
class Afficher
{
   std::ostream &os_;
public:
   Afficher(std::ostream &os)
      : os_(os)
   {
   }
   void operator()(const std::string &s)
      { os_ << s << std::endl; }
};
class RendreMajuscule
{
   const std::locale &loc_;
public:
   RendreMajuscule(const std::locale &loc)
      : loc_(loc)
   {
   }
   void operator()(std::string &s)
      { rendre_majuscule(s, loc_); }
};
int main()
{
   using std::cin;
   using std::cout;
   using std::endl;
   using std::locale;
   using std::string;
   using std::vector;
   using std::for_each;
   vector<string> mots;
   for (string mot; cin >> mot; mots.push_back(mot))
      ;
   const locale &loc = locale(""); // la culture sur cet ordinateur
   for_each(mots.begin(), mots.end(), RendreMajuscule(loc));
   for_each(mots.begin(), mots.end(), Afficher(cout));
}

Une solution avec expressions λ serait la suivante. Notez qu'il est possible que Visual Studio 2010 plante à la compilation avec ce code, car il a parfois de la difficulté à gérer les λ; cependant, le code est correct – testez-le avec un compilateur plus récent, comme par exemple celui livré avec Visual Studio 2012 ou une version récente de g++ ou de Clang :

#include <iostream>
#include <algorithm>
#include <string>
#include <locale>
#include <vector>
void rendre_majuscule(std::string &s, const std::locale &loc)
{
   using std::string;
   using std::toupper;
   for(string::size_type i = 0; i < s.size(); ++i)
      s[i] = toupper(s[i], loc);
}
int main()
{
   using std::cin;
   using std::cout;
   using std::endl;
   using std::locale;
   using std::string;
   using std::vector;
   using std::for_each;
   vector<string> mots;
   for (string mot; cin >> mot; mots.push_back(mot))
      ;
   const locale &loc = locale(""); // la culture sur cet ordinateur
   for_each(mots.begin(), mots.end(), [&](string &s) {
      rendre_majuscule(s, loc);
   });
   for_each(mots.begin(), mots.end(), [&](const string &s) {
      cout << s << endl;
   });
}

Autre exercice pertinent : modifiez la fonction rendre_majuscule() pour qu'elle opère sur des itérateurs plutôt que sur des indices.

Solution possible :

void rendre_majuscule(std::string &s, const std::locale &loc) {
   using namespace std;
   for(string::iterator i = s.begin(); i != s.end(); ++i)
      *i = toupper(*i, loc);
}

Autre solution possible (vive auto) :

void rendre_majuscule(std::string &s, const std::locale &loc) {
   using namespace std;
   for(auto i = s.begin(); i != s.end(); ++i)
      *i = toupper(*i, loc);
}

Autre solution possible, si vous incluez <iterator> :

void rendre_majuscule(std::string &s, const std::locale &loc) {
   using namespace std;
   for(auto i = begin(s); i != end(s); ++i)
      *i = toupper(*i, loc);
}

Pour pratiquer un peu, vous êtes invité(e)s à faire les exercices suivants. N'utilisez pas les algorithmes de l'en-tête <algorithm> pour arriver à vos fins (nous voulons nous pratiquer, après tout) :

  • Écrivez un algorithme nommé inverser_elements() qui prend en paramètre une séquence à demi ouverte et inverse l'ordre de ses éléments. Montrez par un programme de test que votre fonction opère correctement sur un tableau de std::string, un vecteur de int et une liste de double, et ce, que le nombre d'éléments soit nul, un, pair ou impair
  • Écrivez un algorithme nommé compter_occurrences() qui prend en paramètre une séquence à demi ouverte et une instance d'un type T donné, qu'on peut comparer à l'aide de == avec les éléments de la séquence, et qui retourne le nombre d'occurrences de cette instance dans la séquence. Montrez par un programme de test que votre fonction opère correctement sur un tableau de std::string, un vecteur de int et une liste de char, et ce, que le nombre d'éléments soit nul, un ou plus, que la valeur recherchée soit dans la séquence ou non. Notez que je n'ai pas demandé d'utiliser une liste de double dans ce cas-ci... Comprenez-vous pourquoi?
  • Écrivez un algorithme nommé compter_si() qui prend en paramètre une séquence à demi ouverte et un prédicat (un prédicat est une opération booléenne) applicable à chaque élément de la séquence, et qui retourne le nombre d'instances dans la séquence pour lesquelles le prédicat s'avère vrai. Montrez par un programme de test que votre fonction opère correctement sur un tableau de std::string, un vecteur de int et une liste de double, et ce, que le nombre d'éléments soit nul, un ou plus, qu'il y ait ou non des instances pour lesquelles le prédicat est vrai. Écrivez au moins deux prédicats distincts (un foncteur et une fonction)

Par la suite (ne trichez pas!), essayez de voir si ces algorithmes sont codés dans <algorithm> (respectivement sous les noms reverse(), count() et count_if(), tous dans l'espace nommé std), et comparez vos implémentations avec celles que vous y trouverez.

Pour réaliser les exercices proposés ici, il vous faudra utiliser entre autres les types std::vector et std::list, que vous trouverez dans les en-têtes standards <vector> et <list> respectivement :

  • Le type vector représente une sorte de tableau dynamique, très efficace pour accéder à un élément particulier ou pour ajouter ou enlever un élément à la fin, mais moins efficace pour insérer ou retirer des éléments à d'autres positions.
  • Le type list représente une liste doublement chaînée; les opérations sur elle sont en général plus lentes que sur vector, mais les opérations d'insertion et de suppression à un endroit autre qu'à la toute fin y sont beaucoup plus rapides.

Pour en savoir plus sur les conteneurs standards et sur les algorithmes standards, jetez un coup d'oeil à cet article.

30 janvier

L01

 

1er février

T01

 

6 février

L02

 

8 février

T02

 

13 février

L03

 

15 février

T03

 

20 février

L04

 

22 février

T04

 

27 février

L05

 

1er mars

T05

 

6 mars

Journée de mise à niveau (cours suspendus)

8 mars

Journée de mise à niveau (cours suspendus). Bonne Journée internationale des femmes!

13 mars

L06

 

15 mars

T06

 

20 mars

L07

 

22 mars

T07

 

27 mars

T08

Attention : mardi qui est en fait un jeudi à l'horaire. Nous avons donc une séance théorique (deux périodes) plutôt que pratique (trois périodes)

29 mars

Journée pédagogique (cours suspendus)

3 avril

L08

 

5 avril

T09

 

10 avril

L09

 

12 avril

T10

 

17 avril

L10

 

19 avril

T11

 

24 avril

L11

 

26 avril

T12

 

1er mai

L12

 

3 mai

T13

 

8 mai

L13

 

10 mai

Journée d'examen pour les cours de français de la formation générale (cours suspendus)

15 mai

L14

 

17 mai

T14

 

Consignes des travaux pratiques

Les consignes des travaux pratiques sont telles qu'indiqué ci-dessous.

Consignes Document d'accompagnement

TP00

À venir

TP01

À venir

TP02

À venir

Consignes de l'activité synthèse

Les consignes de l'activité synthèse pour la session H2018 seront éventuellement disponibles ici (elles ne sont pas encore écrites!)

Résultats des questions quasi-hebdomadaires

Les moyennes des résultats obtenus aux questions quasi-hebdomadaires pour la session en cours suivent. Notez que l'écart-type par question n'est pas significatif étant donné l'échantillon (petit groupe) et la pondération des questions (sur cinq point, un point de différence représente , ce qui bousille quelque peu cette composante statistique).

 Question   Séance 
Q00
???
Q01
???
Q02
???
Q03
???
Q04
???
Q05
???
Q06
???
Q07
???
Q08
???
Q09
???
:

Résultats des travaux pratiques

Les moyennes des résultats des travaux pratiques pour la session en cours suivent.

TP Remise Poids

TP00 (consignes)

TP01 (consignes)

TP02 (consignes)

A.S.

T14
Cumulatif (sans tenir compte de l'A.S.) :
:

Code de démonstration

Vous trouverez ci-après le code source de divers exemples de vos notes de cours. Il est possible que le code ne soit pas exactement le même que dans les notes de cours puisque j'ai retouché ces dernières récemment (le site Web est un peu en retard côté mises à jour), mais les différences sont cosmétiques.

Sources des exemples du document STR – Volume 01

Cliquez sur cette cible pour obtenir le code de la chaîne pascal simplifiée

Cliquez sur cette cible pour obtenir le code de la chaîne pascal avec itérateurs

Cliquez sur cette cible pour obtenir le code du test 0.0

Cliquez sur cette cible pour obtenir le code du test 0.0b

Cliquez sur cette cible pour obtenir le code du test 0.1

Cliquez sur cette cible pour obtenir le code du test 1.0

Cliquez sur cette cible pour obtenir le code du test 1.1

Cliquez sur cette cible pour obtenir le code du test 1.2

Cliquez sur cette cible pour obtenir le code du test 1.3

Cliquez sur cette cible pour obtenir le code du test 2.0

Cliquez sur cette cible pour obtenir le code du test 2.1

Cliquez sur cette cible pour obtenir le code du test 2.2

Cliquez sur cette cible pour obtenir le code du test 3.0

En lien avec la 1re séance sous QNX

Pour la 1re séance sous QNX, vous trouverez le code source des illustrations à travers les liens suivants :

Pour l'aide en ligne de QNX au sens large, je vous invite à consulter le site http://www.qnx.com/developers/docs/6.3.2/neutrino/lib_ref/about.html qui est, somme toute, assez complet. Vous y trouverez un certain nombre de tutoriels pertinents, entre autres :

En lien avec l'exercice de compression de données

Cliquez sur cette cible pour obtenir le projet bmp00, réalisant une compression RLE sur des bitmaps dans un temps raisonnable. Ce projet n'est pas un STR puisqu'il cherche à réaliser rapidement et correctement une tâche mais n'offre aucune garantie de non-dépassement d'un seuil de temps – il n'y a aucun plafond mesurable dans le temps d'exécution de l'algorithme de compression dans ce programme, donc aucune contrainte de temps dont le respect serait déterministe.

L'idée d'offrir d'abord une version opérationnelle d'un algorithme donné, sans se préoccuper de contraintes TR, est que cette version est en général plus simple que les versions offrant des garanties TR strictes.

Sur le plan pédagogique, cela donne aussi une excuse à votre professeur pour mettre en place des bases conceptuelles clés du code moderne, pour que toutes et tous comprennent ses exemples, sans aller jusqu'à donner un cours général de techniques de programmation contemporaines. J'essaie de mettre en place des bases conceptuelles et techniques communes sans trop me répéter étant donné la nature bigarrée mais techniquement très solide de la clientèle de ce cours.

Cliquez sur cette cible pour obtenir le projet bmp-morcele, réalisant une compression RLE sur des bitmaps dans un temps raisonnable et de manière à ne pas dépasser un certain seuil de tolérance au temps.

Cette version compresse des données RGB brutes selon une approche RLE et peut, contrairement aux deux précédentes, être considérée TR (au sens usuel, pas au sens strict, mais principalement à cause de la plateforme) dans la mesure où le seuil indiquant d'arrêter tiendrait compte du pire cas possible (calculé a priori) pour une séquence de compression RLE donnée. Aller jusque là demanderait toutefois une meilleure connaissance du contexte et obscurcirait quelque peu le propos. Le code du projet est du code de test, montrant qu'il est possible de faire en sorte que l'algorithme de compression s'interrompe « en cours de traitement ».

Quelques suggestions d'exercices pour vous faire la main :

  • Ajoutez un traitement arbitraire (que vous pouvez simuler par une attente active basée sur un délai aléatoire) dans la boucle qui invoque la fonction compressant une séquence selon une approche RLE. Présumez que cette boucle doive itérer fois par seconde, donc que chaque itération de la boucle prenne au pire seconde, et faites en sorte que la compression n'utilise que le temps restant (s'il y en a). Le temps accordé à l'algorithme de compression sera donc un seuil variable plutôt que constant
  • Transformez l'algorithme de compression pour qu'il puisse être interrompu pendant une séquence RLE plutôt qu'entre chaque séquence RLE. Cette version sera globalement plus lente que la version proposée par le professeur mais sera plus près d'une version déterministe, donc moins à risque de déborder des contraintes TR imposées par le contexte. Vous voudrez utiliser un foncteur plutôt qu'une fonction pour réaliser cet exercice
  • L'algorithme qui transforme une séquence de bytes bruts en vecteur de valeurs RGB est lent. Transformez-le de manière à ce qu'il soit interruptible
  • Plus costaud : transformez la fonction qui compresse un bitmap de manière à ce qu'elle soit interruptible. Ceci sera plus facile à réaliser si l'algorithme transformant une séquence de bytes bruts en séquence RGB est lui-même interruptible. Considérez la fonction consommant un bitmap du flux comme était une opération indivisible (ceci vous permettra de vous concentrer sur l'essentiel)
  • Pour que les algorithmes soient plus déterministes, utilisez des tableaux bruts ou des vecteurs préalablement dimensionnés comme conteneurs de destination pour les algorithmes de transformation de séquence de bytes en séquence RGB et de compression RLE. Analysez la solution que vous proposez pour montrer en quoi elle est préférable à la version antérieure et en quoi elle est moins intéressante (évitez les banalités, il y a une réelle réflexion à faire ici)

Cliquez sur cette cible pour la description du format bitmap.

Cliquez sur cette cible pour la description de la compression RLE. Pour un peu de pédagogie sur RLE, voir http://hbfs.wordpress.com/2009/04/14/ad-hoc-compression-methods-rle/


Valid XHTML 1.0 Transitional

CSS Valide !