Introduction

Une carte d'une ville avec une ligne bleue reliant deux points. À côté de la barre de recherche, une étiquette indique « Autocomplétion ». À côté de la ligne bleue, une étiquette indique « Itinéraire de navigation ». À côté du reste de la carte, une étiquette indique « Coordination des lieux, des emplacements et des données cartographiques »

Figure 3.1 Les applications de cartographie en ligne représentent les lieux, les emplacements et les données cartographiques tout en offrant la fonctionnalité de regarder autour, de rechercher des lieux et d'obtenir des itinéraires de navigation. La bonne combinaison de structures de données pour gérer des collections de lieux, d'emplacements et de données cartographiques, ainsi que des algorithmes de recherche et de navigation efficaces, contribuera à optimiser l'expérience des utilisateurs qui tentent de s'orienter sur la carte et permettra également une utilisation optimale des ressources informatiques. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0 ; source des données : OpenStreetMap sous licence Open Database ; source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Plan du chapitre

3.1 Introduction aux structures de données et aux algorithmes

3.2 Conception et découverte d'algorithmes

3.3 Propriétés formelles des algorithmes

3.4 Paradigmes algorithmiques

3.5 Exemples d'algorithmes par problème

3.6 Théorie de l'informatique

Les cartes en ligne aident les gens à naviguer dans un monde en évolution rapide. Il n'y a pas si longtemps, les cartes étaient sur papier et les connaissances provenaient de sources fiables non numériques. Dans ce chapitre, nous étudierons comment les informaticiens conçoivent et analysent les structures fondamentales qui sous-tendent de nombreuses technologies actuelles. Les structures de données et les algorithmes sont non seulement fondamentaux pour les applications de cartographie, mais ils permettent également une variété étonnante d'autres technologies. Des voitures autonomes à la gestion des stocks, en passant par la simulation du mouvement des galaxies et le transfert de données entre ordinateurs, toutes ces applications utilisent des structures de données et des algorithmes pour organiser et traiter efficacement de grandes quantités d'informations.