小瓢虫传媒

Enseignants

Saerens Marco;

Langue
d'enseignement

贵谤补苍莽补颈蝉

笔谤茅补濒补产濒别蝉

Ce cours suppose acquises les notions d'alg猫bre聽 vis茅es par le cours LINFO1112

Le(s) pr茅requis de cette Unit茅 d鈥檈nseignement (UE) sont pr茅cis茅s 脿 la fin de cette fiche, en regard des programmes/formations qui proposent cette UE.

Th猫mes abord茅s

Th茅orie des ensembles

• Rappels des notations et op茅rations ensemblistes
• Relations binaires entre ensembles : applications et lien avec les fonctions en analyse
• Cardinalit茅 d'un ensemble (fini et infini) et notion d'inclusion-exclusion
• Equivalence, classes d'茅quivalence

Logique

• Introduction 脿 la logique des propositions
• Introduction 脿 la logique des pr茅dicats
• M茅thodes de preuve
• Induction math茅matique
• Notions d'alg猫bre de Boole

Introduction 脿 la th茅orie des nombres

• Nombres entiers naturels, principe de r茅currence, nombres premiers, etc
• Division euclidienne, repr茅sentation dans une base, arithm茅tique modulo, repr茅sentation des entiers dans l'ordinateur
• Pcgd, algorithme d'Euclide
• Notions 茅l茅mentaires de cryptographie

Combinatoire

• Comptage
• Permutations
• Arrangements
• Relations de r茅currence
• Solutions d'茅quations de r茅currence

Introduction 脿 la th茅orie des graphes

• Graphes orient茅s et non orient茅s et leurs repr茅sentations matricielles
• Graphes bipartites et probl猫mes de matching
• Chemins sur un graphe et circuits Eul茅riens/Hamiltoniens
• Graphes planaires et coloriage
• Probl猫mes de plus court chemin
• Classement des noeuds d'un graphe : PageRank

Acquis
d'apprentissage

A la fin de cette unit茅 d鈥檈nseignement, l鈥櫭﹖udiant est capable de :
1	Eu 茅gard au r茅f茅rentiel AA du programme 芦 Bachelier en sciences informatiques 禄, ce cours contribue au d茅veloppement, 脿 l'acquisition et 脿 l'茅valuation des acquis d'apprentissage suivants : S1.I1, S1.G1 S2.2 Les 茅tudiants ayant suivi avec fruit ce cours seront capables de : Utiliser 脿 bon escient la terminologie des fonctions, relations et ensemble et r茅aliser les op茅rations associ茅es lorsque le contexte le n茅cessite Expliciter la structure de base des principales techniques de preuve (preuve directe, contrexemple, preuve par l'absurde, induction, r茅currence) Appliquer les diff茅rentes techniques de preuve de mani猫re convaincante en s茅lectionnant la plus adapt茅e au probl猫me pos茅 Analyser un probl猫me pour d茅terminer les relations de r茅currence sous-jacentes Calculer des comptages, permutations, arrangements sur des ensembles dans le cadre d'une application. Mod茅liser divers probl猫mes du monde r茅el rencontr茅s en informatiques en utilisant les formes appropri茅es de graphes Expliquer le probl猫me du plus court chemin dans un graphe et appliquer des algorithmes classiques pour r茅soudre ce probl猫me

M茅thodes d'enseignement

Environ 30 heures de cours magistraux en pr茅sentiel ou distanciel selon les conditions.
Un projet/cas d'茅tude obligatoire portant sur l'impl茅mentation et l'application d'un ouplusieurs algorithmes.

Modes d'茅valuation
des acquis des 茅tudiants

• Un projet/cas d'茅tude obligatoire comptant pour 2 脿 4 points sur 20 (sp茅cifi茅 en d茅but d'ann茅e acad茅mique). Si le projet n'est pas remis, l'茅tudiante ou l'茅tudiant obtiendra 0/3 pour ce projet.
• Un examen 茅crit organis茅 en session comptant pour 18 脿 16聽points sur 20 (sp茅cifi茅 en d茅but d'ann茅e acad茅mique). En pr茅sentiel ou distanciel, selon la situation.

Concernant le projet/cas d'茅tude obligatoire et聽l'utilisation d'IA de type Chat GPT, assurez-vous que聽"En soumettant un travail pour 茅valuation, vous affirmez : (i) qu'il refl猫te fid猫lement le ph茅nom猫ne 茅tudi茅, et pour cela vous devez avoir v茅rifi茅 les faits, surtout s'ils sont pr茅tendus par une IA g茅n茅rative (dont vous devez mentionner explicitement l鈥檜tilisation en tant qu鈥檕util de soutien 脿 la r茅alisation de votre travail) ; (ii) avoir respect茅 toutes les exigences sp茅cifiques du travail qui vous est confi茅, notamment les exigences pour la transparence et la documentation de la d茅marche scientifique mise en 艙uvre. Si l'une de ces affirmations n'est pas vraie, que ce soit intentionnellement ou par n茅gligence, vous 锚tes en d茅faut de votre engagement d茅ontologique vis-脿-vis de la connaissance produite dans le cadre de votre travail, et 茅ventuellement d鈥檃utres aspects de l鈥檌nt茅grit茅 acad茅mique, ce qui constitue une faute acad茅mique et sera consid茅r茅 comme tel".

Ressources
en ligne

痴辞颈谤听

Bibliographie

Rosen K., Discrete mathematics and its applications, 8th edition, 2019. Mc Graw Hill.

Support de cours

• Slide du cours
• Textbook "Math茅matiques discr猫tes" de K. Rosen

Facult茅 ou entit茅
en charge

INFO