بخشی از پاورپوینت
اسلاید 1 :
درمطالعهيالگوريتمهاومحاسبتبحثيراجعبهاينكهوقتيمهاينالگوريتمهاعملابررويكامپيوترانجامميشوندنكردهايم
برايمحاسباتواقعينيازداريمكهنهتنهابدانيمكهمسئلهقابلحلاستبلكهبايدقادرباشيمكهالگوريتميبرايآنبسازيمكهبتوانباكارائيقابلقبولآنراانجامداد.
دراينفصلمابهزبانسادهنظريهپيچيدگيمحاسباتراتشريحميكنيم.بحثمامحدودبهپيچيدگيزمانيخواهدبوداگرچهنتايجمشابهيدرخصوصپيچيدگيفضاوجوددارد.
اسلاید 2 :
بايكمثالاينبحثراشروعميكنيم.فرضكنيدكهليستيازهزارعددصحيحراداريمكهميخواهيمآنهارامرتبكنيم.اينسوالمطرحميشودكهچهمقداروقتبرايانجاماينكارلازماستاطلاعاتبيشتريبرايپاسخبهاينسواللازماست.واضحاستكهتعدادعناصرليست,نقشمهميايفاميكنداماعواملديگريهموجوددارد.برايمثالكامپيوتريكهبكارميرودونحوهينوشتنبرنامهموردنظرمهماست.همچنينالگوريتمهايمتعدديبراييككار ,برايمثالمرتبكردنيكليستوجودداردوانتخابالگوريتمنيزتاثيرداردومسائلديگريهمهست.
ااماتاكيدبررويمسائلاساسيبايدباشدوازمسائلجنبيبايدصرفنظركرد.
اسلاید 3 :
برايبحثدرخصوصپيچيدگيمحاسباتي فرضياتزيررادرنظرميگيريم:
-1مدلموردمطالعهيماماشينتورينگخواهدبودكهدرزيرآنراتوضيحميدهيم.
-2اندازهيمسالهرابا nنشانميدهيمبنابرايندرمسئلهمرتبسازيn,تعدادعناصرليستاستاگرچهاندازهيمسالههميشهبهاينآسانيقابللمسنيستاماهموارهآنرامرتبطبايكعددصحيحميكنيم.
-3درتحليليكالگوريتممعمولابهعملكردآندرشرايطخاصكمترازرفتاركليآنعلاقهمندهستيم.معمولارفتارالگوريتمدرزمانيكهاندازهمسالهبزرگ ميشودبرايمامهماستوبههميندليلسوالاصليآنستكهبهچهسرعتيمنابعموردنيازبارشداندازهي nافزايشمييابد.
بنابراينهدفاصلي مابدستآوردننياززمانيمسئلهبهعنوانتابعيازاندازهآنبااستفادهازماشينتورينگبهعنوانمدلكامپيوتراست.
اسلاید 4 :
ابتدابهمفهومزماندرماشينتورينگميپردازيم.هرحركتماشينتورينگرايكواحدزمانيدرنظرميگيريمولذازمانيكمحاسبه ,تعدادحركاتياستكهانجامميشود.همانگونهكهگفتهشدميخواهيمببينيمكهنيازهايمحاسباتيباافزايشاندازهيمسالهچگونهرشدميكند.البتهمعمولابدترينحالترادرنظرميكيريم.وقتيكهميگوئيم كهمحاسبهايدارايپيچيدگيزماني T(n) استمنظورمااينستكهمحاسبههرمسئلاايبااندازه nباانجام T(n)حركت توسطيكماشينتورينگبهانجامميرسد.
اسلاید 5 :
نكتهيديگركهبايدقبلازبدستآوردننتايجبيشترمطرحشوداينستكهبهمحاسبهبررويمسائلبزرگبانيازهايمحاسباتيبالاعلاقهمنديم.درنتيجهما nرابسياربزرگدرنظرميئگيريم .
بنابراينماشينيكهيكمحاسبهرادرمدت n²انجامميدهدخيليكاراترازماشينيكهn²+nزمان ميبردنيستووقتيكه n بزرگباشدفقطعواملموثرتردرنظرگرفتهميشوند.همچنينمفهومواحدزمانيتعريفشدهنيستبنابراينميتوانديكميليثانيه,يكثانيهويايكسالباشد.
اسلاید 6 :
ميگوئيمكهتابع f(n) ازنوع g(n) استاگرمقدارثابت c بهطوريكه
c ≥f(n) / g (n)
براي تمامي n هاصحتاشتهباشد.براياينكهبگوئيم f ازرده g(order) استمينويسيم
f ( n) =O(g(n))
ايننمادمناسبوسنتياستوليغيرمحكموخطرناكاست.
اسلاید 7 :
علامت = دراينجانبايدبهعنوانتساويتفسيرشود. ومحاسباتيمانند
O(n)+O(n)=2 O(n)
درستنيستوممكناستكهمنجربهنتايجغيرصحيحشود.گرچهنماد O بهدرستياستفادهشودميتوانددرسنجشپيچيدگيمفيدواقعشود.
اسلاید 8 :
-1انتخابالگوريتمچهتاثيريبركاراييمرتبسازيدارد؟
-2نشاندهيدكهنتايجزيردرستاست
)n²+5 log n = O(n²) الف
)3ⁿ=O(n!) ب
) n!=O(nⁿ) ج
-3اثباتمنيدكهاگر f(n)=O(g(n))وg(n)=O(h(n))باشدآنوقت f(n)=O(h(n)) است.
-4نشاندهيدكهاگرf (n)=O(n²) وg (n)=O(n³)باشدآنوقت
f ( n)+g(n)=O(n³) و
f ( n)g(n)=O(n^6) است.
-5درتمرين 4 آيادرستاستكه g(n)/f(n)=O(n)باشد؟
-6فرضكنيدكهf ( n)=2n²+nوg (n)=O(n²)باشد.دردبحثزيرچهاشكاليوجوددارد.
nf (n)=O(n²)+O(n)
nبه طوريكه
nf (n)-g(n)=O(n²)+O(n)-O(n²)
nو بنابراين
nf ( n)-g( n)=O(n)
اسلاید 9 :
زمانيكهصحبتازپيچيدگيميشودديگرتساويبينانواعماشينهايتورينگقابلطرحنيست.
اسلاید 10 :
درمثال 9-4يكماشينتورينگيكنوارهبرايزبان
L = {aⁿbⁿ : n ≥1}ساختهشد.بانكاهيبهالگوريتم .ورداستفادهدرمييابيمكهبراي W= aⁿbⁿتقريبا 2nقدمبرايتطبيقهر aباbمربوطلازماست.
بنابراينكلمحاسبه,زمانيمعادلباO (n²)ميبرد.
اامابايكماشيندونوارهميتوانيمالگوريتمديگريرااستفادهنمائيم.ابتداهمه aهاراروينواردومكپيميكنيمسپسآنها رابا bروينواراولتطبيقميدهي.هردوعملكپيوتطبيقميتوانددرزمان O(n)انجامشود.بنابراين,ماشيندونوارهدارايپيچيدگيزماني n است.
