تجربه هاي شخصي من

فرمولهایی برای علوم کامپیوتر

فراموش کردن یک فرمول ریاضی و یا به یاد نیاوردن پاسخ ساده شده یک عبارت ریاضی اتفاقاتی هستند که در حین درس خواندن و تحقیق کردن بسیار رخ می‌دهند. یادم می‌آید که در ایران کتابی در قطع بسیار کوچک، چاپ شده بود که حاوی بسیاری از این فرمولها بود. در اینترنت نیز یک کتابچه ده صفحه‌ای به نام “Computer Science Cheat Sheet” منتشر شده است که به صورت بسیار فشرده و تمیز و با استفاده از TEX این فرمولها را در خود جای داده است. در واقع خالق اصلی این کتابچه دکتر Steve Seiden می‌باشد که در سال ۲۰۰۲ در اثر برخورد یک کامیون به دوچرخه‌اش فوت کرد. بعد از اینکه به دانمارک آمدم متوجه شدم که این کتابچه بوسیله خیلی از دانشجویان مورد استفاده قرار می‌گیرد.

سوالاتی مهم

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

منبع عکس: Examiner.com

پذیرفته نشدن مقاله

پذیرفته نشدن مقاله‌ات در یک کنفرانس اصلاً حس خوبی نیست. به خصوص اگر در سال آخر دکترا باشی و دربه‌در به دنبال publication. وقتی در ماه فوریه برای فرصت مطالعاتی به انگلیس رفته بودم، با Gerth تصمیم گرفتیم نتایجی را که برای مسئله RMQ بدست آورده بودیم، در یک مقاله بنویسیم و به کنفرانس ICALP10 بفرستیم. از آنجا که اغلب این نتایج را قبلا در یک progress report سی صفحه‌ای نوشته بودم، تبدیل کردن آنها به یک مقاله دوازده صفحه‌ای وقت زیادی از من نگرفت. اما با وجود آنکه با Gerth از طریق skype در تماس بودم و آخرین نسخه‌های ویرایش شده را برایش می‌فرستادم، مقاله در کنفرانس پذیرفته نشد. پاسخ reviewer-ها که از طریق سیستم EasyChair به دست رئیس کنفرانس رسیده بود برای ما ارسال شد و حاوی توضیحاتی در مورد تعداد زیاد اشتباهات نوشتاری و نامفهوم بودن متن بود. دو روز بعد از آن تصمیم گرفتیم که مقاله را دوباره ویرایش کنیم و در چهار روز وقت باقی‌مانده برای کنفرانس ESA10 ارسال کنیم. این بار که در اورهوس بودم و بهتر می‌توانستم سوالاتم را از Gerth بپرسم، مقاله بهتری نوشتم. در حدود نیمی از مقاله را بازنویسی کردم. اما باز هم Gerth وقت کمی اختصاص داد و یک بخش از مقاله را اصلا نخواند و گمان می‌کنم همان بخش بدترین بخش مقاله از نظر نوشتاری باشد. به هر حال مقاله ارسال شد و ما هم باید دو ماهی را در انتظار پذیرشش باشیم. برخی نکاتی که در نوشتن این مقاله به طور مکرر با آنها برخورد کردم را در زیر می‌نویسم:

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

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

- اغلب خوانندگان مقاله‌ها به دنبال Intuition (شهود) می‌گردند. بنابراین باید هر بخش را با توضیحاتی غیر فنی که ایده اصلی آن بخش را بیان می‌کنند آغاز کرد. تعاریف باید به صورت دقیق و غیر مبهم بیان شوند چرا که بقیه بخشهای مقاله همگی بر اساس این تعاریف بیان می‌شوند.

- مهمترین بخش مقاله Introduction می‌باشد و باید در خوب نوشتن آن بسیار تلاش کرد. به این علت که ۱) این بخش پیش و بیش از بقیه بخشها مطالعه می‌شود. ۲) ایده اصلی مقاله را به طور مختصر و مفید بیان می‌کند. ۳) پیشرفتی را که در مسئله مورد بررسی صورت گرفته است نشان می‌دهد (مقایسه با مقاله‌های قبلی). ۴) کاربردها و فواید مسئله مورد بررسی را بیان می‌کند.

- تا جای ممکن باید از اختراع اصطلاحات جدید پرهیز کرد. زیرا خواندن مقاله را مشکل می‌کنند.

- قرار دادن comma (,) و semicolon (;) در جاهای مناسبی از متن بسیار اهمیت دارد (توضیحات بیشتر).

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

