GAC024 Mathématiques discrètes

GAC024 est les mathématiques discrètes : les mathématiques des choses que l'on peut compter et de la logique sur laquelle les ordinateurs fonctionnent. Cinq unités couvrent les ensembles, les systèmes de comptage, le binaire, les algorithmes et les graphes.

Elles s'accordent naturellement avec les modules informatiques, et les universités qui valorisent GAC016 reconnaissent souvent aussi celui-ci pour un cours de base en informatique. L'évaluation suit le schéma habituel : un contrôle, un examen et un travail continu. schéma : un contrôle, un examen et un travail continu.

• ⚠ Les mathématiques discrètes ont peu de formules et beaucoup de raisonnement. Une démonstration ou un algorithme tracé rapportent les points, et une réponse non expliquée rapporte presque rien.

• Un ensemble 集合 est une collection d'objets distincts. L'ordre et la répétition n'ont aucune importance.
• L'union 并集 $A \cup B$ regroupe tout ce qui est dans l'un ou l'autre ; l'intersection 交集 $A \cap B$ rassemble ce qui est dans les deux ; le complémentaire d'ensemble 补集 contient tout ce qui est à l'extérieur.
• Un sous-ensemble 子集 a tous ses éléments contenus dans un autre ensemble.
• Une relation 关系 apparie des éléments de deux ensembles. Une fonction 函数 est une relation où chaque entrée correspond à exactement une sortie.
• Un diagramme de Venn 韦恩图 transforme un problème d'ensembles en image, et le dessiner est généralement plus rapide que de raisonner dessus en mots.

Exemple résolu. Dans une classe de 30 élèves, 18 étudient le français et 15 l'allemand ; 7 étudient les deux. Combien n'étudient aucune des deux langues ?

Soustraire l'intersection une seule fois est le principe d'inclusion-exclusion 容斥原理. Ajouter 18 et 15 sans cela compte les sept deux fois, ce qui constitue l'erreur classique.

• Une base numérique 进制 indique combien de chiffres elle utilise. Décimal 十进制 utilise dix, binaire 二进制 deux, hexadécimal 十六进制 seize.
• La valeur de chaque chiffre dépend de sa position 位值 : en binaire, les positions valent 1, 2, 4, 8, 16, etc.
• L'hexadécimal est une abréviation du binaire : un chiffre hexadécimal vaut exactement quatre bits, c'est pourquoi les adresses mémoire s'écrivent en hexadécimal.

Exemple résolu. Convertissez 1101 en binaire vers décimal.

Écrivez les valeurs de position au-dessus des chiffres avant d'additionner. Le faire mentalement provoque des erreurs d'un (off-by-one).

• L'arithmétique binaire 二进制运算 additionne comme en décimal, en reportant à 2 au lieu de 10.
• Un bit 位 est un chiffre binaire ; un octet 字节 en contient huit.
• L'algèbre de Boole 布尔代数 opère sur le vrai et le faux avec AND, OR et NOT.
• Une table de vérité 真值表 énumère chaque combinaison d'entrées et sa sortie, et elle constitue la preuve complète que deux expressions logiques sont équivalentes.
• Les portes logiques 逻辑门 sont la forme physique de ces opérations, et un circuit logique 逻辑电路 est ce dont est composé un processeur.

• Un algorithme 算法 est une séquence finie d'étapes non ambiguës qui se termine.
• Un organigramme 流程图 le représente : une décision est un losange, un processus un rectangle.
• La pseudo-code 伪代码 l'écrit en anglais structuré, ce que demande généralement un examen.
• Tracer 追踪 un algorithme — un tableau avec une colonne par variable et une ligne par étape — est la technique notée, et c'est ainsi que vous détectez un bug sans exécuter quoi que ce soit.
• L'efficacité 效率 compte : une recherche linéaire vérifie chaque élément, une recherche dichotomique divise la liste par deux à chaque fois, et sur un million d'éléments, cela fait la différence entre un million d'étapes et vingt.

Exemple résolu. Tracez une recherche dichotomique pour 7 dans [1, 3, 5, 7, 9, 11].

Le milieu est 5, inférieur à 7, donc on cherche dans la moitié droite. Le milieu de [7, 9, 11] est 9, supérieur, donc on cherche dans la gauche. Le milieu de [7] est 7. Trouvé, en trois étapes plutôt que quatre.

Le tableau des étapes est la réponse. Le mot « trouvé » ne l'est pas.

• Un graphe 图 est un ensemble de sommaires 顶点 reliés par des arêtes 边. Il modélise tout ayant des connexions : routes, amitiés, dépendances.
• Le degré 度 d'un sommet est le nombre d'arêtes qui y aboutissent.
• Un arbre 树 est un graphe connexe sans cycles, et il représente la structure d'un système de fichiers, d'un organigramme ou d'un document HTML.
• Un problème de plus court chemin 最短路径 cherche l'itinéraire le moins coûteux entre deux sommets, et c'est ce qu'un application de navigation résout à chaque utilisation.