Advanced Algorithmics and Graph Theory with Python

Algorithmics and programming are fundamental skills for engineering students, data scientists and analysts, computer hobbyists or developers.

Learning how to program algorithms can be tedious if you aren’t given an opportunity to immediately practice what you learn. 

We’ll go over data-structures, basic and advanced algorithms for graph theory, complexity/accuracy trade-offs, and even combinatorial game theory.

Course Organization

Fundamentals of Graph Theory

  1. Addressing a Computational Problem
  2. Graphs and Paths
  3. Representing Graphs
  4. Good programming practices

Graph Traversal, Routing, Queuing Structures

  1. Graph Traversal
  2. Routing tables
  3. Queuing Structures

Shortest Paths & Algorithmic Complexity

  1. Dijkstra's Algorithm
  2. Min-heaps
  3. Algorithm complexity

NP-Completeness & Backtracking

  1. Traveling Salesman Problem
  2. Bruteforce and Backtracking to solve NP-Complete Problems
  3. Problem Complexity and NP-Completeness

Accuracy/Complexity tradeoff

  1. Heuristics
  2. Greedy Algorithms
  3. Approximate Solutions

Game Theory & Winning Strategies

  1. Combinatorial Game Theory
  2. Computing Winning Positions in a Game

Instructional Goals

By the end of the course, you should know:

  • Ways to express a computational problem (such as pathfinding) using graph theory
  • How to choose the appropriate algorithm to solve the given computational problem
  • How to code the algorithmic solution in python
  • Methods for evaluating the proposed solution in terms of its complexity (amount of resources, scalability) or performance (accuracy, latency)

Assessment Methods

Each week includes 

  • Practice Questions 
  • A Quiz  
  • A Lab

Practice Questions don't count towards your final grade, but the Quizzes and Labs do. The quizzes are worth 50% of your overall grade and the labs 50%.
You have two attempts for the each question in the Practices Questions and Quizzes, but an unlimited number of attempts for the Labs.

To quality for a badge, you must achieve a total grade of 45% or higher. If not, you will receive a "watcher" badge. Badges are available on your profile.

  • Quizzes count for 50% of the final grade.
  • Labs count for 50% of the final grade.

Contacts and Support

Technical Issues

If you encounter a problem or for any technical question, you can contact referents-pedagotheque@imt.fr. We will make every effort to respond to you within 2 working days.

Free Listeners

If you take this course as a free auditor, the forums will not be active and you will not receive a response from the educational team. You can still chat there with other free listeners.
Also, if you encounter a problem or for any technical question, you can contact referents-pedagotheque@imt.fr. We will make every effort to respond to you within 2 working days.

Class Use (with your teacher)

If you are taking this course under the supervision of one of your teachers, this one is free to use the course forums or any other communication channel that suits them better. Follow the directions given to you to ask your questions.
Also, if you encounter a problem or for any technical question, you can contact referents-pedagotheque@imt.fr. We will make every effort to respond to you within 2 working days.

Mots-clés:

"Advanced Algorithmics", "Graph Theory",  Python graph, algorithmics, algorithme

Advanced Algorithmics and Graph Theory with Python
Cours ouverts aux extérieurs sur demande à christophe.boutrou@imt.fr: Yes
Etablissement porteur: IMT Atlantique
Thématique(s): Programmation
Niveau(x) des étudiants: Tous niveaux
Membre(s) de l'équipe pédagogique: Vincent Gripon, Patrick Meyer, Nicolas Farrugia, Carlos Eduardo Rosar Kos Lassance, Ghouti Boukli Hacene
Conditions d'utilisation du cours: CC BY-NC-SA
Langue: Anglais
Durée du cours: 6 semaines
Accroche: Strengthen your skills in algorithmics and graph theory, and gain experience in programming in Python along the way.
Partenaires:

IMT Atlantique

Financial Support 

Patrick and Lina Drahi Foundation

Programmation Python

Ce cours aborde les fondamentaux de la programmation en Python (Structures de base / conditionnelles /  répétitives, Fonctions, Structures de données, Fichiers). Il est organisé en séances de cours et évaluations et de Travaux Pratiques.

