Introducion

1. Information du cours
   • Techniques abstraites
   • Apprécier la puissance de récurrence
   • Apprendre à analyser des algorithmes
2. Logistique
   • Portail du cours
   • Plateforme Piazza
   • Distribution Note Finale
   • Salle d’entrainement
3. C++
   • Définition
   • Pourquoi C++
   • Compagnies C++
   • Premier programme
   • Deuxième programme
   • Importance des structures de données

Objectifs

Bienvenue dans le cours Problem solving with C++. Comme le nom l’indique l’objectif de cours est:

Aquérir des techniques de base pour la modélisation et la résolution de problèmes complexes avec un ordinateur.

Cependant la notion de problème complèxe evolue avec le temps. Voici une liste de problèmes:

Exploitation d'imitation de les self driving cars. J.Zhou and al 2021

Calculer le chemin le plus court entre deux points étant données informations instantanés.

Le problème de reconnaissance de discours.

Objectifs du cours

Ce cours ne vas pas vous permettre de coder ces projets. Cepenant c’est une étape essentielle pour y arriver.

On peut résumer les trois piliers de cours comme:

1. Explorer des techniques abstraites pour la résolution de problèmes.
2. Maitriser puis apprécier la puissance de la récurrence.
3. Apprendre à analyser et comparer le compléxité des solutions.

Techniques abstraites

1. Comment calculer distance moyenne entre deux utilisateurs facebook.

Quelle est la distance moyenne entre deux utilisateurs aléatoires en facebook. Les techniques de théorie de graphe sont souvent utilisés pour répondre a ce type de question. Ainsi on peut reformuler la question en un question classique de théorie de graphe.

1. Comment peut on envoyer un email d’un ville à une autre.

Etant donné qu'on veut envoyer un mail d'une certaine ville à une autre et une liste de ordinanteurs connectées. Quel est le chemin effectif pour délivrer ce mail. La aussi, la modélisation de ce problème en forme de graphe réduit le problème la notion de plus court chemin.

Apprécier la puissance de récurrence

La récurrence est un paradigme très puissant qui une fois matrisé vous permet de résoudre un large panorama de problèmes complèxes.

Si vous voulez comprendre la récurrence, vous devez comprendre la récurence!!!

Image d'un arbre fractal, Si vous zoumer sur une partie de cette arbre, vous allez trouver la même image

Apprendre à analyser des algorithmes

L’un des objectifs importants de ce cours est de pouvoir analyser et comparer la complexité des algorithmes proposés. Par exemple visiter Sorting algorithms playground pour apprécier la différence entre ces algorithmes de tri.

Playground pour explorer la différence entre les algorithmes de tri.</b>

Logistique du cours

Portail du cours

Le portail principal du cours est:

Il contient:

1. Planning des séances.
2. Contenu à préparer avant le cours.
3. Description des Travaux pratiques.
4. Collections de ressources pour le cours.

Plateforme Piazza

Nous utilisons Piazza pour le suivi des questions réponses. Voici le lien du cours

Vous devez vous inscrire en utilisant vos mails académiques (portant l’extension euromed.org)

Plaforme Piazza pour poser des questions. Votre ressource principale pour chercher des réponses.

Cette plateforme serve comme portail de discussion entre vous et aussi pour poser des questions au professeur.

1. Poser des questions sur chaque notion qui vous bloque.
2. Vous avez le choix de déterminer qui peut voir vos questions:
   • (anonyme) avec le prof ( pas recommandé)
   • (votre nome) mais juste avec le prof (En cas de problème).
   • (Anonyme/non) mais pour toute la classe (Recommandé)
3. Vous êtes aussi encouragés a répondre aux questions de vos amis dans l’onglet réservé aux étudiants.

Distribution Note Finale

le calcul est à priori comme suit

Distribution de la note finale du module.

Salle d’entrainement

je vous recommande le Code Step by Step pour vous entrainner aux notions du cours. D’ailleurs, on va souvement vous reférer à quelques questions du ce site.

Votre salle d'enstrainement où vous pouvez vous exercez sur différentes notions du cours.

Langage C++

Définition

Le language C++ est un language de programmation compilé permettant la programmation avec plusieurs paradigmes (fonctionnels, OOP ou générique). Ses perfermances de rapidité et compatibilité avec C en fontn l’un des languages les plus utilisés des des applications critiques (gourmandes en calcul) comme les moteurs de jeu ou les framework deep learning.

Worldwide language popolarity comparison: Mar 2021 compared to a year ago

Voici une liste de cours qui utilisent C++ comme leurs langage de base.

