Skip to content

Latest commit

 

History

History
458 lines (278 loc) · 13.1 KB

science-informatique.md

File metadata and controls

458 lines (278 loc) · 13.1 KB
Raw

Introduction au séminaire

::: notes

  • Bref CV à l'oral
    • ingénieur, docteur, EC
    • bases de données et sécurité, DS

:::

Plan

::: notes

Exposé proposé pour l'action "Les lycéens à la fac" du salon des études supérieures du 29 juillet 2022 de l'UNC (13h, Amphi A400).

Objectifs de la conférence :

  • rompre certaines idées reçues sur l'informatique et ses métiers
  • positionner la science informatique dans le champ technique et scientifique
    • Beaucoup de métiers en informatique, j'en parle, mais on va centrer sur la science
  • motiver les contenus des formations universitaires en informatique : la conclusion
    • Pour la formation, à l'UNC ou ailleurs, ce n'est pas très différent

:::

Avant-propos

Clause de non-responsabilité : ni philosophe, ni sociologue, ni développeur : enseignant-chercheur en informatique.

Les informaticiens détestent-ils réparer les imprimantes ?

r/ProgrammerHumor -- I can fix it, but not because I'm a programmer

::: notes

:::

Pourquoi les informaticiens détestent-ils réparer les imprimantes ces questions ?

Réparer l'imprimante, le téléphone ou le wifi n'est pas le métier d'un développeur (*) ni celui d'un enseignant-chercheur.

. . .

Quels sont ces métiers ? Qu'est ce qui les différencie ?

. . .

(*) ni celui d'un architecte logiciel, d'un intégrateur, d'un testeur, d'un administrateur réseaux.

::: notes

réponse à la différece : la science informatique VS la technique

séparer l'utilisateur du concepteur va nous amener, retrospectivement à séparer le du développeur/concepteur du chercheur/scientifique :::

L'informatique : science, technique ou même art ?

. . .

  • science : la connaissance, le vrai
  • technique : la résolution de problème, le faisable
  • art : la créativité, le beau

L'informatique : science, technique et art

Amazon -- The Art Of Computer Programming

Métaphore du couteau

Un parallèle entre utiliser, réaliser et penser un couteau en acier et un programme informatique.

Utiliser un couteau

The Spruce Eats -- How to Use A Chef's Knife

Réaliser un couteau

Industrial Heating -- Forging Knives in College

Penser un couteau

Par Cdang — Travail personnel, CC BY-SA 3.0, Wikipedia Commons

::: notes

L'acier a été découvert très tôt dans l'histoire car sa matière première est abondante (minerai), et qu’il est facile à travailler. L'acier « de base » est de fait peu onéreux.

fer : moins de 0,008 % de carbone en masse
acier : entre 0,008 et 2,11 % de carbone ;
fonte : teneur supérieure à 2,11 %.

Diagramme binaire fer-carbone et structure cristalline des aciers à l'état recuit :::

Parallèle

Couteau Programme
Utilisation cuisinier utilisateur
Technique artisan forgeron développeur
ingénieur méttalurgiste ingénieur informaticien
Science physico-chimiste, cristallographe scientifique en informatique

::: notes

  • Une question de recul : les utilisateurs d'un langage de programmation sont des développeurs.
  • La création n'est pas descendante mais faite de va-et-vient : les besoins des développeurs amènent à (re)penser les langages de programmations.
    • dans bcp de process sci, dont les maths
    • pas de sots métiers !
  • Acier/dev : un parallèle assez naturel, car on parle de forge, de craftmanship dans le domaine du développement

:::

Une définition de la science informatique (1/2)

Informatics is the scientific discipline that underpins the digital world.

Informatics Reference Framework for School.

NDA : informatics synonyme de computer science.

Une définition de la science informatique (2/2)

L’informatique parle d’objets de différente nature : informations, langages, machines et algorithmes.

Chacun de ces quatre concepts est antérieur à l’informatique, mais ce qui ce que l’informatique apporte sans doute de nouveaux est leur organisation en une science cohérente.

La place de l'informatique dans la classification des sciences, Gilles DOWEK, 2014

::: notes

:::

L'approche scientifique de l'évaluation des performances

Le problème min-max

Problème trouver le plus grand élément et le plus petit élément d'une collection linéaire non-vide d'entiers naturels (par exemple : liste, tableau).

::: notes

  • on dit aussi séquentielle pour linéaire

:::

Différentes solutions Python

Solution étudiant

def min_max_etudiant(arr):
    min_courant = arr[0]
    max_courant = arr[0]
    for v in arr:
        if v < min_courant:
            min_courant = v
        if v > max_courant:
            max_courant = v

    return min_courant, max_courant

min_max_etudiant([1, 42, 3, 2, 0, 5]) #renvoie (0, 42)

. . .

C'est une solution classique et correcte : une suite d'opérations élémentaires, au plus proche de l'algorithmique.

::: notes

  • arr est non-vide, on prend le premier
  • classique et correcte MAIS un dev de doit jamais écrire ça !

:::

Solution développeur

def min_max_sorter(arr):
    arr_trie = sorted(arr)
    # arr_trie[0] le premier élément après le tri
    # arr_trie[-1] le dernier élément après le tri
    return arr_trie[0], arr_trie[-1]

