{"id":20053,"date":"2024-02-07T06:50:52","date_gmt":"2024-02-07T05:50:52","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=20053"},"modified":"2024-02-13T07:26:15","modified_gmt":"2024-02-13T06:26:15","slug":"exercices-hachage","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/software-analysis\/chopping-exercises\/","title":{"rendered":"3 Corrected Hashing Exercises"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"20053\" class=\"elementor elementor-20053\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4d79fe1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4d79fe1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-fb5e37a\" data-id=\"fb5e37a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-87a9781 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"87a9781\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/analyse-logicielle\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Analyse Logicielle<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-e44cb51\" data-id=\"e44cb51\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b4cac5a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b4cac5a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-fdd7719\" data-id=\"fdd7719\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b4f8d2d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b4f8d2d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/UML_(informatique)\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-68ae044 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"68ae044\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ffa8e6d\" data-id=\"ffa8e6d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-36e331c elementor-widget elementor-widget-heading\" data-id=\"36e331c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/chopping-exercises\/#Exercices-Corriges-sur-le-Hachage-dans-une-base-de-donnees\" >Exercices Corrig\u00e9s sur le Hachage dans une base de donn\u00e9es<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/chopping-exercises\/#Introduction-sur-le-Hachage\" >Introduction sur le Hachage<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/chopping-exercises\/#Exercice-Hachage-statique\" >Exercice Hachage statique<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/chopping-exercises\/#Exercice-Hachage-dynamique\" >Exercice Hachage dynamique<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/chopping-exercises\/#Exercice-Hachage-multicritere\" >Exercice Hachage multicrit\u00e8re<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-Corriges-sur-le-Hachage-dans-une-base-de-donnees\"><\/span>Exercices Corrig\u00e9s sur le Hachage dans une base de donn\u00e9es<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0e76101 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0e76101\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a0fbcb3\" data-id=\"a0fbcb3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-89f36c2 elementor-widget elementor-widget-text-editor\" data-id=\"89f36c2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Le Hachage est particulier au logiciel utilis\u00e9, les exercices corrig\u00e9s suivant explorent les techniques les plus utilis\u00e9es.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"hachage indexation\" width=\"97\" height=\"97\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d1b850f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d1b850f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-81e4d7a\" data-id=\"81e4d7a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6d302c5 elementor-widget elementor-widget-heading\" data-id=\"6d302c5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Introduction-sur-le-Hachage\"><\/span>Introduction sur le Hachage<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-aa7bf98 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"aa7bf98\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a664dc1\" data-id=\"a664dc1\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8afefb9 elementor-widget elementor-widget-text-editor\" data-id=\"8afefb9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Les articles d&rsquo;un <em>fichier al\u00e9atoire<\/em> (on parle \u00e9galement de <em>fichier hach\u00e9<\/em>) sont r\u00e9partis dans des <em>paquets<\/em> compos\u00e9s d&rsquo;une ou plusieurs pages disque. Une fonction de hachage h associe \u00e0 une valeur de cl\u00e9 (discriminante ou non) un entier repr\u00e9sentant un num\u00e9ro de paquet. Tous les articles dont la valeur de cl\u00e9 est telle que la fonction h associe un m\u00eame num\u00e9ro de paquet sont stock\u00e9s ensemble dans ce paquet.\u00a0<\/p><p>Lors d&rsquo;une recherche sur une cl\u00e9 d&rsquo;acc\u00e8s, la fonction h d\u00e9termine de fa\u00e7on unique le paquet contenant tous les articles r\u00e9pondant au crit\u00e8re de recherche. Cette fonction h est rarement injective. Soient c1 et c2 deux cl\u00e9s diff\u00e9rentes, on appelle collision le fait que h(c1) = h(c2).\u00a0<\/p><p>Ce ph\u00e9nom\u00e8ne de collision impose d&rsquo;une part de v\u00e9rifier que chaque article acc\u00e9d\u00e9 satisfait bien le crit\u00e8re de recherche et d&rsquo;autre part rend difficile l&rsquo;\u00e9qui-r\u00e9partition des articles dans les diff\u00e9rents paquets, compliquant la gestion de la m\u00e9moire secondaire. De plus, la fonction h conserve rarement l&rsquo;ordre des cl\u00e9s (c1&lt;c2\u00a0=\/=&gt;\u00a0h(c1)&lt;h(c2)), rendant impossibles les recherches avec un crit\u00e8re d&rsquo;in\u00e9galit\u00e9.<\/p><p>La premi\u00e8re section de cette partie est consacr\u00e9e \u00e0 l&rsquo;\u00e9tude des <em>organisations par hachage statique<\/em> dans lesquelles le nombre de paquets de hachage est fix\u00e9 statiquement \u00e0 la cr\u00e9ation du fichier. L&rsquo;in\u00e9qui-r\u00e9partition des articles dans les diff\u00e9rents paquets peut entra\u00eener le d\u00e9bordement de certains paquets satur\u00e9s, d\u00e9gradant de fa\u00e7on importante les performances des op\u00e9rations de recherche et d&rsquo;insertion d&rsquo;articles dans le fichier.\u00a0<\/p><p>La seconde section de ce th\u00e8me pr\u00e9sente les <em>organisations par hachage dynamique<\/em> \u00e9vitant ce probl\u00e8me au prix d&rsquo;une plus grande <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">complexit\u00e9<\/a> des m\u00e9canismes mis en oeuvre.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ddccb6f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ddccb6f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5ace195\" data-id=\"5ace195\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7421ecc elementor-widget elementor-widget-heading\" data-id=\"7421ecc\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-Hachage-statique\"><\/span>Exercice Hachage statique<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2ff9260 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2ff9260\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f479c50\" data-id=\"f479c50\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7c4f3bb elementor-widget elementor-widget-text-editor\" data-id=\"7c4f3bb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Un fichier organis\u00e9 par hachage statique est d\u00e9compos\u00e9 en N paquets de taille fixe lors de sa cr\u00e9ation. La fonction de hachage associ\u00e9e d\u00e9termine pour chaque valeur de cl\u00e9 d&rsquo;acc\u00e8s un num\u00e9ro de paquet compris entre 0 et N-1. Le choix de la fonction de hachage est primordial pour assurer une \u00e9qui-r\u00e9partition des articles dans les N paquets.\u00a0<\/p><p>Ce choix doit \u00eatre guid\u00e9 par la distribution, rarement uniforme, des cl\u00e9s dans le fichier. Le nombre de collisions (c1 diff c2 et h(c1) = h(c2)) est d&rsquo;autant plus grand que le nombre de paquets de hachage est petit par rapport au nombre d&rsquo;articles \u00e0 ins\u00e9rer dans le fichier. Les collisions vont provoquer une saturation de certains paquets de hachage et entra\u00eener le d\u00e9bordement de ces paquets.<\/p><p><strong>Question 1<\/strong><\/p><p>Quels sont les crit\u00e8res permettant de choisir la taille d&rsquo;un paquet de hachage ? Proposer un format de stockage des articles dans un paquet de hachage.<\/p><p><strong>Question 2<\/strong><\/p><p>Proposer diff\u00e9rentes formes de fonctions de hachage produisant des nombres al\u00e9atoires compris entre 0 et N-1 \u00e0 partir d&rsquo;une cl\u00e9 d&rsquo;acc\u00e8s.<\/p><p><strong>Question 3<\/strong><\/p><p>On suppose dans un premier temps que les paquets satur\u00e9s d\u00e9bordent dans les paquets non encore satur\u00e9s. Proposer diff\u00e9rentes techniques permettant de stocker et de retrouver ult\u00e9rieurement des articles en d\u00e9bordement. Ces techniques sont-elles adapt\u00e9es dans le cas de collisions nombreuses ?<\/p><p><strong>Question 4<\/strong><\/p><p>On consid\u00e8re d\u00e9sormais que le fichier comporte une zone ind\u00e9pendante de d\u00e9bordement dont la taille est fix\u00e9e \u00e0 la cr\u00e9ation du fichier. Les N paquets de hachage initiaux sont appel\u00e9s <em>zone primaire <\/em>afin de les distinguer de la <em>zone de d\u00e9bordement<\/em>.<\/p><p>Proposer de nouvelles techniques de d\u00e9bordement exploitant ce d\u00e9coupage en deux zones ind\u00e9pendantes. Quel est l&rsquo;apport de ces techniques par rapport \u00e0 celles introduites dans la question pr\u00e9c\u00e9dente ? Ces techniques r\u00e9solvent-elles de fa\u00e7on compl\u00e8tement satisfaisante le probl\u00e8me des collisions ? Conclure sur les avantages et inconv\u00e9nients des organisations statiques.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-19c3cb5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"19c3cb5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f87a3e5\" data-id=\"f87a3e5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e9e8167 elementor-widget elementor-widget-toggle\" data-id=\"e9e8167\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2451\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2451\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2451\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2451\"><p><strong>Question 1\u00a0\u00a0\u00a0<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>La taille d&rsquo;un paquet de hachage doit \u00eatre la plus grande possible afin de limiter les d\u00e9bordements en cas de collision. En revanche, un paquet doit pouvoir \u00eatre lu en une seule E\/S. La taille d&rsquo;un paquet de hachage est donc limit\u00e9e par la taille d&rsquo;une page disque (consid\u00e9r\u00e9e comme l&rsquo;unit\u00e9 d&rsquo;E\/S). Les informations de d\u00e9bordement d\u00e9pendent de la strat\u00e9gie employ\u00e9e (bit indicateur de d\u00e9bordement ou num\u00e9ro du premier paquet de d\u00e9bordement (cf. Question 3).<\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-20056 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd42.png\" alt=\"BDD hachage statique\" width=\"611\" height=\"103\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd42.png 611w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd42-300x51.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd42-18x3.png 18w\" sizes=\"(max-width: 611px) 100vw, 611px\" \/><\/p><p><strong>Question 2<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>De nombreuses fonctions de hachage sont envisageables pour d\u00e9terminer un num\u00e9ro de paquet compris entre 0 et N-1 \u00e0 partir d&rsquo;une valeur de cl\u00e9. Les plus courantes sont :<\/p><p><em>\u2013 Division enti\u00e8re:<\/em> c&rsquo;est la fonction la plus simple et la plus fr\u00e9quemment employ\u00e9e. Le r\u00e9sultat de cette fonction, couramment appel\u00e9e <em>modulo<\/em>, est le reste de la division enti\u00e8re de la cl\u00e9 par le nombre de paquets de hachage N. Il est recommand\u00e9 de s&rsquo;assurer que N est un nombre premier afin de limiter les risques de collisions. A titre d&rsquo;exemple, soit un fichier hach\u00e9 dans 11 paquets, l&rsquo;article de cl\u00e9 35 sera plac\u00e9 dans le paquet num\u00e9ro\u00a0 2 (2\u00a0=\u00a035 modulo\u00a011). Si la cl\u00e9 d&rsquo;acc\u00e8s n&rsquo;est pas num\u00e9rique, la fonction modulo est appliqu\u00e9e \u00e0 la repr\u00e9sentation binaire de cette cl\u00e9, consid\u00e9r\u00e9e comme un entier.<\/p><p><em>\u2013 Extraction du carr\u00e9: <\/em>la cl\u00e9 est tout d&rsquo;abord \u00e9lev\u00e9e au carr\u00e9 puis un ensemble de bits (g\u00e9n\u00e9ralement les bits de poids faibles ou de poids moyens) est extrait du nombre obtenu pour former un num\u00e9ro de paquet. Etant donn\u00e9 que k bits permettent d&rsquo;adresser 2k\u00a0paquets, on extraira log_2 N bits pour former un num\u00e9ro de paquet compris entre 0 et N-1.<\/p><p><em>\u2013 Pliage g\u00e9n\u00e9ralis\u00e9:<\/em> si l&rsquo;on consid\u00e8re qu&rsquo;un num\u00e9ro de paquet est exprim\u00e9 par p bits (avec p\u00a0=\u00a0log2N), on divise la cl\u00e9 par tranches de p bits et on applique une op\u00e9ration binaire \u00ab\u00a0ou\u00a0exclusif\u00a0\u00bb entre toutes ces tranches afin d&rsquo;obtenir une nouvelle cha\u00eene de p bits identifiant un paquet. L&rsquo;op\u00e9ration \u00ab\u00a0ou exclusif\u00a0\u00bb est pr\u00e9f\u00e9r\u00e9e \u00e0 l&rsquo;op\u00e9ration \u00ab\u00a0et\u00a0\u00bb qui privil\u00e9gie l&rsquo;apparition de nombreux 0 dans la cha\u00eene de bits r\u00e9sultat et \u00e0 l&rsquo;op\u00e9ration \u00ab\u00a0ou\u00a0\u00bb qui privil\u00e9gie l&rsquo;apparition de nombreux 1.<\/p><p><strong>Question 3<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>Si le paquet d\u00e9sign\u00e9 par la fonction de hachage est satur\u00e9, il faut stocker l&rsquo;article en insertion dans un des N-1 paquets restants et \u00eatre capable de le retrouver ult\u00e9rieurement. Plusieurs techniques de d\u00e9bordement sont envisageables :<\/p><p><em>\u2013 Adressage ouvert:<\/em> supposons que le paquet satur\u00e9 soit le paquet i, cette technique consiste \u00e0 rechercher s\u00e9quentiellement une place libre pour l&rsquo;article en insertion dans les paquets i+1, i+2, \u2026, i+k, jusqu&rsquo;\u00e0 trouver un emplacement de taille suffisante. On m\u00e9morise dans le paquet i le num\u00e9ro du premier paquet dans lequel il a d\u00e9bord\u00e9 afin d&rsquo;acc\u00e9l\u00e9rer les recherches ult\u00e9rieures des articles en d\u00e9bordement. La recherche de tous les articles appartenant au paquet i s&rsquo;effectue de la fa\u00e7on suivante.\u00a0<\/p><p>Les articles stock\u00e9s dans le paquet i sont tout d&rsquo;abord lus s\u00e9quentiellement en v\u00e9rifiant pour chacun d&rsquo;eux qu&rsquo;il appartient bien au paquet i (une comparaison de cl\u00e9 permet d&rsquo;\u00e9liminer les articles d&rsquo;autres paquets stock\u00e9s \u00e9ventuellement en d\u00e9bordement dans le paquet i). Les articles du paquet i stock\u00e9s en d\u00e9bordement sont ensuite recherch\u00e9s s\u00e9quentiellement dans les paquets suivants \u00e0 partir du premier paquet de d\u00e9bordement.<\/p><p><em>\u2013 Cha\u00eenage en d\u00e9bordement:<\/em> cette technique est identique \u00e0 l&rsquo;adressage ouvert mais tous les articles appartenant \u00e0 un m\u00eame paquet sont ici cha\u00een\u00e9s entre eux. Ce cha\u00eenage \u00e9vite le co\u00fbt d&rsquo;une recherche s\u00e9quentielle pour retrouver tous les articles d&rsquo;un m\u00eame paquet stock\u00e9s en d\u00e9bordement. En revanche, outre le co\u00fbt de stockage suppl\u00e9mentaire li\u00e9 au cha\u00eenage,\u00a0 cette technique peut engendrer de nombreuses E\/S si la cha\u00eene des articles est longue et si le cha\u00eenage passe fr\u00e9quemment d&rsquo;un paquet \u00e0 l&rsquo;autre (on peut alors \u00eatre amen\u00e9 \u00e0 lire plusieurs fois le m\u00eame paquet). Dans le pire des cas, le parcours du cha\u00eenage peut g\u00e9n\u00e9rer une E\/S pour r\u00e9cup\u00e9rer chaque article (cf. Chapitre 2, question 4).<\/p><p><em>\u2013 Table d&rsquo;adresse des articles en d\u00e9bordement:<\/em> cette technique, tr\u00e8s similaire \u00e0 la technique du cha\u00eenage en d\u00e9bordement, stocke les adresses de tous les articles en d\u00e9bordement dans une table associ\u00e9e \u00e0 chaque paquet. Les adresses stock\u00e9es dans cette table peuvent \u00eatre maintenues tri\u00e9es afin d&rsquo;\u00e9viter plusieurs lectures d&rsquo;un m\u00eame paquet. Cette technique pose cependant le probl\u00e8me de la place occup\u00e9e et de la taille statique de chacune de ces tables.<\/p><p><em>\u2013 Re-hachage:<\/em> si le paquet i d\u00e9borde, on m\u00e9morise dans le paquet le fait qu&rsquo;il a d\u00e9bord\u00e9 et on applique une nouvelle fonction de hachage aux articles devant \u00eatre ins\u00e9r\u00e9s dans ce paquet. Cette seconde fonction g\u00e9n\u00e8re un num\u00e9ro de paquet diff\u00e9rent de i et compris entre 0 et N-1. La recherche de tous les articles appartenant au paquet i s&rsquo;effectue de la fa\u00e7on suivante.\u00a0<\/p><p>Les articles stock\u00e9s dans le paquet i sont tout d&rsquo;abord lus s\u00e9quentiellement en v\u00e9rifiant pour chacun d&rsquo;eux qu&rsquo;il appartient bien au paquet i (afin d&rsquo;\u00e9liminer les articles d&rsquo;autres paquets stock\u00e9s \u00e9ventuellement en d\u00e9bordement dans le paquet i). Les articles du paquet i stock\u00e9s en d\u00e9bordement sont ensuite recherch\u00e9s dans le paquet identifi\u00e9 par la seconde fonction de hachage appliqu\u00e9e \u00e0 la cl\u00e9 d&rsquo;acc\u00e8s.<\/p><p>Ces techniques offrent une r\u00e9ponse au probl\u00e8me de gestion des articles en d\u00e9bordement mais aucune n&rsquo;est vraiment satisfaisante si le taux de collisions est \u00e9lev\u00e9. Les performances se d\u00e9gradent tr\u00e8s rapidement\u00a0 lors des recherches d&rsquo;articles en d\u00e9bordement. Ce ph\u00e9nom\u00e8ne est d\u00fb au fait que les articles en d\u00e9bordement d&rsquo;un paquet\u00a0i sont stock\u00e9s en lieu et place des articles d&rsquo;un paquet\u00a0j, provoquant rapidement un d\u00e9bordement du paquet\u00a0j par une r\u00e9action en cha\u00eene.<\/p><p><strong>Question 4<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>Les techniques de d\u00e9bordement pr\u00e9sent\u00e9es question 3 restent applicables, \u00e0 quelques modifications pr\u00e8s, \u00e0 un fichier poss\u00e9dant une zone de d\u00e9bordement ind\u00e9pendante. Dans le cas de l&rsquo;<em>adressage ouvert<\/em>, le premier emplacement libre permettant de stocker un article en d\u00e9bordement n&rsquo;est plus cherch\u00e9 dans les paquets de hachage primaires suivants mais s\u00e9quentiellement en zone de d\u00e9bordement. Les techniques de <em>cha\u00eenage en d\u00e9bordement<\/em> et de <em>table d&rsquo;adresses des articles en d\u00e9bordement<\/em> restent inchang\u00e9es mais les liens de cha\u00eenage correspondent \u00e0 des adresses en zone de d\u00e9bordement.\u00a0<\/p><p>Enfin, la technique de <em>re-hachage<\/em> n\u00e9cessite de d\u00e9couper la zone de d\u00e9bordement en P paquets de hachage. Ainsi, lors de l&rsquo;insertion d&rsquo;un article dans le fichier, on applique tout d&rsquo;abord une division enti\u00e8re par N \u00e0 sa cl\u00e9 afin de d\u00e9terminer un num\u00e9ro de paquet primaire. Si ce paquet primaire est satur\u00e9, on applique une division enti\u00e8re par P \u00e0 cette m\u00eame cl\u00e9 afin de d\u00e9terminer un num\u00e9ro de paquet secondaire. Si ce paquet secondaire est satur\u00e9 \u00e0 son tour, alors on utilise une des techniques pr\u00e9sent\u00e9es question 3 dans la zone de d\u00e9bordement.<\/p><p>L&rsquo;avantage de s\u00e9parer la zone primaire de la zone de d\u00e9bordement est d&rsquo;\u00e9viter le ph\u00e9nom\u00e8ne de r\u00e9action en cha\u00eene d\u00fb \u00e0 la saturation de certains paquets g\u00e9n\u00e9r\u00e9e par le d\u00e9bordement d&rsquo;autres paquets (cf. question 3). Ici, le d\u00e9bordement d&rsquo;un paquet primaire n&rsquo;influe pas sur le taux d&rsquo;occupation des autres paquets primaires. Cette gestion des d\u00e9bordements est donc plus robuste face \u00e0 un taux \u00e9lev\u00e9 de collisions. Cependant, la recherche des articles en zone de d\u00e9bordement reste une op\u00e9ration co\u00fbteuse.<\/p><p>Conclusion\u00a0: l&rsquo;avantage majeur des organisations al\u00e9atoires statiques est leur simplicit\u00e9 de mise en oeuvre et les excellentes performances qu&rsquo;elles offrent tant que les d\u00e9bordements de paquets sont peu nombreux. En effet, si aucun paquet n&rsquo;a d\u00e9bord\u00e9, les organisations al\u00e9atoires statiques garantissent la recherche de tous les articles ayant une valeur de cl\u00e9 donn\u00e9e en une seule E\/S. En revanche, les d\u00e9bordements provoquent rapidement un effondrement des performances quelle que soit la technique de gestion des d\u00e9bordements employ\u00e9e. Ce probl\u00e8me n\u00e9cessite une r\u00e9organisation p\u00e9riodique des fichiers d\u00e8s que le taux de d\u00e9bordement d\u00e9passe un seuil de tol\u00e9rance donn\u00e9.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2f5656e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2f5656e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-340db76\" data-id=\"340db76\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8799e83 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"8799e83\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e3ce3a0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e3ce3a0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-428feb8\" data-id=\"428feb8\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d57ca10 elementor-widget elementor-widget-heading\" data-id=\"d57ca10\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-Hachage-dynamique\"><\/span>Exercice Hachage dynamique<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8b23dc5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8b23dc5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f59c221\" data-id=\"f59c221\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3778f0c elementor-widget elementor-widget-text-editor\" data-id=\"3778f0c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>L&rsquo;objectif des organisations par hachage dynamique est de minimiser le co\u00fbt des collisions en substituant aux techniques de d\u00e9bordement un accroissement dynamique de la taille du fichier. De tr\u00e8s nombreuses strat\u00e9gies de hachage dynamique ont \u00e9t\u00e9 propos\u00e9es dans la litt\u00e9rature: hachage extensible [Fagin79], hachage lin\u00e9aire [Litwin80] et trie-hashing [Litwin81], pour ne citer que les plus connues.\u00a0<\/p><p>Chacune de ces strat\u00e9gies constitue une adaptation d&rsquo;un principe commun : l&rsquo;exploitation progressive du contenu de la cl\u00e9 d&rsquo;acc\u00e8s. Supposons une cl\u00e9 d&rsquo;acc\u00e8s dont le hachage produit une cha\u00eene de k bits. Le hachage d&rsquo;une telle cl\u00e9 permet d&rsquo;adresser au plus 2^k\u00a0paquets. Le fichier hach\u00e9 est cr\u00e9\u00e9 initialement avec N paquets (N &lt; 2^k) et les articles sont r\u00e9partis dans ces paquets en exploitant uniquement les p premiers bits issus du hachage de leur cl\u00e9 (N=2^p\u00a0et p &lt; k).\u00a0<\/p><p>En cas de saturation, un paquet est \u00e9clat\u00e9 et les articles qu&rsquo;il contient sont r\u00e9partis en deux paquets en exploitant la valeur du (p\u00a0+\u00a01)\u00e8me\u00a0bit issu du hachage de leur cl\u00e9. Les m\u00e9thodes de hachage dynamique se diff\u00e9rencient suivant la strat\u00e9gie employ\u00e9e pour choisir le paquet \u00e0 \u00e9clater \u00e0 chaque saturation.<\/p><p><strong>Question 5<\/strong><\/p><p>Dans la m\u00e9thode du hachage extensible [Fagin79], un paquet est \u00e9clat\u00e9 en deux d\u00e8s l&rsquo;instant o\u00f9 il devient satur\u00e9. On peut repr\u00e9senter l&rsquo;\u00e9tat d&rsquo;un fichier \u00e0 un instant t par un <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">arbre<\/a> d&rsquo;\u00e9clatement dont les n\u0153uds correspondent aux paquets et dont les arcs mat\u00e9rialisent les \u00e9clatements successifs de paquets. La racine de cet arbre poss\u00e8de 2p\u00a0fils repr\u00e9sentant les 2p\u00a0paquets initiaux.\u00a0<\/p><p>Chaque n\u0153ud correspondant \u00e0 un paquet \u00e9clat\u00e9 est \u00e0 son tour p\u00e8re de deux fils repr\u00e9sentant les deux paquets issus de l&rsquo;\u00e9clatement. Les feuilles de l&rsquo;arbre correspondent donc aux paquets r\u00e9ellement occup\u00e9s par le fichier \u00e0 un instant t alors que les n\u0153uds internes correspondent \u00e0 des paquets ayant exist\u00e9 \u00e0 des instants t-1, \u2026, t-n. Chaque arc de l&rsquo;arbre d&rsquo;\u00e9clatement est valu\u00e9 par la <em>signature<\/em> du paquet qu&rsquo;il r\u00e9f\u00e9rence.\u00a0<\/p><p>On appelle signature d&rsquo;un paquet, la valeur de la cha\u00eene de bits partag\u00e9e par les cl\u00e9s de tous les articles stock\u00e9s dans ce paquet. Ainsi, les arcs partant de la racine sont valu\u00e9s par des signatures de p bits ayant comme valeur respective: 0\u202600, 0\u202601, jusqu&rsquo;\u00e0 1\u202611. Par r\u00e9currence, les arcs correspondant au niveau n de l&rsquo;arbre sont valu\u00e9s par des signatures de p+n-1 bits.<\/p><p>On consid\u00e8re un fichier hach\u00e9 poss\u00e9dant 8 paquets initiaux num\u00e9rot\u00e9s de 0 \u00e0 7. Le paquet num\u00e9ro 6 a \u00e9clat\u00e9 en deux paquets fils, le fils gauche a \u00e9clat\u00e9 \u00e0 son tour. Repr\u00e9senter l&rsquo;arbre d&rsquo;\u00e9clatement de ce fichier en pr\u00e9cisant les valuations des arcs et les paquets occup\u00e9s par le fichier.<\/p><p><strong>Question 6<\/strong><\/p><p>L&rsquo;arbre d&rsquo;\u00e9clatement doit \u00eatre m\u00e9moris\u00e9 (sous une forme quelconque) dans une structure de donn\u00e9es syst\u00e8me appel\u00e9e <em>catalogue<\/em>. Le r\u00f4le du catalogue est de d\u00e9terminer rapidement l&rsquo;adresse du paquet dans lequel doit \u00eatre ins\u00e9r\u00e9 un nouvel article ainsi que l&rsquo;adresse du paquet \u00e0 lire lors d&rsquo;une recherche sur cl\u00e9.<\/p><p>Proposer une organisation du catalogue sous forme de table. Illustrer cette organisation du catalogue par rapport \u00e0 l&rsquo;arbre d&rsquo;\u00e9clatement pr\u00e9c\u00e9dent.<\/p><p>En supposant que la fonction de hachage utilis\u00e9e est le modulo, indiquer le principe de recherche dans le catalogue permettant de retrouver tous les articles du fichier dont la valeur de cl\u00e9 est 54, puis tous ceux dont la valeur de cl\u00e9 est 65.<\/p><p><strong>Question 7<\/strong><\/p><p>Lorsque le fichier est tr\u00e8s grand, le catalogue peut ne plus tenir en m\u00e9moire. Proposer une adaptation de la structure pr\u00e9c\u00e9dente qui permette toujours de retrouver l&rsquo;adresse d&rsquo;un paquet (lors d&rsquo;une insertion ou d&rsquo;une recherche) en une E\/S.<\/p><p>Indiquer le principe de mise \u00e0 jour du catalogue lors des \u00e9clatements de paquets. Donner les diff\u00e9rentes versions du catalogue, \u00e0 la cr\u00e9ation du fichier puis apr\u00e8s chacun des deux \u00e9clatements consid\u00e9r\u00e9s dans la question 5. Combien d&rsquo;entr\u00e9es r\u00e9f\u00e9rencent le paquet 000 et quelle est leur signature respective ?<\/p><p>Comment retrouve-t-on maintenant les articles de cl\u00e9 54 et ceux de cl\u00e9 65 ?<\/p><p><strong>Question 8<\/strong><\/p><p>Un fichier organis\u00e9 selon la m\u00e9thode du hachage dynamique a-t-il une limite de taille\u00a0? Si oui, pr\u00e9ciser laquelle, si non, pr\u00e9ciser pourquoi.<\/p><p><strong>Question 9<\/strong><\/p><p>La m\u00e9thode du hachage lin\u00e9aire [Litwin80] est une m\u00e9thode de hachage dynamique \u00e9vitant la gestion d&rsquo;un catalogue. Plut\u00f4t que d&rsquo;\u00e9clater un paquet d\u00e8s saturation comme dans le hachage extensible, les paquets sont \u00e9clat\u00e9s dans un ordre pr\u00e9d\u00e9fini (d&rsquo;o\u00f9 l&rsquo;appellation lin\u00e9aire). Le fichier est compos\u00e9 de N paquets initiaux, num\u00e9rot\u00e9s de 0 \u00e0 N\u20131. Les articles sont plac\u00e9s dans les paquets initiaux par application de la fonction de hachage h0(cl\u00e9) = cl\u00e9 modulo N. Lorsqu&rsquo;un premier paquet d\u00e9borde (par exemple: le paquet i), un paquet vide de num\u00e9ro N est ajout\u00e9 dynamiquement \u00e0 la fin du fichier et le paquet 0 (et non le paquet i) est \u00e9clat\u00e9 en deux par application de la fonction h1(cl\u00e9) = cl\u00e9 modulo 2N.\u00a0<\/p><p>Si la distribution est uniforme, la moiti\u00e9 des articles du paquet 0 seront d\u00e9plac\u00e9s dans le paquet N et les autres articles resteront dans le paquet 0. L&rsquo;article qui a provoqu\u00e9 le d\u00e9bordement du paquet i est cha\u00een\u00e9 en d\u00e9bordement par une technique classique (ex: adressage ouvert). Lorsqu&rsquo;un autre paquet j d\u00e9borde, un nouveau paquet de num\u00e9ro N+1 est ajout\u00e9 en fin de fichier et le paquet 1 est \u00e9clat\u00e9 avec la fonction h1. En proc\u00e9dant ainsi lin\u00e9airement, les paquets i et j seront t\u00f4t ou tard \u00e9clat\u00e9s \u00e0 leur tour. La fonction h1 peut \u00eatre utilis\u00e9e jusqu&rsquo;\u00e0 ce que le fichier ait doubl\u00e9 de taille (tous les paquets de 0 \u00e0 N-1 ont alors \u00e9t\u00e9 \u00e9clat\u00e9s).<\/p><p>\u00a0A chaque doublement de la taille du fichier, les \u00e9clatements recommencent \u00e0 partir du paquet 0 et la fonction de hachage hk-1 est remplac\u00e9e par la fonction\u00a0 hk(cl\u00e9) = cl\u00e9 modulo (2^k N), o\u00f9 k repr\u00e9sente le nombre de fois o\u00f9 le fichier a doubl\u00e9 de taille (k est appel\u00e9 niveau du fichier).<\/p><p>A un instant t, deux fonctions de hachage suffisent pour assurer la gestion du hachage lin\u00e9aire. Quelle est la r\u00e8gle permettant de d\u00e9terminer la fonction de hachage \u00e0 utiliser lors de la recherche ou de l&rsquo;insertion d&rsquo;un article dans le fichier ? Quelles informations syst\u00e8mes doivent \u00eatre maintenues pour permettre la mise en oeuvre de cette r\u00e8gle ?<\/p><p><strong>Question 10<\/strong><\/p><p>Donner l&rsquo;algorithme correspondant \u00e0 la r\u00e8gle \u00e9dict\u00e9e \u00e0 la question\u00a0pr\u00e9c\u00e9dente<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-81f01f2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"81f01f2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-38b6fbb\" data-id=\"38b6fbb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-aebaa51 elementor-widget elementor-widget-toggle\" data-id=\"aebaa51\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1831\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1831\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1831\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1831\"><p><strong>Question 5\u00a0\u00a0<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>L&rsquo;arbre d&rsquo;\u00e9clatement correspondant au fichier d\u00e9crit est repr\u00e9sent\u00e9 sur la figure 5.2. Les paquets gris\u00e9s correspondent aux paquets occup\u00e9s par le fichier \u00e0 l&rsquo;instant t. On peut noter que la cha\u00eene de bits de la signature est d\u00e9velopp\u00e9e de droite \u00e0 gauche. Ceci permet d&rsquo;exploiter en priorit\u00e9 les bits de poids faibles (dont la distribution est g\u00e9n\u00e9ralement plus al\u00e9atoire) des cl\u00e9s de hachage.<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-20058 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd43.png\" alt=\"BDD hachage dynamique\" width=\"309\" height=\"210\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd43.png 309w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd43-300x204.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd43-18x12.png 18w\" sizes=\"(max-width: 309px) 100vw, 309px\" \/><\/p><p><strong>Figure.<\/strong> Arbre d&rsquo;\u00e9clatement valu\u00e9 par les signatures de paquets<\/p><p><strong>Question 6<\/strong><\/p><p>Le catalogue est mat\u00e9rialis\u00e9 par une table assurant la correspondance entre signature et adresse de paquet. Cette table contient une entr\u00e9e pour chaque paquet occup\u00e9 par le fichier \u00e0 un instant t, comme illustr\u00e9 figure 5.3.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20059 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd44.png\" alt=\"BDD hachage dynamique\" width=\"480\" height=\"246\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd44.png 480w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd44-300x154.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd44-18x9.png 18w\" sizes=\"(max-width: 480px) 100vw, 480px\" \/><\/p><p><strong>Figure. <\/strong>Catalogue correspondant \u00e0 l&rsquo;arbre d&rsquo;\u00e9clatement de la question 6<\/p><p>Pour effectuer la recherche de tous les articles ayant une cl\u00e9 donn\u00e9e, il suffit de trouver dans le catalogue l&rsquo;entr\u00e9e dont la signature correspond \u00e0 un pr\u00e9fixe de la cha\u00eene de bits issue du hachage de la cl\u00e9 recherch\u00e9e. Par exemple, la recherche des articles dont la cl\u00e9 est 54 s&rsquo;effectue de la fa\u00e7on suivante. Cinq bits au plus \u00e9tant actuellement exploit\u00e9s dans les signatures de paquet, on applique la fonction de hachage modulo 2<sup>5<\/sup> \u00e0 la cl\u00e9 54. Le r\u00e9sultat du hachage est donc 22 (54 mod 32).\u00a0<\/p><p>En binaire, 22 s&rsquo;\u00e9crit 10110. On recherche donc la signature 10110 dans le catalogue afin de trouver l&rsquo;adresse du paquet correspondant. Il en va de m\u00eame pour retrouver les articles de cl\u00e9 65. 65 modulo 2<sup>5 <\/sup>donne 1, soit en binaire sur 5 bits 00001. L&rsquo;entr\u00e9e 001 du catalogue sera s\u00e9lectionn\u00e9e car c&rsquo;est la seule entr\u00e9e correspondant \u00e0 un pr\u00e9fixe de 00001.<\/p><p><strong>Question 7<\/strong><\/p><p>La structure propos\u00e9e dans la question 7 impose une lecture s\u00e9quentielle du catalogue. Pour pallier cet inconv\u00e9nient, on modifie le principe de mise \u00e0 jour du catalogue. Tant qu&rsquo;il n&rsquo;y a pas eu d&rsquo;\u00e9clatement de paquet, le catalogue contient des signatures de p bits adressant les 2p\u00a0paquets initiaux. Lors du premier \u00e9clatement d&rsquo;un de ces paquets, la taille du catalogue est doubl\u00e9e et on d\u00e9veloppe un bit suppl\u00e9mentaire de chaque signature de sorte que toutes les entr\u00e9es du catalogue contiennent des signatures de p+1 bits.\u00a0<\/p><p>Les deux paquets issus de l&rsquo;\u00e9clatement sont alors r\u00e9f\u00e9renc\u00e9s chacun par une signature distincte de p+1 bits. Un nouvel \u00e9clatement de l&rsquo;un de ces deux paquets entra\u00eenera \u00e0 nouveau un doublement du catalogue. En revanche, les paquets n&rsquo;ayant pas \u00e9clat\u00e9 se trouvent r\u00e9f\u00e9renc\u00e9s par deux signatures de p+1 bits dont les p premiers bits sont identiques. Si l&rsquo;un de ces paquets \u00e9clate \u00e0 son tour, le doublement du catalogue n&rsquo;est pas utile puisque l&rsquo;on dispose d\u00e9j\u00e0 de deux signatures de p+1 bits pour adresser les deux paquets issus de l&rsquo;\u00e9clatement.\u00a0<\/p><p>Dans ce cas, seule l&rsquo;adresse de paquet associ\u00e9e aux deux signatures doit \u00eatre mise \u00e0 jour. La figure 5.4 montre l&rsquo;\u00e9volution du catalogue apr\u00e8s l&rsquo;\u00e9clatement du paquet 110 puis du paquet 0110. Sur cette figure, <em>ai<\/em> repr\u00e9sente l&rsquo;adresse du paquet <em>i<\/em>.<\/p><p>L&rsquo;avantage de ce principe est double. D&rsquo;une part, les doublements du catalogue \u00e9tant rares, l&rsquo;\u00e9clatement d&rsquo;un paquet n\u00e9cessite le plus souvent une simple mise \u00e0 jour des adresses associ\u00e9es aux signatures. D&rsquo;autre part, toutes les signatures ont un nombre identique de bits d\u00e9velopp\u00e9s. Ainsi, si le catalogue est grand et occupe plusieurs pages, il est possible de d\u00e9terminer par calcul dans quelle page se trouve la (ou les) signature(s) recherch\u00e9e(s). Une seule E\/S est donc n\u00e9cessaire pour effectuer la recherche dans le catalogue, quelle que soit sa taille.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20060 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd45.png\" alt=\"BDD hachage dynamique\" width=\"536\" height=\"680\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd45.png 536w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd45-236x300.png 236w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd45-9x12.png 9w\" sizes=\"(max-width: 536px) 100vw, 536px\" \/><\/p><p><strong>Figure .<\/strong> Etapes de l&rsquo;\u00e9volution du catalogue<\/p><p>Le paquet initial 000 est d\u00e9sormais r\u00e9f\u00e9renc\u00e9 par quatre entr\u00e9es contenant la m\u00eame adresse physique mais dont les signatures respectives sont: 00000, 01000, 10000, 11000. On remarque que ces quatre signatures ont le m\u00eame profil xx000.<\/p><p>La recherche des articles de cl\u00e9 54 s&rsquo;effectue comme dans la question 7, \u00e0 savoir que l&rsquo;on s\u00e9lectionne l&rsquo;entr\u00e9e du catalogue de signature 10110. La recherche des articles de cl\u00e9 65 revient \u00e0 s\u00e9lectionner l&rsquo;entr\u00e9e de signature 00001 qui, dans le cas pr\u00e9sent, r\u00e9f\u00e9rence le m\u00eame paquet que les entr\u00e9es de signature : 01001, 10001 et 11001. En effet, le paquet initial 001 n&rsquo;ayant pas \u00e9clat\u00e9, il est r\u00e9f\u00e9renc\u00e9 par toutes les entr\u00e9es dont le profil de signature est 001.<\/p><p>Remarque: l&rsquo;entr\u00e9e du catalogue contenant la signature 10110 est l&rsquo;entr\u00e9e 22 (10110 en binaire). Par cons\u00e9quent, il n&rsquo;est pas utile de stocker les signatures dans ce type de catalogue car cette information est redondante avec le num\u00e9ro de chaque entr\u00e9e.<\/p><p><strong>Question 8<\/strong><\/p><p>Lorsque la signature d&rsquo;un paquet atteint le nombre de bits total de la cha\u00eene de bits issue du hachage de la cl\u00e9, ce paquet ne peut plus \u00eatre \u00e9clat\u00e9 puisque tous les bits des cl\u00e9s des articles qu&rsquo;il contient ont \u00e9t\u00e9 exploit\u00e9s. Le fichier est dans ce cas satur\u00e9. Il est cependant possible de cha\u00eener un paquet de d\u00e9bordement \u00e0 chaque paquet satur\u00e9 afin de permettre leur extension. Dans ce cas, le fichier n&rsquo;a plus de limite th\u00e9orique de taille.<\/p><p><strong>Question 9<\/strong><\/p><p>Afin de d\u00e9terminer le num\u00e9ro du paquet dans lequel doit \u00eatre recherch\u00e9 ou ins\u00e9r\u00e9 un article, il faut conna\u00eetre le niveau k du fichier et savoir si le paquet en question a d\u00e9j\u00e0 \u00e9t\u00e9 \u00e9clat\u00e9 ou non, ceci\u00a0 afin de d\u00e9terminer si l&rsquo;on doit utiliser la fonction de hachage hk\u00a0ou hk+1. Pour cela, on m\u00e9morise dans le descripteur de fichier : le nombre de fois o\u00f9 le fichier a doubl\u00e9 de taille (niveau k du fichier) et la position du pointeur courant d&rsquo;\u00e9clatement r\u00e9f\u00e9ren\u00e7ant le prochain paquet \u00e0 \u00e9clater.\u00a0<\/p><p>Par connaissance du niveau k du fichier, on applique la fonction de hachage hk\u00a0\u00e0 la cl\u00e9 de l&rsquo;article \u00e0 rechercher ou \u00e0 ins\u00e9rer. Si le num\u00e9ro de paquet d\u00e9termin\u00e9 par cette fonction de hachage est inf\u00e9rieur au pointeur courant d&rsquo;\u00e9clatement, alors le paquet correspondant a d\u00e9j\u00e0 \u00e9t\u00e9 \u00e9clat\u00e9 et l&rsquo;on re-hache la cl\u00e9 de l&rsquo;article avec la fonction hk+1. Sinon, le paquet d\u00e9sign\u00e9 par la fonction hk\u00a0peut \u00eatre directement exploit\u00e9.<\/p><p><strong>Question 10 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/strong><\/p><p>L&rsquo;algorithme d\u00e9terminant la fonction de hachage \u00e0 utiliser, lors de la recherche ou de l&rsquo;insertion d&rsquo;un article dans le fichier, prend en entr\u00e9e le descripteur du fichier, la cl\u00e9 de l&rsquo;article et rend en sortie le num\u00e9ro de paquet dans lequel devrait \u00eatre recherch\u00e9 ou ins\u00e9r\u00e9 cet article. La fonction de hachage utilis\u00e9e dans cet <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithme<\/a> est h\u00a0(k,\u00a0cl\u00e9)\u00a0=\u00a0cl\u00e9\u00a0modulo (2k\u00a0N), o\u00f9 le param\u00e8tre k correspond au niveau du fichier.<\/p><p><strong>fonction<\/strong> Calcul_n\u00b0paquet (descrip_fich: descripteur, cl\u00e9:type_cl\u00e9): entier;<\/p><p><strong>var\u00a0\u00a0 <\/strong>numpaquet, k: entier;<\/p><p><strong>d\u00e9but<\/strong><\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 k := descrip_fich.k;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ niveau du fichier<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 numpaquet := h (k, cl\u00e9);<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>si<\/strong> (numpaquet &lt; descrip_fich.pt\u00e9clat) <strong>alors<\/strong> Calcul_n\u00b0paquet := h (k+1, cl\u00e9);<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>sinon<\/strong> Calcul_n\u00b0paquet := numpaquet;<\/p><p><strong>fin<\/strong><\/p><p>L&rsquo;algorithme d&rsquo;insertion d&rsquo;un nouvel article dans un fichier organis\u00e9 selon la m\u00e9thode du hachage lin\u00e9aire est pr\u00e9sent\u00e9 ci-dessous. La fonction Calcul_n\u00b0paquet utilis\u00e9e dans cet algorithme est celle pr\u00e9sent\u00e9e question\u00a010. La fonction Ecrire(article, numpaquet) \u00e9crit l&rsquo;article \u00ab\u00a0article\u00a0\u00bb dans le paquet numpaquet ou le cha\u00eene en d\u00e9bordement si ce paquet est satur\u00e9.<\/p><p><strong>proc\u00e9dure <\/strong>Ins\u00e9rer(descrip_fich: descripteur, cl\u00e9: type_cl\u00e9, article: type_art)<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><\/p><p><strong>var\u00a0\u00a0 <\/strong><\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>numpaquet, nvnumpaquet: entier;\u00a0<\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>k: entier; \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ niveau du fichier \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 pt\u00e9clat: entier;\u00a0\u00a0\u00a0\u00a0 \/\/ pointeur courant d&rsquo;\u00e9clatement \u00a0\u00a0\u00a0<\/p><p><strong>d\u00e9but<\/strong><\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>k := descrip_fich.k;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 pt\u00e9clat := descrip_fich.pt\u00e9clat; numpaquet := Calcul_n\u00b0paquet (descrip_fich, cl\u00e9);<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>si <\/strong>(numpaquet est satur\u00e9) <strong>alors<\/strong><\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>\/\/ \u00e9clater le paquet de num\u00e9ro pt\u00e9clat dans les<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ paquets pt\u00e9clat et (pt\u00e9clat + 2k\u00a0N)<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>pour chaque<\/strong> articlei\u00a0\u00ce pt\u00e9clat <strong>faire<\/strong><\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>nvnumpaquet := h (k+1, articlei.cl\u00e9);<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Ecrire (article, nvnumpaquet);<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>fpour<\/strong><\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 si<\/strong> (numpaquet = pt\u00e9clat) <strong>alors <\/strong>\u00a0<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ d\u00e9terminer si le nouvel article doit \u00eatre ins\u00e9r\u00e9<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ dans le paquet pt\u00e9clat ou (pt\u00e9clat + 2k\u00a0N)<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 numpaquet := h (k+1, article.cl\u00e9);<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>fsi<\/strong><\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>\/\/ incr\u00e9menter le pointeur courant d&rsquo;\u00e9clatement<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>si<\/strong> (pt\u00e9clat = (2k\u00a0N) &#8211; 1)<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>alors <\/strong>\/\/ m-\u00e0-j du\u00a0 niveau du fichier<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 k := k + 1;<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 pt\u00e9clat := 0;<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>sinon <\/strong>pt\u00e9clat := pt\u00e9clat + 1;<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 \/\/ m-\u00e0-j du descripteur de fichier<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 descrip_fich.k := k;<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 descrip_fich.pt\u00e9clat := pt\u00e9clat;<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>fsi<\/strong><\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>fsi\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>\/\/ \u00e9crire l&rsquo;article dans le paquet numpaquet<\/p><p><strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Ecrire (article, numpaquet);<\/p><p><strong>Fin<\/strong><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-50537bd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"50537bd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d83bb45\" data-id=\"d83bb45\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-758ad5f elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"758ad5f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a4997c6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a4997c6\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c57c9af\" data-id=\"c57c9af\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-209e8e5 elementor-widget elementor-widget-heading\" data-id=\"209e8e5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-Hachage-multicritere\"><\/span>Exercice Hachage multicrit\u00e8re<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fc158f0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fc158f0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ee1caa3\" data-id=\"ee1caa3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8c8a629 elementor-widget elementor-widget-text-editor\" data-id=\"8c8a629\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Dans le domaine des bases de donn\u00e9es, les recherches d&rsquo;articles se font g\u00e9n\u00e9ralement sur des crit\u00e8res multiples (exemple: rechercher les voitures de puissance sup\u00e9rieure \u00e0 10 cv et de marque Citro\u00ebn). Les organisations de fichier \u00e9tudi\u00e9es dans les chapitres 2 et 3 privil\u00e9gient le traitement du crit\u00e8re de recherche le plus fr\u00e9quemment employ\u00e9 sur un fichier, en ordonnan\u00e7ant les articles sur disque en fonction de ce crit\u00e8re. Pour traiter efficacement des recherches multi-crit\u00e8res, il est possible d&rsquo;adapter la majorit\u00e9 des organisations de fichiers afin de faire participer plusieurs attributs \u00e0 la politique de placement.<\/p><p>Une seconde solution consiste \u00e0 utiliser une structure de donn\u00e9es annexe, appel\u00e9e <em>index secondaire<\/em>. Un index secondaire constitue un r\u00e9-ordonnancement logique des articles d&rsquo;un fichier en fonction d&rsquo;une cl\u00e9 d&rsquo;acc\u00e8s (discriminante ou non) diff\u00e9rente de la cl\u00e9 pla\u00e7ante sur laquelle est bas\u00e9e l&rsquo;organisation du fichier. Lors d&rsquo;une recherche sur cl\u00e9 d&rsquo;acc\u00e8s, le balayage de l&rsquo;index secondaire d\u00e9livre les identifiants de tous les articles satisfaisant le crit\u00e8re de recherche.\u00a0<\/p><p>Ces articles sont ensuite r\u00e9cup\u00e9r\u00e9s un \u00e0 un via leurs identifiants, \u00e0 raison d&rsquo;une E\/S par article. La cr\u00e9ation d&rsquo;un index secondaire introduit un co\u00fbt de stockage important. De plus, toute mise \u00e0 jour du fichier de donn\u00e9es entra\u00eene la mise \u00e0 jour de tous les index secondaires portant sur ce fichier. L&rsquo;utilisation d&rsquo;index secondaires doit donc \u00eatre restreinte \u00e0 des crit\u00e8res de recherche fr\u00e9quents.<\/p><p><strong>Question 1<\/strong><\/p><p>Dans la m\u00e9thode du hachage statique \u00e9tudi\u00e9e pr\u00e9c\u00e9demment, un num\u00e9ro de paquet est d\u00e9termin\u00e9 par la valeur d&rsquo;une cha\u00eene de bits issue du hachage de la valeur d&rsquo;un seul attribut. Pour \u00e9tendre cette m\u00e9thode au hachage multi-attributs, la cha\u00eene de bits est obtenue en concat\u00e9nant respectivement b1, b2, \u2026 bn bits issus du hachage des attributs A1, A2, \u2026, An par les fonctions de hachage h1, h2, \u2026, hn.<\/p><p>a) Donner le principe de recherche de tous les articles du fichier satisfaisant la condition Ai\u00a0=\u00a0&lt;valeur&gt;.<\/p><p>b) Calculer le nombre d&rsquo;E\/S n\u00e9cessaire (nombre de paquets acc\u00e9d\u00e9s) pour effectuer la recherche pr\u00e9c\u00e9dente en supposant qu&rsquo;il n&rsquo;y a eu aucun d\u00e9bordement.<\/p><p>c) Une recherche avec la condition (Ai\u00a0=\u00a0&lt;valeur1&gt; et Aj=\u00a0&lt;valeur2&gt;) g\u00e9n\u00e8re-t-elle plus ou moins d&rsquo;E\/S que la recherche pr\u00e9c\u00e9dente ? M\u00eame question avec la condition (Ai\u00a0=\u00a0&lt;valeur1&gt; ou Aj=\u00a0&lt;valeur2&gt;).<\/p><p><strong>Question 2<\/strong><\/p><p>De nombreuses m\u00e9thodes de hachage dynamique multi-attributs ont \u00e9t\u00e9 propos\u00e9es, parmi lesquelles: grid-file [Nivergelt81], hachage lin\u00e9aire multi-attributs [Ouksel83] et arbres de pr\u00e9dicats [Gardarin84]. De fa\u00e7on identique au hachage statique multi-attributs, la cha\u00eene de bits servant \u00e0 d\u00e9terminer un num\u00e9ro de paquet est compos\u00e9e des bits issus du hachage des attributs A1, A2, \u2026, An par les fonctions de hachage h1, h2, \u2026, hn.\u00a0<\/p><p>Cependant, les m\u00e9thodes de hachage dynamique multi-attributs diff\u00e8rent suivant l&rsquo;ordre des bits issus de chaque fonction de hachage hi(Ai) dans cette cha\u00eene de bits (par exemple, les bits associ\u00e9s \u00e0 un attribut Ai ne sont pas obligatoirement contigus dans la cha\u00eene). De m\u00eame que dans le hachage dynamique mono-attribut, cette cha\u00eene de bits est d\u00e9velopp\u00e9e bit \u00e0 bit au fur et \u00e0 mesure des \u00e9clatements de paquets.<\/p><p>Donner le principe de recherche des articles satisfaisant la condition Ai\u00a0=\u00a0&lt;valeur&gt;.<\/p><p><strong>Question 3<\/strong><\/p><p>Supposons un fichier hach\u00e9 dynamiquement sur les attributs A1, A2 et A3. Dans quel ordre doivent \u00eatre rang\u00e9s les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans la cha\u00eene de bits d\u00e9terminant un num\u00e9ro de paquet afin de privil\u00e9gier les acc\u00e8s \u00e0 l&rsquo;attribut A2, puis \u00e0 l&rsquo;attribut A3 puis enfin \u00e0 l&rsquo;attribut A1 dans cet ordre de priorit\u00e9 ?<\/p><p><strong>Question 4<\/strong><\/p><p>La m\u00e9thode du grid-file permet de traiter de fa\u00e7on \u00e9quitable chacun des attributs de placement. Supposons un fichier hach\u00e9 sur les attributs A1, A2 et A3. Dans quel ordre doivent \u00eatre rang\u00e9s les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans la cha\u00eene de bits d\u00e9terminant un num\u00e9ro de paquet afin d&rsquo;assurer cette \u00e9quit\u00e9 ?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6ee2f90 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6ee2f90\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0ebaf95\" data-id=\"0ebaf95\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8fdf887 elementor-widget elementor-widget-toggle\" data-id=\"8fdf887\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1501\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1501\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1501\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1501\"><p><strong>Question 1\u00a0<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>a) Les N paquets d&rsquo;un fichier hach\u00e9 selon une m\u00e9thode statique multi-attributs sont identifi\u00e9s par des cha\u00eenes de p bits (o\u00f9 p=log_2 N) construites par concat\u00e9nation de b1, b2, \u2026, bn bits (o\u00f9 b1+b2+ \u2026+bn = p) associ\u00e9s respectivement aux attributs A1, A2, \u2026, An. La recherche de tous les articles du fichier satisfaisant la condition Ai = &lt;valeur&gt; n\u00e9cessite la lecture de tous les paquets dont les num\u00e9ros sont identifi\u00e9s par une cha\u00eene de p bits dans laquelle les valeurs des bi bits associ\u00e9s \u00e0 Ai correspondent aux valeurs des bi bits issus du hachage de la valeur recherch\u00e9e par la fonction hi. O<\/p><p>n s\u00e9lectionne donc tous les paquets dont les num\u00e9ros ont la forme pr\u00e9sent\u00e9e en figure 6.1. Ces paquets sont ensuite balay\u00e9s s\u00e9quentiellement pour r\u00e9cup\u00e9rer tous les articles satisfaisant le crit\u00e8re de recherche.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20061 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd46.png\" alt=\"bdd hachage multicrit\u00e8re\" width=\"415\" height=\"104\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd46.png 415w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd46-300x75.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd46-18x5.png 18w\" sizes=\"(max-width: 415px) 100vw, 415px\" \/><\/p><p><strong>Figure.<\/strong> Signature des paquets s\u00e9lectionn\u00e9s<\/p><p>b) S&rsquo;il n&rsquo;y a pas eu de d\u00e9bordement, le nombre d&rsquo;E\/S engendr\u00e9es par une telle recherche correspond au nombre de paquets dont les num\u00e9ros ont la forme cit\u00e9e pr\u00e9c\u00e9demment. Puisque le fichier contient 2ppaquets (2p= nombre de combinaisons possibles de p bits), le nombre de paquets s\u00e9lectionn\u00e9s (nombre d&rsquo;E\/S) est \u00e9gal \u00e0 2^(p-bi), c&rsquo;est-\u00e0-dire au nombre de combinaisons possibles de p-bi bits puisque bi bits sont fix\u00e9s par le crit\u00e8re de recherche.<\/p><p>c) En suivant le m\u00eame raisonnement, le nombre d&rsquo;E\/S g\u00e9n\u00e9r\u00e9es par une recherche avec la condition (Ai = &lt;valeur1&gt; et Aj= &lt;valeur2&gt;) est \u00e9gal \u00e0 2^(p-bi-bj). Ce co\u00fbt est donc inf\u00e9rieur au co\u00fbt calcul\u00e9 en b). Le nombre d&rsquo;E\/S g\u00e9n\u00e9r\u00e9es par une recherche avec la condition (Ai = &lt;valeur1&gt; ou Aj= &lt;valeur2&gt;) est quant \u00e0 lui \u00e9gal \u00e0 2^(p-bi) + 2^(p-bj).<\/p><p><strong>Question 2<\/strong><\/p><p>De fa\u00e7on identique au hachage statique multi-attributs, la recherche de tous les articles du fichier satisfaisant la condition Ai\u00a0=\u00a0&lt;valeur&gt; n\u00e9cessite la lecture de tous les paquets dont les num\u00e9ros sont identifi\u00e9s par une cha\u00eene de bits dans laquelle les valeurs des bi bits associ\u00e9s \u00e0 Ai correspondent aux valeurs des bi bits issus du hachage de la valeur recherch\u00e9e par la fonction hi. La diff\u00e9rence est que les paquets sont ici cr\u00e9\u00e9s dynamiquement et que les signatures de paquets sont d\u00e9velopp\u00e9es au fur et \u00e0 mesure des \u00e9clatements.\u00a0<\/p><p>On commence donc par construire une cha\u00eene de bits, appel\u00e9e profil de signature, dans laquelle seules sont renseign\u00e9es les valeurs des bi bits associ\u00e9s \u00e0 Ai. Ce profil de signature est ensuite utilis\u00e9 pour filtrer le catalogue afin de s\u00e9lectionner toutes les signatures dont les valeurs des bi bits de Ai correspondent \u00e0 celles du profil de signature, ind\u00e9pendamment des valeurs des autres bits de la signature. Si certains bits du profil de signature correspondent \u00e0 des bits non encore d\u00e9velopp\u00e9s dans une signature, on applique la comparaison uniquement sur les bits d\u00e9velopp\u00e9s.<\/p><p>Le hachage de la valeur recherch\u00e9e 12 par hi donne 3, soit\u00a0 11 en binaire. Le filtrage du catalogue va donc s&rsquo;effectuer avec le profil ??1?1 (o\u00f9 ? symbolise une valeur de bit inconnue). Ce filtrage va permettre de s\u00e9lectionner les 2^(5-2) entr\u00e9es du catalogue contenant les signatures 00101, 00111, 10101, 10111, 01101, 01111, 11101 et 11111. Le nombre d&rsquo;E\/S r\u00e9sultant est simplement 2 car l&rsquo;ensemble de ces signatures r\u00e9f\u00e9rencent deux paquets initiaux 101 et 111 qui n&rsquo;ont jamais \u00e9clat\u00e9.<\/p><p><strong>Question 3<\/strong><\/p><p>Dans une m\u00e9thode de placement statique, l&rsquo;ordonnancement des bits dans la signature d&rsquo;un paquet n&rsquo;a pas d&rsquo;importance. En revanche, dans une m\u00e9thode de placement dynamique, l&rsquo;\u00e9clatement des paquets se fait en exploitant les bits de la signature l&rsquo;un apr\u00e8s l&rsquo;autre. Seuls les bits exploit\u00e9s de la signature participent au placement, les autres bits restant non significatifs lors des recherches. Privil\u00e9gier l&rsquo;acc\u00e8s \u00e0 un attribut revient donc \u00e0 placer les bits qui lui sont associ\u00e9s en d\u00e9but de signature (c&rsquo;est \u00e0 dire \u00e0 droite) de telle sorte qu&rsquo;ils deviennent significatifs d\u00e8s les premiers \u00e9clatements.<\/p><p>Soient les fonctions de hachage h1(A1), h2(A2), h3(A3) suivantes:<\/p><p>h1(A1) = i^1 i^2 i^3 \u2026 i^n o\u00f9 i^q correspond au q\u00e8me bit de h1(A1)<\/p><p>h^2(A2) = \u00a0j^1 j^2 j^3 \u2026 j^n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 o\u00f9 j^q correspond au q\u00e8me bit de h2(A2)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>h3(A3) = k^1 k^2 k^3 \u2026 k^n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 o\u00f9 k^q correspond au q\u00e8me bit de h3(A3)<\/p><p>Privil\u00e9gier les acc\u00e8s \u00e0 l&rsquo;attribut A2, puis \u00e0 l&rsquo;attribut A3 puis enfin \u00e0 l&rsquo;attribut A1 dans cet ordre de priorit\u00e9 revient \u00e0 placer les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans l&rsquo;ordre suivant: i^1 i^2 i^3 \u2026 in k^1 k^2 k^3 \u2026 k^n j^1 j^2 j^3 \u2026 j^n. Dans cet exemple, le placement sur l&rsquo;attribut A1 ne deviendra effectif que lorsque le fichier aura atteint une grande taille, apr\u00e8s un nombre important d&rsquo;\u00e9clatements de paquet.<\/p><p><strong>Question 4\u00a0\u00a0<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>Afin de traiter de fa\u00e7on \u00e9quitable chacun des attributs de placement, la m\u00e9thode du grid\u2013file m\u00e9lange les bits issus de chaque fonction de hachage dans la cha\u00eene de bits afin d&rsquo;exploiter un bit d&rsquo;un attribut diff\u00e9rent \u00e0 chaque \u00e9clatement d&rsquo;un paquet.<\/p><p>Dans l&rsquo;exemple du fichier hach\u00e9 sur les attributs A1, A2 et A3, la m\u00e9thode du grid\u2013file va exploiter un bit de h1(A1) lors du premier \u00e9clatement d&rsquo;un paquet, puis un bit de h2(A2) au deuxi\u00e8me \u00e9clatement de ce paquet, puis un bit de h3(A3) au troisi\u00e8me \u00e9clatement puis \u00e0 nouveau un bit de h1(A1) au quatri\u00e8me \u00e9clatement et ainsi de suite en tournant cycliquement sur chacun des attributs.<\/p><p>Cette \u00e9quit\u00e9 est donc obtenue en pla\u00e7ant les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans l&rsquo;ordre suivant: k^1 j^1 i^1 k^2 j^2 i^2 \u2026 k^n j^n i^n, o\u00f9 i^q, j^q, k^q ont m\u00eame signification que dans la question 5.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Software Analysis Home Page Wiki Corrected Exercises on Hashing in a Database Hashing is specific to the software used, the corrected exercises... <\/p>","protected":false},"author":1,"featured_media":0,"parent":4609,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-20053","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/20053","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=20053"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/20053\/revisions"}],"predecessor-version":[{"id":20523,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/20053\/revisions\/20523"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4609"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=20053"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}