C2 - Optimiser des applications

Description

Cette compétence vise à appréhender, proposer et construire des applications informatiques optimisées en analysant les problèmes avec méthode et en utilisant les outils mathématiques et algorithmiques appropriés.

Composantes Essentielles

en formalisant et modélisant des situations complexes
en recensant les algorithmes et les structures de données usuels
en s'appuyant sur des schémas de raisonnement
en justifiant les choix et validant les résultats

Apprentissages Critiques

AC1 Analyser un problème avec méthode
AC2 Comparer des algorithmes pour des problèmes classiques
AC3 Expérimenter la notion de compilation et les représentations bas niveau des données
AC4 Formaliser et mettre en œuvre des outils mathématiques pour l'informatique

Mes Acquisitions

Voici comment j'ai développé et acquis cette compétence à travers mes projets et expériences :

Il est capable d'analyser un problème avec méthode (AC 1), en formalisant et modélisant des situations complexes (CE 1)

Contexte : Dans le cadre de la SAE 2.01, j'ai développé une application de gestion de graphes MPM (Méthode du Chemin Critique). Ce projet m'a permis d'analyser méthodiquement un problème complexe de modélisation et de structuration de données.

Réalisation : J'ai conçu une architecture modulaire en 5 étapes pour le chargement et l'initialisation de données structurées : lecture de fichier, validation syntaxique, construction des structures, validation sémantique, et initialisation du graphe. Cette approche démontre ma capacité à formaliser et modéliser des situations complexes.

🛠️ Architecture modulaire développée

Méthode de chargement principal

Architecture modulaire - Point d'entrée du système

Calcul des niveaux - Validation structurelle

Analyse et structuration des données

Calcul des dates - Algorithme MPM

Implémentation de l'algorithme de chemin critique

Détermination du chemin critique

Optimisation et identification du chemin critique

Organisation finale par niveaux

Structure finale et mise à disposition du modèle

Il est capable de comparer des algorithmes pour des problèmes classiques (AC 2), en recensant les algorithmes et les structures de données usuels (CE 2)

Contexte : Dans le cadre des algorithmes fondamentaux, j'ai étudié et implémenté plusieurs méthodes de tri afin de comparer leurs performances et comprendre leurs cas d'usage optimaux.

Démarche : J'ai analysé trois algorithmes de tri classiques (tri par sélection, tri à bulles, tri par insertion) et comparé leurs performances dans différents contextes d'utilisation.

Compétences développées : Analyse algorithmique, optimisation de code, analyse de complexité temporelle et spatiale.

🔍 Algorithmes et structures étudiés

Tri par sélection

Fonctionnement : Pour chaque position du tableau, cet algorithme :

Identifie l'élément minimal dans la portion non triée
Échange cet élément avec celui en début de portion non triée
Avance d'une position et répète jusqu'à la fin

L'algorithme maintient deux sous-tableaux : une portion déjà triée et une portion à trier. Sa complexité est de O(n²) invariablement, mais avec seulement n échanges au maximum.

Tri à bulles

Fonctionnement : Cet algorithme procède par passes successives :

