د محاسبې تیوري

د کمپیوټري او نظري ریاضیاتو اړوندو علومو په برخه کې د محاسبې تیوري هغه څانګه ده، چې په ښکاره توګه دا مورد بیانوي، چې د محاسبې په ماډل کې د یو الګوریتم په کارولو سره کومې ستونزې حل کېدای شي، څنګه کولای شو هغه په اغېزمنه توګه یا هم تر کومې کچې (لکه د کره حللارو په وړاندې تقریبي او تخمیني حل لارې) حل کړي. دا برخه په درې لویو څانګو وېشل شوې ده: اتوماتیکه تیوري او رسمي ژبې، د محاسبې منلو اړونده نظریه او د محاسباتي پېچلتیاوو اړونده نظریه، چې په دې پوښتنې سره له یو بل سره تړاو مومي: «د کمپیوټرونو بنسټیزې وړتیاوې او محدودیتونه څه دي؟».^[۱]

د کمپیوټري علومو پوهان د محاسبې د یوې کره او دقیقې مطالعې د ترسره کولو په موخه له کمپیوټرونو نه د ریاضیاتي خلاصون په توګه کار کوي، چې د محاسبې د ماډل په نوم یادېږي. په دې برخه کې د کارولو اړوند ګڼ شمېر ماډلونه موجود دي، خو تر ټولو عام ماډل یې د تورینګ ماشین دی. د کمپیوټري علومو پوهان د تورینګ ماشین له دې امله مطالعه کوي، چې د جوړولو لپاره ساده دی، په ښه توګه تجزیه او تحلیل او دغه راز د پایلو ثابتولو لپاره کارول کېدای شي؛ ځکه چې د هغه څه استازیتوب کوي، چې زیاتره یې د محاسبې تر ټولو پیاوړی او «مناسب» ماډل بولي (د چرچ – تورینګ مقاله وګورئ). ښایي داسې وبرېښي، چې د لامحدودې بالقوه حافظې ظرفیت یوه ناشونې ځانګړتیا ده، خو هره هغه ستونزه، چې د تورینګ ماشین پرمټ حلېږي، هغه تل یوې محدودې حافظې ته اړتیا لري؛ له همدې امله په اصل کې هره هغه ستونزه، چې د تورینګ ماشین پرمټ حل کېدای شي؛ نو د هغه کمپیوتر په وسیله حل کېدای شي، چې په محدوده کچه حافظه ولري.^[۲]^[۳]

تاریخ

د محاسبې نظریه د کمپیوټري علومو په ډګر کې د هر ډول ماډلونو رامنځته کول ګڼل کېدای شي. له همدې امله له ریاضیاتو او منطق نه ګټه اخیستل کېږي. په تېره پېړۍ کې دا څانګه په یوه خپلواکه اکاډمیکه څانګه بدله شوه او له ریاضیاتو نه جلا شوه.

د محاسبې د نظریې یو شمېر مخکښ غړي دا دي: رامون لول، الونزو کلیسا، کورت ګوډیل، الان تورینګ، استیفان کلین، روزسا پیتر، جان فون نیویمان او کلود شانون.

څانګې

خپل چارې یا اتومات تیوري

خپل چارې یا د اتومات نظریه د تجریدي ماشینونو (یا په مناسبه توګه، تجریدي «ریاضي» ماشینونه یا سیسټمونه) او محاسباتي مسایلو مطالعه ده، چې د دغو ماشینونو په کارولو سره حل کېدای شي، دا تجریدي ماشینونه د خپل چارو یا اتومات په نامه یادېږي. Automata له یوناني کلیمې (Αυτόματα) نه اخیستل شوې او معنا یې دا ده، چې یو شی خپله په یوازې توګه کوم کار ترسره کوي. خپل چارې یا اتوماتا نظریه هم د رسمي ژبو له نظریې سره نږدې تړاو لري؛ ځکه چې خپل چارې یا اتوماتا تر ډېره د رسمي ژبو د ټولګي پر بنسټ ډلبندي کېږي، چې دوی یې د پېژندلو وړ دي. یو اتومات کولای شي د یوې رسمي ژبې یو محدود نمایش وي او ښایي یوه نامحدوده ټولګه وي. اتوماتا د محاسباتي ماشینونو لپاره د نظریاتي ماډلونو په توګه او دغه راز د محاسبې د وړتیاوو ثابتولو لپاره کارول کېږي.^[۴]

