[Amir Shahbazzadeh]

دسته بندی علم نظری رایانه(Computer)

1-منطق ریاضی    
2-نظریه اتوماتا    
3-نظریه اعداد
4-نظریه گراف
5- نظریه انواع
6-نظریه رده‌ها    
7-هندسه محاسباتی    
8-نظریه پردازش کوانتومی

[Amir Shahbazzadeh]

منطق ریاضی، شاخه‌ای از ریاضیات است که به ارتباط ریاضی و منطق می پردازد و گاه به آن منطق صوری (منطق نمادی) می‌گویند. این نام را جوزپه پئانو ریاضیدان ایتالیائی بر این رشته علمی گذاشت. پیشتر لایب نیتز و لامبرت کوشش هائی در این خصوص کرده بودند.

در اواخر قرن نوزدهم میلادی، با کارهای آگوستوس دی مورگان، جرج بول، گوتلوپ فرگه، برتراند راسل، داوید هیلبرت و دیگران این علم به پیشرفت قابل ملاحظه‌ای دست یافت . منطق امروز در ریاضیات، شکل کامل تری از منطق در فلسفه است که اساس خود را با نظریهٔ مجموعه‌ها به اشتراک دارد.

    ۱ -انگیزه و اهداف
    ۲ -کاربردهای ریاضی

 
انگیزه و اهداف

تحقیقات علمی درباره منطق ریاضی، در پی بروز پرسش‌های نوین در بنیان‌های ریاضیات پدید آمد. به عنوان نمونه، فرگه می‌کوشید تا ریاضیات را بر پایهٔ اصول برآمده از منطق و نظریهٔ مجموعه‌ها قرار دهد. راسل، در حذف تناقضات ناشی از دستگاه منطق فرگه تلاش کرد و هدف هیلبرت نشان‌دادن این امر بود که "روش‌های مورد قبول عام در ریاضیات هرگاه که به‌طور همه‌جانبه، کلی نگرانه و به‌عنوان یک کل واحد، در نظر گرفته شود، به هیچ نوع تناقضی منجر نخواهد شد ." (این موضوع به برنامه هیلبرت شهرت یافته است .)


کاربردهای ریاضی

روش‌ها و نتایج بدست‌آمده در منطق ریاضی، نه تنها در حلّ مسائل بنیانی موارد استفاده دارد، بلکه، در بسیاری از شاخه‌های دیگر ریاضیّات نظیر جبر، هندسه و توپولوژی هم مورد بهره‌برداری قرار می‌گیرد.

[Amir Shahbazzadeh]

در علوم نظری رایانه، نظریهٔ اتوماتا (به انگلیسی: Automata theory) یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آنها برای حل مسایل. به این ماشین‌های انتزاعی اتوماتا گفته می شود. این نظریه بسیار نزدیک به نظریه زبان‌های فرمال است. به طوری که اتوماتا اغلب توسط دستهٔ زبان‌های رسمی قابل تشخیص دسته بندی می شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبان‌های فرمال هستند.

    ۱- توضیحات پایه
    ۲ -تعاریف پایه نظریه ماشین‌ها
  ۲.۱ -شرح غیر قراردادی
  ۲.۲ -شرح قراردادی
  ۲.۲.۱ -واژگا
   ۲.۲.۲- ماشین
  ۲.۲.۳ -کلمهٔ ورودی
  ۲.۲.۴ -اجرا
  ۲.۲.۵ -کلمهٔ مورد قبول
   ۲.۲.۶ -زبان شناخته شده
    ۲.۲.۷ -زبان‌های قابل تشخیص
  ۳ -انواع ماشین‌های خودکار کراندار
۳.۱ -گسترهٔ ماشین‌های متناهی

 

توضیحات پایه
مثالی از اتوماتا و مطالعه خصوصیات ریاضی چنین اتوماتونی نظریه اتوماتا است.

یک ماشین، یک مدل ریاضی از ماشین با حالات متناهی (FSM) است. یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که می‌تواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود.

به صورت کلی، یک ماشین شامل مجموعه‌ای متناهی یا شمارا از حالات مختلف است.

در ادامه تعریفی مقدماتی از یک نوع اتوماتا می‌باشد که به فهم مفاهیم ضروری مورد بحث در نظریهٔ ماشین‌ها کمک می‌کند.
تعاریف پایه نظریه ماشین‌ها
شرح غیر قراردادی

یک ماشین خودکار قرار است که بر روی تعدادی ورودی از دنباله یا رشته در مراحل زمانی گسسته اجرا شود. در هر مرحله از زمان، ماشین یک ورودی که از مجموعه‌ای از نمادها یا حرف‌ها برداشته شده‌است را، می‌گیرد که به آن الفبا (Alphabet) گفته می‌شود. یک ماشین حاوی مجموعهٔ متناهی از حالت‌هاست. در هر لحظه از اجرا بسته به نوع ماشین، می‌تواند در یکی یا چند تا از حالت‌هایش باشد. در هر مرحلهٔ زمانی، هنگامی که ماشین یک نماد را می‌خواند، بر اساس حالت فعلی و نماد خوانده شده به حالت بعدی پرش یا گذر می‌کند. این تابع روی حالت فعلی و نماد ورودی تابع گذار گفته می‌شود. ماشین تا زمانی که یک ورودی کامل خوانده شود ورودی را نماد به نماد در دنباله‌ای می‌خواند و از حالتی به حالت دیگر بر اساس تابع گذار، گذر می‌کند. زمانی که ورودی نهایی خوانده می‌شود، اصطلاحاً ماشین متوقف شده‌است و به این حالت، حالت نهایی می‌گویند. بر اساس حالت نهایی گفته می‌شود که ماشین یک ورودی را قبول یا رد کرده‌است. زیر مجموعه‌ای از حالت‌های ماشین وجود دارد که به عنوان مجموعهٔ حالت‌های مورد قبول تعریف می‌شود. اگر حالت نهایی یک حالت مورد قبول باشد ماشین ورودی را پذیرفته‌است. در غیر این صورت ورودی رد می‌شود. به مجموعه‌ای از ورودی‌ها که توسط ماشین پذیرفته می‌شود زبان قابل تشخیص ماشین می‌گویند.
شرح قراردادی
واژگان

   نماد: کوچک‌ترین و بنیادی‌ترین موجودیتی که دارای معنی یا تأثیری بر ماشین است. برخی مواقع به نمادها حرف هم گفته می‌شود.

    الفبا: یک مجموعه متناهی از نمادها که در یک زبان تعریف شده‌اند. الفبای زبان توسط Σ نشان داده می‌شود.

   کلمه: دنباله‌ای متناهی از نمادهای یک الفباست که با عمل الحاق به هم پیوسته‌اند.

    زبان: مجموعه‌ای از رشته‌ها است. این مجموعه می‌تواند متناهی یا نامتناهی باشد.

ماشین

۵ تایی نمایندهٔ یک ماشین خودکار است که در آن:

    Q مجموعه‌ای از حالات است.
    ∑ یک مجموعهٔ کراندار از نمادهاست که ما آن را الفبای زبانی که ماشین خودکار می‌پذیرد، می‌نامیم.
    δ تابع گذار است که

    (برای ماشین خودکار غیر قطعی، یک رشتهٔ خالی نیز یک ورودی قابل قبول است)

    q0 حالت شروع است، یعنی حالتی از ماشین خودکار که در آن، هیچ یک از ورودی‌ها هنوز پردازش نشده‌است (بدیهی است که )
    F مجموعه‌ای از حالات Q است (برای مثال F⊆Q) که وضعیت‌های قبول نامیده می‌شوند.

با داشتن حرف ورودی a که می‌توان تابع گذار را به صورت نوشت. که این کار با استفاده از ترفند سادهٔ مالشصورت می‌گیرد (ترفند مالش عبارت است از نوشتن δ(q,a) = δaq به ازای همهٔ q\in Q). با این روش، تابع گذار به فرم ساده تری تبدیل می‌شود. ترکیب تابع تکرار شده یک مونوئیدرا تشکیل می‌دهد. برای توابع گذار، این مونوئید تحت نام مونوئید گذاریا در بعضی مواقع نیم گروه دگرسازیشناخته می‌شود.

کلمهٔ ورودی

ماشین یک رشتهٔ متناهی از نمادهای a1,a2,....,an را که می‌خواند که کلمهٔ ورودی گفته می‌شود. مجموعهٔ تمام کلمات با *Σ مشخص می‌شود. گاهی اوقات یک کاراکتر خاص برای مشخص کردن انتهای یک رشته به کار می‌رود (بعضی اوقات با λ نمایش داده می‌شود) که همچنین در الفبا نیز موجود است.

اجرا
یک اجرا ماشین بر روی یک کلمهٔ ورودی، یک دنباله از حالت هایq0,q1,q2,....,qn است که، به طوری که q0 حالت شروع است و برای داریم qi = δqi − 1,ai . به عبارت دیگر در ابتدا ماشین در حالت شروع q0 است و بعد ماشین دنباله وار نمادهای کلمهٔ ورودی را می خواند. وقتی ماشین نماد ai را می خواند به حالت qi = δqi − 1,ai جهش می کند. qn حالت نهایی اجرا گفته می شود.

کلمهٔ مورد قبول
یک کلمه توسط ماشین مورد قبول است اگر .

زبان شناخته شده

یک ماشین می تواند یک زبان رسمی(formal language) را تشخیص دهد. یک زبان شناخته شده توسط یک ماشین مجموعه ای از کلمات است که برای ماشین پذیرفته باشد.

زبان‌های قابل تشخیص

زبان‌های قابل تشخیص مجموعه ای از زبان‌ها هستند که برای برخی از ماشین‌ها شناخته شده باشند. برای تعریف بالا از ماشین زبان‌های قابل تشخیص زبان‌های با قاعده هستند. برای تعاریف متفاوت از ماشین، زبان‌ها قابل تشخیص متفاوت هستند.

با داشتن یک جفت از حروفتابع جدید به صورت تعریف می‌شود که نشان دهندهٔ ترکیب توابع است. طبیعتا، این فرایند می‌تواند بطور بازگشتی ادامه یابد و بنابراین یک تعریف بازگشتی از تابع داریم که برای تمام کلمات تعریف شده است و به شرح زیر است

این ساختار می‌تواند معکوس هم بشود، با داشتن، می‌توان دوباره δ را ساخت و بنابراین، این دو توصیف هم ارزند.

سه تایی تحت نام ماشین نیمه خودکار شناخته می‌شود. ماشین نیمه خودکار همان ماشین خودکار است با این تفاوت که وضعیت شروع و مجموعهٔ وضعیت‌های قبول آن نادیده گرفته شده اند. مفهوم‌های افزودهٔ وضعیت اولیه و وضعیت قبول باعث می‌شوند تا توانائی ماشین خودکار بیش از توانائی ماشین نیمه خودکار باشد، بدین شرح که ماشین نیمه خودکار نمی‌تواند یک زبان‌های فرمال را شناسائی کند. زبان L که توسط ماشین خودکار قطعی کراندار پذیرفته شده است، این گونه تعریف می‌شود:

توضیح اینکه، زبان پذیرفته شدهٔ ماشین خودکار(یعنی L) مجموعه‌ای از کلمات w است که با الفبای Σ ساخته شده اند و وقتی به عنوان ورودی به ماشین خودکار داده می‌شوند، نهایتا یکی از وضعیت‌های F را نتیجه می‌دهند. زبانهایی را که توسط ماشین خودکار پذیرفته شده اند، زبان‌های قابل تشخیص می نامند.

