تخمین و تقریب

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

دنباله ساده ای که با فرمول ساده ای بیان نمی شود

فرض کنید
اعداد حقیقی باشد که بر مبنای قانون زیر تولید می شود. عدد اول یا برابر با 1 است و هر عدد بعدی برابر است با حاصل جمع عدد قبلی با ریشه دوم آن به عبارت دیگر به ازای هر n، داریم . این معرفی ساده، این سؤال را به دنبال خواهد داشت که عدد چیست؟ برای این که این سؤال بهتر درک شود اجازه دهید برای مقادیر کوچک n، را حساب کنیم:
و به همین ترتیب برای بقیه nها.
توجه کنید که بیان اعداد سمت راست چندان راحت نیست و در هر مرحله طول رشته اعداد دو برابر مرحله قبل خواهد شد و مثلاً برای عدد ، با مجموعه ای از 024/1 عدد 2 سروکار خواهیم داشت که بخش عمده آن در زیر جنگلی از رادیکال ها پنهان شده است. چنین شرحی از عدد مسلماً نمی تواند کمکی به درک ما از این عدد کند. آیا این بدان معنی است که باید از هر کوششی برای درک این رشته دست برداریم؟
نه، چرا که اگرچه غیر از مواردی که n عدد کوچکی است نمی توان انتظار داشت که راه مناسبی برای محاسبه دقیق مقدار در اختیار داشته باشیم اما در عوض یک تخمین مناسب می تواند در بسیاری از موارد راهگشای ما باشد. در بالا من نمایش دقیقی از عدد را نوشتم اما آیا این چنین نمایشی برای شما کارآمدتر است یا این که بگویم این عدد نزدیک به 5/7 است؟
پس اجازه دهید به جای آن که بپرسیم چند است این سؤال را مطرح کنیم که چقدر بزرگ است؟
این سؤال به ما این اجازه را می دهد تا فرمول ساده ای را پیدا کنیم که تقریب خوبی از را به ما می دهد. چنین فرمولی را می توان این گونه بیان کرد که مقدار تقریباً برابر است برای اینکه نشان دهیم این رابطه تقریباً درست است از یک حیله کوچک ریاضی استفاده می کنیم، توجه کنید که:
بنابراین اگر آن گاه اگر از + صرف نظر كنيم مي بينيم كه روش توليد دقيقاً يكسان است از طرفي اگر n عدد بسيار بزرگي باشد، آنگاه ؟ خطای موجود در جواب نهایی چندان قابل توجه نیست ( این بخش از برهان است که من آن را در اینجا بیان نمی کنم ). بنابراین ها تقریباً به درستی از دنباله ای از ها تولید می شوند و مقدار آن است که تقریب خوبی از مقدار را در اختیار ما می گذارد.

روش های تقریب