- محقق با نوشتن مقاله، نتایج تحقیقات خود را به دیگران (محققین دیگر) می‌فروشد. بنابراین برای اینکه این کالا به خوبی به فروش برسد، نه تنها باید خودش دارای ارزش بالایی باشد بلکه باید در مقاله نیز آن را به خوبی تبلیغ کرد. برای این کار باید دانست که ۱) در حال حاضر چه تحقیقاتی دارای خریدار بیشتری هستند و ۲) چگونه می‌توان بدون دروغگویی و اغراق یک تبلیغ خوبی از کار ارائه کرد.

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

فرستاده شده در ادامه تحصيل در خارج،درس خواندن،علوم کامپیوتر | ۳ نظر

آرشیو Yahoo Messenger

یکی از امکانات برنامه Yahoo Messenger این است که می توان تمام پیغامهایی که بین یک کاربر و تمام دوستانش رد و بدل می شوند را در قسمت آرشیو ذخیره کرد. اگر یک کاربر، برنامه را طوری تنظیم کند که تمام پیغامها در آرشیو ذخیره شوند، از آن به بعد هر یپغامی که با استفاده از یک  کامپیوتر دلخواه می فرستد در همان کامپیوتر ذخیره می گردد که البته این اصلاً خوب نیست و بهتر بود که آرشیو در داخل سرور یاهو ذخیره می شد. به عنوان مثال اگر در یک کافی نت با فردی چت کنید، محتویات چت در کامپیوتر کافی نت ذخیره می شود، مگر آنکه قبل از شروع چت، مجدداً تنظیمات را به حالتی که پیغامها در آرشیو ذخیره نگردند برگردانید. اما باز هم جای شکرش باقی است که پیغامها به صورت کُد شده ذخیره می شوند و با برنامه هایی مثل Notepad قابل خواندن نیستند. ولی در عوض برنامه های دیگری هستند که نه تنها بوسیله آنها می توان تمام پیغامهای ذخیره شده در کامپیوتر را خواند بلکه امکاناتی از قبیل جستجو را نیز دارا می باشند. یکی از آنها Dapyx Messenger Archive Reader می باشد که به صورت رایگان قابل دانلود کردن است.

پدر اینترنت

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

منبع عکس: Soup – Anthony De Rosa

معذرت خواهی از Alan Turing

Alan Turing، از نوابغ علوم کامپیوتر که یک همجنسگرا بود، به خاطر داشتن رابطه جنسی با یک مرد در سال ۱۹۵۲، به زندان افتاد. او پیشنهاد آزادی مشروط از زندان در قبال استفاده از دارویی برای کنترل حس جنسی‌اش را پذیرفت. اما به علت ترسی که در آن روزها از جاسوسی‌های شوروی سابق وجود داشت، مجوز فعالیت وی در ستاد مخابراتی دولت که زیر مجموعه‌ای از آژانش امنیتی انگلیس بود، حذف شد. دو سال بعد، جنازه وی که در اثر خوردن سیانور در خانه‌اش افتاده بود، پیدا شد. چند روز پیش، John Graham Cumming از برنامه‌نویسان معروف، پیشنهاد برپا کردن برنامه‌ای را برای معذرت خواهی از Turing داده است. وی معتقد است که Turing به خاطر فعالیتهایش در آژانس امنیتی انگلیس در دوران جنگ جهانی دوم، یکی از قهرمانان ملی است که به خاطر قانون غلط و عقب افتاده آن روز انگلیس درباره همجنسگراها، در حق او جفا شده است. افراد مختلف، نظرات متفاوتی درباره برگزاری این برنامه داده‌اند. برخی معتقدند که با وجود بزرگداشتهای فراوانی که تا به حال برای Turing برگزار شده است، اما جای یک معذرت خواهی جدی از وی خالی است. در مقابل، برخی می گویند که نه تنها برگزاری چنین برنامه‌ای هیچگونه سودی برای هیچ فرد یا سازمانی ندارد، بلکه اگر می خواهیم جوانمردانه قضاوت کنیم، باید از تمام همجنسگراهایی که در آن روزها در کشور انگلیس به خاطر قوانین غیر منطقی‌اش مجازات شدند، معذرت خواهی کنیم. اما در وبسایت Manchester Evening News کسی را ندیدم که همچنان مانند سالهای دور، به همجنسگرایی به عنوان یک بیماری و یا یک جرم نگاه کند و Turing را شایسته مجازاتی که شده است بداند.

سانسور اینترنت