وقتی مجموعهٔ وضعیت‌های Q کراندار است، ماشین خودکار به عنوان ماشین خودکار وضعیت محدود شناخته می‌شود و مجموعهٔ همهٔ زبان‌های قابل تشخیص آن را، زبان‌های باقاعده می نامیم. در واقع یک هم ارزی قوی وجود دارد: به ازای هر زبان باقاعده یک ماشین خودکار وضعیت محدود وجود دارد.

انواع ماشین‌های خودکار کراندار

در زیر، سه نوع از ماشین‌های خودکار کراندار ذکر شده است

ماشین‌های خودکار کراندار قطعی
    هر وضعیت از یک ماشین خودکار از این نوع، یک گذار برای هر نشانه دارد.
ماشین‌های خودکار کراندار غیر قطعی
    وضعیت‌های یک ماشین خودکار کراندار غیر قطعی، ممکن است برای هر نشانه یک گذار داشته باشد و یا اصلا انتقالی نداشته باشد و یا حتی می‌تواند برای یک نشانه، گذارهای متعددی داشته باشد. این ماشین خودکار، کلمه را در صورتی می پذیرد که حداقل یک مسیر از q0 به وضعیتی از F وجود داشته باشد. اگر گذار تعریف نشده باشد، ماشین نمی‌داند که چگونه به خواندن ورودی ادامه دهد و در نتیجه کلمه پذیرفته نمی‌شود.
ماشین‌های خودکار کراندار غیر قطعی با ε-گذار
    علاوه بر اینکه می‌توانند با هر نشانه‌ای به وضعیت‌های بیشتری( یا هیچ وضعیتی) پرش کنند، این ماشین‌ها می‌توانند که به روی هیچ نشانه‌ای پرش نکنند. به این معنا که، اگر یک وضعیت گذارهای نامگذاری شده با ε را دارد، این ماشین می‌تواند در هر وضعیتی که به وسیلهٔ ε-گذار بدست آمده قرار گیرد که این کار می‌تواند با واسطه یا بدون واسطهٔ وضعیت‌های دیگر صورت گیرد. مجموعهٔ وضعیت هایی که می‌توان به وسیلهٔ این شیوه از وضعیت q بدست آورد، ε-بستار برای qنامیده می‌شود.

با این وجود می‌توان نشان داد که تمام این ماشین ها، می‌توانند زبان‌های مشابهی را بپذیرند.

گسترهٔ ماشین‌های متناهی

خانوادهٔ زبان هایی که با ماشین‌های توصیف شده در بالا پذیرفته می‌شوند، خانوادهٔ زبان‌های باقاعده نامیده می‌شوند. هر چه یک ماشین قوی تر باشد، می‌تواند زبان‌های پیچیده تری را بپذیرد. ماشین‌های خودکار این چنینی عبارتند از:

ماشین‌های خودکار پائین فشردنی
    این ماشین‌ها همانند ماشین‌های خودکار کراندار قطعی (یا ماشین‌های خودکار کراندار غیر قطعی) هستند با این تفاوت که حافظه را به صورت پشته به دوش می‌کشند. و بنابراین تابع گذار δ نیز به نشانه‌ای که در بالای پشته قرار دارد وابسته است و همین تابع مشخص می‌کند که در هر گذار، پشته چگونه باید تغییر داده شود. ماشین‌های پائین فشردنی غیر قطعی، زبان‌های مستقل از متن را می پذیرند.
ماشین‌های خودکار کراندار خطی
    یک ماشین خودکار کراندار خطی، یک ماشین تورینگ محدود شده است که در آن، به جای یک نوار نامتناهی، فضایی متناسب با اندازهٔ رشتهٔ وارد شده، بر روی نوار وجود دارد. این ماشین‌ها زبان‌های حساس به متن را می پذیرند.
ماشین‌های تورینگ
    این ماشین ها، قدرتمندترین ماشین‌های محاسباتی هستند. این ماشین‌ها دارای یک حافظهٔ نامتناهی (به شکل یک نوار) و یک هد (که می‌تواند نوار را بخواند و تغییر دهد و در سرتاسر نوار در هر جهتی جابجا شود) هستند. ماشین‌های تورینگ با الگوریتم‌ها هم ارزند و پایهٔ نظری برای کامپیوترهای جدید می‌باشند. ماشین‌های تورینگ زبان‌های بازگشتی را می پذیرند و زبان‌های بازگشت شمارش پذیر را شناسایی می‌کنند.

[Amir Shahbazzadeh]

نظریه اعداد شاخه‌ای از ریاضیات محض است که در مورد خواص اعداد صحیح بحث می‌کند.

    ۱- نظریه مقدماتی اعداد
    ۲- نظریه تحلیلی اعداد
    ۳ -نظریه جبری اعداد
    ۴ -نظریه هندسی اعداد
    ۵ -نظریه ترکیبیاتی اعداد
    ۶ -نظریه محاسباتی اعداد
    ۷ -اعداد اول گاوس
    ۸ -اعداد صحیح گاوس
    ۹ -به عنوان یک دامنه فاکتور یگانه
    ۱۰ -اعداد اول گاوس
    ۱۱ -پیشینه نظریه اعداد
       

نظریه مقدماتی اعداد

در نظریه مقدماتی اعداد، اعداد صحیح را بی استفاده از روش‌های به‌کار رفته در سایر شاخه‌های ریاضی بررسی می‌کنند. مسائل بخش پذیری، الگوریتم اقلیدس برای محاسبه بزرگ‌ترین مقسوم‌علیه مشترک(ب.م.م)، تجزیه اعداد به اعداد اول، جستجوی عدد تام و همنهشتی‌ها در این رده هستند. برخی از یافته‌های مهم این رشته قضیه کوچک فرما، قضیه اعداد اول و قضیه اویلر، قضیه باقیمانده چینی و قانون تقابل درجه دوم هستند. خواص توابع ضربی مانند تابع موبیوس و تابع φ اویلر و دنباله اعداد صحیح و فاکتوریل‌ها و اعداد فیبوناچی در همین حوزه قرار دارند.

حل بسیاری از مسائل در نظریه مقدماتی اعداد بر خلاف ظاهر ساده آن‌ها نیازمند کوشش بسیار و به‌کار گرفتن روش‌های نوین است. چند نمونه:

    حدس گلدباخ در مورد نمایش اعداد زوج به صورت جمع دو عدد اول،
    حدس کاتالان در مورد توانهای متوالی از اعداد صحیح،
    حدس اعداد اول تؤامان در مورد بینهایت بودن زوج‌های اعداد اول،
    حدس کولاتز در مورد تکرار ساده،
    حدس اعداد اول مرسن در مورد بینهایت بودن اعداد اول مرسن و ...

همچنین ثابت شده که نظریه معادلات دیوفانتی تصمیم‌ناپذیر است

نظریه تحلیلی اعداد

در نظریه تحلیلی اعداد از حسابان و آنالیز مختلط برای بررسی سؤالاتی در مورد اعداد صحیح استفاه می‌شود. مثال‌هایی در این مورد قضیه اعداد اول و فرض ریمان هستند. مسئله وارینگ (یعنی نمایش هر عدد صحیح به صورت جمع چند مربع یا مکعب)، حدس اعداد اول تؤامان (یافتن بینهایت عدد اول با اختلاف ۲)، و حدس گلدباخ (نمایش هر عدد زوج به‌صورت مجموع دو عدد اول) نیز با روشهای تحلیلی مورد حمله قرار گرفته‌اند. اثبات متعالی(ترافرازنده) بودن ثابت‌های ریاضی، مانند π و e نیز در بخش نظریه تحلیلی اعداد قرار دارند. اگرچه حکم‌هایی در مورد اعداد ترافرازنده خارج از محدوده مطالعات اعداد صحیح به نظر می‌آید، در واقع مقادیر ممکن برای چند جمله‌ای‌ها با ضریب‌های صحیح مانند e را بررسی می‌کنند. همچنین این‌گونه مسائل با مبحث تقریب دیوفانتین نیز ارتباط نزدیک دارند که موضوع آن این است که چگونه می‌توان یک عدد حقیقی داده شده را با یک عدد گویا تقریب زد؟

نظریه جبری اعداد

در نظریه جبری اعداد، مفهوم عدد به اعداد جبری، که همان ریشه‌های چند جمله‌ای‌هائی با ضریب گویا هستند، گسترش می‌یابد. در این حوزه اعدادی مشابه اعداد صحیح با نام اعداد صحیح جبری وجود دارد. در این عرصه لازم نیست ویژگی‌های آشنای اعداد صحیح (مانند تجزیه یگانه) برقرار باشد. مزیت روش‌های استفاده شده در این رشته (مثل نظریه گالوا، میدان همانستگی field cohomology، نظریه رده میدان class field theory، نمایش‌های گروه‌ها و توابع-L) این است که برای این رده از اعداد، نظم را تا حدودی تأمین م‌کند.

حمله به بسیاری از سؤالات نظریه اعداد به صورت «پیمانه p، برای کلیه اعداد اول p» مناسب‌تر است. به چنین کاری «محلی سازی» می‌گویند که به ساختن عدد p-ای می‌انجامد. نام این رشته «تحلیل موضعی» است که از نظریه اعداد جبری ناشی می‌شود.

نظریه هندسی اعداد

نظریه هندسی اعداد (که قبلا به آن هندسه اعداد می‌گفتند) جنبه‌هایی از هندسه را به نظریه اعداد پیوند می‌دهد؛ و از قضیه مینکوسکی در ارتباط با نقاط توری در مجموعه‌های محدب و تحقیق در مورد چپاندن کره‌ها (sphere packings) در فضای Rn شروع می‌شود.

نظریه ترکیبیاتی اعداد

نظریه ترکیبیاتی اعداد به مسائلی در نظریه اعداد می‌پردازد که با روش‌های ترکیبیاتی بررسی می‌شوند. پل اردوش بنیان‌گذار اصلی این شاخه از نظریه اعداد بود.

نظریه محاسباتی اعداد

نظریه محاسباتی اعداد به الگوریتم‌های مربوط به نظریه اعداد می‌پردازد. الگوریتم‌های سریع برای امتحان اعداد اول و تجزیه اعداد صحیح در رمزنگاری کاربردهای مهمی دارند .

اعداد اول گاوس

یک عدد اول (مثل 2 یا 3 یا 5) یک عدد طبیعی است (تمام اعداد مثبت) بزرگتر از 1، که فقط بخش پذیر بر خودش و یک می باشد ( و نه اعداد طبیعی دیگر). اعداد طبیعی دیگر (بزرگتر از 1)، اعداد مرکب نامیده می شوند، و قابل تولید با اعداد اول می باشند. یک نه عدد اول است و نه عدد مرکب. به مقالات بیکرانی اعداد اول و sieve of Eratosthenes مراجعه کنید.

در مطالعه اعداد مختلط، اعداد اول مشابهی وجود دارند، به نام اعداد اول گاوس . پاراگراف بعدی برگرفته از مقاله اعداد موهومی من است که ما را با اعداد مختلط آشنا خواهد نمود.

