بخشی از پاورپوینت
اسلاید 1 :
تحلیل و طراحی الگوریتم ها Design and Analysis of Algorithms
اسلاید 2 :
فصل اول الگوريتم ها: كارايي، تحليل و مرتبه
اسلاید 3 :
مقدمه (1)
ریشه کلمه الگوریتم از ”الخوارزمی“، ریاضیدان قرن دوم هجری گرفته شده است.
تعریف: هر عملی که مراحل مختلف انجام کاری را به زبان دقیق و با جزئیات کافی بیان کند به طوریکه ترتیب مراحل و شرط خاتمه عملیات در آن کاملاً مشخص باشد.
طراحی الگوریتمها: روشهای کلاسیکی برای طراحی الگوریتمها وجود دارد، که هر فصل این درس به معرفی یکی از آنها می پردازد.
اسلاید 4 :
مقدمه (2)
معتبر سازی (Validation): اثبات درستی یک الگوریتم
تحلیل الگوریتمها: منظور تخمینی از زمان اجرای الگوریتم و همچنین میزان حافظه مصرفی آن می باشد
پیاده سازی: بعد از مرحله معتبر سازی و تحلیل، می توان الگوریتم را با یک زبان برنامه سازی پیاده سازی نمود
تست برنامه: پس از پیاده سازی الگوریتم، می توان آن را بر روی مجموعه ای از داده های معین اجرا و نتیجه را بررسی نمود
اسلاید 5 :
الگوريتم ها
تكنيك هاي حل مسأله
يافتن يك كلمه در ديكشنري
جستجوي ترتيبي
جستجوي دودويي
زبان هاي برنامه نويسي
الگوريتم: رويه مرحله به مرحله براي حل مساله
كارآيي: زمان و حافظه
اسلاید 6 :
مسائل
مسأله: سؤالي كه ما به دنبال پاسخ آن مي باشيم
مثال ها:
A. مرتب سازي يك ليست S متشكل از n عدد به ترتيب غيرنزولي. پاسخ دنباله مرتب از n عدد مي باشد.
B. تعيين اينكه آيا عدد x در ليست S متشكل از n عدد وجود دارد يا خير. در صورت وجود x در ليست S پاسخ برابر ”بله“ و در غير اين صورت پاسخ برابر ”خير“ خواهد بود.
اسلاید 7 :
پارامترها
پارامترهاي مسأله:
A. S و n
B. S و n و x
مسائلي كه شامل پارامترها هستند بيانگر كلاسي از مسائل مي باشند
نمونه مسأله: هر انتساب خاصي از مقادير به پارامترها
راه حل يك نمونه مسأله: پاسخ سؤال پرسيده شده توسط مسأله در آن نمونه
اسلاید 8 :
مثال ها
مسأله A
نمونه: S = [10, 7, 11, 5, 13, 8] و n = 6
راه حل: [5, 7, 8, 10, 11, 13]
مسأله B
نمونه: S = [10, 7, 11, 5, 13, 8] و n = 6 و x = 5
راه حل: «بله، x در S وجود دارد»
اسلاید 9 :
الگوريتم
يك الگوريتم براي مسأله B
با شروع از اولين عنصر S، به ترتيب x را با هريك از عناصر S مقايسه كن تا اينكه x را پيدا كني و يا به آخر ليست S برسي. اگر x پيدا شد، پاسخ «بله» و در غير اين صورت پاسخ «خير» را توليد كن.
معايب نوشتن الگوريتم ها به زبان طبيعي:
مشكل بودن نوشتن و درك الگوريتم هاي پيچيده
مشكل بودن ترجمه آن به يك زبان برنامه نويسي
شبه كد C++
اسلاید 10 :
جستجوي ترتيبي
◄ الگوريتم 1-1 جستجوي ترتيبي
مسأله: آيا كليد x در آرايه S با n كليد قرار دارد؟
ورودي ها (پارامتر ها): عدد صحيح و مثبت n، آرايه S از كليدها با انديس 1 تا n و كليد x
خروجي ها: location، مكان x در S (اگر x در S نباشد خروجي برابر با صفر مي باشد)
اسلاید 11 :
الگوريتم جستجوي ترتيب๊
اسلاید 12 :
جمع نمودن عناصر آرايه
◄ الگوريتم 1-2 جمع نمودن عناصر آرايه
مسأله: تمام اعداد موجود در آرايه n عنصري S را با هم جمع كنيد.
ورودي ها: عدد صحيح و مثبت n، آرايه S با انديس 1 تا n.
خروجي ها: sum، حاصل جمع اعداد موجود در S.
اسلاید 13 :
الگوريتم جمع نمودن عناصر آرايه
اسلاید 14 :
مرتب سازي تعويضي
◄ الگوريتم 1-3 مرتب سازي تعويضي
مسأله: n كليد را به ترتيب غير نزولي مرتب كنيد.
ورودي ها: عدد صحيح و مثبت n، آرايه S از كليد ها با انديس 1 تا n.
خروجي ها: آرايه S حاوي كليدها به ترتيب غير نزولي.
اسلاید 15 :
الگوريتم مرتب سازي تعويضي
اسلاید 16 :
ضرب ماتريس ها
◄ الگوريتم 1-4 ضرب ماتريس ها
مسأله: حاصل ضرب دو ماتريس n x n را تعيين كنيد.
ورودي ها: عدد صحيح ومثبت n، آرايه هاي دو بعدي A و B كه هر يك داراي سطرها و ستون هايي با انديس 1 تا n مي باشند.
خروجي: آرايه دو بعدي C از اعداد، كه سطرها و ستون هاي آن از 1 تا n شماره گذاري شده است و حاوي حاصل ضرب A و B مي باشد.
اسلاید 17 :
الگوريتم ضرب ماتريس ها
اسلاید 18 :
اهميت توسعه الگوريتم هاي كارآ
كارآيي الگوريتم ها همواره و بدون در نظر گرفتن افزايش سرعت كامپيوترها و كاهش قيمت حافظه، بايد مد نظر باشد.
اجازه دهيد اين موضوع را با مقايسه جستجوي ترتيبي و جستجوي دودويي بيشتر بررسي نماييم.
اسلاید 19 :
جستجوي دودويي
◄ الگوريتم 1-5 جستجوي دودويي
مسأله: تعيين كنيد آيا x در آرايه مرتب S با n كليد قرار دارد يا خير.
ورودي ها: عدد صحيح و مثبت n، آرايه مرتب (غير نزولي) S با انديس 1 تا n و كليد x.
خروجي ها: location، مكان x در S ( اگر x در S نباشد خروجي برابر با صفر مي باشد).
اسلاید 20 :
الگوريتم جستجوي دودويي