زمانی که قرار است از چنین شیوه هایی برای تخمین استفاده کنیم، باید مقدار مناسب تخمین را برای آن مشخص کنیم. میزان مناسب بودن یک تخمین از یک بحث به بحث دیگر فرق می کند.
فرض کنید بخواهید دنباله ای اکیداً صعودی مانند
را با کمک یک دنباله ساده دیگر مانند تخمین بزنید. بهترین و مناسب ترین سری عددی که ممکن است پیدا کنید ( و البته چنین حالتی بسیار کم پیش می آید ) آن است که به ازای هر n، تفاضل همواره کمتر از مقدار ثابتی مثلاً 1000 باشد، در این صورت با افزایش مقادیر آنها نسبت آنها به یک نزدیکتر می شود، مثلاً فرض کنید در یک مرحله و باشند در این صورت تفاضل که در مقایسه با بزرگی عددها، خطای اندکی خواهد بود. بنابراین می توان گفت در حد ثابت جمعی با هم برابر شوند صادق است اما در دیگر حالت ها نیز صدق خواهد کرد. برای مثال اگر باشد در این صورت که با افزایش مقدار n نسبت an و bn به 1 نزدیک می شود اما تفاضل bn-an برابر با 3n است که با افزایش n مقادیر بزرگی خواهد شد.
اما همیشه نمی توان به چنین تقریبی امید داشت و اگر بتوان به تقریبی پیچیده تر از این هم دست یافت باید خوشحال باشیم.
یکی دیگر از تقریب های رایج این است که تقریباً با هم برابر دانسته شوند به شرط آنکه نه و نه از یک عدد مشخص تجاوز نکند. مثلاً این دو نسبت از عددی مانند 1000، بزرگتر نشود، البته هر چقدر این عدد کوچکتر باشد نتیجه بهتر است، به عبارت دیگر در این مورد نباید تفاوت bn، an را در حد مشخص نگاه داشت بلکه باید تفاوت میان نسبت های an, bn را در حد قابل قبولی حفظ کرد.
البته شاید به نظر عجیب برسد که چگونه می توان دو عددی را که یکی از دیگری مثلاً 1000 برابر بزرگتر است را یکی فرض کرد.
علت چنین شایبه ای این است که ما معمولاً با اعداد کوچک سروکار داریم و مسلماً هیچ کس اعدادی مانند 17 و 13895 را حتی به طور تقریبی برابر فرض نمی کند اما اگر اعداد بزرگتر شوند قضیه فرق می کند مثلاً چندان هم بی ربط نیست اگر بگوییم دو عدد
2904756294089761562389545345987608890796872347514348757775468
و
360982345987209761234987098249834087623457796784587345987166464
تقریباً یک اندازه هستند اگرچه دومی تقریباً 1000 برابر بزرگتر است اما هر دوی آنها در تعداد ارقام با هم نزدیکند و در حدود 60 تا 65 رقم دارند. اگر هیچ خاصیت و ویژگی مناسب دیگری در دسترس نباشد، شاید همین حد از دقت هم کارآمد باشد. اما اگر با وضعیتی مواجه شدیم که حتی همین درجه از تقریب هم در دسترس نبود هنوز می توان امید داشت که دو دنباله مانند
را پیدا کنیم و نشان دهیم که دنباله همواره کوچکتر از و دنباله همواره بزرگتر از است، آنگاه می توان گفت: کران پایینی برای کران بالایی برای آن است، برای مثال شاید یک ریاضیدان برای حل مسأله ای مجبور شود بگوید، من حتی نمی توانم به طور تقریبی مقدار را حدس بزنم اما می دانم همواره مقدار از بزرگتر و کوچکتر از
است البته اگر با مسأله دشواری سروکار داشته باشیم، باید گفت که همین نتیجه گیری هم دستاورد مهمی به حساب می آید.
هر آنچه را که باید در مورد لگاریتم ها، مربع ها، ریشه ها و غیره بدانید. یکی از دلایلی که مردمی که در محیط کار ریاضیاتی نیستند کمتر از میزان شیوه تخمین ها و تقریب ها خبر دارند آن است که اکثر ریاضیدانان با زبان خاصی درباره این مسائل صحبت می کنند و از جملاتی مانند نمودارش همانند ، ریشه دوم t و یا به مقدار ثابتی رشد می کند استفاده می کنند. اگر کسی از مقادیر و ارزش های تقریبی لگاریتم ها و ریشه های دوم اعداد بزرگ اطلاع داشته باشد، آنگاه به سادگی می تواند درک کند که این زبانی برای بیان همین تقریب ها است.
اگر شما دو عدد مثبت و صحیح بسیار بزرگ مانند m و n داشته باشید و بخواهید تخمین غیردقیق از حاصل ضرب mn داشته باشید باید چه کار کنید؟ یک شروع خوب این است که تعداد ارقام n,m را بشمارید. اگر m دارای hرقم و n دارای k رقم باشد آنگاه m بین دو عدد و n نیز بین دو عدد است و بنابراین در میان دو عدد قرار دارد. بنابراین با شمارش تعداد ارقام می توانید تخمینی از رده 100 برای حاصل ضرب بدست آورید. چرا که تنها 100 برابر است. اما با توجه به این که عدد مورد نظر در میان این دو حد قرار دارد با در نظر گرفتن حد میانی آنها یعنی ، متوجه می شوید که این عدد با حاصل ضرب m×n تنها تفاوتی از مرتبه 10 دارد.
به عبارت دیگر اگر شما می خواهید فقط تخمینی از یک حاصل ضرب را به دست آورید کار ساده این خواهد بود که ارقام آنها را بشمرید و اگر می خواهید پاسخ واقعی تری داشته باشید عدد 1 را از آن کم کنید و عددی با آن تعداد رقم بنویسید. برای مثال 1293875 ( 7 رقم ) ضرب در 20986759777 ( 11 رقم ) در حدود عدد 10000000000000000 ( 17 رقم است ) اگر می خواهید دقت خود را اندکی افزایش دهید. از آنجا که رقم اول با 1 و رقم دوم با 2 شروع می شود حاصل ضرب شما احتمالاً به عدد 20000000000000000 نزدیکتر است، البته برای بسیاری از کاربردها این حد از دقت، لازم نیست.
از آن جایی که تقریب ضرب دو عدد کار دشواری نیست پس می توان همین کار را برای توان ها و ریشه ها هم انجام داد. در حقیقت وقتی با مربع یک عدد سروکار دارید، اعداد خود را با اعداد جدیدی جایگزین می کنید که دو برابر عدد اول رقم دارد، به همین ترتیب وقتی با ریشه دوم یک عدد سروکار داریم. در حقیقت با نصف ارقام n سر و کار داریم. ( به طور تقریبی ) به طور مشابه با تقسیم تعداد ارقام به 3 به تقریبی از ریشه سوم عدد دست پیدا می کنیم به طور کلی اگر n عدد بزرگ صحیحی و t عددی مثبت و طبیعی باشد آنگاه تقریباً t برابر n رقم خواهد داشت.