Parcourt le tableau en comparant deux éléments adjacents
Si un élément est plus grand que le suivant, les échange
Répète jusqu'à ce que le plus grand élément ait "remonté" à la fin
Recommence sur la portion non triée (sans l'élément placé)

Chaque passe "fait remonter" une bulle (l'élément le plus grand) jusqu'à sa position finale. Sa complexité est de O(n²) en moyenne, mais peut s'arrêter plus tôt si le tableau est déjà trié.

Tri par insertion

Fonctionnement : Similaire à trier des cartes à jouer en main :

Prend un élément de la portion non triée
Le stocke temporairement dans une variable
Décale les éléments plus grands vers la droite
Insère l'élément stocké à la position correcte

L'algorithme construit progressivement un tableau trié en insérant chaque élément à sa place. Sa complexité est de O(n²) dans le pire cas, mais très efficace (O(n)) quand le tableau est presque trié.

📊 Analyse comparative

Tableau récapitulatif

Graphique de comparaison des temps d'exécution

💡 Observations et leçons tirées

Cette analyse comparative m'a permis de comprendre que le choix d'un algorithme dépend fortement du contexte d'utilisation :

Tri par insertion : Optimal pour les tableaux de petite taille ou presque triés
Tri par sélection : Avantage d'un nombre d'échanges minimal
Tri à bulles : Simple à implémenter mais généralement moins performant

Cette étude m'a appris l'importance de l'analyse de complexité et la nécessité d'adapter l'algorithme aux caractéristiques spécifiques du problème à résoudre.

Il a appris à formaliser et à mettre en œuvre des outils mathématiques pour l'informatique (AC 3)

Contexte : Lors d'un devoir surveillé de développement, j'ai dû implémenter un calcul de distance entre deux points en utilisant une formalisation mathématique. Ce projet m'a permis de mettre en œuvre concrètement des outils mathématiques pour résoudre un problème informatique.

Réalisation : J'ai formalisé et implémenté le théorème de Pythagore pour calculer la distance euclidienne entre deux points. La formule mathématique h² = a² + b² a été adaptée en informatique sous la forme : distance = √((A.x - B.x)² + (A.y - B.y)²)

📊 Implémentation du calcul de distance

Énoncé de l'exercice

Énoncé du devoir - Application du théorème de Pythagore

Implémentation et résultat

Code de calcul de distance avec validation des résultats

Résultat de l'exécution

Résultat du calcul de distance entre deux points

Il est capable de s'appuyer sur des schémas de raisonnement (CE 3)

Contexte : Dans le cadre d'une SAE, j'ai dû concevoir et implémenter un placement dynamique des tâches MPM. Ce projet nécessitait une optimisation algorithmique pour assurer un affichage clair et lisible du graphe.

Compétences développées : Analyse des contraintes de placement, optimisation de l'affichage graphique, algorithmes de positionnement, gestion des cas particuliers et chevauchements, tests et validation visuelle des résultats.

📊 Conception du placement dynamique

Schéma conceptuel d'organisation

Schéma de l'algorithme de placement par niveaux

Analyse des cas de positionnement

Détermination des différents cas de placement et leurs solutions

💻 Implémentation de l'algorithme

Algorithme de placement initial

Implémentation du placement dynamique des tâches

🎯 Résultat final

Rendu graphique optimisé

Affichage final du graphe MPM avec placement optimisé

💡 Bilan et apprentissages

Ce projet m'a permis de mettre en application des concepts d'optimisation d'affichage graphique en tenant compte de multiples contraintes :

Lisibilité : Chaque tâche devait être clairement visible et identifiable
Cohérence : Les relations entre tâches devaient être visuellement évidentes
Optimisation spatiale : L'espace disponible devait être utilisé efficacement
Évolutivité : L'algorithme devait s'adapter à différentes tailles et complexités de graphes

Cette expérience a renforcé ma capacité à concevoir des solutions algorithmiques optimisées pour résoudre des problèmes complexes de visualisation de données structurées.

Il a appris à justifier ses choix et à valider les résultats (CE 4)

Contexte : Dans le cadre d'une SAE en groupe, nous avons dû concevoir et comparer 2 types d'horloges : une stockant le temps en secondes et une autre avec 3 attributs (heures, minutes, secondes) et rédiger un rapport d'analyse.

Compétences développées : J'ai pu comprendre comment rédiger un rapport d'analyse d'algorithme mais aussi comment optimiser un programme, notamment en gérant les attributs d'une meilleure façon pour répondre aux exigences de performance et de lisibilité.

📊 Comparaison des implémentations

Version avec attributs multiples - Horloge Normale

Horloge normale - Stockage par attributs séparés

Implémentation avec 3 attributs (heure, minutes, secondes) - Accès direct optimisé

🎯 Caractéristiques de l'Horloge Normale

Stockage : 3 entiers séparés (int heure, int minutes, int secondes)
Avantage : Accès direct sans calcul pour l'affichage standard
Inconvénient : Calculs plus complexes pour les opérations

Version stockage unifié - Horloge Seconde

Horloge avec secondes - Stockage en secondes totales

Implémentation avec stockage en secondes totales - Calculs temporels simplifiés

🎯 Caractéristiques de l'Horloge Seconde

Stockage : 1 entier représentant le temps total en secondes
Avantage : Calculs temporels simplifiés, cohérence arithmétique
Inconvénient : Nécessite des conversions pour l'affichage

Rapport d'analyse comparative

📄 Document d'analyse

📎 Consulter le rapport complet (PDF)

Ce rapport détaille notre analyse comparative des deux implémentations, incluant les mesures de performance, les avantages et inconvénients de chaque approche, et nos recommandations selon les cas d'usage.

💡 Synthèse et apprentissages

Ce projet m'a permis de comprendre l'importance des choix de structure de données dans la conception logicielle. J'ai appris que le choix d'une représentation interne des données doit être guidé par l'usage prévu du programme :

Horloge Normale : Plus intuitive pour l'affichage et la lecture, mais moins adaptée aux calculs
Horloge Seconde : Plus performante pour les opérations mathématiques, mais nécessitant des conversions pour l'affichage

Cette expérience m'a également enseigné comment structurer une analyse comparative rigoureuse et justifier des choix techniques basés sur des critères objectifs plutôt que sur des préférences personnelles.