La science informatique
“pourquoi je ne vais ni réparer ton imprimante ni hacker ton Insta”
romuald.thion@unc.nc
https://romulusfr.github.io/expose-science-informatique/
29 juillet 2022, “les lycéens à la fac”, UNC
Introduction au séminaire
Plan
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 ?
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.
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
Métaphore du couteau
Un parallèle entre utiliser, réaliser et penser un couteau en acier et un programme informatique.
Utiliser un couteau
Réaliser un couteau
Penser un couteau
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 |
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
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).
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.
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.
Solution Pythonista
C’est une solution correcte aussi, où le développeur connait bien le langage Python et propose une solution “Pythonique”.
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 ?
Évaluation empirique (1/2)
Peut-on déterminer quelle est la meilleure solution ?
É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
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_maxPour 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_etudiantest en \(O(n)\)min_max_pythonistaest en \(O(n)\)- car
minetmaxle sont
- car
min_max_sortedest en \(O(n.\log(n))\)- car c’est la compléxité de
sorted - on résoud un problème trop compliqué !
- car c’est la compléxité de
La formation en informatique
Science et technique et art
La science est partout
L’art est partout
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
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 > N, f(n) \leq C g(x)\).