بی انگیزه

این روزها به شدت احساس بی انگیزه بودن میکنم، حتی برای نوشتن این وبلاگ ... 

دیشب ترکوندم ...

دیروز خیلی چیزا نوشتم ... و با فرض اینکه گربه توی اتاق هست ... 

دیشب تونستم ثابت کنم که در هر مرحله حداقل یک انتخاب درست و بدون خطا وجود داره ... 

راه های تازه ... 

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

گرچه این خبر نشون میده که مسأله ای که من روش کار میکنم در واقع NP-Complete هست، یعنی قاعدتا نباید الگوریتم سریعی براش وجود داشته باشه، ولی کار من رو ساده تر کرد، چون دیگه لازم نیست برای پیدا کردن یه تبدیل یا Reduction  برم و نظریه محاسبات بخونم و چندین ماه وقت بگذارم برای پیدا کردن اون تبدیل ... توی اون تز، تبدیلی از مسأله 3SAT  به مسأله من ارائه شده ... یعنی اگه الگوریتم من درست باشه و بتونم درستی ش  و زمان اجرای چند جمله ای ش رو ثابت کنم، یه الگوریتم چند جمله ای برای مسأله 3SAT پیدا شده و این یعنی اثبات درستی الگوریتم من هم ارز با اثبات P=NP هست. 

من میدونستم که مسأله من با اینکه حالت خیلی خاصی از مسأله دورهای همیلتنی هست، ولی بازم  ان پی کامل هست ولی اون تبدیل یا ریداکشن رو نداشتم و آشنایی کافی با نظریه پیچیدگی هم ندارم که بتونم خودم یه تبدیل پیدا کنم ... ولی بیشتر دانشمندان علوم کامپیوتر بر این باور هستند که کلاس P   با کلاس NP  مساوی نیست. یعنی هیچ الگوریتم سریعی  برای هیچ کدوم از مسأله های NP-Complete  وجود نداره ... ( البته با تمام اطمینانی که این دانشمندان دارند، بازم یه فرضیه با یه  قضیه فرق داره، تا وقتی اثباتی برای این فرضیه نداشته باشند، امکان وجود چنین الگوریتمی هست ) 

به خاطر همینه که من همچنان روی اثبات درستی الگوریتمم کار میکنم، حتی با اینکه حالا دیگه اثبات شده که مسأله من NP-Complete هست ... حتی با فرض این که P=NP نباشه و این نابرابری در آینده ثابت بشه، بازم داشتن الگوریتم خوب برای این مسائل خیلی مهمه ... چون این فرضیه روی بدترین حالت اجرای الگوریتم تمرکز داره، ممکنه یه الگوریتم به طور متوسط خیلی خوب کار کنه و در بیشتر موارد یا حتی 99 درصد موارد خیلی سریع به جواب درست برسه ولی مثال های نقضی باشه که توی اونها الگوریتم نیاز به زمان اجرای نمایی داره ... دقیقا مث الگوریتم سیمپلکس که بیشتر وقتا خیلی سریع جواب میده ولی در واقع  مواردی وجود داره که زمان اجراش نمایی میشه. 

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

در واقع این مسأله من یکی از ساده ترین حالت های یکی از مسأله های NP-Complete هست. ... اگه الگوریتمی سریع برای این مسائل وجود داشته باشه، طبیعی هست که توی این حالت های ساده تر بشه پیداش کرد و اگه فرضیه و اعتقاد دانشمندان علوم کامپیوتر درست باشه، حتی توی این ساده ترین حالت هم همچین الگوریتمی پیدا نخواهد شد یا هرگز نمیشه اثبات کرد که زمان اجرا چند جمله ای هست یا  نمیشه ثابت کرد که این الگوریتم  همیشه جواب درست  میده ... 

Finding a Cat in the Empty Room

توی یه اتاق خالی هیچ کسی نمیتونه به هیچ روشی یه گربه پیدا کنه ... 

پس هیچ الگوریتمی نمیتونه جوابی که وجود نداره رو پیدا کنه ... 

بنابراین باید فرض کنم گربه ای وجود داره ... 

... the joy of  Random walk ...

چقد این زبان برنامه نویسی پایتون خوبه ... 

دیشب برای اولین بار نشستم کمی با تابع matshow  بازی کردم ... تصویر پایینی از اولین چیزایی بود که بدست آوردم : 

بعدش ماتریس تصادفی صفر و یک رو ساختم ( متأسفانه این متد و تابع، کنترلی روی رنگ ها نداره و نمیشه رنگ های پیش‌فرض رو عوض کرد )  : 

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

