کتاب ۶۰۰ مسئله دکتر قدسی

به‌نام خدا

کتابی که پیش روی شماست مجموعه‌ای از ۶۰۰ مسئله‌ی چندگزینه‌ای از داده ساختارها و الگوریتم‌هاست که نویسنده‌ی اول با بیش از ۲۵ سال تدریس در این زمینه، برای آزمون‌های ورودی کارشناسی ارشد رشته‌ی مهندسی کامپیوتر، و نیز برای تعدادی از آزمون‌های مرحله‌ی اول المپیادهای کامپیوتر کشور طراحی و برخی را نیز با کسب اجازه از طراحان جمع‌آوری کرده است.

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

صورت مسئله‌ها در ۷ فصل دسته‌بندی شده‌اند: تحلیل الگوریتم‌ها، مرتب‌سازی، داده‌ساختارهای ساده و پیش‌رفته، الگوریتم‌ها، گراف‌ها و تعدادی از مسئله‌های الگوریتمی المپیاد کامپیوتر ایران. فصل ۸ شامل راهنمایی‌های کوتاه برای تعدادی از مسئله‌هاست که به حل مسئله‌ها کمک می‌کند. فصل ۹ حاوی گزینه‌های درست و فصل ۱۰ شامل راه‌حل‌های کامل برای تمام مسئله‌هاست. تعدادی از مسئله‌های مشکل را با یک ستاره (*) و برخی را که خیلی مشکل هسند با دو ستاره (**) مشخص کرده‌ایم. از آن‌جا که بخش عمده‌ای از محتوای کتاب راه‌حل‌های تشریحی است، توصیه می‌شود که اگر پاسخ صحیح مسئله‌ای را یافتید، راه حل آن‌را نیز بخوانید تا با ایده‌های جدید و نکته‌های ظریف در حل آن مسئله آشنا شوید.

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

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

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

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

محمد قدسی،

استاد دانشکده‌ی مهندسی کامپیوتر،

دانشگاه صنعتی شریف،

ghodsi@sharif.edu

sharif.edu/~ghodsi

آیدین نصیری شرق،

مهندس نرم‌افزار،

شرکت Google،

aideen@gmail.com،

aideen.org

فصل اول:  تحلیل الگوریتم‌ها

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

فصل دوم: مرتب‌سازی

مرتب‌سازی سریع، مرتبه‌ی آماری، ادغام دنباله‌های مرتب، مسئله‌های دیگر

فصل سوم:   داده ساختارهای ساده

لیست، پشته و صف، درخت‌ها، عبارت، درخت عبارت، هرم‌ها، درهم‌سازی و سایر داده ساختارها

فصل چهارم:  داده ساختارهای پیش‌رفته

درخت دودویی جست و جو، درخت قرمز – سیاه، درخت ای.وی.ال و دیگر گسترش‌ها، مجموعه‌های مجزا، داده ساختارهای دیگر

فصل پنجم:  الگوریتم‌ها

الگوریتم‌های عمومی، الگوریتم‌های حریصانه، روش پویا، الگوریتم هافمن، مسئله‌های دیگر

فصل ششم: گراف‌ها

مقدمات و شمارش، عمومی و الگوریتمی، کوتاه‌ترین مسیر، هم‌بندی و درخت فراگیر کمینه

فصل هفتم:  مسئله‌های المپیاد

گراف، برنامه‌نویسی، مرتب‌سازی و رابطه‌های بازگشتی، الگوریتم‌ها و متفرقه

فصل هشتم: راهنمایی‌ها

فصل نهم: گزینه‌های درست

فصل دهم: راه حل‌ها