د رسمي ژبې نظریه

د ژبې نظریه د ریاضیاتو یوه څانګه ده، چې په یوه الفبا باندې د عملیاتو د یوې ټولګې په توګه د ژبې تشرېح کولو پورې اړه لري. دا نظریه له اتوماتا نظریې سره تړاو لري؛ ځکه چې له اتوماتاوو نه د رسمي ژبو د تولید او تشخیص لپاره کار اخیستل کېږي. د رسمي ژبو زیاتې ټولګي شته، چې هره یوه یې د مخکینۍ ژبې په پرتله خورا پېچلي ژبني مشخصات تشخیصوي، د بېلګې په توګه د چامسکي درجه بندي او هر یو یې په یوې اتوماتیکې ټولګي پورې اړوند وي. دا چې اتوماتا د محاسباتو لپاره د ماډلونو په توګه کارول کېږي؛ نو رسمي ژبې د هرې هغې ستونزې لپاره د مشخصاتو ترجیحي حالت دی، چې باید محاسبه شي.^[۵]

د محاسبې پذیرۍ نظریه

د محاسباتو اړونده نظریه په لومړۍ برخه کې دې پوښتنې ته ځواب وایي، چې څومره یوه ستونزه په کمپیوټر کې د حل وړ ده. دا بیان چې د بندېدو ستونزه د تورینګ ماشین پرمټ نه شي حل کېدای، د محاسباتي نظریې له تر ټولو مهمو پایلو نه ده؛ ځکه چې دا د یوې سختې ستونزې بېلګه ده، چې په فارمولي شکل برابرول یې اسانه او د تورینګ ماشین په کارولو سره یې حلول ناشوني دي. زیاتره محاسباتي نظریې د ستونزو د پایلو پر مخ رامنځته شوې دي. ^[۶]

د محاسباتو په تیورۍ کې یو بل مهم پړاو د رایس قضیه وه، چې وایي د جزيي تابعو د ټولو نا معمولي ځانګړنو لپاره، داسې پرېکړه نه شو کولای، چې ایا د تورینګ ماشین یوه جزیي تابع له هغو ځانګړتیاوو سره محاسبه کوي که نه.^[۷]

د محاسبه کولو نظریه د تکرار نظریې په نامه د ریاضياتي منطق اړوندې برخې سره نږدې تړاو لري، چې یوازې د محاسبې ماډلونو د مطالعې هغه محدودیت لرې کوي، چې د تورینګ ماډل ته د کمېدو وړ دي. زیاتره ریاضي پوهان او محاسباتي تیوریستانو د تکرار نظریې د مطالعه کولو پرمهال دا نظریه د محاسبې منلو نظریې په توګه یاده کړې ده. ^[۸]

د محاسباتي پېچلتیاوو تیوري

د ېیچلتیا تیوري نه یوازې دا موضوع په پام کې نیسي، چې ایا یوه ستونزه بېخي په کمپیوټر کې حلولای شو، بلکې دا چې د هغې ستونزې د ګټې او کارېدو کچه هم په موثره توګه حل کېدای شي په دې برخه کې دوه لوی اړخونه په پام کې نیول کېږي: د وخت پېچلتیا او د ځای پېچلتیا، چې په ترتیب سره د محاسبې ترسره کولو لپاره څو پړاوه ترسره کېږي او د دغو محاسباتو د ترسره کولو لپاره اړینه بولي، چې څومره حافظې ته اړتیا شته.

دا چې یو ورکړل شوی الګوریتم څومره وخت او ځای ته اړتیا لري، د تحلیل او تجزیه کولو لپاره یې د کمپیوټر ساینس برخې پوهان د ستونزې د حل کولو لپاره اړین وخت یا ځای د ننوتلو ستونزې د اندازې اړوند تابع په توګه بیانوي. د بېلګې په توګه، د اعدادو یا شمېرو د لړلیک په اوږدېدو سره، د اعدادو په دې لوی لست کې د یو ځانګړي عدد یا شمېرې موندل ډېر ستونزمنېږي. که موږ ووایو چې په لیست کې د n عدد شامل دی؛ نو که چېرې لیست په هېڅ ډول ترتیب یا منظم شوی نه وي؛ نو موږ باید هر عدد او هره شمېره وګورو ترڅو هغه شمېره پیدا کړو، چې موږ یې په لټه کې یو. له همدې امله موږ وایو، چې د دې ستونزې د حل لپاره، کمپیوتر باید یو شمېر مرحلې ترسره کړي، چې د ستونزې په اندازې کې په خطي توګه وده کوي.