درباره لگاریتم ها چه می توانیم بگوییم؟

از دیدگاه تقریب داستان لگاریتم ها نیز بسیار ساده هستند لگاریتم یک عدد تقریباً در حد تعداد ارقام آن است برای مثال لگاریتم 34587 و 49238797548735 به ترتیب در حدود 5 و 15 است.
البته این تقریب زمانی است که با لگاریتم در مبنای 10 سر و کار دارید. این همان لگاریتمی است که با علامت LOG روی ماشین حساب جیبی شما مشخص شده است. اما زمانی که ریاضیدانان درباره لگاریتم حرف می زنند عموماً منظورشان لگاریتم طبیعی است که به معنی لگاریتم در مبنای e است. این ریشه عددی بسیار مهم و اساسی در ریاضیات است اما فعلاً ما چیزی که لازم است درباره آن بدانیم آن است که لگاریتم طبیعی یک عدد ( که در ماشین حساب با فشردن دکمه LN آن را مشاهده می کنید ) تقریباً با تعداد ارقام یک عدد ضرب در 2/3 برابر است. بنابراین لگاریتم طبیعی 2305799985748 تقریباً برابر 29.9= 2.3×13 است ( اگر شما درباره لگاریتم ها اطلاعاتی داشته باشید خواهید دید که در حقیقت این تعداد ارقام را باید در عدد ضرب کنید ).
فرض کنید شما عددی مانند t در اختیار دارید و می دانید این عدد لگاریتم طبیعی عدد دیگری مانند n است در این صورت n را توان نمایی (exponential) t می نامند و به شکل نشان می دهند. در این صورت x تقریباً چه اندازه است؟ خوب کافی است برای تقریب n تعداد ارقام n را شمرده در 3/2 ضرب کنیم. بنابراین تعداد ارقام x باید حدود باشد و بدین ترتیب حداقل تقریبی از مقدار n به دست می آوریم.
مهمترین ویژگی تقریب این است که به شما امکان مقایسه می دهد. برای مثال کاملاً مشخص است که لگاریتم عدد بزرگی مانند n بسیار کوچکتر از ریشه سوم آن است: اگر n، 75 رقم داشته باشد، آن گاه مکعب آن بسیار بزرگ خواهد بود و تقریباً 25 رقم دارد اما لگاریتم طبیعی آن در حدود 5/172=3/2×75 خواهد بود. به طور مشابه توان نمایی عددی مانند m بسیار بزرگتر از توان مثلاً m10 خواهد بود. مثلاً اگر m، 50 رقم داشته باشد حدود 500 رقم دارد اما تعداد ارقام در حدود که بیشتر از 500 رقم می شود.
نمونه های زیر نتایج تقریبی اعمال برخی عملگراها را روی عدد n=941192 نشان می دهد. البته من را در نظر نگرفته ام چرا که در این صورت می بایست عنوان این کتاب را عوض می کردم و آن را از حالت مقدماتی خارج می کردم.

قضیه اعداد اول

