IFT-7012 Théorie algorithmique des graphes
IFT-7012
IFT
7012
Théorie algorithmique des graphes
Informatique
Description
Ce cours aborde des sujets tels la connexité dans un graphe (problèmes du flot maximum, de la dualité min-max, de couplage parfait, etc.), la planarité d'un graphe (formule d'Euler, théorème de Kuratowski, graphe dual), le coloriage d'un graphe (coloriages entiers et fractionnaires des sommets ou des arêtes, graphes de Kneiser), les problèmes de transversales d'un graphe (parcours eulériens, cycles hamiltoniens, graphes de DeBruijn, etc.) et la notion de marche aléatoire sur un graphe (chaînes de Markov, existence de la distribution limite, « mixing time », etc.). Plusieurs problèmes sur les graphes ont d'élégantes solutions, d'autres évidemment sont NP-complets; une partie de ce cours portera donc sur la théorie de la complexité (problèmes NP et NP-complets, théorème de Cook, algorithmes de réductions).
Cours cycles etudes XML
a:2:{i:0;a:6:{s:15:"codeCycleEtudes";s:1:"2";s:11:"description";s:15:"Deuxième cycle";s:28:"affichableDansListeDeValeurs";s:1:"1";s:22:"cycleEtudesSuperieures";s:1:"1";s:31:"disponibleAdmissionLibreService";s:1:"1";s:32:"descriptionAdmissionLibreService";s:15:"Deuxième cycle";}i:1;a:6:{s:15:"codeCycleEtudes";s:1:"3";s:11:"description";s:16:"Troisième cycle";s:28:"affichableDansListeDeValeurs";s:1:"1";s:22:"cycleEtudesSuperieures";s:1:"1";s:31:"disponibleAdmissionLibreService";s:1:"1";s:32:"descriptionAdmissionLibreService";s:16:"Troisième cycle";}}
Cours formules enseignement XML
N;
Sections cours
a:1:{s:12:"sectionCours";a:2:{i:0;a:15:{s:7:"session";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:6:"201801";}s:5:"titre";a:1:{i:0;s:10:"Hiver 2018";}}}s:3:"nrc";a:1:{i:0;s:5:"10058";}s:10:"codeGroupe";a:1:{i:0;s:1:"A";}s:11:"typeHoraire";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:1:"R";}s:5:"titre";a:1:{i:0;s:9:"Régulier";}}}s:6:"campus";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:3:"000";}s:5:"titre";a:1:{i:0;s:9:"Principal";}}}s:12:"modeNotation";a:1:{i:0;s:0:"";}s:19:"formuleEnseignement";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:1:"P";}s:5:"titre";a:1:{i:0;s:11:"Présentiel";}}}s:9:"dateDebut";a:1:{i:0;s:10:"2018-01-15";}s:7:"dateFin";a:1:{i:0;s:10:"2018-04-27";}s:19:"nombrePlacesMaximum";a:1:{i:0;s:2:"30";}s:25:"reservationsPlacesSection";a:1:{i:0;s:0:"";}s:19:"restrictionsSection";a:1:{i:0;s:0:"";}s:11:"professeurs";a:1:{i:0;s:0:"";}s:13:"plagesHoraire";a:1:{i:0;s:0:"";}s:14:"sectionsFilles";a:1:{i:0;s:0:"";}}i:1;a:15:{s:7:"session";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:6:"202401";}s:5:"titre";a:1:{i:0;s:10:"Hiver 2024";}}}s:3:"nrc";a:1:{i:0;s:5:"15908";}s:10:"codeGroupe";a:1:{i:0;s:1:"A";}s:11:"typeHoraire";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:1:"R";}s:5:"titre";a:1:{i:0;s:9:"Régulier";}}}s:6:"campus";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:3:"000";}s:5:"titre";a:1:{i:0;s:9:"Principal";}}}s:12:"modeNotation";a:1:{i:0;s:0:"";}s:19:"formuleEnseignement";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:1:"P";}s:5:"titre";a:1:{i:0;s:11:"Présentiel";}}}s:9:"dateDebut";a:1:{i:0;s:10:"2024-01-15";}s:7:"dateFin";a:1:{i:0;s:10:"2024-04-26";}s:19:"nombrePlacesMaximum";a:1:{i:0;s:2:"30";}s:25:"reservationsPlacesSection";a:1:{i:0;s:0:"";}s:19:"restrictionsSection";a:1:{i:0;s:0:"";}s:11:"professeurs";a:1:{i:0;s:0:"";}s:13:"plagesHoraire";a:1:{i:0;a:1:{s:12:"plageHoraire";a:1:{i:0;a:8:{s:16:"typePlageHoraire";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:4:"CLAS";}s:5:"titre";a:1:{i:0;s:15:"Cours en classe";}}}s:4:"jour";a:1:{i:0;s:5:"Lundi";}s:9:"dateDebut";a:1:{i:0;s:10:"2024-01-15";}s:7:"dateFin";a:1:{i:0;s:10:"2024-04-26";}s:10:"heureDebut";a:1:{i:0;s:5:"12:30";}s:8:"heureFin";a:1:{i:0;s:5:"15:20";}s:8:"pavillon";a:1:{i:0;s:14:"Adrien-Pouliot";}s:11:"numeroLocal";a:1:{i:0;s:4:"2504";}}}}}s:14:"sectionsFilles";a:1:{i:0;s:0:"";}}}}
Substituts
N;
Temps à consacrer
a:3:{s:13:"nbHeuresCours";a:2:{s:6:"valeur";s:1:"3";s:4:"type";s:4:"fixe";}s:19:"nbHeuresLaboratoire";a:2:{s:6:"valeur";s:1:"0";s:4:"type";s:4:"fixe";}s:14:"nbHeuresAutres";a:2:{s:6:"valeur";s:1:"6";s:4:"type";s:4:"fixe";}}
Cours attributs de cours
N;
Cours restrictions
a:1:{s:11:"restriction";a:1:{i:0;a:3:{s:15:"typeRestriction";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:3:"LVL";}s:5:"titre";a:1:{i:0;s:15:"Cycle d'études";}}}s:18:"inclusionExclusion";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:1:"I";}s:5:"titre";a:1:{i:0;s:9:"Inclusion";}}}s:18:"elementsRestreints";a:1:{i:0;a:1:{s:16:"elementRestreint";a:2:{i:0;a:2:{s:4:"code";a:1:{i:0;s:1:"2";}s:5:"titre";a:1:{i:0;s:15:"Deuxième cycle";}}i:1;a:2:{s:4:"code";a:1:{i:0;s:1:"3";}s:5:"titre";a:1:{i:0;s:16:"Troisième cycle";}}}}}}}}
Cours type d'horaires
a:1:{s:11:"typeHoraire";a:1:{i:0;a:2:{s:4:"code";a:1:{i:0;s:1:"R";}s:5:"titre";a:1:{i:0;s:9:"Régulier";}}}}
Cours préalables XML
N;
Cours concomitant
N;
Nombre de crédits XML
a:3:{s:7:"minimum";a:1:{i:0;s:1:"3";}s:8:"indicUEC";a:1:{i:0;s:1:"N";}s:10:"affichable";a:1:{i:0;s:1:"3";}}
Prochaine session offert XML
a:2:{s:4:"code";a:1:{i:0;s:14:"indéterminée";}s:5:"titre";a:1:{i:0;s:14:"indéterminée";}}
Faculté
Formules d’enseignement
Présentiel
Présentiel
Matières
IFT - Informatique
Modes d’enseignement
Régulier
Sessions d’inscription
Hiver 2018
Hiver 2024
Cours cycle