چند وقت پیش زمانی که می‌خواستم به دنبال فیلمی در ThePirateBay بگردم، متوجه شدم که این وبسایت توسط ISP که اینترنت خوبگاه ما را تأمین می‌کند، فیلتر شده است. بعد متوجه شدم که از چندین هفته قبل، روند فیلتر کردن این وبسایت در کشورهای اروپایی آغاز شده است و همچنان هم ادامه دارد. این وبسایت که محلی است برای ذخیره کردن فایلهای Torrent برای به اشتراک‌گذاری ویدئو، موزیک، نرم‌افزار و هر چیز دیگر، در شانزده فوریه ۲۰۰۹، به دادگاه عالی کشور سوئد فراخوانده شد و محاکمه چهار نفر صاحبان این وبسایت به اتهام نقض قانون کپی‌رایت، بیش از دو هفته به طول انجامید. حال قرار است در ساعت یازده صبح روز جمعه، هفدهم آوریل، حکم دادگاه اعلام شود. اگر این افراد مجرم شناخته شوند، امکان مجازات صد و هشتاد میلیون دلاری و دو سال زندان برایشان وجود دارد و نمی‌دانم چه بر سر وبسایتی می‌آید که جزء صد وبسایت پربیننده دنیا است.

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

سه سال پیش اسماعیل رادکانی، گفته بود که تا به حال ۱۰ میلیون وبسایت در ایران فیلتر شده‌اند و روزانه هم ۳۰۰ وبسایت به جمع آنها افزوده می‌شوند. فعلاً که من در ایران نیستم، اما خبر دارم که نرم‌افزار FreeGate، که خیلی از افراد از طریق آن، وبسایتهای فیلتر شده را باز می‌کردند، دیگر کار نمی‌کند و برخی به سراغ نرم‌افزار GPass رفته‌اند. نرم‌افزاری هم که اغلب کشورهای دنیا برای فیلتر کردن وبسایتها استفاده می‌کنند، SmartFilter می‌باشد.

صفحه‌ای که بعد از باز کردن وبسایت ThePirateBay  نشان داده می‌شود.

تکنیک Fingerprinting

هر گاه تعدادی فایل داشته باشیم که هر یک از آنها شامل میلیونها رکورد اطلاعاتی هستند به طوریکه برخی از این فایلها دارای محتوای یکسانی هستند و تنها ترتیب قرارگیری رکوردها در آنها متفاوت است، اما برخی دیگر از این فایلها هم به طور کل محتوایی متفاوت دارند. یکی از ساده‌ترین راهها برای یافتن فایلهای دارای رکوردهای یکسان، این است که در هر یک از فایلها، تمام رکوردها را بر اساس ترتیبی خاص مرتب کنیم و سپس برای تشخیص برابری هر دو فایل، مقایسه رکوردهایشان را از اولین رکورد آغاز کنیم تا به آخرین رکورد برسیم. این کار برای دو فایل ۸ مگابایتی، ۳۰ ثانیه طول می‌کشد و مسلماً وقتی اندازه فایلها بیشتر و تعدادشان زیادتر گردد، این زمان بسیار بالا می‌رود. روش دیگر برای مقایسه دو فایل که در پروژه درس الگوریتمهای تصادفی انجام دادم و این زمان را به ۲ ثانیه کاهش می‌دهد این است که هر یک از n رکورد داخل هر فایل را به یک عدد ۳۲ بیتی تبدیل کنیم و سپس با استفاده از این n عدد، برای هر فایل یک چند جمله‌ای درجه n بسازیم. حال می‌توان ادعا کرد که دو فایل دارای رکوردهای یکسانی هستند، اگر و تنها اگر دارای چندجمله‌ای‌های یکسانی باشند. اما مقایسه دو چند جمله‌ای نیز کار زمانبری است. در اینجا می‌توان از تکنیک Fingerprinting استفاده کرد که یکی از روشهای مهم برای مقایسه دو شئ (Object) می‌باشد به این صورت که هر گاه اندازه دو شئ بسیار بزرگ باشد، با استفاده از این روش می‌توان اندازه آنها را کوچک کرد و البته باید خطای این کار را هم به طور دقیق محاسبه کرد. به عنوان مثال برای اینکه بفهمیم آیا دو چند جمله‌ای P و Q با هم برابر هستند یا خیر، می‌توانیم مقدار (P(x و (Q(x را به ازای یک x خاص محاسبه کنیم و در صورت برابرای آنها، برابری P و Q را اعلام کنیم. مسلماً در این روش خطا وجود دارد. قضیه Schwartz-zippel ثابت می‌کند که اگر x به طور تصادفی و از یک مجموعه نسبتاً بزرگ انتخاب شود، میزان خطا بسیار کم می‌شود.
———————–
منابع:
- کتاب Randomized Algorithms نوشته Rajeev Motwani و Prabhakar Raghavan.
- تعریف پروژه درس الگوریتمهای تصادفی
- گزارش من برای پروژه