یک عدد موهومی ترکیبی از یک عدد حقیقی و مضربی از رادیکال 1ـ می باشد. رادیکال 1ـ معمولاً i نامیده می شود، که عدد صحیح نیست، عدد حقیقی نیز نمی باشد. این عدد پاسخ سؤال «مربع چه عددی منفی یک (1ـ) است ؟» می باشد. هیچ عدد عادی نمی تواند پاسخ این سؤال باشد. اما دلیل خوبی برای تعریف نوع جدیدی از اعداد، اعداد موهومی، صرفاً برای پاسخ به این سؤال وجود دارد. i3 یا i7ـ اعداد موهومی هستند. در حقیقت اگر ما اعداد موهومی را تعریف کنیم باید اعداد مختلط را نیز تعریف کنیم. یک عدد مختلط ترکیبی از یک عدد حقیقی بعلاوه یک عدد موهومی است. یک عدد موهومی در واقع یک عدد مختلط مثل i3 + 0 می باشد. و یک عدد صحیح معمولی، مثل 5، نیز یک عدد مختلط است : 0i+5.یک عدد صحیح گاوس یک عدد مختلط است با اعداد صحیح برای هر دو بخش حقیقی و موهومی آن. یک عدد اول گاوس، یک عدد صحیح گاوس است که تنها بر خودش و عدد 1 بخش پذیر می باشد( و نه اعداد صحیح گاوس دیگر). ما فقط اعداد مختلطی که بخش حقیقی انها مثبت و بزرگتر یا مساوی ارزش مطلق بخش موهومی است را امتحان می کنیم. وقتی که شروع به امتحان بعضی اعداد اول می کنیم فوراً متوجه می شویم که این اعداد اول گاوس بصورت (a-bi)و(a+bi) هستند و هردو اینها طبق تعریف بالا بعنوان عدد صحیح گاوس محسوب می شوند. و وقتی آنها را در هم ضرب می کنیم به یک عدد صحیح می رسیم : a2 + b2 = (a + bi)(a − bi).همچنین بعضی اعداد اول معمولی ممکن است بوسیله اعداد اول گاوس قابل قبول باشند. بعبارت دیگر این اعداد صحیح اول ممکن است عدد اول گاوس نباشند. این حالت را امتحان می کنیم. با گرفتن یک سرنخ از مقاله Eratosthenes of Sieve، با کوچکترین عدد مختلط صحیح شروع خواهیم نمود، یعنی 1+i فرض می کنیم که این عدد اول گاوس است و می بنیم به چه عدد صحیحی می رسیم :

2=(i+1)(i-1)

بنابراین 2 یک عدد اول گاوس نیست. بعدی 2+i است : 5=(i+2)(i-2) 1+2i به ما همان جواب را می دهد. که مستدل بر آن است که چرا من تصریح نمودم، ما باید فقط اعداد مختلطی را که بخش حقیقی آنها بزرگتر یا مساوی بخش موهومی است، امتحان کنیم . بنابراین اعداد اول ما در دسته های چهارتایی بصورت i+2،2-i،1+2i،1-2i هستند. عدد 3 را که به نظر یک عدد اول گاوس است امتحان نکرده و رد شده ایم . همچنین می توانیم از 2+2i نیز که بطور وضوح مرکب است صرفنظر کنیم. 3+i را امتحان می کنیم.