Plan du cours

L'algorithmique

  1. Notion de problème, d’algorithme
  2. Algorithmes informatiques
  3. Formuler un algorithme
  4. Structures fondamentales
  5. Analyse descendante

Programmation en Python

  1. Présentation brève du langage Python
  2. Distributions de Python
  3. Distribution Anaconda
  4. Utilisation en mode console
  5. Utilisation en mode script

Structures de base

  1. Le langage
  2. Variables, types et valeurs
  3. Déclarations : Variables, Constantes
  4. Structure générale
  5. Interactions avec l’extérieur
  6. Expressions arithmétiques
  7. Affectations
  8. Trace d’exécution
  9. Compléments et Spécificités

Structures conditionnelles

  1. Conditions
  2. Sélectives Si
  3. Sélective Si-Sinon-Si
  4. Arbre de choix
  5. Sélective Selon

Structures répétitives

  1. Structures répétitives
  2. Schéma itératif

Algorithmes paramétrés

  1. Fonctions et procédures de test
  2. Procédures et paramètres formels

Listes et tableaux

  1. Les listes
  2. Tableau unidimensionnel
  3. Tableaux multidimensionnels

Structuration de l'information

  1. Le type structuré
  2. Le type Chaîne

Fichiers

  1. Présentation
  2. Primitives
  3. Python: spécificités

Objectifs pédagogiques

Information non disponible.

Modalités d'évaluation

En semaines 2, 3, 4, 5, 6, 7 et 8, des exercices vous sont proposés. Vous ne disposez que d'un seul essai. Chaque question vaut 1 point et le score total est ramené sur 10.
Également en semaines 3, 4, 5, 6, 7 et 8, des TP vous sont proposés. Ils sont notés sur 100.

Un badge de suivi avec succès est attribué aux étudiants obtenant une note supérieure ou égale à 70%. Dans le cas contraire, un badge de suivi vous sera remis. Ce badge sera disponible dans votre profil.

  • La moyenne des quiz vaut 30% de la note finale.
  • La moyenne des TP vaut 70% de la note finale.

Contacts et accompagnement

Questions d'ordre technique

Si vous rencontrez un problème ou pour toute question d'ordre technique, vous pouvez contacter referents-pedagotheque@imt.fr. Nous mettrons tout en œuvre pour vous répondre sous 2 jours ouvrés.

Auditeurs libres

Si vous suivez ce cours en auditeur libre, les forums ne seront pas actifs et vous n'y obtiendrez pas de réponse de l'équipe pédagogique. Vous pouvez néanmoins y discuter avec d'autres auditeurs libres.
Également, si vous rencontrez un problème ou pour toute question d'ordre technique, vous pouvez contacter referents-pedagotheque@imt.fr. Nous mettrons tout en œuvre pour vous répondre sous 2 jours ouvrés.

Utilisation en classe (avec votre enseignant)

Si vous suivez ce cours sous la supervision de l'un de vos enseignants, ce dernier est libre d'utiliser les forums du cours ou tout autre canal de communication qui lui conviendrait mieux. Suivez les indications qu'il vous aura données pour lui poser vos questions.
Également, si vous rencontrez un problème ou pour toute question d'ordre technique, vous pouvez contacter referents-pedagotheque@imt.fr. Nous mettrons tout en œuvre pour vous répondre sous 2 jours ouvrés.

Mots-clés:

programmation python
informatique
Cours ouverts aux extérieurs sur demande à christophe.boutrou@imt.fr: No
Etablissement porteur: Établissement externe à l'IMT
Nom de l'écoles associées, sous convention, filiales ou affiliées ou de l'établissement externe: Unisciel
Thématique(s): Programmation
Niveau(x) des étudiants: Tous niveaux, Bac+1, Bac+2, Bac+3, Bac+4, Bac+5, Autre
Conditions d'utilisation du cours: CC BY-NC-SA
Langue: Français
Durée du cours: + de 7 semaines
Accroche: Découvrir les fondamentaux de la programmation Python
Partenaires: Production et coordination
Logo UniscielLogo Université Haute-Alsace