عدد اول عدد صحیحی است که از 1 بزرگتر بود و جز بر خود و 1 قابل تقسیم نباشد. اعداد اول کوچکتر از 150 عبارتند از:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149.
هر عدد کوچکتر از 150 دیگری که در نظر بگیرید قابل تجزیه است مثلاً 13×7=91 ( شاید برخی درباره این که چرا 1 را در رده اعداد اول جای ندادیم تعجب کنند. این مسأله مشکل چندانی ایجاد نمی کند و فقط به این قصد صورت گرفته است که بر این واقعیت تأکید کند که تنها یک روش برای تجزیه اعداد وجود دارد ).
اعداد اول ذهن ریاضیدانان را از زمان یونانیان باستان به خود مشغول کرده است چرا که این اعداد به طور تقریباً تصادفی در میان اعداد توزیع شده اند. البته این توزیع چندان هم تصادفی نیست. هنوز هیچ کس نتوانسته است قانون ساده ای را پیدا کند که به شما بگوید n امین عدد اول کدام است ( البته امکان دارد کسی بخواهد همه اعداد را بنویسد تا به n امین عدد اول برسد اما این روشی است که برای مقادیر بزرگ n چندان مناسب نیست ).
ضمن این که بسیاری گمان می کنند اصولاً ممکن است چنین روشی حتی وجود هم نداشته باشد.
با وجود این بررسی همین 35 عدد اول ابتدایی نشان می دهد که این اعداد از خاصیت های جالبی برخوردارند. اگر تفاضل های دو عدد متوالی را بنویسید رشته عددی زیر به دست می آید:
1, 2, 2, 4, 2, 4, 2, 4, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 1, 4, 4, 6, 2, 10
( چرا که 11-7=4 , 7-5=2, 5-3=2, 3-2=1و ... ).
این رشته از اعداد نامنظم است اما رابطه ای در اعدادی که نشان می دهند وجود دارد و واضح است که رشد اعداد این رشته به طور پیوسته نیست، یعنی اعداد رشته اخیر به سرعت رشد نمی کنند و اعدادی مانند 10 و 4 انتها در آخرین مراحل ظاهر می شود و اعداد ابتدایی این رشته همگی 2 یا کوچکتر از آن هستند.
اگر شما این فرایند را برای نخستین هزار عدد اول ادامه دهید متوجه خواهید شد که با افزایش تعداد اعداد، شکاف هایی که میان اعدادی از یک رده وجود دارد افزایش پیدا می کند و آشکارتر می شود. به عبارت دیگر اعداد اول بزرگتر با فواصل بیشتری در میان اعداد پخش می شوند. البته این مطابق انتظار اولیه ما نیز هست چرا که برای اعداد بزرگتر امکان این که بر اعداد بیشتری تقسیم پذیر باشند، بیشتر خواهد بود. برای مثال عددی مانند 10001 را در نظر بگیرید، در نگاه اول ممکن است این عدد به نظر اول بیاید، چرا که به هیچ یک از اعداد 2 و 3 و 5 و 7 و 11 و 13 و 17 یا 19 تقسیم پذیر نیست اما تصور ما درباره اول بودن آن اشتباه است چرا که به راحتی می توان آن را به شکل تجربه 137×73 نوشت.
هیچ ریاضیدان کاردانی وقت خود را بیشتر از این برای بررسی یا حتی اثبات این موضوع تلف نمی کند که ببیند اعداد اول بزرگتر کمیاب ترند. در حقیقت چیزی که مورد توجه چنین دانشمندی است این نکته است که میزان کمیاب بودن آن ها چگونه است؟ مثلاً اگر شما عددی تصادفی میان 1000001 و 1010000 انتخاب کنید چقدر احتمال دارد که این عدد، عددی اول باشد؟ به عبارت دیگر چگالی اعداد اول در نزدیکی 1000000 آیا کم است یا خیلی کم است؟
دلیلی که چنین سؤالی برای مردم عادی که تحصیلات دانشگاهی در زمینه ریاضیات ندارند پیش نمی آید این است که آنها از زبانی استفاده نمی کنند که بتوانند چنین مسایلی را درون آن ریخته، قالب بندی کرده و درباره آن فکر کنند اما اگر شما مطالب این فصل را به طور کامل بخوانید و آن را متوجه شوید آنگاه در موقعیتی قرار خواهید گرفت که قدردان و سپاسگزار یکی از مهمترین و بزرگترین دستاوردهای دانش ریاضیات قرار بگیرید و این دست آورد بزرگ چیزی نیست جز قضیه اعداد اول، این قضیه بیان می کند که چگالی اعداد اول در اطراف عددی مانند n در حدود خواهد بود.
یک بار دیگر احتمال این که عددی تصادفی میان 1000001 و 1010000، عددی اول باشد را در نظر بگیرید. همه اعداد موجود در این بازه در حدود 1 میلیون عدد هستند. بنابراین طبق قضیه اعداد اول خواهیم داشت که چگالی اعداد اول موجود در حول و حوش این عدد عبارت است از یک تقسیم بر لگاریتم طبیعی یک میلیون، لگاریتم این عدد در مبنای 10، عدد 6 است ( دراین مورد خاص با روش تقریب زنی که گفتیم به حدود 7 می رسیم، اما چون جواب دقیق را می دانیم ترجیح می دهیم از جواب قطعی و دقیق استفاده کنیم ). بنابراین لگاریتم طبیعی آن در حدود 6×2/3، یا 13/8 است. بنابراین با احتمال 1 به 14 عددی که در این بازه انتخاب شده است عددی اول خواهد بود که شانسی معادل اندکی بیش از 7% به حساب می آید.
در مقابل احتمال این که عددی کوچکتر از 100، اول باشد 24 است که تقریباً معادل کل اعداد به شمار می رود. این مقایسه نشان می دهد که چگونه با افزایش اعداد چگالی اعداد اول کاهش پیدا می کند.
ماهیت توزیع تقریباً تصادفی اعداد اول، این موضوع را که می توان قضایایی را در مورد آنها اثبات کرد، تعجب برانگیز می کند. جالب آن که اکثر قضایایی که در این باره به شیوه استخراجی اثبات می شود ظاهراً تصادفی نیستند. برای مثال قضیه ای معروف به نام وینوگرادوف که در سال 1937 ثابت شد، نشان می دهد هر عدد فرد بزرگی را می توان به صورت حاصل جمع 3 عدد اول نوشت. شرح اثبات این قضیه فراتر از سطح بحث ما در این کتاب است، اما او نتوانست روشی برای تولید اعداد فرد مبتنی بر جمع 3 عدد اول ارائه دهد.
چنین رویکردی قطعاً با شکست روبه رو می شد. چرا که ما هنوز روشی برای تولید همه اعداد اول هم در اختیار نداریم.
به جای اثبات مستقیم، بر مبنای کارهایی که هاردی (1) و لیتل وود (2) قبلاً انجام داده بودند، وینوگرادوف استدلال خود را تقریباً به شیوه زیر بیان نمود. اگر یک رشته عددی تصادفی از اعدادی را انتخاب کنید که چگالی آن همانند چگالی اعداد اول باشد آن گاه برخی نظریات بنیادی احتمالات بیان می کند که به احتمال قریب به یقین شما خواهید توانست هر عدد به اندازه کافی بزرگی را به شکل حاصل جمع 3 عدد آن رشته بنویسید. در حقیقت شما این کار را می توانید به روش های گوناگون صورت دهید. از آنجا که اعداد اول ساختاری شبه تصادفی دارند ( یکی از سخت ترین بخش های اثبات این قضیه تفسیر این جمله و بعد اثبات منطقی آن است ) بنابراین رفتار آن همانند رفتار دنباله اولیه است. بنابراین هر عدد به اندازه کافی بزرگی را می توان به شکل حاصل جمع 3 عدد اول نوشت و البته می توان این کار را به روش های مختلف انجام داد. برای این که این پدیده را واضح تر کنیم در زیر تمام روش های ممکن که می توان عدد 35 را به شکل مجموع 3 عدد اول نوشت، بیان شده است.
35=2+2+31=3+3+29=3+13+19=5+7+23=5+11+125+13+17=7+11+17=11+11+13
بسیاری از تحقیقاتی که روی اعداد اول انجام می شوند از این گونه اند. ابتدا مدلی احتمالی برای اعداد اول در نظر می گیرید؛ خود را قانع می کنید که اعداد اول هم بر مبنای شیوه ای کاملاً تصادفی تولید می شوند. سپس با توجه به این موضوع به بررسی آنچه می پردازید که در این شرایط ممکن است درست باشد و این موضوع باعث می شود که شما پاسخ بسیاری از پرسش ها را حدس بزنید. سرانجام، سعی خواهید کرد که نشان دهید که حدس های شما تا حد واقع بینانه ای درست هستند. توجه کنید که برای طی کردن این مراحل، اگر بخواهید خود را مقید به دانستن پاسخ های دقیق در هر مرحله کنید، غیرممکن خواهد شد.
نکته جالب توجه آن است که مدل احتمالاتی، مدلی از یک پدیده فیزیکی نیست، بلکه به بخش دیگری از ریاضیات مربوط است. حتی اگر اعداد اول را بتوان با دقت مشخص و تعیین کرد باز هم آنها حکم اطلاعاتی آزمایشی را دارند. چیزی که ما از آنها می خواهیم پاسخ به پرسش هایی در خصوص رفتارهای مدل های احتمالاتی است و چنین مدل هایی گاه مردم را به اثبات های معتبری برای خود اعداد اول راهنمایی می کنند.
اگرچه چنین شیوه ای موفقیت های چشمگیری به همراه دارد اما بسیاری از مسایل را نیز بدون پاسخ باقی می گذارد. برای مثال حدس گلد باخ (3) ادعا می کند که هر عدد زوج بزرگتر از 4 را می توان به صورت حاصل جمع دو عدد اول فرد نوشت.
بحث درباره چنین حدسی بسیار دشوارتر از بحثی است که وینگادوف مطرح کرده بود.
مورد دیگرم مشابه حدس دوقلوهای اول است که بیان می کند بی نهایت زوج عدد اول با تفاضل 2 مانند 19 و 17 یا 139 و 137 وجود دارند. بیان دیگر این حدس آن است که اگر شما رشته تفاضل های پیاپی اعداد اول را بنویسید، ( مانند آنچه در بالا انجام دادیم ) عدد 2 به طور نامتناهی در این رشته تکرار خواهد شد.
شاید یکی از معروف ترین مسایل باز در ریاضیات فرضیه ریمان باشد. این فرضیه را می توان به چندین صورت متناظر بیان کرد که یکی از آنها بستگی جدی به صحت و دقت تخمینی دارد که از قضیه اعداد اول ناشی می شود. همان طور که گفتم قضیه اعداد اول به شما می گوید که چگالی تقریبی اعداد اول در اطراف هر عدد دلخواهی چه مقدار است. با کمک چنین اطلاعاتی ممکن است بتوان تعداد تقریبی اعداد اولی را تا پیش از n را بیان کرد اما با چه دقتی می توان این کار را کرد؟
اگر p(n) تعداد اعداد اول تا n و q(n) تخمینی از تعداد اعداد اول پیش از n باشد که قضیه اعداد اول بیان می کند آنگاه، فرضیه ریمان بیان می کند که تفاضل p(n) و q(n) بزرگتر از نخواهد بود. اگر چنین فرضیه ای اثبات شود کاربردهای فراوانی از آن استخراج می شود اما تاکنون چنین دستاوردی برای ریاضیات به دست نیامده است.