10 عدد مرکب است. پس ما می توانیم استنباط کنیم که i+3 نیز مرکب است چون بطور وضوح بر i+1 بخش پذیر می باشد. با انجام تقسیم (i-2=(i+1)/( i+3 می توانیم استنباط کنیم که a+bi وقتی هر دوی a و b فرد هستند ( به جز i+1) عدد اول نیست، زیرا a2 + b2 عددی زوج خواهد شد. حالا (3+2i) را امتحان می کنیم.

13=(2iـ3)(3+2i)

3+2i به نظر یک عدد اول گاوس می رسد، ولی 13 عدد اول گاوس نیست. اعداد اول 7 و 11 را رد می کنیم چون به نظر می رسد که اعداد اول گاوس هستند. بعدی i+4 است :

17=( iـ4)(i+4)

پس i+4 یک عدد اول است و 17 عدد گاوس نیست. 3i+3 و 2i+4 بطور واضح اعداد مرکب هستند. 3i+4 بعدی است:

25=( 3iـ4)(4+3i)

25 عددی مرکب است، پس 3i+4 بر i +2 بخش پذیر است. i+5 عددی مرکب است وقتی هر دوی 5 و 1 فرد هستند. 5+2i بعدی است:

29=( 2iـ5)(5+2i)

5+3iمرکب است چون 5 و 3 هر دو فرد هستند. i +6 بعدی است:

37=( iـ6)(i+6)

41=( 4iـ5)(5+4i)

53=( 2iـ7)(7+2i)

61=( 5iـ6)(6+5i)

65=( 4iـ7)(7+4i) (مرکب)

65=( iـ8)(8+i) (مرکب)

73=( 3iـ8)(8+3i)

85=( 6iـ7)(7+6i) (مرکب)

85=( 2iـ9)(9+2i) (مرکب)

89=( 5iـ8)(8+5i)

97=( 4iـ9)(9+4i)


اعداد اول گاوس را که یافته ایم به ترتیب زیر لیست می کنیم :


•1+i

•2+i

• 3

•3+2i

•4+i

•5+2i

•7+i

•5+4i

• 7

•7+2i

•6+5i

•8+3i

•8+5i

•9+4i


اعداد صحیح کوچکتر از 100 که عدد اول گاوس هستند ذیلاً آمده‌اند :

• 3

• 7

•11

•19

•23

•31

•43

•47

•59

•67

•71

•83

اعداد صحیح گاوس


در تئوری اعداد یک عدد صحیح صحیح گاوسی عددی مرکب است که بخش موهومی و حقیقی آن هر دو صحیح هستند. اعداد صحیح گاوسی با جمع معمولی و ضرب اعداد مرکب یک دامنه صحیح را تشکیل می‌دهند که معمولاً به صورت [Z[iنوشته می‌شود. اعداد صحیح گاوسی یک نمونه خاصی از اعداد صحیح درجه دوم هستند.این دامنه فاقد نظمی کلی است که از علم حساب تبعیت می‌کند.

به طور معمول اعداد صحیح گاوسی به صورت زیر هستند:

تابع یک عدد صحیح گاوسی برحسب یک عدد طبیعی به صورت زیر است:



(تأکید روی «a+bi» برمیگردد به مزدوج مرکب)

تابع ضربی است مثل:

. بنابراین یکان و دهگان [Z[i به طور خلاصه همان عناصر تابع 1 مثل 1, −1, iو −i هستند.

به عنوان یک دامنه فاکتور یگانه

اعداد صحیح گاوسی یک دامنه فاکتور یگانه را با مؤلفه‌های 1, −1, i, −i تشکیل میدهند. اگر x یک عدد صحیح گاوسی باشد چهار عدد x, ix, −x, −ix مضارب x نامیده می‌شوند. مؤلفه‌های اول تابع [Z[iبه عنوان اعداد اول گاوسی می‌باشند. مضرب یک عدد اول گاوسی نیز یک عدد اول گاوسی می‌باشد. اعداد اول گاوسی حول محور اعداد حقیقی و اعداد موهومی متقارن است.

یک عدد صحیح گاوسی a + bi اول است اگر و تنها اگر : یکی از a, b صفر است و دیگری یک عدد اول از تابع 4n + 3 یا منفی آن − (4n + 3) وقتی که n \geq 0 یا اینکه هر دویشان صفر نیستند و a2 + b2 عددی اول است. 2 یک نمونه خاص است ( در زبان تئوری اعداد جبری 2 تنها عدد اول منشعب در اعداد صحیح است.) عدد صحیح 2 وقتی که 2 = i(1 − i)2 یک عدد صحیح گاوسی محسوب می‌شود. 2 تنها عدد صحیح اول است که قابل تولید با مربع یک عدد اول گاوسی است. شروط لازم به این صورت بیان می‌شوند: یک عدد صحیح گاوسی اول است وقتی که تابع آن اول است یا تابع آن مربع یک عدد اول است. چون برای هر عدد صحیح گاوسی g داریم g | g\bar{g} =N(g). حالا N(g) یک عدد صحیح است. بنابراین می‌تواند یکی از فاکتورهای اعداد اول گویا باشد مثل اعداد اول در\mathbb{Z} به وسیله قضیه بنیادی حساب. طبق تعریف عدد اول اگرg عدد اول باشد به ازای همه یi می‌تواند pi را تولید کند. همچنین \bar g, \overline{p_i}=p_i را تولید میکند. بنابراین N(g) = g\bar{g} | p_{i}^{2}. این در دوحالت امکان دارد: یا تابع g اول است یا مجذور یک عدد اول است. اگر برای هر عدد اول گویای p، باشد N(g) = p2 پس هر دوی g and \overline{g} می‌توانند p2 را تولید کنند. بنابراین g = pu and \overline{g}=p\overline{u} وقتی که u یک مقسوم علیه مؤلفه‌است. به همین خاطر یا a = 0 یا b = 0 است وقتی که g = a + bi اما هر عدد اول گویای p یک عدد اول گاوسی نیست.2 اینطور نیست چون2 = i(1 − i)2 . اعداد اول تابع 4n + 1 همین طور هستند چون تئوری جمع دو مربع فرما مارا مطمئن می‌کند که این اعداد میتوانند به صورت a2 + b2 برای اعداد صحیح a و b نوشته شوند و a2 + b2 = (a + bi)(a − bi) . تنها نوع اعداداول که باقی می‌ماند تابع 4n + 3 هستند. اعداد اول گویای تابع 4n + 3 اعداد اول گاوسی نیز هستند. به فرض g = p + 0i برای تابع p = 4n + 3 یک عدد اول باشد و به صورت g = hk باشد، یعنی h و k مؤلفه‌های آن باشند و آن را تولید کنند، آنگاه p2 = N(g) = N(h)N(k) . اگر g یک عدد صحیح گاوسی باشد با تابع اول، آنگاه g یک عدد اول گاوسی است. چون اگر g = hk باشد آنگاه N(g) = N(h)N(k) و چون اول است پس یکی از N(k) یا N(h) باید 1 باشد بنابراین یکی ازh یا k باید مؤلفه باشد.


اعداد اول گاوس

یک عدد اول (مثل 2 یا 3 یا 5) یک عدد طبیعی است (تمام اعداد مثبت) بزرگتر از 1، که فقط بخش پذیر بر خودش و یک می باشد ( و نه اعداد طبیعی دیگر). اعداد طبیعی دیگر (بزرگتر از 1)، اعداد مرکب نامیده می شوند، و قابل تولید با اعداد اول می باشند. یک نه عدد اول است و نه عدد مرکب. به مقالات بیکرانی اعداد اول و sieve of Eratosthenes مراجعه کنید. در مطالعه اعداد مختلط، اعداد اول مشابهی وجود دارند، به نام اعداد اول گاوس . پاراگراف بعدی برگرفته از مقاله اعداد موهومی من است که ما را با اعداد مختلط آشنا خواهد نمود. یک عدد موهومی ترکیبی از یک عدد حقیقی و مضربی از رادیکال 1ـ می باشد. رادیکال 1ـ معمولاً i نامیده می شود، که عدد صحیح نیست، عدد حقیقی نیز نمی باشد. این عدد پاسخ سؤال «مربع چه عددی منفی یک (1ـ) است ؟» می باشد. هیچ عدد عادی نمی تواند پاسخ این سؤال باشد. اما دلیل خوبی برای تعریف نوع جدیدی از اعداد، اعداد موهومی، صرفاً برای پاسخ به این سؤال وجود دارد. i3 یا i7ـ اعداد موهومی هستند. در حقیقت اگر ما اعداد موهومی را تعریف کنیم باید اعداد مختلط را نیز تعریف کنیم. یک عدد مختلط ترکیبی از یک عدد حقیقی بعلاوه یک عدد موهومی است. یک عدد موهومی در واقع یک عدد مختلط مثل i3 + 0 می باشد. و یک عدد صحیح معمولی، مثل 5، نیز یک عدد مختلط است : 0i+5.یک عدد صحیح گاوس یک عدد مختلط است با اعداد صحیح برای هر دو بخش حقیقی و موهومی آن. یک عدد اول گاوس، یک عدد صحیح گاوس است که تنها بر خودش و عدد 1 بخش پذیر می باشد( و نه اعداد صحیح گاوس دیگر). ما فقط اعداد مختلطی که بخش حقیقی انها مثبت و بزرگتر یا مساوی ارزش مطلق بخش موهومی است را امتحان می کنیم. وقتی که شروع به امتحان بعضی اعداد اول می کنیم فوراً متوجه می شویم که این اعداد اول گاوس بصورت bi+a وa+bi هستند و هردو اینها طبق تعریف بالا بعنوان عدد صحیح گاوس محسوب می شوند. و وقتی آنها را در هم ضرب می کنیم به یک عدد صحیح می رسیم : a^2+b^2=(a-bi)bi+a)) همچنین بعضی اعداد اول معمولی ممکن است بوسیله اعداد اول گاوس قابل قبول باشند. بعبارت دیگر این اعداد صحیح اول ممکن است عدد اول گاوس نباشند. این حالت را امتحان می کنیم. با گرفتن یک سرنخ از مقاله Eratosthenes of Sieve، با کوچکترین عدد مختلط صحیح شروع خواهیم نمود، یعنی 1+i فرض می کنیم که این عدد اول گاوس است و می بنیم به چه عدد صحیحی می رسیم : 1+ i)(1-i)=2 ) بنابراین 2 یک عدد اول گاوس نیست. بعدی 2+i است : (2+I)(2-i)=5 1+2i به ما همان جواب را می دهد. که مستدل بر آن است که چرا من تصریح نمودم، ما باید فقط اعداد مختلطی را که بخش حقیقی آنها بزرگتر یا مساوی بخش موهومی است، امتحان کنیم . بنابراین اعداد اول ما در دسته های چهارتایی بصورت 2+i،2-i،1+2i،1-2i هستند. عدد 3 را که به نظر یک عدد اول گاوس است امتحان نکرده و رد شده ایم . همچنین می توانیم از 2+2i نیز که بطور وضوح مرکب است صرفنظر کنیم. 3+i را امتحان می کنیم. 3+i)(3-i)=10 ) 10 عدد مرکب است. پس ما می توانیم استنباط کنیم که i+3 نیز مرکب است چون بطور وضوح بر i+1 بخش پذیر می باشد. با انجام تقسیم iـ2= (i+1)/( i+3) می توانیم استنباط کنیم که a+bi وقتی هر دوی a و b فرد هستند ( به جز i+1) عدد اول نیست، زیرا 2^a + 2^b عددی زوج خواهد شد. حالا i2+3 را امتحان می کنیم. 13=(i2ـ3)(i2+3) i2+3 به نظر یک عدد اول گاوس می رسد، ولی 13 عدد اول گاوس نیست. اعداد اول 7 و 11 را رد می کنیم چون به نظر می رسد که اعداد اول گاوس هستند. بعدی i+4 است : 17=( iـ4)(i+4) پس i+4 یک عدد اول است و 17 عدد گاوس نیست. i 3+3 و i 2+4 بطور واضح اعداد مرکب هستند. i 3+4 بعدی است: 25=( i 3-4)(i 3+4) 25 عددی مرکب است، پس i 3+4 بر i +2 بخش پذیر است. i+5 عددی مرکب است وقتی هر دوی 5 و 1 فرد هستند. i 2+5 بعدی است: 29=( i 2-5)(i 2+5) i3+5 مرکب است چون 5 و 3 هر دو فرد هستند. i +6 بعدی است:

   

کد [انتخاب] Expand

                                                                                                                                  37=( i ـ6)(i +6)
                                                                                                                                    41=( i4ـ5)(i4+5)

53=( i2-7)(i2+7) 61=( i5-6)(i5+6)

                                (مرکب)                                                     65= (i4-7)(i4+7)
                                (مرکب)                                                  65=( i-8)(i+8)

73=( i3-8)(i3+8)

                                (مرکب)                                                     85 =( i6-7)(i6+7)
                                (مرکب)                                                  85=( i2-9)(i2+9)


89=( i5-8)(i5+8) 97=( i4-9)(i4+9) اعداد اول گاوس را که یافته ایم به ترتیب زیر لیست می کنیم : • 1+i • 2+i • 3 • 3+2i • 4+i • 5+2i • 7+i • 5+4i • 7 • 7+2i • 6+5i • 8+3i • 8+5i • 9+4i اعداد صحیح کوچکتر از 100 که عدد اول گاوس هستند ذیلاً آمده‌اند : • 3 • 7 • 11 • 19 • 23 • 31 • 43 • 47 • 59 • 67 • 71 • 83

پیشینه نظریه اعداد

پس از دوران یونان باستان، نظریه اعداد در سده شانزدهم و هفدهم با زحمات ویت Viete، باشه دو مزیریاک Bachet de Meziriac، و بخصوص فرما دوباره مورد توجه قرار گرفت. در قرن هجدهم اویلر و لاگرانژ به قضیه پرداختند و در همین مواقع لوژاندرLegendre (۱۷۹۸)و گاوسGauss (۱۸۰۱) به آن تعبیر علمی بخشیدند. در ۱۸۰۱ گاوس در مقاله Disquisitiones Arithmeticæ حساب نظریه اعداد مدرن را پایه گذاری کرد.

چبیشف Chebyshev (۱۸۵۰) کران‌هایی برای تعداد اعداد اول بین یک بازه ارائه داد. ریمانRiemann (۱۸۵۹) اظهار کرد که حد تعداد اعداد اول از یک عدد داده شده تجاوز نمی‌کند. (قضیه عدد اول) و آنالیز مختلط را در تئوری تابع زتای ریمان Riemann zeta functionگنجاند. و فرمول صریح تئوری اعداد اولexplicit formulae of prime number theory را از صفرهای آن نتیجه گرفت. تئوری همنهشتی congruences از Disquisitiones گاوس شروع شد. او علامت‌گذاری زیر را پیشنهاد کرد: mod(c)

چبیشف در سال ۱۸۴۷ به زبان روسی کاری را در این زمینه منتشر کرد و سره Serret آن را در فرانسه عمومی کرد. بجای خلاصه کردن کارهای قبلی، لوژاندر قانون تقابل درجهٔ دوم را گذاشت. این قانون از استقراء کشف شد و قبلاً اویلر آن را مطرح کرده بود. لوژاندر در کتاب تئوری اعداد Théorie des Nombres (۱۷۹۸) برای حالت‌های خاص آن را ثابت کرد. جدا از کارهای اویلر و لوژاندر، گاوس این قانون را در سال ۱۷۹۵ کشف کرد و اولین کسی بود که یک اثبات کلی ارائه داد. کوشی Cauchy؛ دیریشله Dirichlet (که مقاله Vorlesungen über Zahlentheorie) او یک مقاله کلاسیک است؛ جکوبی Jacobi که علامت جکوبی Jacobi symbol را معرفی کرد؛ لیوویل Liouville؛ زلر Zeller؛ آیزنشتین Eisenstein؛ کومرKummer و کرونکر Kronecker نیز در این زمینه کارهایی کرده‌اند. این تئوری تقابل درجه دوم و سوم cubic and biquadratic reciprocity را شامل می‌شود (گاوس؛ جکوبی که اولین بار قانون تقابل درجه سوم cubic reciprocity را ثابت کرد؛ و کومر).

نمایش اعداد با صورت درجه دوم دوتایی binary quadratic forms مدیون گاوس است. کوشی، پوانسو Poinsot (۱۸۴۵)، لوبکLebesque (۱۸۵۹-۱۸۶۸) و بخصوص هرمیت Hermite به موضوع چیزهایی افزوده‌اند. آیزنشتاین در تئوری صورت‌های سه‌گانه پیشتاز است، و تئوری فرم‌ها theory of forms به طور کلی مدیون او و اچ. اسمیتH. J. S. Smith است. اسمیت دسته بندی کاملی از صورتهای سه گانه انجام داد و تحقیقات گاوس در مورد صورت‌های درجه دوم حقیقی به فرمهای مختلط افزود. جستجوهایی در مورد نمایش اعداد به صورت جمع ۴، ۵، ۶، ۷، ۸ مربع توسط آیزنشتاین ادامه یافت و اسمیت آن را کامل کرد.

دیریشله اولین کسی بود که در یک دانشگاه آلمانی در این مورد سخنرانی کرد. او در مورد بسط قضیه اویلر که می‌گوید:


که اویلر و لوژاندر برای ۰۴ ۳ = n آن را ثابت کردند و دیریشله نشان داد که: z5 y5 x۵ +.

بین نویسندگان فرانسوی بورل Borel و پوانکاره Poincare ذهن قوی داشتند و تانریTannery و استیلچز Stieltjes. کرونکر، کومر، شرینگ Schering، باخمن Bachmann و ددکیند Dedekind آلمانی‌های پیشتاز هستند. در اتریش مقاله استلز Stolz's vorlesungen uber allgemeine Arithmetik (۱۸۸۵-۸۶) و در انگلستان تئوری اعداد ماتیو Mathew (قسمت اول، ۱۸۹۲) جزو کارهای عمومی دانشگاهی هستند. جنوچیGenocchi، سیلوستر Sylvester، و جی. گلیشرJ.W.L. Glaisher به این تئوری چیزهایی افزوده‌اند.

[Amir Shahbazzadeh]

نظریه گرافشاخه‌ای از ریاضیات است که دربارهٔ گراف‌ها بحث می‌کند. به صورت شهودی، گراف نموداری است، شامل تعدادی رأس، که با یال‌هایی به هم وصل شده‌اند.

1- تعریف
۲- اندازه گراف
۳- درجه راس‌ها
  ۴ -انواع گراف
        ۴.۱- گراف هی وود(Heawood Graph)
-۴.۲ گراف کنزر(Kneser)
- ۴.۳ گراف کامل
        ۴.۴ -گراف پترسن
        ۴.۵ -گراف دو بخشی
            ۴.۵.۱ -مفهوم شهودی
            ۴.۵.۲ -تعریف
        ۴.۶ -گراف ساده
        ۴.۷ -گراف همیلتونی
        ۴.۸ -گراف چرخ
        ۴.۹ -گراف چندگانه
        ۴.۱۰ -گراف مکعبی
        ۴.۱۱ -گراف جهت دار
        ۴.۱۲ -گراف جهتدارو کاربردهای آن
        ۴.۱۳ -گراف مسطح
        ۴.۱۴ -گراف وزن دار
    ۵ -خصوصیات گراف‌های خاص
    ۶- الگوریتم‌های مهم
        ۶.۱- الگوریتم کراسکال(kruskal)
- ۶.۱.۱ کد برنامه به زبان C
-  ۶.۲ الگوریتم پریم(prim)
- ۶.۲.۱ کد برنامه به زبان C
-۶.۳ الگوریتم فلوید-وارشال(الگوریتم کوتاهترین مسیر)
  ۶.۳.۱ -کد برنامه به زبان C
- ۷ گراف‌های کاربردی
    ۸- کاربردها
    ۹- مطالعهٔ بیشتر

تعریف

تعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط (وصل) شده‌اند.

یال‌ها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده‌ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید. همچنین برای اینکه فاصله بین دو شهر را در گراف نشان دهید، می‌توانید از گراف وزن دار استفاده کنید و مسافت بین شهرها را با یک عدد بر روی هر یال نشان دهید.

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اولر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بوده‌است.

مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.

یکی از قسمت‌های پرکاربرد نظریهٔ گراف، گراف مسطح است که به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل راس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.

نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و ... است.

روابط میان راس‌های یک گراف را می‌توان با کمک ماتریس بیان کرد .

برای نمایش تصویری گراف‌ها معمولاً از نقطه یا دایره برای کشیدن راس‌ها و از کمان یا خط راست برای کشیدن یال بین راس‌ها استفاده می‌شود.

اندازه گراف

اندازه گراف تعداد یال‌های یک گراف است و به صورت |(E(G| بیان می‌شود.

درجه راس‌ها

در نظریه گراف‌ها، درجه یک راس به تعداد یال‌های متصل به آن راس گفته می‌شود. به عبارت دیگر. درجه یک راس تعداد همسایگی (مجاورت)‌های مستقیم یک راس را بیان می‌کند. از آنجا که هر یال در گراف دو راس را به هم وصل می‌کند، مجموع درجه راس‌های یک گراف با دو برابر تعداد یال‌های ان گراف برابر است.

انواع گراف

گراف همبند گرافی است که بین همهی راسهای آن یالی وجود داشته باشد
گراف هی وود(Heawood Graph)
گراف کنزر(Kneser)

گراف کامل

در نظریه گراف ٫یک گراف کامل ٫گرافی است که بین هر دو راس آن دقیقاً یک یال وجود داشته باشد. یک گراف کامل از مرتبه n ٫ دارای n راس و \left(frac({\left(n-1\right)\times n}){2}\right) یال است و آن را با nk نشان می‌دهند.یک گراف کامل یک گراف منتظم از درجه n-۱ است.
گراف پترسن [ویرایش]

گراف پترسن گرافی با ۱۰ راس و ۳- منتظم است که به صورت زیر رسم می گردد:

گراف دو بخشی
مفهوم شهودی
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده اند. حال این سوال مطرح می‌شود که آیا می توان به هر متقاضی شغلی متناسب او اختصاص داد؟ برای حل چنین مسئله ای که به مسئلهٔ تخصیص موسوم است، با استفاده از گراف می توان وضعیت‌های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه ای به نام Y قرار می دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال‌ها وصل می نماید. به عبارت دیگر گراف بوجود امدی دارای یالهای xy است که مر متقاضی x را از مجموعه X به شغلهای مناسب y از مجموعه Y متصل می نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X(متفاضیان) یا هیچ دو راس متعلق به مجموعه Y(مشاغل) توسط هیچ یالی به هم متصل نمی باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می گویند.

تعریف

گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می نامند.

    یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که:

   مثال

به عنوان مثال گراف زیر یک گراف دو بخشی است:
مثالی از يک گراف دو بخشی

گراف ساده

گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأسهای G و اعضای E را یالهای G می‌نامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.


گراف همیلتونی
گراف چرخ

هر گراف G که دارای n راس باشد کهn≥۴ و یکی از رئوس از درجهٔ n-۱ و بقیه از درجهٔ سه باشند، را یک گراف چرخ می نامیم- مانند مثال‌های زیر:

گراف چرخn راسی را با nW نمایش می دهیم.


گراف چندگانه

گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می‌گوییم.

گراف مکعبی

یک گراف «k مکعب» (k-Cube) گرافی است که رئوس آنk تایی از «صفر» و «یک» هستند که دو رأس آن به یکدیگر متصل هستند اگر و فقط اگر دو رأسشان دقیقاً در یک مؤلفه با یکدیگر تفاوت داشته باشند. به‌عبارت دیگر اگر kعددی طبیعی باشد منظور از « kمکعب» گرافی است که رأس‌های آن همهٔ دنباله‌های رقمی از «صفر» و «یک» هستند و دو رأس در این گراف مجاور بوده هرگاه دنباله‌های متناظرشان دقیقاً در یک مؤلفه اختلاف داشته باشند .

می‌توان نشان داد که یک گراف «k مکعب» (k-Cube) دارای ویژگی‌هایی نظیر ذیل است:

    تعداد رؤوس =۲k
    تعداد یال‌ها=k*۲(k-۱)
    گرافی «دوبخشی» (Bipartite) است.

گراف جهت دار
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای V است.

گراف جهتدارو کاربردهای آن

گراف جهت دارو کاربردهای آنگراف جهت دار D، یک سه تایی مرتب( O(D) و A(D) و ( V(D)است که تشکیل شده از یک مجموعه ناتهی V(D) از راسها ویک مجموعه (D) A مجزای از V(D)از کمانها و یک تابع وقوع O(D)که به هر کمان D یک زوج مرتب از راسهای D- که الزاماً متمایز نیستند- را نسبت میدهد. اگر a یک کمان وu,v دو راس باشند به طوری که(u,v) =(a)O (D)، آنگاه میگوئیم که u,a را به v وصل کرده است؛ u، دم v,a سرa نامیده می شود.

گراف مسطح

گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند.

گراف وزن دار

گراف وزن دار: در یک گراف وزن دار، به هر یال یک وزن (عدد) نسبت داده می‌شود. معمولاً اعداد حقیقی به عنوان وزن یال‌ها استفاده می‌شوند. اما بسیاری از الگوریتم‌های پر کاربرد فقط برای گراف‌هایی که دارای وزن صحیح یا مثبت هستند طراحی شده‌اند.

خصوصیات گراف‌های خاص

    اگر درجهٔ همهٔ راس‌ها در گراف ساده با هم برابر و برابر بزرگترین درجهٔ ممکن (یعنی p-۱ ) باشد، گراف مورد نظر منتظم کامل است. در این گونه گراف‌ها، رابطهٔ میان رأس‌ها و یال‌ها چنین است:

    که در آن p \! تعداد راسها، و q \! تعداد یالها است.

    اگر گراف همبند باشد (یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید) ولی دور نداشته باشد (یعنی هیچ نقطه‌ای از دوراه به نقطهٔ بعدی نرسد) می‌گویند گراف درختی است. در اینگونه گراف‌ها فرمول زیر صدق می‌کند (شرط لازم):

    که در آن p \! تعداد رأس‌ها، و q \! تعداد یال‌ها است.

  گراف اویلری و همیلتونی:گاهی اوقات ما می‌خواهیم در یک گراف حرکت کنیم.به اینصورت که از راسی به راسی دیگر برویم.در اینصورت ممکن است برای ما مهم باشد که از روی یال یا راس تکراری حرکت نکنیم(مشابه مسالهٔ فروشندهٔ دوره گرد).این مساله در صرفه جویی زمان و هزینه هم مهم است.(یعنی مبحث بهینه سازی).دراینجا دو موضوع گرافهای اویلری(دور زدن در گراف بدون یال تکراری)و همیلتونی(دور زدن بدون راس تکراری) مطرح می‌شود.براحتی می‌توان بررسی کرد که راسهای گراف اویلری باید درجهٔ زوج داشته باشند.اما اینکه شرایط کامل لازم و کافی برای همیلتونی بودن یک گراف چیست هنوز حل نشده مانده‌است.

الگوریتم‌های مهم
الگوریتم کراسکال(kruskal)
کد برنامه به زبان C

کد [انتخاب] Expand

void kruskal()
{
int i, m, V, E;   
struct edge
{ char v1, v۲; int w; };
struct edge e[maxE];
PQ pq(maxE); EQ eq(maxE);
cin >> V >> E;
for (i = ۱; i <= E; i++)
cin >> e[i].v۱ >> e[i].v۲ >> e[i].w;
for (i = ۱; i <= E; i++)
pq.insert(i, e[i].w);
for (i = ۰; i < V-۱; )
{
if (pq.empty()) break; else m = pq.remove();
if (eq.find(index(e[m].v1),index(e[m].v2),۱))
{ cout << e[m].v۱ << e[m].v۲ << ' '; i++; };
}
}

الگوریتم پریم(prim)
کد برنامه به زبان C

کد [انتخاب] Expand

int testForPrime (int n) {
int p, i;
p = ۱;
i = ۳;
int result = n;
while (i < result) {
result = n / i;
if (n == i * result) {
p = ۰;
i = n;
}
i = i + ۲;
}
return (p);
}

int main (int argc, char * const argv[]) {
int p, i, n;
i = ۳;
n = ۵;
std::cout << «Initiating prime number generation sequence...\n\n۱: ۲\n۲: ۳\n»;
while (۱) {
p = testForPrime (n);
if (p == ۱) {
std::cout << i << «: » << n << «\n»;
i++;
}
n = n + ۲;
}
return ۰;
}[/align]

الگوریتم فلوید-وارشال(الگوریتم کوتاهترین مسیر)
کد برنامه به زبان C

کد [انتخاب] Expand

#include <stdio.h>
#include <conio.h>
void floyd(int cost[۴][۴],int p[۴][۴],int a[۴][۴]);
int cost[۴][۴];
int p[۴][۴];
int a[۴][۴];
int n=۴;
main()
{  int i,j;
        for(i=۰;i<n;i++)
                for(j=۰;j<n;j++)
                        {
                                printf(«Please Enter cost[٪d][٪d] = »,i,j);
                                scanf(«٪d»,&cost[i][j]);
                        }
        floyd(cost,p,a);
        printf(«\n\nArray A = \n»);
        for(i=۰;i<n;i++)
        {  printf(«\n»);
                for(j=۰;j<n;j++)
                        {
                                printf(«  ٪d  »,a[i][j]);
                        }
        }
        printf(«\n\nArray P = \n»);
        for(i=۰;i<n;i++)
        {  printf(«\n»);
                for(j=۰;j<n;j++)
                        {
                                printf(«  ٪d  »,p[i][j]);
                        }
        }
        getch();
        return ۰;
}
void floyd(int cost[۴][۴],int p[۴][۴],int a[۴][۴])
{
        int i,j,k;
        for (i=۰;i<n;i++)
                for (j=۰;j<n;j++)
                {
                        a[i][j] = cost[i][j];
                        p[i][j]=-۱;
                }
        for (k=۰;k<n;k++)
                for (i=۰;i<n;i++)
                        for (j=۰;j<n;j++)
                                if (a[i][k] + a[k][j] < a[i][j])
                                        {
                                                a[i][j] = a[i][k] + a[k][j];
                  p[i][j] = k;
                                        }

گراف‌های کاربردی

گراف بازه‌ها
کاربردها
از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش در آورد. برای مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد. به این صورت که هر وب سایت را به یک راس در گراف تبدیل می‌کنیم و در صورتیکه در این وب سایت لینکی به وب سایت دیگری بود، یک یال جهت دار از این راس به راسی که وب سایت دیگر را نمایش می‌دهد وصل می‌کنیم.

از گراف‌ها همچنین در شبکه‌ها، طراحی مدارهای الکتریکی، اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک، و.... استفاده میشود. مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود. در این جا به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل راس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.

کاربرد گراف بازه‌ها از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده میشود. ساختارهای زیادی را میتوان به کمک گراف‌ها به نمایش در آورد.

درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد . کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاههای معادلات خطی مربوط به شبکه‌های الکتریکی درختها را کشف و نظریه درختها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربنها کشف کرد وقتی مثلا میگوییم در ایزومر مختلف c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقیمانده یک است. اگر هزینه کشیدن مثلا راه آهن بین هر دو شهر ازp شهر مفروض مشخص باشد ارزانترین شبکه ای که این p شهر را به هم وصل می‌کند با مفهوم یک درخت از مرتبه p ارتباط نزدیک دارد. به جای مساله مربوط به راه آهن میتوان وضعیت مربوط به شبکه‌های برق رسانی و لوله کشی نفت و لوکشی گاز و ایجاد کانالهای آبرسانی را در نظر گرفت . برای تعیین یک شبکه با نازلترین هزینه از قاعده ای به نام الگوریتم صرفه جویی استفاده می‌شود که کاربردهای فراوان دارد. از گرافها می توان به عنوان کدهای کمکی نام برد که به DVB Player‌ها در بالا بردن قابلیت‌های آنها کمک میکنند. گراف‌ها دارایی مزایای مختلفی هستند که شفاف تر کردن و واضحتر کردن تصویر و کاهش مصرف CPU به عنوان یکی از اصلی‌ترین مزایای آنها بشمار می رود.

[Amir Shahbazzadeh]

نظریه نوع‌ها شاخه‌ای از منطق، دانش رایانه و فلسفه است که به شناخت سیستم‌های منطقی و کاربرد آن‌ها به جای نظریه مجموعه‌ها می‌پردازد. در نظریه زبان‌های برنامه‌نویسی نظریه نوع‌ها ممکن است به طراحی، تحلیل و شناخت انواع داده‌ها اشاره داشته باشد.

[Amir Shahbazzadeh]

نظریه رده‌ها (نظریه رسته‌ها) شاخه‌ای از ریاضیات محض است که به سازه‌های ریاضی و روابط بین آن‌ها می‌پردازد و به ابزاری مهم در دانش رایانه تبدیل شده است به خصوص در زبان‌های برنامه‌نویسی، نظریهٔ حوزه‌ها، و همزمانی که در این شاخه‌ها معمولاً نظریهٔ رده‌ها پیش‌نیاز است.

[Amir Shahbazzadeh]

هندسه محاسباتییکی از شاخه‌های علوم کامپیوتر است که برای حل مسائل هندسی از روش‌های الگوریتمی استفاده می‌کند. بعضی از مسائل کاملاً هندسی، برآمده از مطالعهٔ الگوریتم‌های هندسهٔ محاسباتی است و مطالعه این گونه مسائل نیز به عنوان بخشی از هندسه محاسباتی به حساب می‌آید.

انگیزهٔ اصلی برای قلمداد کردن هندسه محاسباتی به عنوان یک رشتهٔ علمی، پیشرفت در گرافیک کامپیوتری، طراحی و تولیدات با کمک رایانه  بود. ولی طبیعتاً بسیاری از مسائل در هندسه محاسباتی، قدیمی هستند.

کاربردهای مهم دیگر هندسه محاسباتی در دانش رباتیک (برنامه ریزی حرکتی و مشکلات بصری)، سیستم‌های اطلاعات جغرافیایی(جستجو و مکان‌یابی هندسی، نقشه کشی راه‌ها)، طراحی مدار مجتمع(طراحی و بازبینی هندسی مدارهای مجتمع) و مهندسی با کمک رایانه (برنامه‌ریزی ماشین‌های کنترل عددی)می‌باشد.

شاخه‌های اصلی هندسه محاسباتی عبارتند از:

هندسهٔ محاسباتی ترکیبی (هندسه الگوریتمی): این هندسهٔ محاسباتی اشیای هندسی را به عنوان موجودات گسسته در نظر می‌گیرد. براساس کتابی که توسط پرپاراتا و شاموس[۹] نوشته شده‌است، لفظ هندسه محاسباتی با این مفهوم، نخستین بار در سال ۱۹۷۵ بیان شده‌است.
هندسه محاسباتی عددی (هندسه ماشینی، طراحی هندسی با کمک رایانه و یا مدلسازی هندسی): اساس کار این هندسه محاسباتی این است که اشیای دنیای واقعی را به صورت مناسبی برای محاسبات رایانه‌ای در سیستم‌های کد/کم در آورد. این شاخه ممکن است به عنوان هندسه توصیفی پیشرفته در نظر گرفته شود و اغلب یکی از شاخه‌های گرافیک کامپیوتری و یا کد به حساب می‌آید. هندسه محاسباتی با این معنا، از سال ۱۹۷۱ مورد استفاده قرار گرفت

۱ -هندسهٔ محاسباتی ترکیبی
۱.۱- انواع سؤالات
۱.۱.۱- مسائل ایستا
۱.۱.۲- مسائل جستجوی هندسی
۱.۱.۳ -مسائل پویا
۱.۲ -حالت‌های گوناگون
۲ -هندسهٔ محاسباتی عددی

هندسهٔ محاسباتی ترکیبی

هدف اصلی از پژوهش در زمینهٔ هندسه محاسباتی ترکیبی این است که، برای حل مسائلی که در زمینه اشیای پایه هندسی(نقاط، خط‌ها، چند ضلعی‌ها، چند وجهی‌هاو ...) مطرح می‌شوند، الگوریتم‌ها و ساختارهای داده ی مناسبی تولید شود.

برخی از این مسائل به قدری آسان به نظر می‌رسند که تا زمان پیدایش رایانه‌ها مشکل به حساب نمی‌آمدند. برای مثال به مسئلهٔ نزدیک‌ترین جفت توجه کنید:

  n نقطه در صفحه داریم. دو نقطه‌ای که کمترین فاصله را از یکدیگر دارند پیدا کنید.

می‌توان فاصله بین جفت نقطه‌ها، که تعدادشان معلوم هست را پیدا کرد و بعد کوچک‌ترین عدد را انتخاب کرد. این الگوریتم از مرتبهٔn2 است. منظور این است که زمان اجرایش به مربع تعداد نقاط بستگی دارد. یک نتیجهٔ کلاسیک در هندسهٔ محاسباتی ایجاد الگوریتمی بود که از مرتبهٔ n log n زمان بگیرد. الگوریتم‌های تصادفی که از مرتبهٔ n زمان می‌برند، علاوه بر الگوریتم‌های تعیین کننده‌ای که از مرتبهٔ n log n زمان می‌برند نیز کشف شده‌اند.

برای GIS جدید، گرافیک کامپیوتری و سیستم‌های طراحی مدارهای مجتمع که روزانه ده‌ها و صدها میلیون نقطه را به کار می‌گیرند، تفاوت بین مرتبهٔ n2و مرتبهٔ n log n می‌تواند تفاوت بین روزها و ثانیه‌ها محاسبه، باشد. به همین دلیل است که در هندسه محاسباتی تاکید زیادی روی پیچیدگی محاسباتی شده است.

انواع سؤالات

مسائل اساسی در هندسه محاسباتی را می‌توان با در نظر گرفتن معیارهای گوناگون، به روش‌های گوناگونی طبقه‌بندی کرد. یکی از این رده بندی‌ها در زیر آمده است.

مسائل ایستا

در این گروه ازمسائل، نوعی ورودی داده می‌شود و خروجی متناسب باید به دست بیاید یا پیدا شود. برخی مسائل اساسی این نوع عبارتند از:

    پوستهٔ محدب(رویه محدب): تعدادی نقطه داریم، کوچک‌ترین چند ضلعی یا چند وجهی محدبی را پیدا کنید که دربرگیرندهٔ همه نقطه‌هاست.
    تقاطع پاره خط‌ها: تقاطع‌های بین تعدادی پاره خط را پیدا کنید.
    مثلث بندی دلونی
    دیاگرام ورونوی: با دریافت مجموعه‌ای از نقاط، فضا را بر اساس نزدیک‌ترین نقطه تقسیم‌بندی کنید.
    برنامه نویسی خطی
    نزدیک‌ترین جفت نقطه: با دریافت مجموعه‌ای از نقاط، دونقطه‌ای را بیابید که کم‌ترین فاصله را دارند.
    کوتاه‌ترین مسیر اقلیدسی: دو نقطه را در فضای اقلیدسی (با یک مانع چند وجهی) با کوتاه‌ترین مسیر به هم وصل کنید.
    مثلث بندی چند ضلعی: با دریافت یک چند ضلعی، سطح داخل آن را به تعدادی مثلث تقسیم کنید.

پیچیدگی محاسباتی برای این دسته از مسائل براساس زمان و فضای(حافظهٔ کامپیوتری) لازم برای حل مسئله تقریب زده می‌شود .

مسائل جستجوی هندسی

در مسائل جستجوی هندسی ورودی از دو قسمت تشکيل شده است: قسمت فضای جستجو و قسمت جستجو، که در هر مسئله تغییر می‌کند. قسمت فضای جست‌وجو باید به گونه‌ای پیش پردازش شود که بتواند به نحو مطلوبی به سوالات متعدد جواب دهد.

برخی مسائل اساسی جستجوی هندسی عبارتند از:

    جست‌وجوی محدوده: مجموعه‌ای از نقاط را پیش پردازش می‌کند برای اینکه در داخل محدوده مطلوب، تعداد نقاط را بشمارد.
    محل یابی نقطه: با دریافت فضایی که تقسیم بندی شده، یک ساختار داده تولید می‌کند که به ما می‌گوید نقطه مورد نظر، در کدام قسمت قرار دارد.
    نزدیک‌ترین همسایه: مجموعه‌ای از نقاط را به این منظور پیش پردازش می‌کند که تعیین کند کدام نقطه، به نقطهٔ مورد نظر نزدیک‌تر است.
    ردیابی پرتو: با دریافت مجموعه‌ای از اجسام در فضا، یک ساختار داده تولید می‌کند تا تعیین کند که پرتوی جستجو ی مورد نظر، نخستین بار با کدام جسم برخورد می‌کند.

اگر فضای جستجو ثابت باشد، پیچیدگی محاسباتی برای این دسته از مسائل بر اساس مطالب زیر تخمین زده می‌شود:

    زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که باید در داخل آن جستجو شود.
    زمان (و برخی مواقع یک حافظهٔ اضافی) برای پاسخ به جستجوها.

مسائل پویا
یکی دیگر از گروه‌های اصلی مسائل، مسائل پویا هستند که در آن‌ها هدف، یافتن الگوریتمی مناسب برای یافتن راه حلی است که بعد از هر تغییر دادهٔ ورودی (اضافه یا حذف کردن عناصر هندسی) تکرار شود. الگوریتم‌های این نوع مسائل اغلب شامل ساختارهای دادهٔ پویااست. هر کدام از مسائل هندسه محاسباتی را می توان به مسئلهٔ پویا تبدیل کرد. برای مثال، مسئلهٔ جستجوی محدوده را می‌توان با اضافه کردن امکان اضافه یا حذف کردن نقطه‌ها به مسئلهٔ جستجوی پویای محدوده تبدیل کرد. مسئلهٔ پوستهٔ محدب پویا همان کار مسئلهٔ پوستهٔ محدب را برای مجموعهٔ نقاطی که به طور پویا تغییر می‌کنند انجام می‌دهد.

پیچیدگی محاسباتی این دسته از مسائل با توجه به عوامل زیر تخمین زده می‌شود:

    زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که باید در داخل آن جستجو شود.
    زمان و حافظهٔ لازم برای تغییر دادن ساختار دادهٔ مورد جستجو، بعد از یک تغییر در فضای جستجو.
    زمان (و برخی مواقع یک حافظهٔ اضافی) برای پاسخ به جستجوها.

حالت‌های گوناگون

می‌توان با برخی داده‌ها به گونه‌ای برخورد کرد که با توجه به محتوایشان جزو هر کدام از گروه‌های معرفی شده قرار گیرند. برای مثال، مساله زیر را در نظر بگیرید: نقطه در چند ضلعی: مشخص کنید که یک نقطهٔ مورد نظر داخل چند ضلعی است یا خارج آن. در بسیاری از موارد با این مسئله به عنوان یک تک تیربرخورد می‌شود، یعنی اینکه مربوط به گروه اول است. برای مثال، در بسیاری از نمونه‌های گرافیک کامپیوتری یک مسئلهٔ رایج این است که مشخص کند کدام ناحیه از صفحه توسط نشانه‌گر ماوسکلیک شده است. اما در برخی موارد چند ضلعی مورد نظر تغییر ناپذیر است در حالی که نقطه مورد جستجو را به نمایش می‌گذارد. برای مثال، چند ضلعی وارد شده می‌تواند نمایندهٔ مرز یک کشور باشد و نقطه، مکان یک هواپیما و مسئله تعیین کردن این است که آیا هواپیما از مرز عبور کرده است یا نه. در نهایت، در مثال‌های بیان شده در گرافیک کامپیوتری ورودی‌های متغیر درساختارهای دادهٔ پویا ذخیره می‌شوند، تا به حل سوالاتی که مربوط به نقاط داخل چند ضلعی است، سرعت بخشد.

هندسهٔ محاسباتی عددی

این شاخه به مدل سازی هندسی و طراحی هندسی با کمک کامپیوتر نیز معروف است و اغلب تحت کلیدواژه‌یمنحنی‌ها و سطح‌ها دیده می‌شود. مسئله‌های اصلی در این نوع از هندسهٔ محاسباتی، مدل سازی و ارائهٔ منحنی و سطح می‌باشد. در اینجا مهم‌ترین ابزارها، منحنی‌های پارامتری و سطح‌های پارامتری هستند، مانند خم‌های بزیر، خم‌ها و سطح‌های نواری. از مهم‌ترین روش‌های غیر پارامتری، روش تنظیم رده است. از نخستین و مهم‌ترین کاربردهای هندسهٔ محاسباتی عددی، کاربرد در کشتی سازی، هواپیماسازی و صنایع ماشین آلات می‌باشد. اما امروزه، به دلیل حضور گستردهٔ رایانه‌ها و پیشرفته‌تر شدن آن‌ها حتا جعبه‌های عطر و شامپو نیز با تکنیک‌هایی که برای کشتی‌سازان دهه‌ی1960 ناشناخته بود طراحی می‌شوند.

[Amir Shahbazzadeh]

کامپیوتر کوانتومی ماشینی است که از پدیده‌ها و قوانین مکانیک کوانتوم مانند برهم نهی (Superposition) و درهم تنیدگی (Entanglement) برای انجام محاسباتش استفاده می کند. کامپیوترهای کوانتومی با کامپیوترهای فعلی که با ترانزیستورها کار می کنند تفاوت اساسی دارند. ایده اصلی که در پس کامپیوترهای کوانتومی نهفته است این است که می توان از خواص و قوانین فیزیک کوانتوم برای ذخیره‌سازی و انجام عملیات روی داده‌ها استفاده کرد. یک مدل تئوریک و انتزاعی از این ماشین ها، ماشین تورینگ کوانتومی(Quantum Turing Machine) است که کامپیوتر کوانتومی جهانی (Universal Quantum Computer) نیز نامیده می شود.

اگر چه محاسبات کوانتومی تازه در ابتدای راه قرار دارد، اما آزمایش هایی انجام شده که در طی آنها عملیات محاسبات کوانتومی روی تعداد بسیار کمی از کوبیت‌ها اجرا شده است. تحقیقات نظری و عملی در این زمینه ادامه دارد و بسیاری از موسسات دولتی و نظامی از تحقیقات در زمینه کامپیوترهای کوانتومی چه برای اهداف غیرنظامی و چه برای اهداف امنیتی (مثل تجزیه و تحلیل رمز، Cryptanalysis) حمایت می کنند. اگر کامپیوترهای کوانتومی در مقیاس بزرگ ساخته شوند، می توانند مسائل خاصی را با سرعت خیلی زیاد حل کنند (برای مثال الگوریتم شُور، Shor's Algorithm). البته باید توجه داشت که توابعی که توسط کامپیوترهای کلاسیک محاسبه پذیر (Computable) نیستند، توسط کامپیوترهای کوانتومی نیز محاسبه پذیر نخواهند بود. این کامپیوترها نظریه چرچ-تورینگ را رد نمی کنند. کامپیوترهای کوانتومی فقط برای ما سرعت بیشتر را به ارمغان می آورند.

۱ -نقاط کوانتومی
۲- اصول گزیده ای از کامپیوترهای کوانتومی
۳ -محاسبات کوانتومی
-۳.۱ توانایی و قدرت محاسبات کوانتومی
۴ -پیاده سازی
۵ -منابع

نقاط کوانتومی

تعریف ساده ی نقطه ی کوانتومی این است که یک ذره مادی کوچک، که افزایش یا کاهش یک الکترون خواص آن را به نحو ارزشمندی تغییر دهد. البته اتم‌ها نقطه کوانتومی محسوب می‌شوند، ولی توده‌های چندمولکولی نیز چنین‌اند. در زیست‌شیمی، نقاط کوانتومی گروه‌های اکسیداسیون- احیا خوانده می‌شوند. در نانوتکنولوژی به آنها بیت‌های کوانتومی یا کیوبیت گفته می‌شود. اندازه آنها در حد چند نانومتر است و از انواع مواد همچون سلنید کادمیوم- که رنگهای مختلفی را تولید می‌کند- ساخته می‌شوند. کاربردهای بالقوه آنها در مخابرات و اپتیک است. نانوذرات فلورسنت- که تا پیش از تابش ماوراءبنفش نامرئی هستند- ساختار نانوبلوری قادر به تغییر رنگ از دیگر تعاریف آنهاست. نقاط کوانتومی از دیگر مواد فلورسنت انعطاف بیشتری دارد؛. لذا استفاده از آن‌ها در ساخت کامپیوترهای نانومقیاس بهره‌گیرنده از نور برای پردازش اطلاعات مناسب است.


اصول گزیده ای از کامپیوترهای کوانتومی

رویای محاسبات ماشینی یا ماشینی که بتواند مسائل را در اشکال گوناگون حل کند کمتر از دو قرن است که زندگی بشر را به طور جدی در بر گرفته است. اگر از ابزارهایی نظیر چرتکه و برخی تلاشهای پراکنده دیگر در این زمینه بگذریم، شاید بهترین شروع را بتوان به تلاشهای «چارلز بابیج» و « بلز پاسکال» با ماشین محاسبه مکانیکی شان نسبت داد. با گذشت زمان و تا ابتدای قرن بیستم تلاشهای زیادی جهت بهبود ماشین محاسب مکانیکی صورت گرفت که همه آنها بر پایه ریاضیات دهدهی (decimal) بود، یعنی این ماشین‌ها محاسبات را همان طور که ما روی کاغذ انجام می دهیم انجام می دادند. اما تحول بزرگ در محاسبات ماشینی در ابتدای قرن بیستم شروع شد. این زمانی است که الگوریتم و مفهوم فرایندهای الگوریتمی (algorithmic processes) به سرعت در ریاضیات و بتدریج سایر علوم رشد کرد. ریاضیدانان شروع به معرفی سیستم‌های جدیدی برای پیاده سازی الگوریتمی کلی کردند که در نتیجه آن، سیستم‌های انتزاعی محاسباتی بوجود آمدند. در این میان سهم برخی بیشتر از سایرین بود. آنچه امروزه آنرا دانش کامپیوتر و یا الکترونیک دیجیتال می نامیم مرهون و مدیون کار ریاضیدان برجسته انگلیسی به نام «آلن تورینگ» (Alan Turing) است. وی مدلی ریاضی را ابداع کرد که آنرا ماشین تورینگ می نامیم و اساس تکنولوژی دیجیتال در تمام سطوح آن است. وی با پیشنهاد استفاده از سیستم دودویی برای محاسبات به جای سیستم عدد نویسی دهدهی که تا آن زمان در ماشین‌های مکانیکی مرسوم بود، انقلابی عظیم را در این زمینه بوجود آورد. پس از نظریه طلایی تورینگ، دیری نپایید که «جان فون نویمان» یکی دیگر از نظریه پردازان بزرگ قرن بیستم موفق شد ماشین محاسبه گری را بر پایه طرح تورینگ و با استفاده از قطعات و مدارات الکترونیکی ابتدایی بسازد. به این ترتیب دانش کامپیوتر بتدریج از ریاضیات جدا شد و امروزه خود زمینه ای مستقل و در تعامل با سایر علوم به شمار می رود. گیتهای پیشرفته، مدارات ابر مجتمع، منابع ذخیره و بازیابی بسیار حجیم و کوچک، افزایش تعداد عمل در واحد زمان و غیره از مهم‌ترین این پیشرفتها در بخش سخت افزاری محسوب می شوند. در 1965 «گوردون مور» اظهار کرد که توان کامپیوترها هر دو سال دو برابر خواهد شد. در تمام الین سالها، تلاش عمده در جهت افزایش قدرت و سرعت عملیاتی در کنار کوچک سازی زیر ساختها و اجزای بنیادی بوده است. نظریه مور در دهه‌های 60 و 70 میلادی تقریبا درست بود. اما از ابتدای دهه 80 میلادی و با سرعت گرفتن این پیشرفتها، شبهات و پرسش هایی در محافل علمی مطرح شد که این کوچک سازی‌ها تا کجا می توانند ادامه پیدا کنند؟ کوچک کردن ترازیستورها و مجتمع کردن آنها در فضای کمتر نمی تواند تا ابد ادامه داشته باشد زیرا در حدود ابعاد نانو متری اثرات کوانتومی از قبیل تونل زنی الکترونی بروز می کنند. گرچه همیشه تکنولوژی چندین گام بزرگ از نظریه عقب است، بسیاری از دانشمندان در زمینه‌های مختلف به فکر رفع این مشکل تا زمان رشد فن آوری به حد مورد نظر افتادند. به این ترتیب بود که برای نخستین بار در سال 1982 «ریچارد فاینمن» معلم بزرگ فیزیک و برنده جایزه نوبل، پیشنهاد کرد که باید محاسبات را از دنیای دیجیتال وارد دنیای جدیدی به نام کوانتوم کرد که بسیار متفاوت از قبلی است و نه تنها مشکلات گذشته و محدودیت‌های موجود را بر طرف می سازد، بلکه افق‌های جدیدی را نیز به این مجموعه اضافه می کند. این پیشنهاد تا اوایل دهه 90 میلادی مورد توجه جدی قرار نگرفت تا بالاخره در 1994 «پیتر شور» از آزمایشگاه AT&T در آمریکا نخستین گام را برای محقق کردن این آرزو برداشت. به این ترتیب ارتباط نوینی بین نظریه اطلاعات و مکانیک کوانتومی شروع به شکل گیری کرد که امروز آنرا محاسبات کوانتومی یا محاسبات نانو متری (nano computing) می نامیم. در واقع هدف محاسبات کوانتومی یافتن روشهایی برای طراحی مجدد ادوات شناخته شده محاسبات ( مانند گیت‌ها و ترانزیستورها ) به گونه ایست که بتوانند تحت اثرات کوانتومی، که در محدوده ابعاد نانو متری و کوچکتر بروز می کنند، کار کنند. به نمودار صفحه بعد دقت کنید. در این شکل به طور شماتیک و در سمت چپ یک مدار نیم جمع کننده را مشاهده می کنید که معادل کوانتومی و نانو متری آن در سمت راست پیشنهاد شده است. نوع اتم‌های به کار رفته، نحوه چینش اتم ها، چگونگی ایجاد سلول نمایش یافته ( معماری سلولی ) و چند ویژگی دیگر خصوصیات معادل با گیت‌های به کار رفته در نمونه دیجیتال هستند. یک راه نظری برای پیاده سازی سلول در این طرح، استفاده از «نقاط کوانتومی» (quantum dots) یا چیزی است که در زبان مکانیک کوانتومی آنرا «اتم مصنوعی » می نامیم.

محاسبات کوانتومی

کامپیوتر تنها بخشی از دنیایی است که ما آنرا دنیای دیجیتالی می نامیم. پردازش ماشینی اطلاعات، در هر شکلی، بر مبنای دیجیتال و محاسبات کلاسیک انجام می شود. اما کمتر از یک دهه است که روش بهتر و قدرتمندتر دیگری برای پردازش اطلاعات پیش رویمان قرار گرفته که بر اساس مکانیک کوانتومی می باشد. این روش جدید با ویژگیهایی همراه است که آنرا از محاسبات کلاسیک بسیار متمایز می سازد. گرچه محاسبات دانشی است که اساس تولد آن در ریاضیات بود، اما کامپیوترها سیستم هایی فیزیکی هستند و فیزیک در آینده این دانش نقش تعیین کننده ای خواهد داشت. البته وجود تفاوت بین این دو به معنای حذف یکی و جایگزینی دیگری نیست. به قول «نیلس بور» گاهی ممکن است خلاف یک حقیقت انکار ناپذیر منجر به حقیقت انکار ناپذیر دیگری شود. بنابراین محاسبات کوانتومی را به عنوان یک زمینه و روش جدید و بسیار کارآمد مطرح می کنیم. وجود چند پدیده مهم که مختص فیزیک کوانتومی است، آنرا از دنیای کلاسیک جدا می سازد. این پدید ه‌ها عبارتند از: بر هم نهی(superposition)، تداخل (interference) ، Entanglement، عدم موجبیت (non determinism)، نا جایگزیدگی (non locality) و تکثیر ناپذیری (non clonability) . برای بررسی اثرات این پدیده‌ها در این روش جدید، لازم است که ابتدا واحد اطلاعات کوانتومی را معرفی کنیم. هر سیستم محاسباتی دارای یک پایه اطلاعاتی است که نماینده کوچکترین میزان اطلاعات قابل نمایش، چه پردازش شده و چه خام است. در محاسبات کلاسیک این واحد ساختاری را بیت می نامیم که گزیده واژه «عدد دودویی» است زیرا می تواند تنها یکی از دو رقم مجاز صفر و یک را در خود نگه دارد. به عبارت دیگر هر یک از ارقام یاد شده در محاسبات کلاسیک، کوچکترین میزان اطلاعات قابل نمایش محسوب می شوند. پس سیستم هایی هم که برای این مدل وجود دارند باید بتوانند به نوعی این مفهوم را عرضه کنند. در محاسبات کوانتومی هم چنین پایه ای معرفی می‌شود که آنرا کیوبیت (qubit) یا بیت کوانتومی می نامیم. اما این تعریف کیوبیت نیست و باید آنرا همراه با مفهوم و نمونه‌های واقعی و فیزیکی درک کرد. در ضمن فراموش نمی کنیم که کیوبیت‌ها سیستم هایی فیزیکی هستند، نه مفاهیمی انتزاعی و اگر از ریاضیات هم برای توصیف آنها کمک می گیریم تنها بدلیل ماهیت کوانتومی آنها است. در فیزیک کلاسیک برای نگه داری یک بیت از حالت یک سیستم فیزیکی استفاده می شود. در سیستم‌های کلاسیکی اولیه ( کامپیوترهای مکانیکی ) از موقعیت مکانی دندانه‌های چند چرخ دنده برای نمایش اطلاعات استفاده می شد. از زمانیکه حساب دودویی برای محاسبات پیشنهاد شد، سیستم‌های دو حالتی انتخابهای ممکن برای محاسبات عملی شدند. به این معنی که تنها کافی بود تا سیستمی دو حالت یا دو پیکربندی مشخص، متمایز و بدون تغییر داشته باشد تا بتوان از آن برای این منظور استفاده کرد. به همین جهت، از بین تمام کاندیداها، سیستم‌های الکتریکی و الکترونیکی برای این کار انتخاب شدند. به این شکل، هر بیت، یک مدار الکتریکی است که یا در آن جریان وجود دارد یا ندارد. هر بیت کوانتومی یا کیوبیت عبارت است از یک سیستم دودویی که می تواند دو حالت مجزا داشته باشد. به عبارت فنی تر، کیوبیت یک سیستم دو بعدی کوانتومی با دو پایه به شکل و است. البته نمایش پایه‌ها یکتا نیست، به این دلیل که بر خلاف محاسبات کلاسیک در محاسبات کوانتومی از چند سیستم کوانتومی به جای یک سیستم ارجح استفاده می کنیم. اولین کاندید برای نمایش کیوبیت استفاده از مفهوم اسپین است که معمولاً اتم هیدروژن برای آن به کار می رود. در اندازه گیری اسپین یک الکترون، احتمال بدست آمدن دو نتیجه وجود دارد: یا اسپین رو به بالاست که با آنرا با نشان می دهیم و معادل است و یا رو به پائین است که با نشان می دهیم و معادل است با |1>| . بالا یا پائین بودن جهت اسپین در یک اندازه گیری از آنجا ناشی می‌شود که اگر اسپین اندازه گیری شده در جهت محوری باشد که اندازه گیری را در جهت آن انجام داده ایم، آنرا بالا و اگر در خلاف جهت این محور باشد آنرا پائین می نامیم. علاوه بر اسپین از وضع قطبش یک پرتو فوتونی و نیز سطوح انرژی مجزای یک اتم دلخواه نیز می توان به عنوان سیستم کیوبیتی استفاده کرد. شاید بتوان مهم‌ترین تفاوت بیت و کیوبیت را در این دانست که بیت کلاسیک فقط می تواند در یکی از دو حالت ممکن خود قرار داشته باشد در حالیکه بیت کوانتومی می تواند به طور بالقوه در بیش از دو حالت وجود داشته باشد. تفاوت دیگر در اینجاست که هرگاه بخواهیم می توانیم مقدار یک بیت را تعیین کنیم اما اینکار را در مورد یک کیوبیت نمی توان انجام داد. به زبان کوانتومی، یک کیوبیت را با عبارت نشان می دهیم. حاصل اندازه گیری روی یک کیوبیت حالت |o> را با احتمال C12 و حالت |1>| را با احتمال C22 بدست می دهد. البته اندازه گیری یک کیوبیت حتماً یکی از دو نتیجه ممکن را بدست می دهد. از سوی دیگر اندازه گیری روی سیستم‌های کوانتومی حالت اصلی آنها را تغییر می دهد. کیوبیت در حالت کلی در یک حالت بر هم نهاده از دو پایه ممکن قرار دارد. اما در اثر اندازه گیری حتماً به یکی از پایه‌ها برگشت می کند. به این ترتیب هر کیوبیت، پیش از اندازه گیری شدن می تواند اطلاعات زیادی را در خود داشته باشد.



توانایی و قدرت محاسبات کوانتومی

بین کامپیوترهای کلاسیک و کامپیوترهای کوانتومی نسل آینده تفاوت اساسی وجود دارد. یک کامپیوتر کلاسیک بر اساس قوانین فیزیک کلاسیک دستورات از پیش تعیین شده ای را اجرا می‌کند، اما یک کامپیوتر کوانتومی دستگاهی است که یک پدیده ی فیزیکی را بر اساس مکانیک کوانتومی به صورت منحصر به فردی در می آورد تا به صورت اساسی یک حالت جدید از پردازش اطلاعات را تشخیص دهد. در یک کامپیوتر معمولی اطلاعات به صورت یک سری بیت کد کذاری می شوند و این بیت‌ها از طریق گیتهای منطقی بولین که سری هستند برای نتیجه ی نهایی دستکاری می شوند به طور مشابه یک کامپیوتر کوانتومی، کوبیت‌ها یا بیت‌های کوانتومی را با اجرای یک از گیت‌های کوانتومی دستکاری می کندو هر واحد انتقال بر روی یک تک کوبیت یا یک جفت کوبیت عمل می کند. با به کار بردن این کمیت‌های متوالی یک کامپیوتر کوانتومی می تواند یک واحد انتقال پیچیده از طریق مجموعه ای از کوبیت‌ها در بعضی حالات ابتدایی ایجاد کند. پیشبرد پروژه ایجاد رایانه‌های کوانتومی در یک رایانه کوانتومی به جای استفاده از ترانزیستورها و مدارهای رایانه ای معمولی از اتم‌ها و سایر ذرات ریز برای پردازش اطلاعات استفاده می شود. یک اتم می تواند به عنوان یک بیت حافظه در رایانه عمل کند و جابجایی اطلاعات از یک محل به محل دیگر نیز توسط نور امکان می پذیرد. • کریس مونرو و همکارانش در دانشگاه میشیگان برای ذخیره اطلاعات با استفاده از حالت مغناطیسی اتم از یک اتم کادمیم به دام افتاده در میدان الکتریکی استفاده کردند. در این روش انرژی توسط یک لیزر به درون اتم پمپاژ شده و اتم وادار به گسیل فوتونی می‌شود که رونوشتی از اطلاعات اتم را در بر دارد و توسط آشکارساز قابل تشخیص است. • ذخیره اطلاعات در رایانه‌ها به صورت سری هایی از بیت‌های با حالت‌های روشن و خاموش صورت می گیرد. در اتم کادمیم در صورتی که میدان‌های مغناطیسی کوچک هسته و الکترون‌های بیرونی در یک جهت قرار بگیرند روشن و در خلاف جهت خاموش محسوب می شوند. کریس مونرو گفته است: اتم کادمیم در هریک از این حالات که باشد می تواند هزاران سال در همان حالت بماند.

جعبه متن

(ویکی پدیا)