Algorithme d'Euclide

développé avec l’essor des ordinateurs et de la programmation, mais il existait depuis longtemps déjà : songer à l’algorithme d’Euclide, par exemple. Il a atteint une maturité certaine et a, maintenant, un contenu classique qu’il faut connaître. Cependant, c’est une science non figée qui continue d’évoluer, et les chercheurs dé- couvrent, constamment, de nouveaux algorithmes et structures de données. De même, la programmation n’est plus une science mineure, et son importance est considérable, à la

notions essentielles de programmation y sont introduites de fa¸con volontairement non exhaustive, dans le but de favoriser une acquisition correcte, rapide et intuitive des concepts fondamentaux n´ecessaires ` a la mise en œuvre en Java des algorithmes ´etudi´es par la suite. ii Table des mati` eres I Pour d´ ebuter rapidement en Java 1 1 Fondements 1.1 Repr´esentation des donn´ees en machine . . . . . . . . . . . . . . . 1.1.1 La m´emoire . . . . . . . . . . . . . . .

le code] Dans l'usage contemporain, le substantif « informatique » devient un mot polysémique qui désigne autant le domaine industriel en rapport avec l'ordinateur (au sens de calculateur fonctionnant avec des algorithmes), que la science du traitement des informations par des algorithmes. Les expressions « science informatique », « informatique fondamentale » ou « informatique théorique » sont utilisées pour désigner sans ambiguïté la science, tandis que « technologies de l'information » ou « technologies

d´compression et les pertes . . . . . . . . . . . e 1.1.6 Les d´fauts de ce code . . . . . . . . . . . . . . . . e 1.1.7 Ordres de grandeur et complexit´ des algorithmes e Taille des nombres . . . . . . . . . . . . . . . . . . La vitesse des ordinateurs . . . . . . . . . . . . . . Taille et ˆge de l’univers . . . . . . . . . . . . . . . a Complexit´ des algorithmes . . . . . . . . . . . . . e 1.2 Codage par flot et probabilit´s . . . . . . . . . . . . . . . e 1.2.1 Le code de Vernam . . . . . . . . . . . . .

sémantique Dans l'usage contemporain, le substantif « informatique » devient un mot polysémique qui désigne autant le domaine industriel en rapport avec l'ordinateur (au sens de calculateur fonctionnant avec des algorithmes), que la science du traitement des informations par des algorithmes. Les expressions « science informatique », « informatique fondamentale » ou « informatique théorique » sont utilisées pour désigner sans ambiguïté la science, tandis que « technologies de l'information » ou « technologies

expansion rel`eve n´eanmoins quelques exigences dantesques, notamment en mati`ere de s´ecurit´e et de chiffrement. Beaucoup de cryptosyst`emes, comme le RSA reposent sur le fait qu’il n’existe aucun algorithme permettant la factorisation d’entiers en un temps raisonnable. L’existence d’un tel algorithme compromettrait donc la validit´e de ces cryptosyst`emes et potentiellement la s´ecurit´e informatique mondiale. Dans les ann´ees 70, il ´etait consid´er´e comme impossible de factoriser un simple

Perrin – Ugine – Savoie Francois.Thirioux@ac-grenoble.fr 2012-2013 version du 19 février 2013 Préambule Pratique d’un cours polycopié Le polycopié n’est qu’un résumé de cours. Il ne contient pas tous les schémas, exercices d’application, algorithmes ou compléments prodigués en classe. Il est indispensable de tenir des notes de cours afin de le compléter. Compléments Certains passages vont au-delà des objectifs exigibles du programme de terminale S. Le programme complet (B.O. spécial n°8 du 13/10/2011)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Algorithmes de parcours d’un arbre binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.4 Arbres binaires de recherche (ABOH = Arbres Binaires Ordonnés Horizontalement) . . . . . Énoncés des exercices et des problèmes . . .

et les spéculations philosophiques, ont fait preuve d'abstraction. Deux branches se sont distinguées, l'arithmétique et la géométrie. Ont été formalisées les notions de démonstration et de définition axiomatique des objets d'étude. Les Éléments d'Euclide[5] relatent d'une partie des connaissances géométriques en Grèce au IIIe siècle avant notre ère. La civilisation islamique a permis la conservation de l'héritage grec et l'interfécondation avec les découvertes chinoises et indiennes, notamment en

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 65 68 70 70 71 72 7 Introduction a ` la complexit´ e des algorithmes 7.1 Complexit´e des algorithmes . . . . . . . . . . . . . . . . . . 7.2 Calculs ´el´ementaires de complexit´e . . . . . . . . . . . . . . 7.3 Quelques algorithmes sur les tableaux . . . . . . . . . . . . 7.3.1 Recherche du plus petit ´el´ement . . . . . . . . . . . 7.3.2 Recherche dichotomique . . . . . . . . . . . . . . .