نمونه سوالات طراحی الگوریتم

طراحی الگوریتم

سوال ستاره دار استاد شکری

عنوان سوال :بر اساس عملکرد مسئله Huffman مرتبه زمانی کد گذاری آن را محاسبه کنید ؟

جواب :

در pseudocode زیر فرض می کنیم که C مجموعه ای از n کاراکتر است به نحوی که برای هر کاراکتر c داریم:

فراوانی هر کاراکتر را با c.freq نمایش می دهیم. این الگوریتم ساختار درختی T را به صورت بهینه به روش bottom-up می سازد.

درخت نهایی T از تعداد |C| برگ و تعداد |C|-1 عملیات ادغام ساخته خواهد شد.

الگوریتم زیر از یک priority-queue بنام Q با هدف مشخص کردن دو کاراکتر با کمترین فراوانی برای ادغام استفاده می کند.

پرسش : priority-queue چیست ؟

Queue=first in first out

Stack=last in first out

priority-queueیک abstract data-type یا یک نوع داده خلاصه است. بعلاوه آنکه در این queue هر المان یک priority یا اولویت مشخص دارد.

یک priority-queue حداقل دارای دو عملیات زیر است:(heap operation)

۱-insert with priority : اضافه کردن یک المان به queue بر اساس اولویت

۲-Extract-Min/Max : خارج کردن المانی که پایین ترین اولویت را دارد از داخل queue

زمانی که دو المان با هم ادغام می شوند نتیجه یک المان جدید است که فراوانی آن برابر مجموع فراوانی دو المان ادغام شده است.

عملکرد Huffman

عملکرد Huffman

بعنوان مثال اگر C شامل ۶ کاراکتر باشد n=6 و تعداد ادغام های لازم برای ساختن Heap Tree برابر ۵ خواهد بود.

در line2 از الگوریتم بالا یک priority-queue بنام Q از کاراکترهای داخل مجموعه C تشکیل می شود.

حلقه for از line3 تا line8 مکررا دو node بنام های X,Y را که کمترین فراوانی را دارند از داخل queue استخراج کرده، آنها را ادغام و توسط تابع Insertبا یکnodeجدید به نام Z جایگزین می نماید. فراوانی گره Z برابر مجموع فراوانی X,Y است.

Node جدید Z یک left child بنام X و یک right child بنام Y دارد.

بعد از n-1 بار اجرای عملیات ادغام به line9 می رسیم که در اینجا تنها node باقیمانده در queue که همان Tree-Rootاست،  به برنامه اصلی return می شود.

تحلیل مرتبه زمانی الگوریتم Huffman :

برای آنالیز مرتبه زمانی الگوریتم بالا فرض می کنیم Q به صورت binary min-heap پیاده سازی شده است. از آنجائیکه برای تشکیل این queue باید تمام کاراکترهای درون مجموعه C به طور کامل trace شوند پس مرتبه زمانی این بخش برابر  می باشد.

حلقه for موجود در الگوریتم نیز دقیقا عملیات ادغام را n-1بار اجرا خواهد کرد.

و از آنجائیکه مرتبه زمانی تمامی heap operationهای داخل این حلقه  می باشد، بنابراین مرتبه زمانی نهایی الگوریتم Huffman برابر  خواهد بود.

عملکرد Huffman

عملکرد Huffman

عملکرد Huffman

عملکرد Huffman

دانلود فایل :

لینک دانلود
لینک دانلود

نـظــــر کـاربــران

نـظــــرات و پــیام های شما برای ما مـهـم اسـت.



مطالـب مرتـبـط

لطفا از مطالـب مرتـبـط دیدن فرمایید.



تماس با ما

  • میدان شهدا - خیابان ایران - خیابان مهدوی پور پلاک 30 -شرکت تهران آی تی و مستر آی تی
  • 09121486770
  • 02133503646
  • ahadian2@gmail.com
کلیه حقوق مادی و مادی این اثر برای مستر آی تی محفوظ است
با مــا در تـــماس باشید
تلفن : 02133503646
تلفن همراه : 09121486770
ایمیل : ahadian2@gmail.com
آدرس : میدان شهدا خیابان ایران خیابان مهدوی پور پلاک 20