الگوریتم های مرتب سازی

یکی دیگر از شاخه های ریاضیات که مملو از تخمین ها است نظریه علوم کامپیوتر است. اگر کسی برنامه ای کامپیوتری را برای انجام کار مشخص بنویسد باید آن را به گونه ای طراحی کند که اجرای آن به سریعترین روش ممکن اتفاق بیفتد اما سؤالی که برای یک دانشمند علوم کامپیوتر پیش می آید این است که این سریع ترین روش ممکن تا چه حدی باید سریع باشد؟
البته تقریباً در همه موارد انتظار به جایی نیست که پاسخ دقیق و صریحی از این سؤال را انتظار داشته باشیم. شاید لازم باشد به جای چنین پرسشی، فرد گزاره ای مانند این را اثبات کند که اگر ورودی ما اندازه ای در حد n داشته باشد، الگوریتم طراحی شده طی در مرحله به پاسخ می رسد. بر اساس چنین گزاره ای است که شخص می تواند این نتیجه را بگیرد که یک کامپیوتر شخصی Pc، می تواند داده های ورودی از رده 1000 را با این الگوریتم مورد تحلیل قرار دهد اما توان انجام این عملیات برای مثلاً داده هایی از رده 1000000 را ندارد.
بنابراین چنین تخمینی دارای ارزش عملیاتی بسیار بالایی است.
یکی از عملکردهای رایج و کارآمدی که از کامپیوترها انتظار داریم. عملیات مرتب سازی است. منظور از مرتب سازی این است که تعداد زیادی از اشیا را بر مبنای ضابطه مشخص مرتب کنیم.
برای روشن شدن موضوع تصور کنید می خواهید مجموعه ای از اشیاء ( که الزاماً شیء هم نیستند و مثلاً می توانند نامزدهای کسب یک شغل باشند ) را بر مبنای اولویت آنها مرتب کنید. فرض کنید که شما نمی توانید ارزش عددی به هر یک از اشیاء خود دهید تا بر اساس آن عملیات مرتب سازی خود را انجام دهید اما در عوض می توانید در بین دو شی از آن مجموعه تصمیم بگیرید که کدام یک اولویت دارند. و در نظر بگیرید که هیچ گاه حالتی پیش نمی آید که A نسبت به B, B نسبت به C و C نسبت به A همزمان برتری داشته باشد. حال مسأله شما این است که در حداقل مراحل و گام های ممکن این مرتب سازی را انجام دهید. زمانی که تعداد اشیاء خیلی کم باشند انجام دادن این کار چندان دشوار نیست. برای مثال اگر با دو شی مواجه باشید تنها یک مقایسه کافی است و یک بار که این کار را انجام دهید به نتیجه مورد نظر می رسید. اگر 3 شی C,B,A مقابل شما باشند، دیگر یک مقایسه کافی نیست و باید از یک مقایسه که مهم نیست میان کدام اشیاء هم باشد کار را شروع کنید. فرض کنید مطابق قانون و شرایطی که در نظر دارید مقایسه ای میان A,B انجام می دهید و A را برمی گزینید. حال باید مقایسه خود را میان A,B با C انجام دهید. اگر A را با C مقایسه کردید و C را بر A ترجیح داید، آنگاه نتیجه ناگهانی کار شما مشخص خواهد شد و ترتیب B,A,C را به دست خواهید آورد، اما ممکن است متوجه شوید که A بر C ارجحیت دارد. در این صورت شما می دانید که A نسبت به هر دو گزینه B,C دارای ارجحیت است. در این صورت انجام مقایسه سوم میان B و C نیز ضروری می شود. بنابراین انجام 3 مقایسه همواره کافی و در مواردی ضروری است. حال اگر قرار باشد این کار را میان D,C,B,A انجام دهید چه اتفاقی می افتد؟ در این صورت تحلیل شما پیچیده تر خواهد شد. ممکن است شما مقایسه خود را میان A و B آغاز کنید اما به محض اینکه این کار را به اتمام رساندید. شما با دو احتمال یکسان برای قدم بعدی مواجه هستید. می توانید A یا B را با C مقایسه کنید یا به مقایسه C با D بپردازید. مشخص نیست که کدام یک از این انتخاب ها گزینه بهتری است. فرض کنید B را با C مقایسه کنید. اگر خوش شانس باشید خواهید توانست ترتیبی میان A و B و C به دست آورید. تصور کنید مرتب شده این 3 شی به شکل A , B, C باشد. حال باید مشخص کنید جایگاه D در این میان کجا است. بهترین انتخاب در این شرایط مقایسه D با B است. بعد از این کار، تنها مرحله ای که باقی می ماند این است که اگر D را بر B ارجح دانستید، D را با A و اگر B را بر D ترجیح دادید، D را با C مقایسه کنید. بنابراین تا این مرحله 4 مقایسه صورت گرفته است اما هنوز تحلیل این مسأله به پایان نرسیده است. شاید پس از 2 مقایسه اول تنها به این نتیجه برسید که A و C به B ارجح است، در این صورت با مسأله غامضی مواجه خواهید شد: آیا بهتر است که A را با C یا B مقایسه کنید یا اول D را با یکی از B,A یا C مقایسه کنید.
و اگر راه دوم را انتخاب می کنید آیا باید D با B مقایسه شود با یکی از A یا C؟ و بعد از این که بررسی این موارد و زیرشاخه های آن را تمام کردید هنوز باید بررسی کنید که اگر دومین مقایسه شما بین D,C می بود چه اتفاقی می افتاد؟
اگرچه چنین تحلیلی خسته کننده است اما انجام آن امکان پذیر است. نتیجه نهایی نشان می هد که همیشه 5 مقایسه کافی خواهد بود که گاهی باید هر 5 مرحله را انجام دهید و همیشه دومین مقایسه باید بین C و D صورت گیرد.
یکی از مشکلات چنین استدلالی آن است که تعداد مراحلی که شخص باید آنها را بررسی کند به سرعت افزایش می یابد. لازم نیست بگوییم که مثلاً اگر قرار باشد میان 100 شی این تحلیل را انجام دهیم چه تعداد حالت مختلف ممکن است پیش آید و فکر می کنم هیچ کس هیچ گاه پاسخ این سؤال را نخواهد دانست ( من به خوبی به خاطر می آورم که اولین باری که یک ریاضیدان گفت هیچ گاه معلوم نمی شود که دقیقاً چه تعداد از مراحل برای انجام این کار لازم است چقدر شوکه شدم ). اما اکنون به خوبی درک می کنم که این مسأله، اتفاق عادی در ریاضیات به شمار می رود و نه یک استثناء کمیتی که در آن سؤال مطرح بود عدد رمزی (4) R(5,5) بود کوچکترین عددی مانند n به طوری که در جمعیتی با n نفر عضو 5 نفر پیدا شوند که همگان را بشناسند و یا 5 نفر باشند که هیچ کس آنها را نشناسد ).
در عوض به جای اینکه در مسأله ای مانند مسأله بالا عدد دقیق را مشخص کنیم می توانیم کرانه های بالا و پایین پاسخ را تعیین کنیم. در این مسأله، کران بالای به این معنی است که مرتب کننده ها که درحال مرتب کردن n شی است هیچ گاه بیش از مقایسه را انجام ندهد و یک کران پایین مانند به این معنی است که ثابت کنیم فارغ از این که چقدر شما باهوش یا خوش شانس هستید، حداقل مقایسه برای رسیدن به نتیجه لازم است.
مثال فوق، نمونه بارزی از مسایلی است که کرانه های بالا و پایین آن بر مبنای ضرب اعضا مجموعه مشخص می شد. معلوم شده است که تعداد مقایسه های لازم برای مرتب کردن n شی nlogn است.
راهی برای این که جذابیت این قضیه را درک کنید این است که سعی کنید که شیوه ای برای مرتب سازی را خودتان بسازید. یک روش بدیهی این است که کار خود را با پیدا کردن شی که بالاتر می آید آغاز کنید. آن را به کناری بگذارید و سپس این مراحل را با بقیه تکرار کنید. برای پیدا کردن اولین شی باید اول، دو شی نخست را مقایسه کنید، سپس برنده را با شی سوم و همین طور تا آخر انجام این مراحل n-1 مقایسه را برای پیدا کردن بهترین اولویت نیاز دارند، سپس n-2 مقایسه برای یافتن شی دوم، و الی آخر. در کل ( n-1 )+( n-2 )+…+1 مقایسه در کل لازم خواهد بود که در نتیجه نیاز به مقایسه دارید.
ویژگی این روش آن است که در طی این مراحل شما همه زوج های ممکن را با هم مقایسه کرده اید و بالطبع این ایده آل ترین حالت ممکن نخواهد بود. اگر n خیلی بزرگ باشد مشاهده می کنیم که مقدار nlogn مرحله پیشرفت قابل ملاحظه ای نسبت به است، چرا که logn به مراتب کوچکتر از است.
روش زیر که به مرتب کردن سریع (5) مشهور است اگرچه تضمین نمی کند که کار شما زودتر به پایان برسد اما در اکثر اوقات سریع تر عمل می کند. این روش به شکل بازگشتی به شکل زیر تعریف می شود. ابتدا یکی از اشیاء مانند x را انتخاب کنید و بقیه را در دو ستون قرار دهید؛ یکی آنهایی که ارجحیت دارند و دیگری آنهایی که فاقد ارجحیتند. این کار نیازمند n-1 مقایسه است. تمام آنچه اکنون باید انجام دهید آن است که هر یک از دو ستون را با همین روش مرتب سازی سریع مرتب کنید. یعنی از هر ستون یک عضو را انتخاب و بقیه اعضاء را به دو ستون دیگر تقسیم کنید و همین مراحل را تکرار کنید. معمولاً و غیر از مواردی که بدشانسی بیاورید، زمانی که مقایسه اول خود را تمام می کنید طول دو ستون تقریباً برابر است و می توان نشان داد که تعداد مقایسه هایی که در این حالت باید انجام دهید در حد nlogn است. و این بدان معنی است که این روش به همان خوبی که از یک تقریب فزاینده انتظار دارید خوب عمل می کند.

پي‌نوشت‌ها:

1. Hardy
2. Little wood
3. Goldbach Conjectury
4. Ramsey
5. Quick sort

منبع مقاله :
گاورز، تیموتی؛ ( 1391 )، ریاضیات، پوریا ناظمی، تهران: بصيرت، چاپ دوم