payamvha/North_RAG huggingface dataset:
مختلفی وجود داشته باشند. این الگوریتم به صورت بهینه نوع خاصی از مرتب‌سازی که به طول run بستگی دارد (به‌طور مثال اگر اندازهٔ آن از مقدار خاصی کمتر باشد از مرتب‌سازی درجی استفاده می‌کند) بنابراین این مرنب‌سازی انطباقی نامیده می‌شود. اندازهٔ run با اندازهٔ کوچکترین run مقایسه می‌شود. اندازهٔ کوچکترین run که «minrun» نامیده می‌شود که به اندازهٔ آرایه بستگی دارد. برای آرایه‌هایی که اندازهٔ آن از ۶۴ کمتر باشد، اندازهٔ minrun به اندازهٔ خود آرایه می‌باشد و اساساً به مرتب‌سازی درجی تبدیل می‌گردد. برای آرایه‌های
به مرتب‌سازی درجی تبدیل می‌گردد. برای آرایه‌های بزرگتر اندازهٔ minrun بین بازهٔ ۳۲ تا ۶۵ انتخاب می‌شود. الگوریتم نهایی برای انتخاب minrun، شش بیت قابل توجه اندازهٔ آرایه را در نظر می‌گیرد. اگر هر کدام از بیت‌های باقی‌مانده یک بودند، یک اضافه می‌کند و از آن به‌عنوان minrun استفاده می‌کند. این روش برای همهٔ آرایه‌هایی که سایز آن‌ها از ۶۴ کمتر است و شامل یک هستند، درست عمل می‌کند. مرتب‌سازی درجی. هنگامی که یک آرایه به صورت رندم باشد، با احتمال زیادی یک run طبیعی تعداد عناصر کمتری از minrun دارد. در این موارد
تعداد عناصر کمتری از minrun دارد. در این موارد تعداد مناسبی از عناصر در نظر گرفته می‌شوند و از مرتب‌سازی درجی برای مرتب کردن آن‌ها استفاده می‌شود. سپس اندازهٔ آن افزایش می‌یابد تا به اندازهٔ minrun بشود. مرتب‌سازی ادغامی. عملیات ادغام معمولاً روی دو run پیاپی انجام می‌شود. برای این کار سه run بالای پشته را که مرتب نشده‌اند را در نظر می‌گیرد. اگر طول این سه run را x، y، z در نظر بگیریم، الگوریتم طوری آن‌ها را ادغام می‌کند که دو شرط زیر برقرار شود. این دو قانون باعث می‌شود که طول runها نزدیک به هم نگه داشته
باعث می‌شود که طول runها نزدیک به هم نگه داشته شوند و بازدهی الگوریتم بالاتر باشد. رویهٔ ادغام‌کردن. ادغام کردن دو run همسایه به کمک یک حافظهٔ کمکی انجام می‌شود. اندازهٔ این حافظه به اندازهٔ run کوچکتر می‌باشد. الگوریتم آرایهٔ کوچکتر را در حافظه کپی می‌کند و سپس برای ذخیرهٔ run نهایی از حافظهٔ اصلی و حافظهٔ run بزرگتر استفاده می‌کند. کارایی الگوریتم. طبق نظریه اطلاعات هیچ الگوریتم مرتب‌سازی مقایسه‌ای نمی‌تواند کارایی بهتر از formula_1 در حالت میانگین داشته باشد. در داده‌های واقعی الگوریتم تیم معمولاً با
باشد. در داده‌های واقعی الگوریتم تیم معمولاً با تعداد مقایسه‌های کمتر از formula_1 مرتب‌سازی را انجام می‌دهد زیرا از این مزیت که زیر مجموعه‌ای از داده‌ها مرتب هستند. در مواردی که هیچ زیر مجموعه‌ای از داده‌ها مرتب‌شده نیستند الگوریتم نمی‌تواند از این مزیت استفاده کند و با کارایی formula_1 کار می‌کند. در جدول زیر کارایی الگوریتم با دیگر الگوریتم‌های مقایسه‌ای مقایسه شده‌است. در جدول زیر انواع مختلف الگوریتم‌ها بر اساس پیچیدگی مقایسه شده‌اند.
حبابچه‌دارن (همراه با حفره) (Alveolate) فرمانرو بزرگی از جانداران هستند که در گذشته در دسته آغازیان طبقه بندی می‌شدند. اما اکنون که مشخص شده است آغازیان دارای منشاء مشترکی نبودند، حبابچه‌داران خود فرمانرویی جداگانه شمرده می‌شوند. این گروه پنج شاخه دارد: منابع. Wikipedia contributors, "Alveolate," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/w/index.php?title=Alveolate&amp;oldid=679155201 (accessed September 6, 2015).
در نظریه گراف، شاخه‌ای از ریاضیات، الگوریتم ادمون برای پیدا کردن انشعاب بهینهٔ بیشینه یا کمینه به کار می‌رود. زمانی که راس‌ها با یال‌های وزن دار و جهت دار به یکدیگر متصل شده باشند، دیگر نمی‌توانیم از الگوریتم درخت پوشای کمینه استفاده کنیم. بنابراین از الگوریتم انشعاب بهینه استفاده می‌کنیم که در سال ۱۹۶۷ توسط ادمون ارائه شد. برای یافتن مسیر با طول بیشینه، ابتدا یال‌ها بر اساس وزن شان مرتب می‌شوند. از بزرگترین یال شروع کرده و آن یال بین دو راس قرار می‌گیرد. بعد از آن به سراغ یال بزرگتر بعدی رفته و همین کار
بعد از آن به سراغ یال بزرگتر بعدی رفته و همین کار برای باقی یال‌ها نیز انجام می‌شود. اگر یالی باعث ایجاد دور در گراف شود، آن یال حذف می‌شود. برای پیدا کردن مسیر با طول کمینه نیز، یال‌ها از کوچک به بزرگ مرتب می‌شوند و کار با یال کوچکتر شروع می‌شود. زمان اجرا. زمان اجرای این الگوریتم برابر با formula_1 است. پیاده‌سازی سریعتری از این الگوریتم، توسط روبرت تارجان ارائه شد که زمان اجرای آن برای یک گراف نا متراکم formula_2 و برای گراف متراکم برابر با formula_3 است. زمان اجرای آن به تندی الگوریتم پریم، برای یافتن
زمان اجرای آن به تندی الگوریتم پریم، برای یافتن درخت پوشای کمینهٔ بدون جهت است. بعدها در سال ۱۹۸۶، گابو، گلیل، اسپنسر، و تارجان پیاده‌سازی سریعتری را ارائه کردند که زمان اجرای آن برابر است با formula_4. الگوریتم. تابعی مانند formula_5 را در نظر می‌گیریم که به عنوان ورودی، یک گراف وزن دار و جهت دار formula_6 و یک راس formula_7 به عنوان ریشه می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با ریشهٔ formula_7، به ما می‌دهد. توصیف دقیق الگوریتم در ادامه آمده‌است. با گرفتن یک گراف وزن دار و جهت دار مانند
با گرفتن یک گراف وزن دار و جهت دار مانند formula_6، با ریشهٔ formula_7، به این صورت عمل می‌کنیم که در ابتدا، مجموعهٔ یال‌های موازی(یال‌هایی که بین دو راس یکسان قرار دارند و دارای یک جهت می‌باشند) را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال‌های موازی است، جایگزین می‌کنیم. توصیف. این الگوریتم یک توصیف شهودی بازگشتی دارد. تابعی مانند formula_5 را در نظر می‌گیریم. این تابع به عنوان ورودی، گراف وزن دار و جهت دار formula_6، با یک راس formula_7 به عنوان "ریشه" را می‌گیرد و به عنوان خروجی، یک درخت
عنوان "ریشه" را می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با کمترین هزینه، می‌دهد. توصیف دقیق الگوریتم در ادامه آمده‌است. با گرفتن یک گراف وزن دار و جهت دار formula_6 با ریشهٔ formula_7، در ابتدا به این صورت عمل می‌کنیم که مجموعه‌ای از یال‌های موازی (یال‌های بین دو راس یکسان که دارای یک جهت هستند)را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال‌های موازی است، جایگزین می‌کنیم. حالا برای هر راس formula_16 به جز ریشه، یال ورودی به آن راس که دارای کمترین هزینه‌است را علامت(به‌طور قراردادی)
دارای کمترین هزینه‌است را علامت(به‌طور قراردادی) می‌زنیم. راسی که در سر دیگر این یال قرار دارد را با formula_17 مشخص می‌کنیم. اگر یال‌های علامت زده شده، تشکیل یک SRT(درخت فراگیر ریشه دار) را می‌دادند، یعنی تابع formula_18 این SRT را مشخص کرده‌است. در غیر این صورت، مجموعه یال‌های علامت زده شده، تشکیل حداقل یک دور را می‌دهند. یکی از دورها را (به صورت دلخواه) formula_19 بنامید. حالا ما یک گراف وزن دار و جهت دار formula_20 که دارای ریشه formula_21 است را تعریف می‌کنیم. به این صورت که، راس‌های formula_20 مانند
می‌کنیم. به این صورت که، راس‌های formula_20 مانند راس‌های formula_6 هستند نه formula_19، به اضافه یک راس "جدید" که با formula_25 مشخص می‌شود. اگر formula_26 یالی در formula_6 باشد، با این شرط که formula_28، یال formula_29 را به صورت شرح داده شده در زیر به formula_20 اضافه می‌کنیم. اگر formula_31، formula_32 و formula_33 در غیر این صورت، اگر formula_34، formula_35 و and formula_36. ما هیچ یال دیگری را به formula_20 اضافه نمی‌کنیم. ریشهٔ formula_21 در formula_20، همان ریشهٔ formula_7 در formula_6. است. با
همان ریشهٔ formula_7 در formula_6. است. با صدا کردن تابع formula_42، یک SRT در formula_20 می‌یابیم. در نظر داشته باشید که در این SRT، یال ورودی (یکتا) به formula_25، یال formula_45 است. این یال می‌تواند از زوج مرتب‌هایی مانند formula_26 با شرط formula_28 و formula_31 باشد. علامت formula_49 را بردارید و formula_26 را علامت بزنید. حالا مجموعه یال‌های علامت زده شده، یک SRT می‌سازند که ما می‌توانیم آن را مقدار تابع formula_18 در نظر بگیریم. دقت کنید که تابع formula_18 به وسیله تابع formula_42 تعریف شده‌است. و
به وسیله تابع formula_42 تعریف شده‌است. و تابع formula_20 که یک گراف وزن دار، جهت دار و ریشه دار است، نسبت به گراف formula_6 به شدت تعداد راس‌هایش کمتر است و استفاده از formula_18 برای یک گراف تک راس، کاری بیهوده‌است. پیاده سازی. BV را یک مجموعه‌ای برای رئوس و BE را مجموعه‌ای برای یال‌ها در نظر بگیرید. اگر "V" را یک راس در نظر بگیرید و "e" هم یالی با بیشترین وزن مثبت و متصل به "V" باشد، Ci یک دور خواهد بود. G۰ = (V۰,E۰) گراف اصلی است و "ui" یک راس جانشین برای Ci است. codice_1
در هندسۀ محاسباتی، الگوریتم چان که به افتخار Timothy M. Chan و پس از او نامگذاری شد، الگوریتمی بهینه و حساس به خروجی است که پوش محدب در مجموعه ای از n نقطه که در فضای دو یا سه بعدی قرار دارند را محاسبه می‌کند. این الگوریتم از مرتبهٔ (O(n log h زمان می‌گیرد که در آن h، تعداد راس‌های خروجی (پوش محدب) است. در حالت مسطح، این الگوریتم، الگوریتمی از مرتبۀ پیچیدگی (O(n log n (مانند جستجوی گراهام) را با الگوریتم بسته‌بندی هدیه هدیه ترکیب می‌کند تا در زمان بهینۀ اجرا شود.این الگوریتم از آن جهت که بسیار ساده‌تر از
شود.این الگوریتم از آن جهت که بسیار ساده‌تر از الگوریتم نهایی پوش محدب برای سطح است و به‌طور طبیعی هم قابلیت تعمیم به فضای 3 بعدی را دارد، مورد توجه قرار گرفته‌است. الگوریتم. در ابتدا فرض می کنیم که عدد h را داریم و بنابراین پارامتر m را برابر h تعریف می کنیم. این فرض شاید به نظر واقعی نرسد، اما بعداً این فرض را از الگوریتم حذف خواهیم کرد.این الگوریتم در ابتدا با تقسیم دلخواه مجموعۀ نقاط(P) به حداکثر 1+n/m زیر مجموعه که در هر یک از آن‌ها حداکثر m نقطه وجود دارد، شروع می‌شود. سپس با استفاده از الگوریتم پوش
دارد، شروع می‌شود. سپس با استفاده از الگوریتم پوش محدب، می‌توان در هر یک از این زیر مجموعه‌ها با زمان (O(n log n، پوش محدب را محاسبه کرد.توجه کنید که از آنجا که (O(n/m زیر مجموعه که هر یک شامل(O(m نقطه است وجود دارد، این مرحله حداکثر (O(n/m)O(m log m) = O(n log m زمان می‌گیرد. در مرحلۀ دوم از مسئلۀ بسته‌بندی کادو استفاده می‌شود. همچنین برای افزایش سرعت اجرا، در این مرحله از مقادیر از پیش محاسبه شدۀ پوش‌های محدب استفاده می‌شود. در هر گام از اجرای الگوریتم بسته بندی، نقطه‌ای مانند "pi" در پوش محدب فرض می‌شود
بندی، نقطه‌ای مانند "pi" در پوش محدب فرض می‌شود و الگوریتم به دنبال این است که نقطه ای مانند (pi+1 = "f(pi,P" پیدا کند با این ویژگی که بقیۀ نقاط در P، در سمت راست خط گذرنده از "pi" و"pi+1" قرار گیرند. اگر پوش محدب را برای m نقطه که در مجموعۀ Q قرار دارند مشخص باشد، می‌توان "(f(pi,Q" را با استفاده از جستجوی دودویی، در زمان (O(log m محاسبه کرد.همچنین می‌توان (f(pi,Q را برای هر یک از (O(n/m زیر مجموعۀ P حساب کرد. این کار از مرتبۀ زمانی (O(n/m log m طول می کشد. سپس با استفاده از همین تکنیک، "(f(pi,P"' محاسبه
سپس با استفاده از همین تکنیک، "(f(pi,P"' محاسبه می‌شود. اما این کار فقط نقاطی را در نطر می گیرد که زیر مجموعه‌ای مانند Qاز P وجود داشته باشد که برای آن نقطه "(f(pi,Q" را حساب کرده باشد. همان گونه که الگوریتم بسته بندی هدیه این فرایند را (O(h بار تکرار می‌کند، مرحلۀ دوم این الگوریتم هم به اندازۀ (O(n log m زمان می برد و چنانچه m=h باشد، (O(n log h زمان می برد. با اجرای دو مرحلۀ اول الگوریتم مطابق آنچه در بالا توصیف شد، می توان پوش محدب را برای n نقطه، با این فرض که مقدار h از قبل مشخص است، در زمان (O(n logh
فرض که مقدار h از قبل مشخص است، در زمان (O(n logh محاسبه کرد. با فرض اینکه m&lt;h باشد، آنگاه می توان اجرای الگوریتم را پس از m+1 گام متوقف کرد. بنابراین اجرای آن تنها به اندازۀ (O(nlog m، البته بدون محاسبۀ پوش محدب، زمان می گیرد. می توانیم در ابتدا، m را ثابت کوچکی در نطر بگیریم و سپس مقدار آنرا افزایش دهیم تا زمانی که m&gt;h شود.در این حالت، پوش محدب به عنوان خروجی بدست می آید.ثابت اولیۀ m را نیز در فرض های خود 2 در نظر می گیریم اما در عمل عددی حدود 5 بهتر عمل می کند. اگر مقدار m خیلی آرام افزایش یابد،
عمل می کند. اگر مقدار m خیلی آرام افزایش یابد، ممکن است الگوریتم مراحل بالا را دفعات زیادی تکرار کند و این باعث می‌شود زمان اجرا بسیار زیاد شود. از طرف دیگر، اگر مقدار m به سرعت افزایش یابد، ممکن است m ناگهان از h خیلی بیشتر شود و این امر خود باعث افزایش زمان اجرا می شود. الگوریتم چان، مقدار m را در هر تکرار مربع می کند و هر بار اطمینان حاصل می کند که مقدار m هیچگاه از n بیشتر نشود.به عبارت دیگر در تکرار tام(که t از صفر شروع می شود)، formula_1. زمان اجرای کل الگوریتم برابر است با: formula_2 برای تعمیم این
الگوریتم برابر است با: formula_2 برای تعمیم این روش به فضای 3 بعدی، باید به جای الگوریتم جستجوی گراهام، از الگوریتم با زمان اجرای (O(n log n برای محاسبۀ پوش محدب در فضای 3 بعدی استفاده شود. همچنین به جای الگوریتم مارش برای بسته بندی هدیه، باید از نسخۀ 3بعدی آن استفاده کنیم. با این تغییرات، پیچیدگی اجرای الگوریتم همچنان (O(n log h باقی می ماند. پیاده سازی. در مقالۀ چان، روش‌های پیشنهادی زیادی برای بهبود عملی کارایی الگوریتمش آمده است که بعضی از آنها عبارتند از:
واکنش اشمیت-کولب که در شیمی آلی مورد بحث قرار می‌گیرد عبارت است از یک واکنش شیمیایی که طی آن نمک یک فنول با کربن دی اکسید واکنش داده و گروه کربوکسیل جانشین هیدروژن می‌شود. این فرایند معمولاً در فشار ۱۰۰ اتمسفر و دمای ۱۲۵ درجه سانتی گراد انجام می‌پذیرد و حاصل این واکنش پس از قرار گرفتن در معرض سولفوریک اسید یک هیدروکسی اسید آروماتیک خواهد بود. مهمترین کاربرد این واکنش تبدیل فنول به سالیسیلیک اسید است.
Trivial File Transfer Protocol) TFTP) یک پروتکل انتقال فایل است که به دلیل سادگی در به‌کارگیری، پرکاربرد شده است. این پروتکل به کاربران دسترسی برای قرار دادن یا دریافت فایل از ریموت هاست را می‌دهد. از عمده‌ترین کاربرد آن می‌توان به انتقال خودکار فایل‌های مربوط به تنظیمات یک دستگاه یا فایل‌های مورد نیاز یک دستگاه برای بوت شدن در یک شبکه محلی اشاره کرد. این پروتکل اولین بار در سال ۱۹۸۱ استانداردسازی شد که مشخصات فعلی این پروتکل را می‌توان در RFC 1350 یافت. بررسی اجمالی. تی‌اف‌تی‌پی دارای طراحی ساده‌ای است که
اجمالی. تی‌اف‌تی‌پی دارای طراحی ساده‌ای است که به‌کارگیری آن را آسان کرده است. این پروتکل برای انتقال اطلاعات در مراحل اولیه بوت کردن از طریق شبکه مانند BOOTP ,PXE ,PSDP و… استفاده می‌شود. در واقع تی‌اف‌تی‌پی یکی از عناصر PXE یا پروتکل بوت شدن دستگاه‌ها از محیط شبکه است که در واقع درون بایوس کارت شبکه رایانه‌های میزبان، الگوریتمی برای استفاده از آن پیش‌بینی و نهادینه شده است. از تی‌اف‌تی‌پی برای انتقال دیسک ایمیج‌های سیستم عامل‌ها و پرونده‌های پیکربندی به روتر، آی‌پی‌های تلفن و فایروال‌ها نیز استفاده
به روتر، آی‌پی‌های تلفن و فایروال‌ها نیز استفاده می‌شود. طراحی این پروتکل از پروتکل ای‌اف‌تی‌پی که بخشی از مجموعه پروتکل‌های PUP است تأثیر گرفته است. امروزه به‌دلیل امنیت پایین این پروتکل از آن در انتقالات فایل در اینترنت استفاده نمی‌شود و تقریباً تنها استفاده آن در شبکه محلی (LAN) می‌باشد. تی‌اف‌تی‌پی اولین بار در سال ۱۹۸۱ توسط IEN 133 تعریف شد. پس از آن در سال بعد در ماه ژوئن تجدیدنظر دوم این پروتکل به عنوان RFC 783 منتشر شد. بعد از آن آپدیت‌های مختلفی برای این پروتکل ارائه شد که آپدیت‌های کلی آن به
برای این پروتکل ارائه شد که آپدیت‌های کلی آن به ترتیب عبارتند از: پروتکل تی‌اف‌تی‌پی که یکی از ساده‌ترین پروتکل‌های انتقال است با استفاده از پروتکل UDP از پورت شمارهٔ ۶۹ استفاده می‌کند. کار با این پروتکل بسیار آسان است و از بسیاری از تنظیمات و امکانات پیشرفته‌ای که بسیاری از پروتکل‌های انتقال داده پیشنهاد می‌کنند مستثنا است. این پروتکل تنها برای خواندن و نوشتن اطلاعات به ریموت سرور یا از ریموت سرور طراحی شده است و نمی‌تواند اطلاعات را تغییر نام دهد، حذف یا لیست کند. تفاوت تی‌اف‌تی‌پی و اف‌تی‌پی. در مقایسه
لیست کند. تفاوت تی‌اف‌تی‌پی و اف‌تی‌پی. در مقایسه با پروتکل انتقال داده تی‌اف‌تی‌پی، اف‌تی‌پی بسیار ساده‌تر عمل می‌کند. به‌عنوان مثال در تی‌اف‌تی‌پی خبری از احراز هویت استفاده‌کننده نیست و هر کسی که دسترسی شبکه به آن داشته باشد می‌تواند از آن استفاده کند درحالی‌که برای استفاده از اف‌تی‌پی احراز هویت اهمیت بالایی دارد. البته این موضوع امنیت تی‌اف‌تی‌پی را کاهش می‌دهد. تی‌اف‌تی‌پی در مقایسه با اف‌تی‌پی از سرعت بالاتری نیز برخوردار است. دلیل این موضوع این است که اف‌تی‌پی در هنگام انتقال اطلاعات نیاز به تصدیق
که اف‌تی‌پی در هنگام انتقال اطلاعات نیاز به تصدیق کردن بسته فرستاده‌شده(Packet) دارد ولی تی‌اف‌تی‌پی منتظر تصدیق بسته فرستاده‌شده نمی‌ماند و فایل بعدی را ارسال می‌کند. در نتیجه سرعت آن بسیار بالاتر از اف‌تی‌پی است و می‌تواند فایل‌های با حجم بالایی را انتقال دهد. میزبان‌های تی‌اف‌تی‌پی. سایت‌های زیر نمونه‌هایی از تی‌اف‌تی‌پی سرور هستند:
مرتب‌سازی ادغامی دسته‌ای فرد–زوج معرفی. مرتب‌سازی ادغامی دسته‌ای فرد–زوج یک ساز و کار عمومی برای مرتب‌سازی شبکه‌هاست. این روش توسط کِن بچر ابداع شده است. اگر تعداد عناصری که می خواهیم مرتب کنیم n باشد اندازه (تعداد مقایسه کننده‌های استفاده شده) این الگوریتم nlog۲n و عمق (حداکثر تعداد مقایسه کننده‌هایی که در مسیر یک ورودی به خروجی قرار دارند) آن log۲n است. هرچند که مقایسه خوبی نیست اما دانلد_کنوت در سال ۱۹۹۸ به این نتیجه رسید که روش دسته‌ای نسبت به روش شبکه AKS بهتر است مگر اینکه n بیش از کل ظرفیت حافظه
AKS بهتر است مگر اینکه n بیش از کل ظرفیت حافظه رایانه‌های روی زمین باشد. این الگوریتم به عنوان یکی از ساده‌ترین راه‌ها برای انجام مرتب‌سازی‌های منطقی بهینه بر روی انواع سخت‌افزارهای پردازش گرافیکی انجام پذیر است. نمونه کد. یک نمونه پیاده‌سازی از این الگوریتم به زبان پایتون در زیر آمده است. ورودی آن یک لیست x به طول توانی از ۲ است. def compare_and_swap(x، a، b): if x[a]&gt; x[b]: x[a], x[b] = x[b], x[a] def oddeven_merge(x، lo، hi، r): step = r * 2 if step &lt;hi - lo: oddeven_merge(x, lo, hi, step)
step &lt;hi - lo: oddeven_merge(x, lo, hi, step) oddeven_merge(x, lo + r, hi, step) for i in range(lo + r, hi - r, step): compare_and_swap(x, i, i + r) else: compare_and_swap(x, lo, lo + r) def oddeven_merge_sort_range(x، lo، hi): """ sort the part of x with indices between lo and hi. Note: endpoints (lo and hi) are included. if (hi - lo)&gt;= 1: # if there is more than one element, split the input # down the middle and first sort the first and second # half, followed by merging them. mid = lo + ((hi - lo)
followed by merging them. mid = lo + ((hi - lo) / 2) oddeven_merge_sort_range(x, lo, mid) oddeven_merge_sort_range(x, mid + 1, hi) oddeven_merge(x, lo, hi, 1) def oddeven_merge_sort(x): oddeven_merge_sort_range(x, 0, len(x)-1) »&gt; data = [۴، ۳، ۵، ۶، ۱، ۷، ۸] »&gt; oddeven_merge_sort(data) »&gt; data [۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸]
قضیه پنج رنگ نتیجه‌ای است از نظریه گراف که صفحه‌ای به چند منطقه تقسیم شده داده می‌شود. مناطق به گونه‌ای به پنج رنگ مختلف رنگ آمیزی می‌شوند که هیچ دو منطقه مجاوری رنگ یکسان نداشته باشند. قضیه پنج رنگ از قضیه چهار رنگ می‌رسد اما به طور قابل توجهی اثباتش از آن ساده‌تر است. اثبات این قضیه بر مبنای تلاش شکست خورده‌ای برای اثبات قضیه چهار رنگ توسط آلفرد کمپ در سال ۱۸۷۹ می‌باشد. یازده سال بعد پرسی جان هیوود یک خطا از آن پیدا کرد و بر مبنای کار کمپ قضیه پنج رنگ را اثبات نمود. نمای کلی اثبات توسط تناقض. در ابتدا یک
نمود. نمای کلی اثبات توسط تناقض. در ابتدا یک گراف مسطح G را به نقشه داده شده نسبت می‌دهیم به این صورت که هر منطقه را متناظر با یک رأس در نظر می‌گیریم و بین دو رأس یال وجود دارد اگر و تنها اگر بین دو منطقه متناظر مرز مشترکی باشد؛ بنابراین حالا مسئله به مسئله رنگ آمیزی گراف تبدیل شده است: رنگ کردن رئوس گراف به طوری که هیچ یالی دو سر همرنگ نداشته باشد. اثبات بر مشخصه اویلر استوار است تا نشان دهد حتماً باید یک رأس V وجود داشته باشد که بین حداکثر پنج یال مشترک است و با توجه به این که G مسطح است مثلاً می‌تواند
است و با توجه به این که G مسطح است مثلاً می‌تواند در یک صفحه بدون یال‌های متقاطع تعبیه شود. حال V را از G حذف می‌کنیم. گراف از این کار حاصل می‌شود که یک رأس کمتر از G دارد. پس ما می‌توانیم با استقرا فرض کنیم که این را می‌توان با پنج رنگ، رنگ آمیزی کرد. V حتماً باید به پنج رأس دیگر متصل شود؛ چون در غیر این صورت می‌تواند در گراف G با رنگی که در آن‌ها استفاده نشده است، رنگ آمیزی شود. پس حالا به پنج رأس formula_1، formula_2، formula_3، formula_4، formula_5 نگاه می‌کنیم که در ترتیب دایره‌ای مجاور V هستند (که
می‌کنیم که در ترتیب دایره‌ای مجاور V هستند (که بستگی به این دارد که چگونه G را نوشته‌ایم). اگر ما همه پنج رنگ را استفاده نکرده باشیم، مسلماً می‌توانیم رأس V را به رنگی متفاوت از آن‌ها رنگ آمیزی کنیم و گرافی پنج رنگ را تحویل دهیم. پس ما می‌توانیم فرض کنیم که رئوس به ترتیب رنگ‌های ۱ تا ۵ را گرفته‌اند. حال زیر گراف formula_6 از formula_7 را در نظر می‌گیریم که تنها از رئوسی تشکیل شده که رنگ‌های ۱ و ۳ را دارند و یال‌هایی که دو تا از این رئوس را به هم متصل می‌کند. اگر formula_1 و formula_3 در مؤلفه‌های همبندی
اگر formula_1 و formula_3 در مؤلفه‌های همبندی متفاوتی از formula_6 باشند، می‌توانیم رنگ آمیزی مؤلفه همبندی شامل formula_1 را معکوس کنیم که بنابراین رأس V رنگ ۱ را می‌گیرد و کار تمام است. اما اگر formula_1 و formula_3 در مؤلفه‌های همبندی یکسانی از formula_6 بودند، می‌توانیم مسیری در formula_6 که آن دو را به هم متصل می‌نماید پیدا نماییم که ترتیبی از یال‌ها و رئوس فقط رنگ شده با ۱ و ۳ باشد. حال زیر گراف formula_16 از formula_7 را که در بر گیرنده رئوس رنگ شده با ۲ و ۴ و یال‌های متصل کننده این رئوس به هم است را
۲ و ۴ و یال‌های متصل کننده این رئوس به هم است را در نظر می‌گیریم و روندی مشابه قبلی برای آن اجرا می‌کنیم. پس یا می‌توانیم رنگ آمیزی زیر گراف formula_16 را برعکس نموده و رأس V را به رنگ ۲ بزنیم یا از مسیری متشکل از رئوس تنها رنگ شده با ۲ و ۴، formula_2 و formula_4 را به هم متصل نماییم. احتمال بعدی به روشنی نامعقول است که مسیری با مسیر ساخته شده در formula_6 تقاطع داشته باشد؛ بنابراین مخالف با استنباط اولیه G در واقع می‌تواند با پنج رنگ، رنگ آمیزی شود. الگوریتم پنج رنگ کردن در زمان خطی. در سال ۱۹۹۶،
الگوریتم پنج رنگ کردن در زمان خطی. در سال ۱۹۹۶، رابرتسون، ساندرز، سیمور و توماس یک الگوریتم چهار رنگ کردن از درجه دوم در «گراف مسطح کارآمد چهار رنگ کردن» خود تعریف کردند. در همان‌جا، آن‌ها مختصراً یک الگوریتم پنج رنگ کردن در زمان خطی تعریف کردند که به طور مجانبی بهینه بود. الگوریتمی که در این جا توصیف شده بر روی چند گراف عمل می‌کند و بر قابلیت داشتن چندین نسخه از یال‌ها بین یک جفت رأس تکیه دارد. این قضیه بر اساس قضیه ورنیک می‌باشد که در پایین آمده است: قضیه ورنیک: فرض می‌کنیم G یک گراف مسطح غیر خالی است که
ورنیک: فرض می‌کنیم G یک گراف مسطح غیر خالی است که هیچ منطقه‌ای ندارد که با دو یال محدود شده باشد و حداقل درجه پنج دارد. پس G حتماً یک رأس از درجه پنج دارد که مجاور رأسی با درجه حداکثر شش است. ما نمایشی از این گراف را به کار می‌بریم که در آن هر رأس یک لیست پیوندی دایره‌ای از رئوس مجاور را در جهت ساعتگرد گراف مسطح نگه می‌دارد. در مفهوم، الگوریتم بازگشتی است؛ در هر مرحله گراف را به یک گراف با یک رأس کمتر کاهش می‌دهد؛ آن را پنج رنگ می‌کند و سپس از آن رنگ کردن استفاده می‌کند تا معین کند رنگ کردن گراف بزرگتر در
می‌کند تا معین کند رنگ کردن گراف بزرگتر در زمان ثابتی انجام می‌شود. در عمل بیش از این که برای هر گراف کوچک شده، نمایش یک گراف صریح را نگه داریم، ما رئوس را از گراف حذف می‌کنیم و آن‌ها را به یک پشته اضافه می‌کنیم. سپس در آخر هنگامی که آن‌ها را از پشته خارج می‌کنیم، رنگشان می‌کنیم. ما سه تا پشته را نگه خواهیم داشت: الگوریتم به نحوه زیر کار می‌کند:
تحلیل سر‌شکن: در این نوع آنالیز، n عمل انجام می‌شود و هزینه زمانی آن روی n عمل سرشکن می‌شود. در واقع ممکن است عملیات انجام شده هزینه‌های مختلفی داشته باشند و برخی هزینه زیادی داشته باشند ولی هزینه متوسط هر عمل کوچک باشد. لازم به ذکر است که آنالیز استهلاکی با آنالیز در حالت میانگین متفاوت است و روش‌های آماری را شامل نمی‌شود. در واقع آنالیز استهلاکی زمان اجرای متوسط هر عمل در بدترین حالت را نشان می دهد. برای این نوع آنالیز 3 روش مطرح است: آنالیز تجمعی در این روش هزینه n عمل را به دست می آوریم سپس به n تقسیم
روش هزینه n عمل را به دست می آوریم سپس به n تقسیم می کنیم . مثلاً n عمل formula_1 روی پشته s که در ابتدا خالی است انجام داده ایم formula_2 (عنصر از پشته pop می کند، البته اگر کمتر از k عنصر در پشته باشند، همه عناصر pop می شوند) درست است که هزینه formula_2 ممکن است formula_4 باشد ولی n عمل از عملیات فوق روی هم هزینه formula_5 باشد ولی N عمل از عملیات فوق روی هم هزینه formula_5 دارند پس هزینه هر عمل به صورت سرشکن شده برابر formula_7 است. روش حسابرسی در این روش به عملیات مختلف، شارژهای مختلفی نسبت می دهیم که
به عملیات مختلف، شارژهای مختلفی نسبت می دهیم که ممکن است شارژی که نسبت می دهیم، از هزینه واقعی عمل کمتر یا بیشتر باشد . مقداری که یک عمل شارژ می‌شود را «هزینه استهلاک » آن عمل گویند. اگر « هزینه استهلاک » یک عمل از «هزینه واقعی » آن عمل بیشتر باشد، تفاوت این دو به عنوان «اعتبار» به عناصر خاصی از ساختمان داده تخصیص می یابد. این اعتبار را می توان بعداً برای عملیاتی که هزینه استهلاکشان کمتر از هزینه واقعی شان است، صرف کرد. به عنوان مثال عملیات پشته را در نظر بگیرید . می دانیم هزینه واقعی عملیات عبارت است از :
. می دانیم هزینه واقعی عملیات عبارت است از : formula_8 که s تعداد عناصر موجود در پشته هنگام فراخوانی Multipop است. ولی ما هزینه استهلاکی زیر را به عملیات نسبت می دهیم : formula_9 با این مقادیر، می توان هر دنباله از عملیات را پشتیبانی کرد. هر push که انجام می شود، هزینه واقعی اش 1 است، پس از شارژ 2 مقداری آن ، 1 مقدار برای هزینه اش صرف می‌شود و 1 مقدار در عنصر push شده به عنوان اعتبار ذخیره می شود، پس تمام عناصری که در پشته هستند، اعتبار 1 مقداری دارند. حال اگر pop انجام شود، چون هزینه واقعی pop ، 1 است،
اگر pop انجام شود، چون هزینه واقعی pop ، 1 است، این 1 را از اعتبار عنصری که pop می شود، دریافت می کند . پس از آنجایی که هزینه استهلاکی push ، pop و Multipop ثابت formula_10 است پس هزینه Nعمل ، formula_5 است. روش پتانسیل روش قبلی، اعتبار را به عنصر تخصیص می داد ولی این روش، اعتبار را به صورت پتانسیل به کل ساختمان داده تخصیص می دهد. فرض کنیدformula_12 وضعیت اولیه ساختمان داده ای است که می خواهیم formula_13 عمل روی آن انجام دهیم. formula_14 هزینه واقعی عمل i ام ، formula_15 وضعیت ساختمان داده است پس از انجام
، formula_15 وضعیت ساختمان داده است پس از انجام عمل i ام روی formula_16 تابع پتانسیلی تعریف می کنیم به اسمformula_17 که به هر وضعیت ساختمان داده، یک عدد حقیقی نسبت می دهد: یک عدد حقیقی=formula_18 بنابراین هزینه استهلاکی formula_19 عمل i ام برابر است با : formula_20&lt;br&gt; پس کل هزینه استهلاکی برابر است با : formula_21 مثلاً فرض کنید در عملیات پشته formula_1، تابع پتانسیل formula_17 را برابر عناصر موجود در پشته فرض کنیم . در حالت پشته خالی formula_12، که حالت شروع استformula_25. از آنجایی که تعداد عناصر