عنوان پایان‌نامه
تصادف از دیدگاه الگوریتمی و احتمالاتی در دستگاه های دینامیکی
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 6347;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 76985;کتابخانه پردیس علوم شماره ثبت: 6347;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 76985
- تاریخ دفاع
- ۰۷ مهر ۱۳۹۵
- دانشجو
- محمدصادق خسروانی
- استاد راهنما
- مجید علی زاده
- چکیده
- دستگاه دینامیکی مفهومی ریاضی است که فرایندهای طبیعت را مدل می‌کند . دسته خاصی از دستگاه‌های دینامیکی که ارگودیک نام دارند از ابزار نظریه اندازه و احتمال استفاده می‌کنند. در این پایان‌نامه با کمک توسعه مفاهیم محاسبه‌پذیری از اعدادطبیعی به فضای متریک و فضای اندازه تعریفی از تصادفی بودن یک نقطه بدست می‌دهیم و آن را با مفهوم تصادفی بودن از دیدگاه شور (که از پیچیدگی کولموگروف چیتین استفاده می‌کند) مقایسه می‌کنیم. با استفاده از مفهوم محاسبه‌پذیری یک مدل نمادی موثر می‌سازیم که به کمک آن رفتار نقاط تصادفی در دستگاه دینامیکی بررسی می‌شود و مشاهده می کنیم نقاط تصادفی، بازگشتی‌اند. بعد از بیان مفاهیم آنتروپی و پیچیدگی مداری در دستگاه‌های دینامیکی به بررسی رابطه آنتروپی و پیچیدگی مداری نقاط تصادفی می‌پردازیم . ثابت می‌شود که پیچیدگی مداری نقاط تصادفی برابر آنتروپی کولموگروف-سینایی است، و سوپریمم پیچیدگی مداری برابر آنتروپی توپولوژیک است.
- Abstract
- Dynamical systems is one of the mathematical concepts that models the processes of the nature. A specific class of dynamical systems that are called ergodic,use measure theory and probability tools.In this thesis, we expand the notion of computablityto metric space and measure space. We give a notion of randomness of apoint in this spaces and compare it to other definitions of randomness in senceof Schnorr(that use Kolmogrov-Chaitin complexity).Then we introduce computable symbolic dynamicsand help it to investigetebehavior of random points in dynamical systems. We observe that random points are recurrent.Afterexplaining the notion of entropy and orbit complexity in dynamical systems, we investigate the relation between entopy and orbit complexity on random points and prove that orbit complexity is equal to kolmogrov-Sinai entropy, and the suprimum of orbit complexity is equal to topological entropy.Keywords: Computable metric space - algorithmic randomness -Kolmogrov-Chaitin complexity -Birkhoff’s ergodic theorem -symbolic dynamics -entropy -orbit complexity