د دې ستونزې د ساده کولو لپاره، د کمپیوټر برخې پوهانو د غټې O له علامې (Big O Notation) نه کار اخیستی دی، چې اجازه ورکوي ترڅو توابع په داسې يوه طریقه له یو بل سره پرتله کړي او دا ډاډ ترلاسه شي، چې اړتیا نشته ترڅو د ماشین جوړونې ځانګړي اړخونه په پام کې ونیول شي، بلکې یوازې د ستونزو له غټېډو سره اړوند چلند په پام کې نیسي. له همدې امله ‎زموږ په مخکینۍ بېلګه کې، ښایي داسې ووایو، چې ستونزې د حل لپاره {\displaystyle O(n)} پړاوونو ته اړتیا لري.

کېدای شي د کمپیوتر په ټولو علومو کې تر ټولو مهمه څرګنده ستونزه دا پوښتنه وي، چې ایا هغه لوی مسایل چې د NP په وسیله ښودل کېږي، هغه په موثره توګه حل کولای شو؟ د دې موضوع په هکله د پېچلتیا یعنې د P او NP په ټولګیو کې بحث کېږي او د P په وړاندې د NP ستونزه د زریزې د جایزې اړوند د اووو مسئلو له ډلې نه ده، چې د ریاضیاتو د Clay موسسې په وسیله په ۲۰۰۰ز کال کې بیان شوه. د دې مسئلې رسمي بیان د تورینګ جایزې ګټونکي سټیفن کوک په وسیله بیان شوی دی.

محاسباتي ماډلونه

پر تورینګ ماشین سربېره، د محاسباتو یو شمېر نور معادل ماډلونه (د کلیسا تورینګ مقاله وګورئ) هم کارول کېږي.

د لامدا حساب

د لامدا د لومړۍ څرګندونې د محاسبې ثبات (یا دوه عبارتونه، که غواړئ کارکول او ننوتۍ یې جلا کړئ) او د لامبدا اصطلاحات محدود ترتیب لري، چې هر یو یې له مخکنۍ څرګندونې نه د یو غوښتنلیک په وسیله استنباط کېږي.

سرچينې

↑ Michael Sipser (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1)
↑ Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary ed.). Princeton University Press. ISBN 978-0-691-15564-7.
↑ Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.
↑ Hopcroft, John E. and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9.
↑ Chomsky hierarchy (1956). "Three models for the description of language". Information Theory, IRE Transactions on. 2 (3). IEEE: 113–124. doi:10.1109/TIT.1956.1056813.
↑ Alan Turing (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. 2 (42). IEEE: 230–265. doi:10.1112/plms/s2-42.1.230. بياځلي په 6 January 2015.^{[مړه لينکونه]}
↑ Henry Gordon Rice (1953). "Classes of Recursively Enumerable Sets and Their Decision Problems". Transactions of the American Mathematical Society. 74 (2). American Mathematical Society: 358–366. doi:10.2307/1990888. JSTOR 1990888.
↑ Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281.

[Sipser-3rd-1] Michael Sipser (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1)

[Hodges-2012-2] Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary ed.). Princeton University Press. ISBN 978-0-691-15564-7.

[3] Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.

[hopcroft-ullman-4] Hopcroft, John E. and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9.

[5] Chomsky hierarchy (1956). "Three models for the description of language". Information Theory, IRE Transactions on. 2 (3). IEEE: 113–124. doi:10.1109/TIT.1956.1056813.

[6] Alan Turing (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. 2 (42). IEEE: 230–265. doi:10.1112/plms/s2-42.1.230. بياځلي په 6 January 2015.^{[مړه لينکونه]}

[7] Henry Gordon Rice (1953). "Classes of Recursively Enumerable Sets and Their Decision Problems". Transactions of the American Mathematical Society. 74 (2). American Mathematical Society: 358–366. doi:10.2307/1990888. JSTOR 1990888.

[davis-8] Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]