. . .

C'est une solution correcte, où le développeur utilise une fonction de tri qu'il sait disponible dans à peu près tous les langages.

::: notes mais... il y a un mais ! :::

Solution Pythonista

def min_max_pythonista(arr):
    return min(arr), max(arr)

. . .

C'est une solution correcte aussi, où le développeur connait bien le langage Python et propose une solution "Pythonique".

::: notes

pythonista : une notion subjective de beauté, presque d'art

:::

Quelle est la meilleure solution ?

. . .

Définir meilleure

. . .

  • la plus efficace en temps ?
  • la plus efficace en mémoire ?
  • la plus élégante, la plus lisible ?
  • la plus rapide à programmer ?

. . .

On va ici évaluer l'efficacité en temps

Critères d'efficacité en temps

. . .

Comment avoir une évaluation robuste des trois solutions ?

. . .

Comment faire des prédictions quant-à leurs comportements selon la taille des données ?

::: notes

Robuste : (indépendantes des contigences matérielles), voir du modèle de calcul

Ne pas sous-estimer/oublier que généralement on a pas besoin de performance !

Si on fait la somme du temps d'exec plus du temps de dev, Python est plus rapide que le C car on code beaucoup plus rapidement des tâches complexes

Pour l'évaluation empirique des performances sur quelle machine, quel OS, quelle version de Python, quel jeu de données ?

:::

Évaluation empirique (1/2)

Peut-on déterminer quelle est la meilleure solution ?

::: notes

Pas vraiment

On voit au passage que l'ordre n'est pas le même et qu'il y a de la variance.

Une autre exec ne donnera pas le même résultat

:::

Évaluation empirique (2/2)

Peut-on déterminer quelle est la meilleure solution ?

La compléxité algorithmique

  • Peut-on modéliser les comportements de ces algorithmes ?
    • Oui, avec la complexité asymptotique en temps
  • Peut-on comparer leurs comportements ?
    • Oui, en partie en comparant leur complexité
  • Peut-on prédire le temps d'exécution ?
    • Non, car à un facteur près

::: notes

comportements = allure des courbes

détails des trois questions :

On va compter le nombre de comparaisons entre entiers.

  • avec l'évaluation (asymptotique) de la complexité (au pire cas) en fonction de la taille de l'entrée
  • , car on est dépendants de facteurs inconnus et des entrées

:::

Déterminer le nombre de comparaisons

def min_max_etudiant(arr):
    # soit n la longueur de la séquence, n = len(arr)
    the_min = arr[0]
    the_max = arr[0]
    for v in arr: # on passe (n) fois dans cette boucle
        # une comparaison ici
        if v < the_min:
            the_min = v
        # une autre comparaison là
        if v > the_max:
            the_max = v
    return the_min, the_max

. . .

Pour une entrée de longueur $n$, on effectue $2 \times n$ comparaisons

. . .

Ce qui compte, c'est l'ordre de grandeur, ici, proportionnel à $n$, qu'on note $O(n)$, dit grand $O$ de n.

Comparaison des compléxités

notation compléxité exemple
$O(1)$ constante accès à un élément
$O(log(n))$ logarithmique recherche dichotomique
$O(n)$ linéaire recherche 👈
$O(n.\log(n))$ "bon" tri 👈
$O(n^2)$ quadratique "mauvais" tri
$O(n^c)$ polynomiale produit de matrice naïf ($c=3$)
$O(c^n)$ exponentielle voyageur de commerce

Comparaison des compléxités des solutions min-max

  • min_max_etudiant est en $O(n)$
  • min_max_pythonista est en $O(n)$
    • car min et max le sont
  • min_max_sorted est en $O(n.\log(n))$
    • car c'est la compléxité de sorted
    • on résoud un problème trop compliqué !

::: notes

  • Tout est à un coefficient près
  • Rien n'est dit sur les constantes, clairement celle de pythonista est meilleure que celle de étudiant
  • Optimiser, c'est changer la constante mais surtout changer les ordres de grandeurs
  • Une notion de frugalité : ne pas utiliser un algo générique/trop puissantpour un problème simple

Ceci explique/confirme les allures des courbes !

:::

La formation en informatique

. . .

Science et technique et art

La science est partout

SourabhSKatoch

L'art est partout

Cable porn at github

Les programmes d'informatique

Sciences et techniques (et art !) se déclinent :

  • langages
    • paradigmes de programmation, développement, compilation
  • algorithmes
    • structures de données, théorie de la compléxité, décidabilité, modèles de calculs
  • informations et machines
    • codage/représentation, réseau, système, informatique embarquée

Références

https://romulusfr.github.io/expose-science-informatique/

Notation de Landau

Notation de Landau, dite grand $O$ :

Soient $f,g : \mathbb{N} \to \mathbb{R}^+$ deux applications, on dit que f est dominée par g (en $+\infty$) que l'on note $f(n) = O (g(x))$ lorsqu'il existe un rang $N \in \mathbb{N}$ et une constante $C \in \mathbb{R}^+$ tels que $\forall n &gt; N, f(n) \leq C g(x)$.