1. Physics Based simulation Biological Structure.
2. Introduction to Cuda (Deep learning).
3. Introduction to Computer Networks
4. Convolutional Neural Networks
5. Parallel computing in Healthcare.
6. Medical Robotics.
7. Music computing design.
8. Signal processing models.

Pourquoi C++

Etant donné l’explosion et l’efficacité des réseaux de neurones. Tous les framework en base sont implémentés en C++ pour leur efficacité. Puis offrent des interfaces en des langages simples comme Python pour leur exploitation.

/*
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
    http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
==============================================================================*/

#include <vector>

#include "tensorflow/cc/framework/grad_op_registry.h"
#include "tensorflow/cc/framework/gradients.h"
#include "tensorflow/cc/ops/array_ops_internal.h"
#include "tensorflow/cc/ops/standard_ops.h"
#include "tensorflow/core/lib/strings/strcat.h"

namespace tensorflow {

REGISTER_NO_GRADIENT_OP("ShapeN");
REGISTER_NO_GRADIENT_OP("Rank");
REGISTER_NO_GRADIENT_OP("Size");

Status UnpackGrad(const Scope& scope, const Operation& op,
                  const std::vector<Output>& grad_inputs,
                  std::vector<Output>* grad_outputs) {
  int axis;
  TF_RETURN_IF_ERROR(GetNodeAttr(op.node()->attrs(), "axis", &axis));
  grad_outputs->push_back(Stack(scope, grad_inputs, Stack::Axis(axis)));
  return scope.status();
}

Compagnies C++

Les compagnies qui utilisent C++

Ensemble des compagnies qui utilisent C++ dans le développement de leur code.

Quelques logiciels écrits en C++

Quelque logiciels écrit en C++

Projets écrit en C++

Pourqu’oi doit ont choisir C++

Premier programme

Pour avoir une iddée sur la syntaxe de cpp qui resssemble aimplement à celle de Java, On se propose de résoudre le problème d’affichier les trois premiers nombres parfaits.

Un nombre est parfait s’il est égal à la somme de tous ces diviseurs sauf lui même.

Par exemple le nombre \(6\) est parfait car

#include <iostream>  

//utiliser l'espace des nom std
using namespace std;

//Fonction pour vérifier si n est pafait
bool is_perfect( int n)
{
    auto S = 0;

    for(auto div=1; div <= n/2; div++)
        if ( n % div == 0)
            S += div;

    return S == n;
}

//fonction principale
int main(int argc, char *argv[])
{

    int count = 0;  //count des nombres parfaits

    int candidate = 1; //nombre à vérifier

    while( count < 3)
         {
             if(is_perfect( candidate ))
                {
                   cout<<candidate<<" ";                
                     count++;
                }
             candidate++;
         }
    //Retour à la ligne
    cout<<endl; 
    
    return 0;
}

Deuxième programme

/*tracer une distribution normale
 */

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
#include <cmath>
 
int main()
{
    // Seed with a real random value, if available
    std::random_device r;
 
    // Choose a random mean between 1 and 6
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Randomly-chosen mean: " << mean << '\n';
 
    // Generate a normal distribution around that mean
    std::seed_seq seed2{r(), r(), r(), r(), r(), r(), r(), r()}; 
    std::mt19937 e2(seed2);
    std::normal_distribution<> normal_dist(mean, 2);
 
    std::map<int, int> hist;
    for (int n = 0; n < 10000; ++n) {
        ++hist[std::round(normal_dist(e2))];
    }
    std::cout << "Normal distribution around " << mean << ":\n";
    for (auto p : hist) {
        std::cout << std::fixed << std::setprecision(1) << std::setw(2)
                  << p.first << ' ' << std::string(p.second/200, '*') << '\n';
    }
}

Importance des structures de données

La maitrise des structure de données est un atout indispensable à n’importe quel programmeur sérieux. Savoir utiliser la structure de donnée adéquate peut réduire le temps l’éfficacité de programme par des facteurs de centaines.

Supposons qu’on veut écrire un programme qui collection.

1. Ajouter \(10^6\) éléments a cette collection.
2. Exécuter \(10^6\) recherche dans cette collection pour confirmer l’éxistence d’un élément.
3. Essayer de supprimer \(10^6\) de cette collection.

Voici les résultats de cette expérience sur un ordinateur 2.8GHz Intel Core i7 en utilisant différents structure de données.

On remarque que la structure hashmap est parfaitement adaptée pour cette tâche. Cependant on va voir qu’ll offre son comprimis. Par rapport à l’utilisation d’un vecteur simple on as une accélération de \(103\)x. Et par rapport à liste chainée on a une réduction de \(\mathbf{636}\)x.