دقیقا تا هشت صبح داشتم با اینا سروکله میزدم و خیلی خیلی لذت بخش بود ... برای اولین بار از برنامه نویسی خوشم اومد ... این پیچیده ترین کدی هست که تا حالا نوشتم، البته توی پایتون همه چی خیلی آسونه ... ولی خب اینکه بتونم توی اولین شبی که با پایتون، برنامه نویسی کردم، کد  قدم زدن تصادفی رو بنویسم نشون میده که میتونم برنامه نویس خفنی بشم :))) 

برنامه نویسی پویا ... 

اسم برنامه نویسی پویا رو شنیده بودم ولی دقیقا نمیدونستم چیه ... امروز وقتی داشتم وبگردی میکردم، دوباره باهاش برخورد داشتم و کنجکاو شدم که چیه ... وقتی این مقاله ویکی پدیا رو خوندم، چیزهای خیلی مفیدی یاد گرفتم ... من به این ایده ها فکر کرده بودم ولی نمیدونستم اسمش برنامه نویسی پویا هست ... به هر حال دو شرط اساسی برای اینکه بشه یه مسأله رو بشه با الگوریتم های پویا حل کرد، اول اینکه مسأله رو بشه به مسأله های کوچیکتر تقسیم کرد و  دوم اینکه اون مسأله‌های کوچیکتر همپوشانی داشته باشند، اگه همپوشانی بین زیر مسأله ها وجود نداشته باشه، میشه الگوریتم تقسیم و غلبه ... 

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

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

وقتی به این مفاهیم فکر میکنم، درک جدیدی از اینکه چرا الگوریتم من میتونه درست باشه بدست میارم ... وقتی جواب نهایی رو بررسی میکنم می بینم که از ترکیب جواب مسأله های کوچیکتر ساخته شده ... البته اینجا بخش ترکیب جواب ها  خیلی پیچیده ست ... و من از ترکیب جواب ها استفاده نکردم ... من مسأله رو بازگشتی حل میکنم ولی بازگشتی ساده هم نیست ... چون فالس نگاتیو داریم و  وقتی فالس نگاتیو  پیش میاد، الگوریتم خودش رو اصلاح میکنه ...  توی الگوریتم های بازگشتی ما اصلاح جواب نداریم ... این ویژگی توی الگوریتم های ژنتیک و الگوریتم های تکاملی  دیده میشه ... ولی این الگوریتم من  الگوریتم فرگشتی هم نیست ... :))) 

الگوریتم های تکاملی الگوریتم هایی هستند که از ایده نظریه فرگشت داروین استفاده میکنند ... الگوریتم های ژنتیک هم از مفهوم جهش و تغییر جوابها استفاده میکنند ... و خب من اینجا از این مفاهیم استفاده نکردم، من فقط یه  راه حل برای جلوگیری از اشتباه الگوریتم  پیدا کردم ... شبیه وقتی هست که انتگرال حل میکنی و بعدش مشتق میگیری ببینی درست حل کردی یا نه ... اگه از جواب انتگرال،  مشتق بگیری  ممکنه بفهمی که انتگرال رو اشتباه حل کردی و برمیگردی و دوباره با یه روش دیگه حل میکنی ... البته این یه مثال هست و الگوریتم من هیچ ربطی به حساب دیفرانسیل و انتگرال نداره ... :))) 

شباهت گرامری متلب و جولیا ... 

دیشب و امروزم بیشتر به وبگردی گذشت و درباره زبان های برنامه نویسی میخوندم که بتونم  از بین گزینه های مختلف  یکی رو  انتخاب کنم و یاد بگیرم. گزینه های اصلی من  زبان های پایتون و جولیا  و برنامه های  SageMath   و متلب بودند ... و بین این چهارتا گزینه تردید داشتم ... البته  تو دانشگاه ++C  خوندیم و باهاش آشنایی نسبی دارم ولی خیلی زبان سختی هست و ترجیح میدم تا مجبور نشدم سراغش نرم ... چون حوصله سروکله زدن با اشاره‌گرها و تخصیص حافظه رو ندارم ... 

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

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

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

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

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

گرامر پایتون  برای زبان  پایتون و برنامه SageMath   ... و گرامر  زبان جولیا برای  زبان جولیا و  برنامه متلب ... 

حالا یا باید یکی از دو زبان پایتون یا جولیا رو انتخاب کنم  یا اینکه  هر دو رو یاد بگیرم ... 

به هر حال میدونم که هیچ کدوم به سختی ++C  نخواهد بود :)))) 

++ حالا که حرف از شباهت شد، بهتره بگم تفاوت هایی هم هست ... 

اینجا تفاوت‌های گرامر جولیا  با گرامر متلب، پایتون و  ++C  رو گفته.