لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل : .doc ( قابل ویرایش و آماده پرینت )
تعداد صفحه : 3 صفحه
قسمتی از متن .doc :
ارتباط بین کلاس های پیچیدگی "P و NP" یکی از مسائل حل نشده در علوم رایانه نظری است و به عنوان مهمترین مسئله این زمینه مطرح گردیده است.
سؤال P=NP؟ در واقع این پرسش را مطرح می نماید که: اگر همیشه به سادگی بتوان صحت یک راهحل را بررسی کرد، آیا پیدا کردن راهحل نیز میتواند به آن سادگی باشد؟ ( در زمان چندجملهای به جواب رسید. )
به عنوان مثال مسئله جمع اعضای زیرمجموعه را در نظر بگیرید. این یک مثال از مسئلهای است که تحقیق درستی راه حل آن ساده است، اما باور بر این است ( اما اثبات نشده است ) که محاسبه جواب آن مشکل است. فرض کنید یک مجموعه از عداد صحیح داده شده است، آیا یک زیر مجموعه ناتهی از آن وجود دارد که مجموع اعضای آن ۰ شود؟ به عنوان مثال،آیا زیر مجموعهای از مجموعه { ۲-، ۳-، ۱۵، ۱۴، ۷، ۱۰- } وجود دارد که مجموع اعضای آن صفر شود؟ پاسخ مثبت است زیرا زیرمجموعه { ۲-، ۳-، ۱۵، ۱۰- } وجود دارد که در شرط صدق می کند و تحقیق این که جواب درست است یا خیر تنها با انجام سه عمل جمع امکان پذیر است. اما پیدا کردن این مجموعه در آغاز کار، کمی وقت گیر است. به اطلاعاتی که برای تحقیق پاسخ مثبت به این دست سؤال ها مورد نیاز است، یک Certificate گفته می شود. با در اختیار داشتن این اطلاعات درست، تحقیق درست بودن پاسخ در مسئله ما، در زمان چندجملهای امکان پذیر است. بنابر این، این مثال در کلاس NP قرار می گیرد.
پاسخ به پرسش P=NP مشخص خواهد کرد که آیا راه حل مسائلی مانند جمع اعضای زیرمجموعه به سادگی تحقیق درستی پاسخ آن هاست یا خیر. در صورتی که ثابت شود P≠NP، آنگاه می توان نتیجه گرفت که بعضی مسائل وجود دارند که به صورت ذاتی، یافتن پاسخ آنها، "سخت تر" از تحقیق درستی پاسخ است.
مؤسسه ریاضیات Clay، جایزه یک میلیون دلاری برای اولین اثبات درست این مسئله تعیین کرده است.[۱]
مفهوم مسئله
ارتباط بین کلاس های پیچیدگی P و NP در نظریه پیچیدگی محاسباتی -بخشی از نظریه محاسبات که به بررسی منابع مورد نیاز در زمان محاسبه جواب یک مسئله می پردازد- مطالعه می شود. مهمترین منابع یکی زمان (مراحل یا گام های مورد نیاز برای دستیابی به جواب) و دیگری فضا (حافظه مورد نیاز برای حل مسئله) است.
در آنالیزهایی شبیه به این، یک مدل از رایانهای که باید بر طبق آن، زمان محاسبه شود مورد نیاز است. به طور معمول، این مدل ها فرض می کنند که رایانه، "فطعی" (به این مفهوم که به ازای یک حالت معین و برای تمامی ورودی ها، رایانه تنها می تواند یک عمل ممکن انجام دهد) و "ترتیبی" (به این معنی که عملی را بعد از عمل دیگر انجام می دهد) است.
در این نظریه، کلاس P شامل تمام مسئلههای تصمیم گیری است -در زیر تعریف شده- که پاسخ به آن ها بر روی یک ماشین قطعی ترتیبی، در زمان چندجملهای به ازای ورودی، ممکن باشد؛ کلاس NP شامل تمام مسئلههای تصمیم گیری است که پاسخ های مثبت آن ها می تواند در زمان چند جملهای با اطلاعات درست، تحقیق شود و یا بطور معادل، پاسخ های آن ها در زمان چندجملهای بر روی یک ماشین غیر قطعی، یافت شود.[۲]
با این تعاریف، مهمترین سؤال این است که رابطه این دو کلاس چگونه است؟ آیا P=NP؟
در یک نظرسنجی در سال ۲۰۰۲ از ۱۰۰ محقق، ۶۱ نفر به این پرسش پاسخ منفی دادند، ۹ نفر پاسخ مثبت و ۲۲ نفر هنوز مطمئن نبودند. ۸ نفر هم معتقد بودند که شاید سؤال خارج از اصول موضوعه پذیرفته شده کنونی باشد بنابر این رد و یا اثبات آن غیر ممکن است.[۳]
تعریف های رسمی برای کلاس های P و NP
تعریف مسئله تصمیم گیری: مسئلهای که یک رشته به عنوان ورودی دریافت کرده و پاسخ "بله" یا "خیر" می دهد.اگر یک الگوریتم وجود داشته باشد (یک ماشین تورینگ و یا یک برنامه رایانهای با حافظه نامتناهی) که قادر باشد به ازای هر ورودی به طول n در حداکثر مرحله که k و c اعداد ثابتی مستقل از طول ورودی هستند، جواب درست بدهد آنگاه می گوییم مسئله می تواند در زمان چندجملهای حل شود و آن را در کلاس P قرار می دهیم.
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 22
برنامه خطی اعداد صحیح دوتایی (BILP)
یک مورد خاص ILP زمانی اتفاق می افتد که همه متغیرهای نمونه بتوانند فقط یک یا دو رقم 0 یا 1 را قبول کنند . چنین متغیرهایی متغیرهای دوتایی نامیده می شوند ، و نمونه ها ، برنامه ها ، برنامه های 1-0 یا برنامه های خطی اعداد صحیح دو تایی (BILPS) نامیده می شوند . هر حالتی که بتواند با بله / نه ، (خوب / بد) یا 0/1 نمونهبرداری شود به عنوان متغیردوتایی شناخته می شود . در زیر نمونه های زیادی از متغیرهای دوتایی ذکر شده که ممکن است در طرح تجاری یافت شود :
، اگر یک طرح مراقبت سلامتی جدید پذیرفته شود .
، اگر پذیرفته نشود .
، اگر مجلس خط B برای تولید نمونه های کولس به کار رود .
، اگر به کار نرود .
، اگر یک ایستگاه پلیس جدید در پایین شهر شناخته شود .
، اگر ساخته نشود .
، اگر تولید یک اجناس به عنوان نوع «خوب» قابل قبول باشد .
، اگر به این صورت نباشد .
، اگر بزرگراه 50 ، در سفر بین ددو شهر به کار رود .
، اگر به این صورت نباشد .
، اگر محدودیت خاصی باشد .
، اگر آن محدودیت نیاز نباشد .
، اگر یک گیاه جدید در گاری هندوستان پرورش یابد .
، اگر به این صورت نباشد .
، اگر سومین انتقال به کار رود .
، اگر به این صورت نباشد .
همانطور که این مثالها نشان می دهند ، خیلی ساده است که متغیر دوتایی را به عنوان یک تحقیق در نظر می گیریم یعنی این که این تحقیق قبول شده ، یعنی این تحقیق قبول نشده است . با تفاسیر داده شده در مورد متغیرها ، اکنون ما چند نوع اجبار را مورد آزمایش قرار می دهیم ، که تحت بررسی شورای شهر در «سالم اورگون» می باشد .
شورای شهر سالم :
در آخرین جلسه مالیاتی سال ، شورای شهر «سالم» ، طرح هایی مختص سرمایه باقی مانده در بودجه یک سال ارائه کرده است . نه تحقیق تحت بررسی کامل یک سال قرار گرفته اند . برای آمارگیری حمایت مردم از تحقیق های مختلف ، پرسشنامه هایی به طور تصادفی به رای دهندگان در کل شهر فرستاده می شود و از آنها خواسته می شود که تحقیق ها را به ترتیب از خوب به بد طبقه بندی کنند . ( بالاترین تقدم ، پایین ترین تقدم ) شورا امتیازها را بر اساس 500 پاسخی که دریافت می کند تطبیق می دهد .با این وجود هیئت شورا مکرراً متذکر می شود که تنها به نتایج پرسشنامهها اکتفا نمی کند . آنها در حالیکه تخصیص های بودجه را تهیه می کنند ، مسائل دیگر را هم محاسبه می کنند . برای تخمین هزینه هر تحقیق ، میزان تخمینی ثابت هر شغل جدید باید فراهم شده ، و تطبیق امتیاز پرسشنامه ها در جدول 3-5 خلاصه شده است.
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 23
اعداد اول
اعداد اول اعدادی طبیعی هستند که بر هیچ عددی بجز خودشان و عدد ۱ بخشپذیر نباشند. تنها استثنا عدد ۱ است که جزو این اعداد قرار نمیگیرد. اگرعددی طبیعی وبزرگتر از ۱ اول نباشد مرکب است.
عدد یکان اعداد اول بزرگتر از ۱۰ فقط ممکن است اعداد ۱، ۳، ۷، ۹ باشد.
پیدا کردن ضابطه ای جبری برای اعداد اول جزو یکی از معماهای ریاضی باقیمانده است و هنوز کسی به فرمولی برای آنها به دست نیاورده است.
دنبالهٔ اعداد اول به این صورت شروع میشود: ۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹ ...
قضیه ۱: تعداد اعداد اول بینهایت است.
برهان: حکم را به روشی که منسوب به اقلیدس است اثبات میکنیم: فرض کنید تعداد اعداد اول متناهی و تعداد آنها n تا باشد. حال عدد M را که برابر حاصلضرب این اعداد به علاوه ۱ را در نظر بگیرید. این عدد مقسومعلیهی غیر از آن n عدد دارد که با فرض در تناقض است.
قضیه ۲ (قضیه اساسی حساب): هر عدد طبیعی بزرگتر از ۱ را می توان به شکل حاصلضرب اعدادی اول نوشت.
قضیه ۳ (قضیه چپیشف):اگر n عددی طبیعی و بزرگتر از ۳ باشد، حتما" بین n و ۲n عدد اولی وجود دارد. قضیه ۴ هر عدد زوج را میتوان بصورت جمع سه عدد اول نوشت.
قضیه ۵ هر عدد فرد (شامل اعداد اول) را میتوان به صورت جمع سه عدد اول نوشت (اثبات بر پایه قضیه ۴)
قضیه 6-هر عدد فرد را میتوان به صورت دو برابر یک عدد اول بعلاوه یک عدد اول دیگر نوشت (برهان آن را بنویسد).
خواص اعداد اول:
1- هر عدد اول برابر است با 6n+1 یا 6n-1 که n یک عدد صحیح است.
2-مجذور هر عدد اول برابر است با 24n+1.
3-تفاضل مجذورهای دو عدد اول مضربی از 24 است.
4-حاصلضرب هر دو عدد اول بجز 2و3 مضربی از 6 بعلاوه یا منهای یک است.
توان چهارم هر عدد اول بجز 2و3 مضربی از 240 بعلاوه یک است.
بزرگترین عدد اول کشف شده برابر دو به توان ۳۰میلیون و ۴۰۲هزار و ۴۵۷منهای یک است.این عدد یک عدد مرسن است. عدد مرسن عددی است که برابر 2 به توان n منهای یک است.
لازم به ذکر است که تعداد 3000 عدد اول در سایت مگاسندر www.megasender.org وجود دارد و افرادی که مایل به دریافت بیشتر این اعداد هستند می توانند با سایت مذکور تماس گرفته و تعداد بیشتری از آنها را بر روی لوح فشرده دریافت نمایند و طراحان این سایت خودشان این اعداد را محاسبه نموده اند
تاریخچه اعداد اول
در سال ۲۰۰۱دو تن از دانشجویان او یعنی کایال و سکسنا به یک نکته بسیار حساس و فنی توجه کردند. ابتدا این مساله سبب شد تا گروه سه نفره در آبهای عمیق نظریه اعداد غوطه ور شوند، اما اندک اندک برایشان روشن شد که تنها یک مانع در راه تکمیل روشی جهت آزمودن دقیق و سریع اعداد اول وجود دارد. مانع از این قرار بود که روش آنان تنها در صورتی کار میکرد که عدد اول مورد نظر که با pنمایش داده میشود همواره در محدوده خاصی جای داشته باشد که با اعدادی که در آزمون شرکت داده میشوند مرتبط باشد. مشخصه ویژه این مانع آن است که عدد " p-1 " باید یک مقسوم علیه یا بخشیاب بسیار بزرگ باشد. گروه سه نفر ریاضی دانان هندی برای غلبه بر مشکل به هر دری زدند و با بررسی مقالات مختلف بالاخره دریافتند که در سال ۱۹۸۵یک ریاضیدان فرانسوی به نام اتن فووری از دانشگاه پاریس ۱۱این نکته را به صورت ریاضی اثبات کرده است. به این ترتیب آخرین بخش معما حل شد و آلگوریتم پیشنهادی این سه نفر با موفقیت پا به عرصه گذارد. اما این موفقیت "مشروط" بود. به این معنی که این روش برای اعداد اولی که انسان در حال حاضر میتوان به سراغ آنها برود از کارآیی چندانی برخوردار نیست. در روایت اولیه روش پیشنهادی، زمان لازم برای محاسبات که متناسب با ارقام عدد اول مورد نظر بود، با آهنگ ۱۰۱۲ازدیاد پیدا می کرد. در روایتهای بهبود یافته اخیر این روش، سرعت ازدیاد زمان لازم برای محاسبات به ۱۰۷.۵کاهش یافته اما حتی در این حالت نیز این روش در مقایسه با روش آ پی آر تنها در هنگامی موثر تر خواهد بود که تعداد ارقام عدد اولی که قصد شکار و یافتن آن را داریم در حدود ۱۰۱۰۰۰باشد. اعدادی تا این اندازه بزرگ در حافظه هیچ کامپیوتر جای نمیگیرند و حتی آن را نمیتوان در کل کیهان جای داد. اما حال که ریاضی دانان توانستهاند یک طبقه خاص از آلگوریتمهای توانی را برای شناسایی اعداد اول مشخص کنند، این امکان پدید آمده که به دنبال نمونههای بهتر این روش بگردند. پومرانس و هندریک لنسترا از دانشگاه کالیفرنیا در برکلی با تلاش در همین زمینه توانستهاند زمان لازم برای محاسبات را از توان ۷.۵به توان ۶کاهش دهند. این دو از همان استراتژی کلی گروه هندی موسسه کانپور استفاده کردند اما تاکتیهای دیگری را به کار گرفتند. اگر فرضیههای دیگری که درباره اعداد اول مطرح شده درست از کار درآید آنگاه میتوان زمان محاسبه را از توان ۶به توان ۳تقلیل داد که در این حد این روش کارآیی عملی پیدا خواهد
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 15
اعداد اول
اعداد اول اعدادی طبیعی هستند که بر هیچ عددی بجز خودشان و عدد ۱ بخشپذیر نباشند. تنها استثنا عدد ۱ است که جزو این اعداد قرار نمیگیرد. اگرعددی طبیعی وبزرگتر از ۱ اول نباشد مرکب است.عدد یکان اعداد اول بزرگتر از ۱۰ فقط ممکن است اعداد ۱، ۳، ۷، ۹ باشد.اعداد اول جزو یکی از معماهای ریاضی باقیمانده است و هنوز کسی به فرمولی برای آنها به دست نیاورده است.سری اعداد اول به این صورت شروع میشود: ۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹ ...قضیه ۱: تعداد اعداد اول بینهایت است.
قضیه ۱: تعداد اعداد اول بینهایت است.
به این اثبات دقت کنیداز برهان خلف استفاده می کنیم:
فرض خلف : اعداد اول متناهی است.
اعداد اول را در هم ضرب می کنیم.
P1,P2,P3,...,Pn
ضرب اعداد از Pi بزرگتراست.
که عدد ۱ جزو اعداد اول نیست پس به تناقض می رسیم و فرض خلف باطل است. اعداد اول نامتناهی هستند.
برهان: حکم را به روشی که منسوب به اقلیدس است اثبات میکنیم: فرض کنید تعداد اعداد اول متناهی و تعداد آنها n تا باشد. حال عدد M را که برابر حاصلضرب این اعداد به علاوه ۱ را در نظر بگیرید. این عدد مقسومعلیهی غیر از آن n عدد دارد که با فرض در تناقض است.قضیه ۲ (قضیه اساسی حساب): هر عدد طبیعی بزرگتر از ۱ را به شکل حاصلضرب اعدادی اول نوشت.قضیه ۳ (قضیه چپیشف):اگر n عددی طبیعی و بزرگتر از ۳ باشد، حتما" بین n و ۲n عدد اولی وجود دارد. قضیه ۴ هر عدد زوج را میتوان بصورت جمع سه عدد اول نوشت.قضیه ۵ هر عدد فرد (شامل اعداد اول) را میتوان به صورت جمع سه عدد اول نوشت (اثبات بر پایه قضیه ۴)قضیه 6-هر عدد فرد را میتوان به صورت دو برابر یک عدد اول بعلاوه یک عدد اول دیگر نوشت.خواص اعداد اول:1- هر عدد اول برابر است با 6n+1 یا 6n-1 که n یک عدد صحیح است.2-مجذور هر عدد اول برابر است با 24n+1.3-تفاضل مجذورهای دو عدد اول مضربی از 24 است.4-حاصلضرب هر دو عدد اول بجز 2و3 مضربی از 6 بعلاوه یا منهای یک است.توان چهارم هر عدد اول بجز 2و3 مضربی از 240 بعلاوه یک است.بزرگترین عدد اول کشف شده برابر دو به توان ۳۰میلیون و ۴۰۲هزار و ۴۵۷منهای یک است.این عدد یک عدد مرسن است. عدد مرسن عددی است که برابر 2 به توان n منهای یک است.لازم به ذکر است که تعداد 3000 عدد اول در سایت مگاسندر [url]www.megasender.org[/url] وجود دارد و افرادی که مایل به دریافت بیشتر این اعداد هستند می توانند با سایت مذکور تماس گرفته و تعداد بیشتری از آنها را بر روی لوح فشرده دریافت نمایند و طراحان این سایت خودشان این اعداد را محاسبه نموده اند
روشی برای شکار اعداد اول
کی از اولین و در عین حال درخشانترین کارهای بشر در نظریه اعداد، اثبات اقلیدس از نامتناهی بودن اعداد اول در کتاب اصول است که امروزه می توان آن را در کتاب های درسی دبیرستانی خواند. نمونه ای عالی از زیبایی و سادگی ریاضیات. یونانی ها اعداد اول را می شناختند و از نقش آن ها به عنوان بلوک های سازنده دیگر اعداد آگاه بودند. بعد از این دستاوردهای بزرگ طبیعی ترین سوالی که به ذهن بشر رسید این بود که چه نظمی بر دنباله اعداد اول حاکم است، چگونه می توان اعداد اول را یافت و چطور می توان اعدادی را که اول نیستند به عوامل اول شان تجزیه کرد. شاید اولین پاسخ به این سوال غربال اراتستن بوده باشد. تا امروز تلاش های زیادی برای یافتن یک فرمول تولید کننده اعداد اول و یا الگویی برای ظهور اعداد اول در
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 17
برنامه خطی اعداد صحیح دوتایی (BILP)
یک مورد خاص ILP زمانی اتفاق می افتد که همه متغیرهای نمونه بتوانند فقط یک یا دو رقم 0 یا 1 را قبول کنند . چنین متغیرهایی متغیرهای دوتایی نامیده می شوند ، و نمونه ها ، برنامه ها ، برنامه های 1-0 یا برنامه های خطی اعداد صحیح دو تایی (BILPS) نامیده می شوند . هر حالتی که بتواند با بله / نه ، (خوب / بد) یا 0/1 نمونهبرداری شود به عنوان متغیردوتایی شناخته می شود . در زیر نمونه های زیادی از متغیرهای دوتایی ذکر شده که ممکن است در طرح تجاری یافت شود :
، اگر یک طرح مراقبت سلامتی جدید پذیرفته شود .
، اگر پذیرفته نشود .
، اگر مجلس خط B برای تولید نمونه های کولس به کار رود .
، اگر به کار نرود .
، اگر یک ایستگاه پلیس جدید در پایین شهر شناخته شود .
، اگر ساخته نشود .
، اگر تولید یک اجناس به عنوان نوع «خوب» قابل قبول باشد .
، اگر به این صورت نباشد .
، اگر بزرگراه 50 ، در سفر بین ددو شهر به کار رود .
، اگر به این صورت نباشد .
، اگر محدودیت خاصی باشد .
، اگر آن محدودیت نیاز نباشد .
، اگر یک گیاه جدید در گاری هندوستان پرورش یابد .
، اگر به این صورت نباشد .
، اگر سومین انتقال به کار رود .
، اگر به این صورت نباشد .
همانطور که این مثالها نشان می دهند ، خیلی ساده است که متغیر دوتایی را به عنوان یک تحقیق در نظر می گیریم یعنی این که این تحقیق قبول شده ، یعنی این تحقیق قبول نشده است . با تفاسیر داده شده در مورد متغیرها ، اکنون ما چند نوع اجبار را مورد آزمایش قرار می دهیم ، که تحت بررسی شورای شهر در «سالم اورگون» می باشد .
شورای شهر سالم :
در آخرین جلسه مالیاتی سال ، شورای شهر «سالم» ، طرح هایی مختص سرمایه باقی مانده در بودجه یک سال ارائه کرده است . نه تحقیق تحت بررسی کامل یک سال قرار گرفته اند . برای آمارگیری حمایت مردم از تحقیق های مختلف ، پرسشنامه هایی به طور تصادفی به رای دهندگان در کل شهر فرستاده می شود و از آنها خواسته می شود که تحقیق ها را به ترتیب از خوب به بد طبقه بندی کنند . ( بالاترین تقدم ، پایین ترین تقدم ) شورا امتیازها را بر اساس 500 پاسخی که دریافت می کند تطبیق می دهد .با این وجود هیئت شورا مکرراً متذکر می شود که تنها به نتایج پرسشنامهها اکتفا نمی کند . آنها در حالیکه تخصیص های بودجه را تهیه می کنند ، مسائل دیگر را هم محاسبه می کنند . برای تخمین هزینه هر تحقیق ، میزان تخمینی ثابت هر شغل جدید باید فراهم شده ، و تطبیق امتیاز پرسشنامه ها در جدول 3-5 خلاصه شده است.
هدف هیئت شورا بالا بردن حمایت کل رای دهندگان دریافت شده (داشتن پرسشنامه به عنوان مدرک) و دادن محدودیت ها و مطالب قابل توجه دیگر هیئت شورا می باشد که به شرح زیر است :
900.000 دلار باقیمانده در صندوق
نیازهای هیئت شورا برای ایجاد حداقل 10 شغل جدید .
با وجودیکه جلوگیری از جنایت ، برای مردم از اهمیت بیشتری برخوردار است ، هیئت شورا برای بخش های دیگر خدمات مردم باید به خوبی عمل کند . بنابراین امید می رود که در بیشتر تحقیق های مربوط پلیس سرمایه گذاری شود .
هیئت شورا مایل است که تعداد وسایل نقلیه اضطراری شهر را افزایش دهد ولی اکنون با توجه به مطالب دیگر ، فقط یکی از دو تحقیق در مورد وسایل نقلیه اضطراری باید سرمایه گذاری کند . پس دو ماشین پلیس و دو ماشین آتش نشانی هم باید خریداری شود .
هیئت شورا معتقد است در صورتیکه تصمیم بگیرد نزولهای سرمایه را از برنامههای ورزشی در مدارس برگرداند ، نزولهای سرمایه از برنامه های موسیقی هم باید برگردانده شوند و برعکس .