عنوان کتاب: ریاضیات گسسته و ترکیبیاتی - جلد اول
ازمجموعه کتابهای : ریاضیات گسسته و ترکیبیاتی
تألیف : رالف پ. گریمالدی
ترجمه : محمدعلی رضوانی , بیژن شمس
ویرایش : مهران اخباریفر
چاپ ششم - ۱۳۸۸
قیمت پشت جلد ۱۵۵۰۰۰ ریال
تعداد صفحات : ۴۲۸
شابک سیزده رقمی: ۹۷۸-۹۶۴-۳۱۸-۱۷۰-۳
شابک ده رقمی: ۹۶۴-۳۱۸-۱۷۰-۷
قطع کتاب : وزیری
وزن کتاب : ۶۰۲ گرم
نوع جلد : نرم
فهرست مطالب:
پیشگفتار مترجمان
پیشگفتار
قسمت اول: مبانی ریاضیات گسسته
فصل ۱: اصول بنیادی شمارش
۱ـ۱ قاعده‌های حاصل جمع و حاصل ضرب
۱ـ۲ جایگشتها
۱ـ۳ ترکیبها: قضیهٔ دوجمله‌ای
۱ـ۴ ترکیبهای با تکرار؛ توزیعها
۱ـ۵ کاربردی در علم فیزیک (اختیاری)
۱ـ۶ خلاصه و مروری تاریخی
مراجع
تمرینات تکمیلی
فصل ۲: اصول بنیادی منطق
۲ـ۱ رابطهای اساسی و جداول ارزش
۲ـ۲ هم‌ارزی منطقی: قانونهای منطق
۲ـ۳ استلزام منطقی: قاعده‌های استنتاج
۲ـ۴ استفاده از سورها
۲ـ۵ سورها، تعاریف و اثبات قضایا
۲ـ۶ خلاصه و مروری تاریخی
مراجع
تمرینات تکمیلی
فصل ۳: نظریهٔ مجموعه‌ها
۳ـ۱ مجموعه‌ها و زیرمجموعه‌ها
۳ـ۲ اعمال مجموعه‌ای قوانین نظریهٔ مجموعه‌ها
۳ـ۳ شمارش و نمودار وِن
۳ـ۳ سخنی دربارهٔ احتمالات
۳ـ۵ خلاصه و مروری تاریخی
مراجع
تمرینات تکمیلی
فصل ۴: ویژگیهای اعداد صحیح: استقرای ریاضی
۴ـ۱ اصل خوش ترتیبی: استقرای ریاضی
۴ـ۲ تعریفهای بازگشتی
۴ـ۳ الگوریتم تقسیم: اعداد اول
۴ـ۴ بزرگترین مقسوم‌علیه مشترک: الگوریتم اقلیدسی
۴ـ۵ قضیهٔ بنیادی حساب
۴ـ۶ خلاصه و مروری تاریخی
مراجع
تمرینات تکمیلی
فصل ۵: رابطه و تابع
۵ـ۱ حاصل ضربهای دکارتی و روابط
۵ـ۲ توابع: معمولی و یک‌به‌یک
۵ـ۳ توابع پوشا: اعداد استرلینگ نوع دوم
۵ـ۴ توابع خاص
۵ـ۵ اصل لانهٔ کبوتر
۵ـ۶ ترکیب توابع و توابع وارون
۵ـ۷ پیچیدگی محاسباتی
۵ـ۸ تحلیل الگوریتمها
۵ـ۹ خلاصه و مروری تاریخی
مراجع
تمرینات تکمیلی
پاسخها و راه‌حلها
نمادگذاری
فرمولها
پیشگفتار
پیشرفتهای تکنولوژیک بیست وپنج سال اخیر موجب تغییرات زیادی در برنامهٔ درسی دورهٔ کارشناسی دانشگاهها شده است. این تغییرات ورود دروس یک ترمی و چند ترمی زیادی را که در آنها بعضی از مطالب زیر معرفی می‌شوند، به همراه داشته است:
1. روشهایی گسسته که بر طبیعتی متناهی که ذاتیِ بسیاری از مسائل و ساختار‌هاست تأکید دارد؛
2. ترکیبیات ـ جبر یکایک شمردن، یا شمارش؛
3. نظریهٔ گرافها همراه با کاربردها و پیوندهای متقابل آن با زمینه‌هایی نظیر ساختار داده‌ها و روشهای بهینه‌سازی؛ و
4. ساختارهای جبری و متناهی که در ارتباط با شاخه‌هایی نظیر نظریهٔ کدگذاری، روشهای شمارش، شبکه‌های دریچه‌ای، و طرحهای ترکیبیاتی پیش می‌آیند.
یک دلیل اولیهٔ پرداختن به مطالعهٔ مواد موجود در هر یک یا همهٔ این چهار موضوع کلی، فراوانی کاربردهایی است که هنگام مطالعهٔ علوم کامپیوتر ـ به‌ویژه در زمینه‌های ساختار داده‌ها، نظریهٔ زبانهای کامپیوتری، و تحلیل الگوریتمها با آنها روبه‌رو میشویم. علاوه بر آن، کاربردهایی نیز در مهندسی، فیزیک، علوم زیستی، و همچنین در آمار و علوم اجتماعی وجود دارد. در نتیجه، موضوع مورد بحث ریاضیات گسسته و ترکیبیاتی مواد ارزشمندی را در اختیار دانشجویان بسیاری از تخصصها می‌گذارد و به دانشجویانی که در ریاضیات یا علوم کامپیوتر تخصص می‌گیرند منحصر نمی‌شود.
هدف عمدهٔ این ویرایش جدید نیز این است که مقدمات مطالعه در ریاضیات گسسته و ترکیبیاتی را فراهم آورد. مطالب برای دانشجویان مبتدی طرح‌ریزی شده‌اند، از این‌رو، تعداد زیادی مثال با توضیحات تفصیلی آورده شده است. علاوه بر آن، اثباتها نیز، هر جا که داده شده‌اند، با تفصیل کافی همراه‌اند (زیرا مبتدیها را نیز در نظر داشته‌ایم).
این کتاب تلاش دارد تا اهداف زیر را به انجام برساند:
1. آشنا کردن دانشجویانی که در سطح سال دوم یا سوم کارشناسی یا پایینتر هستند با موضوعات و فنون روشهای گسسته و استدلال ترکیبیاتی. مسائل مربوط به شمردن، یا شمارش، نیاز به تحلیلی دقیق از ساختار (مثلاً نقش داشتن یا نداشتن ترتیبها و تکرار‌ها) و امکانات منطقی دارند. در برخی از موقعیت‌ها حتی ممکن است مسألهٔ وجود مطرح شود. با پیگیری چنین تحلیل دقیقی غالباً درمی‌یابیم که برای حل یک مسأله به فنون ساده‌ای برای شمردن نتایج ممکن حاصل از خردکردن مسألهٔ مفروض به مسائل کوچکتر نیاز داریم.
2. وارد کردن طیف وسیعی از کاربردها. در این مورد، هر جا که به ساختار‌هایی از جبر مجرد نیاز داشته‌ایم، فقط نکات اساسی آن نظریه را که برای کاربرد مورد بحث لازم بوده‌اند بسط داده‌ایم. علاوه بر آن، حل بعضی از کاربردها مستلزم روشهایی تکراری‌اند که به الگوریتمهای مشخصی منجر می‌شوند. رهیافت الگوریتمی برای حل مسائل بحثی بنیادی در ریاضیات گسسته است و این رهیافت پیوندهای نزدیک موجود بین این شاخه و علوم کامپیوتر را تقویت می‌کند.
3. پرورش بلوغ ریاضی دانشجویان از طریق مطالعه در زمینه‌ای بسیار متفاوت با مطالب سنتی حساب دیفرانسیل و انتگرال و معادلات دیفرانسیل. مثلاً، در اینجا این فرصت پیش می‌آید که با شمردن گردایه‌ای معین از اشیا به بیش از یک طریق، نتایجی را به اثبات رسانیم. این عمل، اتحادی ترکیبیاتی را به‌دست می‌دهد؛ ضمناً فنی جدید برای ارائهٔ اثبات معرفی می‌کند. در این ویرایش، ماهیت اثبات را، همراه با آنچه استدلالی معتبر نامیده می‌شود، در فصل 2 در ارتباط با قوانین منطق و قواعد استنتاج گسترش داده‌ایم. مطالب ارائه شده در این زمینه مفصلتر از مطالب ارائه شده در ویرایش دوم است. اثبات به وسیلهٔ استقرای ریاضی (همراه با تعاریف بازگشتی) را در فصل 4 آورده‌ایم و سپس آنها را در همهٔ فصول بعدی به‌کار گرفته‌ایم.
در مورد قضایا و اثبات آنها در بسیاری از موارد تلاش کردهایم تا با بررسی و مطالعهٔ مثالهایی مشخص، انگیزهٔ پیدایش آنها را استخراج کنیم. علاوه بر آن، هرجا که موقعیتی متناهی نتیجه‌ای به‌دست می‌دهد که در حالت نامتناهی درست نیست، این موقعیت را برای توجه جدا کردهایم. اثباتهایی را که بسیار طولانی و یا طبیعتی نسبتاً خاص دارند حذف کردهایم. ولی، برای این تعداد بسیار کم از اثباتها که از قلم انداخته شده‌اند، مراجعی را برای خوانندهٔ علاقه‌مند به دیدن اعتبار این نتایج، معرفی کردهایم. (تأکیدی که روی هر اثبات گذاشته می‌شود به اهداف هر مدرس و اهداف دانشجویان مخاطب او بستگی خواهد داشت.)
4. ارائهٔ دید کلی مناسبی از موضوعات برای دانشجویانی در علوم کامپیوتر که در حال گذراندن درسهایی پیشرفته‌تر در زمینه‌هایی نظیر ساختار داده‌ها، نظریهٔ زبانهای کامپیوتری، و تحلیل الگوریتمها هستند. مطالب ارائه شده دربارهٔ گروهها، حلقه‌ها، هیأتها، و جبر‌های بولی مقدمه‌ای کاربردی در اختیار آن دسته از دانشجویان ریاضی قرار می‌دهد که مایل‌اند مطالعات خود را در جبر مجرد ادامه دهند.
مطالب مورد نیاز برای به‌کارگیری این کتاب اساساً عبارتند از زمینه‌ای محکم در ریاضیات دبیرستانی و علاقه به مسائل متنوع و مبادرت به حل آنها. هیچ توانایی خاصی در برنامه‌نویسی خواسته نشده است. ولی، قطعه برنامه‌های فراوانی (که به زبان پاسکال ارائه شده‌اند) وجود دارند و این‌ها را به‌منظور تقویت مثالهای خاص طرح کردهایم و توضیح داده‌ایم. در مورد حساب دیفرانسیل و انتگرال بعداً در همین پیشگفتار متذکر خواهیم شد که تا چه حد در فصلهای 9 و 10 به آن پرداخته‌ایم.
انگیزهٔ اصلی من در نوشتن ویرایش‌های اول و دوم این کتاب ناشی از تشویقی بود که در طول سال‌های متمادی از طرف دانشجویان و همکارانم و همچنین، دانشجویان و استادانی که ویرایش نخست این کتاب را در کالجها و دانشگاههای متفاوت مورد استفاده قرار داده‌اند، دریافت کردم. در آن دو ویرایش هم علایق خودم و دانشجویانم و هم توصیه‌های کمیتهٔ ویژه برنامه‌ریزی برای دورهٔ کارشناسی ریاضی1 و انجمن سازندگان ماشین‌های محاسبه2 ، منعکس بود. این ویرایش سوم در همان راستاست و اینک منعکس‌کنندهٔ توصیه‌های مدرسان و به‌ویژه دانشجویانی است که از ویرایش دوم کتاب بهره گرفته‌اند و یا در حال حاضر از آن بهره می‌گیرند.
ویژگی ها
در زیر توصیف کوتاهی از بعضی ویژگیهای اصلی ویرایش جدید می‌آوریم. این توصیف به منظور یاری‌رساندن به خواننده (دانشجو یا غیر دانشجو) در فراگیری مبانی ریاضیات گسسته و ترکیبیاتی تدوین شده است.
تأکید بر الگوریتمها و کاربردها. الگوریتمها و کاربردهایی را در بسیاری از زمینه‌ها در سرتاسر متن ارائه کردهایم. مثلاً،
1. فصل 1 حاوی موارد متعددی است که در آنها مباحث مقدماتی شمارش مورد نیازند ـ به‌ویژه یک مثال جدید به مسألهٔ اضافه شماری اشاره دارد.
2. بند 7 از فصل 5 مقدمه‌ای بر پیچیدگی محاسباتی را دربردارد. بعداً این مطلب را در بند 8 همین فصل، به منظور تحلیل زمان اجرای چند قطعه برنامهٔ مقدماتی، که یکی از آنها به تولید اعداد فیبوناچی میپردازد، به‌کار گرفته‌ایم.
3. مواد فصل 6 دربارهٔ زبانها و ماشین‌های متناهی‌الحالت است. این فصل خواننده را با زمینه‌ای مهم در علوم کامپیوتر ـ نظریهٔ زبانهای کامپیوتری ـ آشنا می‌سازد.
4. فصلهای 7 و 12 حاوی بحثهایی دربارهٔ کاربردها و الگوریتم‌هایی است که مرتب‌سازی توپولوژیک و فنون جستجو، مشهور به «نخست عمق را جستجو کن» و «نخست عرض را جستجو کن»، را مورد بحث قرار می‌دهند.
5. در فصل 10 موضوع روابط بازگشتی را می‌یابیم. مطالب این فصل حاوی کاربردهایی است دربارهٔ (الف) مرتب‌کردن حبابی، (ب) جستجوی دوتایی، (پ) اعداد فیبوناچی، (ت) دانهٔ برف کوخ، (ث) شبکه‌های مقاومت خطی، (ج) ساختار داده‌هایی به‌نام پشته، و (چ) درخت‌های دوتایی.
6. فصل 16 خواص بنیادی ساختاری جبری به‌نام گروه را معرفی می‌کند. مطالب این فصل نشان می‌دهد که چگونه این ساختار در مطالعهٔ جبری نظریهٔ کدگذاری و در مسائل شمارش که به روش شمارش پولیا نیازمندند، به‌کار گرفته می‌شود.
توضیحات مفصل. توضیحات، چه در مثالها و چه در اثبات قضایا، چنان طرح شده‌اند که دقیق و کامل باشند. نحوهٔ ارائهٔ مطلب اساساً برای بهتر کردن درک خواننده‌ای است که برای نخستین بار این نوع مطالب را می‌بیند.
تمرینات. نقش تمرینات در هر متن ریاضی نقش برجسته‌ای است. مدت زمان مصرف شده برای تمرینات به‌طور قابل ملاحظه‌ای روند درس را تحت تأثیر قرار می‌دهد. با توجه به علاقه و زمینهٔ ریاضی دانشجویان مخاطب، یک مدرس باید دریابد که مدتی از وقت کلاس که صرف بحث دربارهٔ تمرینات می‌شود، متفاوت است.
بیش از 1700 تمرین در 17 فصل کتاب گنجانده شده است. آنهایی که در پایان هر بند آمده‌اند معمولاً ترتیب تنظیم مطالب آن بند را منعکس می‌کنند. این تمرینات به‌منظور (الف) مرور مفاهیم اساسی موجود در آن بند؛ (ب) ایجاد پیوند با ایده‌های ارائه شده در بندهای قبلی همان فصل؛ و (پ) معرفی مفاهیمی اضافی که در ارتباط با مواد موجود در همان بندند، طرح شده‌اند. بعضی از تمرینات، ابداع الگوریتمی یا نوشتن برنامه‌ای کامپیوتری را غالباً برای حل حالتی از مسأله‌ای کلی می‌طلبند. معمولاً این تمرینات فقط به مقدار کمی از تجربهٔ برنامه‌نویسی نیاز دارند.
هر فصل با مجموعه‌ای از تمرینات تکمیلی پایان می‌پذیرد. این تمرینات مروری دیگر از ایده‌های ارائه شده در آن فصل را فراهم می‌آورند و همچنین، مواد ارائه شده در فصلهای قبلی را به‌کار می‌گیرند.
تقریباً حل همهٔ قسمت‌های تمریناتِ دارای شمارهٔ فرد در پایان کتاب آورده شده است.
خلاصهٔ فصلها. در هر فصل، آخرین بند، مروری مختصر و تاریخی دربارهٔ ایده‌های اصلی ارائه شده در آن فصل را دربردارد. هدف از تدوین این بند این است که دیدی کلی از محتوای فصل مورد بحث به خواننده داده شود و اطلاعاتی برای مطالعه و کاربردهای بیشتر در اختیار او قرار گیرد. به‌آسانی می‌توان با استفاده از فهرست مراجعی که آورده شده است چنین مطالعهٔ عمیقتری را به انجام رساند.
به‌ویژه، خلاصه‌های واقع در پایان فصلهای 1، 5 و 9 حاوی جدولهایی دربارهٔ فرمولهای شمارشی است که در هر یک از این فصلها معرفی شده‌اند. گاهی این جدولها حاوی نتایجی از فصلهای قبلی به منظور انجام مقایسه با نتایج جدید و نشان‌دادن این امر است که چگونه نتایج جدید قبلی را وسعت می‌بخشند.
سازماندهی
زمینه‌های ریاضیات گسسته و ترکیبیاتی در برنامهٔ درسی دورهٔ کارشناسی تا اندازه‌ای جدیدند، از این‌رو، سلیقه‌های متفاوتی دربارهٔ موضوعاتی که باید در این زمینه‌ها ارائه شوند وجود دارد. هر مدرس و هر دانشجو ممکن است علائق گوناگونی داشته باشد. درنتیجه، مطابق روال هر دورهٔ درسی کلی، مطالب ارائه شده نسبتاً وسیع‌اند. با این‌حال، موضوعات دیگری نیز هستند که برخی از خوانندگان ممکن است احساس کنند که باید آنها را در این دورهٔ درسی گنجاند. علاوه بر آن، همیشه در مورد ترتیب بعضی از موضوعات ارائه شده در این متن اختلاف نظرهایی وجود خواهد داشت.
در سراسر کتاب بر طبیعت و اهمیت رهیافت الگوریتمی در حل مسائل تأکید کردهایم. با آشکار ساختن پیوندهای موجود بین شمارش و ساختار، دو موضوع اصلی دیگر که شیرازهٔ مطالب مورد بحث کتاب را تشکیل می‌دهند، بر ایده‌ها و رهیافتها در حل مسائل تأکید بیشتری ورزیده‌ایم.
مطالب کتاب را به چهار زمینهٔ اصلی تقسیم کردهایم. هفت فصل نخست هستهٔ زیربنای کتاب را تشکیل می‌دهند و مبانی ریاضیات گسسته را ارائه می‌کنند. این مطالب برای درسی نیم‌ترمی یا یک‌ترمی در ریاضیات گسسته کفایت می‌کنند. کسانی که زمینه‌ای قبلی در منطق دارند می‌توانند فصل 2 را مرور کنند. کسانی که به گسترش و نوشتن اثباتها علاقه‌مندند باید این مطالب را بسیار دقیق بررسی کنند. درسی در سطح بالاتر ـ درسی که بر ترکیبیات تأکید داشته باشد ـ باید دربرگیرنده، فصلهای 8، 9 و 10 (و اگر زمان اجازه دهد، بندهای 1، 2، 3، 9 ، 10 و بند 11 از فصل 16) باشد. در فصل 9 چند نتیجه از حساب دیفرانسیل و انتگرل را به‌کار گرفته‌ایم؛ یعنی، کلیاتی دربارهٔ مشتقگیری و تجزیه به کسر‌های جزئی. ولی کسانی که می‌خواهند این فصل را کنار بگذارند، باز می‌توانند بندهای 1، 2، 3، 6، و7 از فصل 10 را در مطالعهٔ خود بگنجانند. برای ارائهٔ درسی که بر نظریه و کاربردهای گرافهای متناهی تأکید داشته باشد می‌توان فصلهای 11، 12، و13 را مورد استفاده قرار داد. این فصلها سومین تقسیم‌بندی اصلی این کتاب را تشکیل می‌دهند. برای ارائهٔ درسی در جبر کاربردی، فصلهای 14، 15، 16، و 17 (چهارمین و آخرین تقسیم‌بندی) ساختارهای جبری ـ گروهها، حلقه‌ها، جبر‌های بولی و هیأتها ـ را مورد بررسی قرار می‌دهند و حاوی کاربردهایی دربارهٔ توابع راه‌گزین، نظریهٔ جبری کدگذاری، و طرحهای ترکیبیاتی است. سرانجام، برای ارائهٔ درسی دربارهٔ نقش ساختارهای گسسته در علوم کامپیوتر می‌توان از مواد موجود در فصلهای 11، 12، 13، 15، و بندهای 1-8 از فصل 16 بهره برداری کرد. زیرا در اینجا، علاوه بر مقدمه‌ای بر نظریهٔ گرافها و درختها و نقش آنها در بهینه‌سازی، کاربردهایی را دربارهٔ توابع راه‌گزین و نظریهٔ جبری کدگذاری می‌یابیم.
با در نظر گرفتن وابستگیهای موجود بین فصلهای کتاب که در زیر می‌آید، می‌توان دوره‌های درسی دیگری را تنظیم کرد.
فصل وابستگی به فصلهای قبلی
1 بدون وابستگی
2 بدون وابستگی (بنابراین مدرس می‌تواند درسی دربارهٔ ریاضیات گسسته را با مطالعهٔ منطق یا مقدمه‌ای بر شمارش آغاز کند.)
3 1، 2
4 1، 2، 3
5 1، 2، 3
6 1، 2، 3، 5 (وابستگی‌ای جزئی در بند 6. 1 به بندهای 4. 1، 4. 2)
7 1، 2، 3، 5، 6 (وابستگی‌ای جزئی در بند 7. 2 به بندهای 4. 1، 4. 2)
8 1، 3 (وابستگی‌ای جزئی در مثال 8. 3 از بند 8. 1 به بند 5. 3)
9 1، 3
10 1، 3، 4، 5، 9
11 1، 2، 3، 4، 5 (گرچه در فصلهای 5، 6، 7، 8، و 10 به بعضی از ایده‌های نظریهٔ گرافها اشاره شده است، ولی مواد این فصل بدون وابستگی به موادی دربارهٔ نظریهٔ گرافها که در این نتایج آورده شده است گسترش یافته است.)
12 1، 2، 3، 4، 5، 11
13 3، 5، 11، 12
14 2، 3، 4، 5، 7تابع فی اویلر را به‌کار گرفته‌ایم. این تابع در بند به دست آمده است ولی می‌توان نتیجه را اینجا در فصل 14 بدون توجه به مطالب فصل 8 به‌کار گرفت.
15 2، 3، 5، 7
16 1، 2، 3، 4، 5، 7
17 2، 3، 4، 5، 7، 14
تغییرات ویرایش سوم
تغییرات انجام گرفته در ویرایش سوم ریاضیات گسسته و ترکیبیات طیفی گسترده از معتدل تا مفصل را تشکیل می‌دهند. ولی، آهنگ و هدف متن یکسان باقی‌مانده است. این همان هدف مؤلف است که می‌خواهد در چارچوب این صفحات، مقدمه‌ای محکم، خواندنی، و قابل درک بر ریاضیات گسسته و ترکیبیاتی برای دانشجوی مبتدی فراهم آورد. در اینجا به بعضی از تغییرات ویرایش سوم که آنها را براساس تفسیر‌ها و انتقادات مدرسان و دانشجویانی اعمال کردهایم که دو ویرایش نخست این کتاب را مورد استفاده قرار داده‌اند، اشاره می‌کنیم:
• این ویرایش حاوی مقدمه‌ای (در فصل 1) بر کاربرد نمادگذاری حاصل‌جمع (یا سیگما) و (در فصل 4) نمادگذاری حاصلضرب (یا پی) است. در ویرایش‌های قبلی فرض را بر این گذاشته بودیم که خواننده با این نماد‌گذاری‌ها آشنایی دارد.
• در فصل 2 نوشتن اثباتها را گسترش داده‌ایم. به‌ویژه، بند جدید 2. 5 حاوی مطالبی دربارهٔ قواعد تخصیص و تعمیم و نقش آنها در نوشتن اثباتهاست. سپس این مطالب را در بند نخست فصل 3، آنجایی که آنها را در اثبات قضایایی دربارهٔ مجموعه‌ها و زیر مجموعه‌ها به‌کار برده‌ایم، نیز آورده‌ایم.
• در ویرایش دوم تعاریف بازگشتی را در بند 4. 1، هنگام معرفی مفهوم استقرای ریاضی، مورد بحث قرار داده بودیم. در این ویرایش جدید، بند 4. 2 را به گسترش مفهوم تعریف بازگشتی اختصاص داده‌ایم. این امر این امکان را برای ما فراهم آورد تا اعداد فیبوناچی و اعداد وابسته به آنها یعنی اعداد لوکاس را زودتر (از فصل 10) معرفی کنیم.
• در بند 4. 1 (برای نخستین بار) اعداد همساز ر آورده‌ایم و مطالب مربوط به اعداد کاتالان واقع در بند 10. 5 را بسط داده‌ایم.
• سه پیوست افزوده‌ایم تا به شرح زیر به خواننده یاری رسانند: دو پیوست نخست حاوی مروری دربارهٔ توابع نمایی و لگاریتمی و مقدمه‌ای بر ماتریسهاست. خواننده درخواهد یافت که این مواد برای درک مطالبی از کتاب که به این مفاهیم مربوط‌اند، مناسب است. آخرین پیوست حاوی مطالبی دربارهٔ مجموعه‌های شمارش‌پذیر و شمارش‌ناپذیر برای کسانی است که می‌خواهند کمی بیشتر دربارهٔ مجموعه‌ها و توابع بدانند و در واقع این پیوست ایده‌های ارائه شده در فصلهای 3 و 5 را گسترش می‌دهد.
• از زمان انتشار ویرایش دوم برای مؤلف فرصتهای زیادی پیش آمد تا با دانشجویانی که ریاضیات را در این کتاب مطالعه کرده بودند گفتگو کند. این گفتگوها، همراه با نظرات دانشکده‌هایی که ویرایش دوم را مورد استفاده قرار داده بودند، به افزایش 87 مثال جدید انجامید. هدف از این مثالها یاری رساندن به دانشجویی است که قبلاً در بعضی از موقعیت‌ها به مثالی دیگر نیاز پیدا می‌کرده است.
• بیش از 1700 تمرین در این ویرایش جدید وجود دارد. این نمایانگر افزایش بیش از 300 تمرین نسبت به ویرایش دوم است.
• بسیاری از خلاصه‌ها و مرور‌های تاریخی واقع در پایان فصلها را بسط داده‌ایم و به فهرست مراجع هر فصل مراجع جدید را افزوده‌ایم. علاوه بر آن، در این ویرایش جدید هر خاصه و مرور تاریخی حاوی تصویری از حداقل یک ریاضیدان است که نامش را در همان مرور تاریخی ذکر کردهایم.
ر.پ.گ
تِراوت، ایندیانا
1 . Committee on the Undergraduate Program in Mathematics
2 . Association of Computing Machinery
پیشگفتار مترجمان
یکی از ویژگیهای بارز ریاضیات، قدرت مدلسازی آن است. تاریخ تحول فکری بشر سرشار از مثالهایی در تأیید این مطلب است. جالب آن است که هرگاه مسأله‌ای متعلق به یکی از شاخه‌های معرفت بشری تن به قالبی ریاضی سپرده است نه فقط زودتر به پاسخ خود رسیده بلکه جوانب عمیقتر آن مسأله آشکارتر شده و پیشرفت آن شاخهٔ علمی نیز سرعت فزاینده‌ای گرفته است.
پیشرفتهای سریع و همه‌جانبهٔ علوم و تکنولوژی و تحولات عظیم اقتصادی و گسترش بی‌سابقهٔ ارتباطات و دیگر دانشهای بشری در قرن بیستم و به ویژه در نیمهٔ دوم آن، مسائل جدیدی را مطرح ساخته است. طبیعت متناهی (و گاه نامتناهی ولی گسستهٔ) بسیاری از این مسائل همراه با به‌کارگیری ابزار جایگزین‌ناپذیر کامپیوتر (و علم کامپیوتر) «ریاضیات مناسبی غیر از حساب دیفرانسیل و انتگرال سنتی» را طلب می‌کند. در این چارچوب است که بار دیگر ریاضیات خصلت مدلسازی خود را آشکار می‌سازد و این بار در قالب «ریاضیات گسسته» به بیان دقیقتر مسائل مطرح شده پرداخته و سپس، با ابداع الگوریتمهای مناسب و پیاده‌سازی کامپیوتری آنها، به حل این مسائل میپردازد.
آشنایی جدی با علوم کاربردی ـ فنی (و گاه نظری) امروزی بدون داشتن درکی صحیح از مباحث ریاضیات گسسته امری دشوار و در واقع محال است. به همین سبب امروزه کشور‌های پیشرفتهٔ جهان درس ریاضیات گسسته (و دروس وابسته به آن) را در برنامهٔ درسی دبیرستانها گنجانده‌اند. همچنین، همهٔ دانشگاههای معتبر جهان این درس را در مواد درسی دورهٔ کارشناسی رشته‌های ریاضی، علوم کامپیوتر و بسیاری از رشته‌های دیگر خود منظور کرده‌اند. در کشور ما نیز اخیراً این اقدام بجا انجام گرفته است. ولی جای خالی مرجعی جامع و معتبر در این زمینه که بتواند پاسخگوی نیاز‌های روز‌افزون دانش‌آموزان دبیرستانها و به‌ویژه دانش‌آموزان دورهٔ پیش‌دانشگاهی، دبیران ریاضی و دانشجویان دورهٔ کارشناسی باشد، احساس می‌شد1 . نگارندگان این سطور بین کتابهای معتبر موجود در سطح جهان، کتاب حاضر را که یکی از بهترین متون در این زمینه است برگزیدند و به ترجمهٔ آن همت گماردند.
یکی از ویژگیهای کتاب حاضر این است که علاوه بر وجود تعداد زیادی تمرین در انتهای هر بند و در پایان هر فصل، تعداد بسیار زیادی مثال حل شده دربارهٔ هر مبحث، چه قبل و چه بعد از معرفی آن، گنجانده شده است و این درست همان چیزی است که دانش‌آموزان، دبیران ریاضی و دانشجویان را به طور مؤثری در درک مفاهیم ارائه شده و استفادهٔ بهینه و خلاقانه از آنها یاری می‌دهد.
همان‌گونه که از عنوان فارسی کتاب آشکار است، نام اصل آن «ریاضیات گسسته و ترکیباتی» و مؤلف آن رالف پ. گریمالدی است. این کتاب در هفده فصل و در قالب چهار قسمت تنظیم شده است و مترجمان چهار قسمت مورد نظر مؤلف را با کمی تغییر در چهار مجلد تنظیم کرده‌اند. (به سبب ملاحظات مربوط به حجم این چهار مجلد، فصلهای 6 و 7 که مربوط به قسمت اول کتاب‌اند در مجلد دوم آمده‌اند). نکتهٔ دیگری که اشاره به آن ضروری به نظر می‌رسد این است که صورت بعضی از مثالها و تمرین‌ها به گونه‌ای بوده است که با فرهنگ جامعهٔ ما همخوانی ندارد و بنابراین، بدون آنکه در محتوای علمی آنها کمترین تغییری دهیم، صورت آنها را دگرگون ساختیم. در مورد اسامی نیز به همین ترتیب عمل کردهایم، یعنی تا آنجا که مقدور بوده است اسامی فارسی را به جای اسامی بیگانه گذاشته‌ایم.
در پایان متذکر میشویم که پیشگفتار مؤلف حاوی توضیحاتی تفصیلی دربارهٔ فصلهای کتاب، نحوهٔ سازماندهی مطالب آن، وابستگی فصلها به یکدیگر، تغییرات ایجاد شده به وسیلهٔ مؤلف در ویرایش سوم (انگلیسی) کتاب و غیره است و از این نظر نیازی به تکرار آنها احساس نمی‌کنیم.
سخن را کوتاه می‌کنیم و امید‌واریم که ترجمهٔ این کتاب در نظر اهل علم و معرفت و به ویژه جوانان شیفتهٔ نیل به قله‌های دانش و فضیلت مقبول افتد.
محمدعلی رضوانی ـ بیژن شمس
1. در سال 1375 در همین زمینه کتابی خلاصه‌تر با عنوان «ریاضیات گسستهٔ مقدماتی» تألیف وی.کی. بالاکریشنان، ترجمهٔ مترجمان حاضر، به وسیلهٔ مؤسسهٔ انتشارات فاطمی به چاپ رسید.
متن پشت جلد:
ریاضیات گسسته و ترکیبیاتی شاخهٔ مهمی از ریاضیات نوین است که علاوه بر ریاضیات، در علوم دیگر نیز کاربردهای فراوانی یافته است. کتاب ریاضیات گسسته و ترکیبیاتی نوشتهٔ رالف پ. گریمالدی یکی از جامع‌ترین منابع این رشته در سطح پیش‌دانشگاهی و دانشگاهی است.
جلد اول این کتاب به بحث دربارهٔ روش‌ها و قواعد گوناگون شمارش، آشنایی با زبان مجموعه‌ها، مفهوم تابع، و مقدمات منطق ریاضی میپردازد. در جلد دوم، زبانها و ماشین‌های متناهی‌الحالت، رابطه‌ها، گرافها، توابع مولد و افرازهای اعداد صحیح، اصل شمول و طرد، و روابط بازگشتی مورد بحث قرار می‌گیرد. جلد سوم حاوی بحثی گسترده دربارهٔ گرافها، درختها و کاربردهای گوناگون آنها در حل بسیاری از مسائل است. آشنایی با بهینه‌سازی و نظریهٔ تطابق بخش دیگری از این کتاب را تشکیل می‌دهد. در جلد چهارم، ساختارهای جبری گروه، حلقه و هیأت‌های متناهی، مورد بحث قرار می‌گیرند.
مطالعهٔ کتاب ریاضیات گسسته و ترکیبیاتی برای دانشجویان رشته‌های ریاضی و علوم کامپیوتر، دانش‌آموزان دورهٔ پیش‌دانشگاهی رشتهٔ ریاضی، علاقه‌مندان به شرکت در آزمون‌های المپیاد ریاضی، و دبیران ریاضی سودمند است.