{"id":689,"date":"2020-12-15T23:03:32","date_gmt":"2020-12-15T22:03:32","guid":{"rendered":"http:\/\/maths-code.fr\/cours\/?page_id=689"},"modified":"2025-02-04T10:39:05","modified_gmt":"2025-02-04T09:39:05","slug":"type-abstrait-de-donnee","status":"publish","type":"page","link":"https:\/\/maths-code.fr\/cours\/type-abstrait-de-donnee\/","title":{"rendered":"Type abstrait de donn\u00e9e"},"content":{"rendered":"\n<p>Un type de donn\u00e9es abstrait est la description d\u2019un ensemble organis\u00e9 d\u2019objets et des op\u00e9rations de manipulation sur cet ensemble (les primitives). Ces op\u00e9rations comprennent les moyens d\u2019acc\u00e9der aux \u00e9l\u00e9ments de l\u2019ensemble, et aussi, lorsque l\u2019objet est dynamique, les possibilit\u00e9s de le modifier.<br>L&rsquo;ensemble de ces op\u00e9rations est appel\u00e9 <strong>interface<\/strong>. il est g\u00e9n\u00e9ralement constitu\u00e9 des 4 op\u00e9rations \u00e9l\u00e9mentaires suivantes:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Cr\u00e9er une donn\u00e9e.<\/li>\n\n\n\n<li>Lire une donn\u00e9e.<\/li>\n\n\n\n<li>Modifier une donn\u00e9e.<\/li>\n\n\n\n<li>Supprimer une donn\u00e9e.<\/li>\n<\/ul>\n\n\n\n<p>Avec ces d\u00e9finitions, une structure de donn\u00e9es est la r\u00e9alisation, l\u2019impl\u00e9mentation explicite d\u2019un type de donn\u00e9es.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>D\u00e9crire un type abstrait de donn\u00e9es, le <strong>sp\u00e9cifier<\/strong>, c\u2019est d\u00e9crire les op\u00e9rations possibles et licites, et leur effet.<br>D\u00e9crire une structure de donn\u00e9es, c\u2019est expliciter comment les objets sont repr\u00e9sent\u00e9s et comment les op\u00e9rations sont impl\u00e9ment\u00e9es. Pour l&rsquo;\u00e9valuation d\u2019algorithmes, il importe&nbsp; de conna\u00eetre leur co\u00fbt en temps et en place.<br><em>(D. Beauquier, J. Berstel, Ph. Chr\u00e9tienne, El\u00e9ments d&rsquo;algorithmique)<\/em><\/p>\n<\/blockquote>\n\n\n\n<p><em>Remarque: Nous n&rsquo;\u00e9voquerons que la complexit\u00e9 en temps des primitives.<br><\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Structures lin\u00e9aires<\/h3>\n\n\n\n<p>Listes, piles, et files sont des types lin\u00e9aires.<br>Les piles et files sont des types de donn\u00e9es simples mais pr\u00e9sents partout:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Dans une pile, le dernier \u00e9l\u00e9ment entr\u00e9 est le premier sorti: <em>First In First Out<\/em>.<br><strong>Exemples<\/strong>: Pile d&rsquo;appel r\u00e9cursifs, bouton de retour en arri\u00e8re d&rsquo;un navigateur.<\/li>\n\n\n\n<li>Dans une file, le dernier \u00e9l\u00e9ment entr\u00e9 est le dernier sorti: <em>Last in Last Out<\/em>.<br><strong>Exemples<\/strong>: File d&rsquo;attente pour l&rsquo;impression.<hr><\/li>\n\n\n\n<li><a title=\"cours sur les Piles, files et les listes.\" href=\"http:\/\/maths-code.fr\/NSI\/terminale\/TAD\/TAD_eleve.pdf\">Cours sur les Piles, files et les listes.<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/maths-code.fr\/NSI\/terminale\/TAD\/Exo_File_BAC2023.pdf\">TP 1 extrait d&rsquo;un sujet de BAC <\/a>(files).<\/li>\n\n\n\n<li><a href=\"https:\/\/maths-code.fr\/NSI\/terminale\/TAD\/tri_crepe.pdf\">TP 2 sur les piles : Le tri du cr\u00eapier -adapt\u00e9 d&rsquo;un sujet de BAC.<\/a><\/li>\n\n\n\n<li><a title=\"TP sur les piles\" href=\"http:\/\/maths-code.fr\/NSI\/terminale\/TAD\/Pilefile\/TP-pile.pdf\">TP 3 sur les piles : Le Labyrinthe<\/a><\/li>\n\n\n\n<li><a title=\"TP sur les files\" href=\"http:\/\/maths-code.fr\/NSI\/terminale\/TAD\/Pilefile\/TP-file.pdf\">TP 4 sur les files<\/a>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Structures hi\u00e9rarchiques<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Les <a title=\"graphes\" href=\"https:\/\/maths-code.fr\/cours\/wp-admin\/post.php?post=216&amp;action=edit\">graphes<\/a>.<\/li>\n\n\n\n<li>Les arbres.<br><hr><\/li>\n<\/ul>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un type de donn\u00e9es abstrait est la description d\u2019un ensemble organis\u00e9 d\u2019objets et des op\u00e9rations de manipulation sur cet ensemble (les primitives). Ces op\u00e9rations comprennent les moyens d\u2019acc\u00e9der aux \u00e9l\u00e9ments de l\u2019ensemble, et aussi, lorsque l\u2019objet est dynamique, les possibilit\u00e9s de le modifier.L&rsquo;ensemble de ces op\u00e9rations est appel\u00e9 interface. il est g\u00e9n\u00e9ralement constitu\u00e9 des 4 op\u00e9rations \u00e9l\u00e9mentaires suivantes: Avec ces d\u00e9finitions, une structure de donn\u00e9es est la r\u00e9alisation, l\u2019impl\u00e9mentation explicite d\u2019un type de donn\u00e9es. D\u00e9crire un type abstrait de donn\u00e9es, le sp\u00e9cifier, c\u2019est d\u00e9crire les op\u00e9rations possibles et licites, et leur effet.D\u00e9crire une structure de donn\u00e9es, c\u2019est expliciter comment les objets sont repr\u00e9sent\u00e9s et comment les op\u00e9rations sont impl\u00e9ment\u00e9es. Pour l&rsquo;\u00e9valuation d\u2019algorithmes, il importe&nbsp; de conna\u00eetre leur co\u00fbt en temps et en place.(D. Beauquier, J. Berstel, Ph. Chr\u00e9tienne, El\u00e9ments d&rsquo;algorithmique) Remarque: Nous n&rsquo;\u00e9voquerons que la complexit\u00e9 en temps des primitives. Structures lin\u00e9aires Listes, piles, et files sont des types lin\u00e9aires.Les piles et files sont des types de donn\u00e9es simples mais pr\u00e9sents partout: Structures hi\u00e9rarchiques<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"class_list":["post-689","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/689","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/comments?post=689"}],"version-history":[{"count":34,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/689\/revisions"}],"predecessor-version":[{"id":6364,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/689\/revisions\/6364"}],"wp:attachment":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/media?parent=689"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}