عنوان

پیچیدگی محاسباتی روش های نظریه دامنه ای حل مساله ی مقدار اولیه

پ۲۴۲۲۸

per

پیچیدگی محاسباتی روش های نظریه دامنه ای حل مساله ی مقدار اولیه

مینا محمدیان

علوم ریاضی

۱۳۹۹

۱۲۷ص.

سی دی

دکتری

ریاضی محض گرایش منطق ریاضی

۱۳۹۹/۰۹/۲۴

یافتن مدل محاسباتͬ برای برخͬ ساختارهای ریاضͬ ی ͬͺاز موضوعات مهم در علوم کامپیوتر نظریبه شمار مͬ آید، در این راستا نظریه دامنه ی ͬͺاز شاخه های مهم ریاضیات است که به دلیل در برگرفتنمفاهیم تقریب و اعمال بازگشتͬ برای محاسبه نقطه ثابت، در علوم کامپیوتر جایͽاه انکارناپذیرییافته است. پیوستگͬ توپولوژی ͬͺی ͷمفهوم بنیادین در نظریه دامنه مͬ باشد. با وجود اینکه بررسͬمحاسبه پذیری ی ͷساختار با دشواری هایی همراه است اما بررسͬ پیوستگͬ توپولوژی ͬͺکه در نظریهدامنه دارای تعریف جبری است بسͬ سهل تر مͬ باشد. هدف نهایی ما بررسͬ محاسبه پذیری و نیزیافتن پیچیدگͬ محاسباتͬ روش های نظریه دامنه ای حل مسئله مقدار اولیه مͬ باشد. به این منظوردو روش اتخاذ کرده ایم. ابتدا ی ͷنظریه ساختنͬ برای دامنه های پیوسته از دیدگاه استخراج برنامهرا توسیع داده و نشان مͬ دهیم که برنامه نوشته شده در نظریه مذکور به واقع نشان دهنده محاسباتمورد نظر است. در گام بعدی با تعریف مفاهیم نظریه حساب در این چارچوب امید داریم که بتوانیممساله مقدار اولیه را بصورت کلͬ حل کرده و به بررسͬ پیچیدگͬ محاسباتͬ آن بپردازیم. در روشͬدیͽر، در راستای حل مساله مقدار اولیه در چارچوب نظریه دامنه ای کلاسی ،ͷمحاسبه پذیری روشاویلر مرتبه دوم را بررسͬ کرده و کرانͬ برای پیچیدگͬ محاسباتͬ روش ارایه مͬ دهیم

Domain theory is a large mathematical theory with applications in many areassuch as denotational semantics, type theory, and recursive mathematics. In thisthesis we have chosen to see domain theory as a theory of approximations and atheory of computability via approximations.hBiH2, *QKTmiiBQMH *QKTH2tBiv Q7 .QKBM@i?2Q`2iB+ SQHmiBQMb Q7 i?2AMBiBH oHm2 S`Q#H2KamT2`pBbQ`b, C7` S/2;? 1BpxHQQ- ##b 1/Hi/pBbQ`, JbQm/ SQm`K?/BMThe main goal in this thesis is solving IVP problems in domain theoreticalstructure. Accordingly, we use two approaches. First we develop a constructivetheory of continuous domains from the perspective of program extraction.Technically, we start from a predomain base and construct a completion. We theninvestigate continuity with respect to the Scott topology, and present aconstruction of the function space. As next step, our approach should bebenchmarked by establishing standard results of computable analysis, e.g.integration, differentiation. In second approach, we present a classic domaintheoretic method for solving IVPs, together with proofs of soundness,completeness, and results on the algebraic complexity of the method

Compuational complexity of Domain - theoretic solution of the initial value problem

محمدیان،

مینا

تهيه کننده

‏ عیوضلو،

‏ عدالت،

پورمهدیان،

جعفر صادق

عباس

مسعود

استاد راهنما

استاد راهنما

استاد مشاور

‏ تبریز