Algorithmique et programmation avancée I
sturhan@gsu.edu.tr
Contenus
Objectif du Cours
L'objectif de ce cours est d'améliorer les capacités de programmation des étudiants en étudiant certains algorithmes courants, leurs implémentations et leurs applications aux certaines problèmes de calcul.
Contenu du Cours
Revue de programmation (avec Python): variables, conditions, boucles, fonctions
Structures de données: liste, array multidimensionnel, arbre
Algorithmes: recherche, tri, fonctions d'agrégation
Recursion: calcul numérique, traversée d'arbre (inorder / preorder / postorder)
Analyse algorithmique: classes de complexité temps / espace
Acquis d'Apprentissage du Cours
-étant donnée un problème, les étudiants seront capables d'identifier les composants logiques du problème, leurs interdépendances et les algorithmes qui peuvent être utilisés pour résoudre chacun de ces composants.
-étant donnée un algorithme, les étudiants seront capables de comparer leurs performances et leurs caractéristiques avec d'autres algorithmes de la même classe.
-étant donnée un code source, les étudiants seront capables d'identifier les structures de données et les algorithmes implémentés dans le code source donné.
Méthodes d'Enseignement
lecture théorique, devoir
Ressources
The Art of Computer Programming - Donald Knuth
Python - How to Program - Deitel
Data Structures and Algorithms Using Python - Rance D. Necaise
Data Structures and Algorithms with Object-Oriented Design Patterns in Python - Bruno R.Preiss
Intitulés des Sujets
| Semaine | Intitulés des Sujets |
|---|---|
| 1 | Revue de programmation: valeur, expression, variable, type de données, affectation, état du programme, boucles énumératif |
| 2 | Revue de programmation: conditionnelles, branchement d'exécution, boucles conditionnelles, compositions des boucles et des conditionnelles |
| 3 | Revue de programmation: fonctions, paramètres, valeur de retour, flux de code, cadre de pile, cadres des variables |
| 4 | Séquences, motifs, motifs multidimensionnels par les indices des boucles, dépendance des données |
| 5 | Implémentation des fonctions d'agrégation: min, max, somme, compte, moyenne, std.dev, unique |
| 6 | Tri des valeurs sur une liste: approche naïve, tri par insertion, tri à bulles, tri par fusion |
| 7 | Partielle |
| 8 | Récursivité: limiter par profondeur, flux d'appels de fonction, exemples: factoriel, fibonacci, tri rapide |
| 9 | Arbres: traversée première profondeur, traversée première en largeur, traversée en-ordre / pré-ordre / post-ordre |
| 10 | Pile, queue, relation de pile avec récursion, suppression de récursion |
| 11 | Partielle |
| 12 | Algorithmes numériques: génération de nombres aléatoires, recherche numerique des racines, régression linéaire |
| 13 | Recherche: recherche simple, recherche binaire, recherche récursive |
| 14 | Complexité temps / espace, classes de complexité, comparaison d'algorithmes |
Système d'évalution
| Activités | Numéro | Contribution |
|---|---|---|
| Contribution du contrôle continu à la note finale | 2 | 40 |
| Contribution de l'examen final à la note finale | 1 | 60 |
| Total | 3 | 100 |
| Activités | Numéro | Contribution |
|---|---|---|
| Devoir | 0 | 0 |
| Présentation | 0 | 0 |
| Examen partiel (temps de préparation inclu) | 2 | 40 |
| Projet | 0 | 0 |
| Travail de laboratoire | 0 | 0 |
| Autres travaux pratiques | 0 | 0 |
| Quiz | 0 | 0 |
| Devoir/projet de session | 0 | 0 |
| Portefeuille | 0 | 0 |
| Rapport | 0 | 0 |
| Journal d'apprentissage | 0 | 0 |
| Mémoire/projet de fin d'études | 0 | 0 |
| Séminaire | 0 | 0 |
| Autre | 0 | 0 |
| Total | 2 | 40 |
Evalution de la Compétence
| No | Objectifs Pédagogiques du Programme | Contribiton | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | comprend les principes de la méthode hypothético-déductive; s'est interrogé systématiquement sur la pertinence et la justesse des énoncés mathématique qu'il a rencontré ou produit; | X | ||||
| 2 | sait énoncer et utiliser judicieusement les concepts et les résultats des mathématiques de base; | X | ||||
| 3 | maîtrise les techniques de calcul et les algorithmes courants; possède une bonne intelligence de calcul pour les mettre en œuvre; est capable d'identifier les outils pertinents, parmi ceux qu'il connaît, pour la résolution d'un problème, et est capable de juger s’il ne possède pas ces outils; | X | ||||
| 4 | est capable d'exprimer de manière organisée, tant à l'écrit qu'à l'oral, ses idées mathématiques; | X | ||||
| 5 | a réalisé les relations essentielles qui lient entre eux ces concepts et résultats; est capable de passer de l'un à l'autre de divers mode de représentation des objets mathématiques (dessins, formules, énoncés précis, heuristiques, collection d'exemples,...); | X | ||||
| 6 | a poursuivi, en autonomie, une stratégie d'apprentissage guidée; s'est engagé dans des stratégies de résolution d'un problème complexe; | X | ||||
| 7 | a les bases théoriques et pratiques suffisantes en informatique pour pouvoir poursuivre l'apprentissage d'un langage de programmation; | X | ||||
| 8 | s'est interrogé sur la pertinence de la modélisation mathématique et l'usage des outils mathématiques dans les sciences naturelles et dans le monde professionnel; a été sensibilisé à l'évolution historique des concepts mathématiques; | X | ||||
| 9 | a eu l'opportunité de choisir librement certains de ses cours (de mathématiques ou d'autres disciplines) et a, à l'occasion, appris à prendre ses responsabilités et à organiser son projet éducatif par lui-même; | X | ||||
| 10 | a une maîtrise de la langue française et d'une autre langue étrangère suffisante pour pouvoir poursuivre des études ou travailler à l'étranger. | X | ||||
Tableau de la Charge de Travail
| Activités | Nombre | Durée | Charge totale de Travail |
|---|---|---|---|
| Durée du cours | 14 | 3 | 42 |
| Préparation pour le cours | 14 | 2 | 28 |
| Devoir | 14 | 1 | 14 |
| Examen partiel (temps de préparation inclu) | 1 | 10 | 10 |
| Examen final (temps de préparation inclu) | 1 | 20 | 20 |
| Charge totale de Travail | 114 | ||
| Charge totale de Travail / 25 | 4.56 | ||
| Crédits ECTS | 5 | ||