payamvha/North_RAG huggingface dataset:
اندازه منطقی کراندار است، این ساختار داده کفایت می‌کند. تغییر دادن اندازه آرایه زیرین عملی هزینه بر است، گاهی ناچار می‌شویم تمام محتویات آرایه را کپی کنیم. تصاعد هندسی و هزینه واگذار شده. برای جلوگیری از تحمیل هزینه‌های اضافی حاصل از تغییر اندازه دادن‌های مکرر، آرایه‌های پویا به مقدار زیادی تغییر اندازه می‌دهند، مثلاً به دو برابر اندازه اولیه تغییر اندازه می‌دهند، و فضای رزرو شده را برای بسط بعدی استفاده می‌کنند. عمل اضافه کردن یک عنصر باید مانند زیر انجام شود: function insertEnd("dynarray" a, "element" e)
function insertEnd("dynarray" a, "element" e) if (a.size = a.capacity) "// (اندازه را به دو برابر مقدار اولیه تغییر می‌دهیم): a.capacity ← a.capacity * 2 "// (کپی کردن محتویات در محل حافظه جدید)" a[a.size] ← e a.size ← a.size + 1 در فرایند درج n عنصر، ظرفیت‌ها تشکیل تصاعد هندسی می‌دهند. بسط دادن آرایه با هر نسبت ثابتی تضمین می‌کند وارد کردن عصر در کل از (O(n زمان می‌برد، یعنی وارد کردن هر عنصر زمان سرشکن شده ثابتی می‌برد. مقدار این تناسب منجر به لزوم سبک‌سنگین کردن این فصله زمانی می‌شود: زمان متوسط هر بار
کردن این فصله زمانی می‌شود: زمان متوسط هر بار وارد کردن تقریباً (a/(a-۱ است، در حالی که تعداد خانه‌های تلف شده از بالا به a−۱)n) کراندار است. انتخاب a بستگی به برنامه دارد، ولی معمولاً a=۲ می‌گیرند. بعلاوه در بسیاری از آرایه‌های پویا اگر مقدار استفاده شده از حدی کمتر شود، مانند ۳۰٪ ظرفیت، آن را آزاد می‌کنند. آرایه‌های پویا مثال رایجی در تدریس تحلیل سرشکن شده هستند. کارایی. کارایی آرایه پویا شبیه آرایه‌است، بعلاوه عمل حذف و افزودن عناصر به انتها: بسیاری از مزیت‌های آرایه‌ها در آرایه‌های پویا نیز وجود دارد،
آرایه‌ها در آرایه‌های پویا نیز وجود دارد، از جمله محل مناسب مرجع و استفاده از حافظه نهان، تراکم (کم استفاده کردن از حافظه)، و دسترسی تصادفی. معمولاً آرایه‌های پویا در کل فقط یک حافظه اضافی کوچکی برای اطلاعات اندازه و ظرفیت دارند. این ویژگی موجب می‌شود آرایه‌های پویا ابزار مناسبی برای ساختن داده ساختار متناسب با حافظه نهان شوند. آرایه‌های پویا در مقایسه با لینک لیست، قابلیت شاخص گذاری سریع تری دارند (زمان ثابت در برابر زمان خطی) و معمولاً به دلیل اصلاح محل مرجع عناصر سریعتر می‌توان بر روی عناصر واقع در
مرجع عناصر سریعتر می‌توان بر روی عناصر واقع در خانه‌های آرایه حرکت کرد؛ اگرچه، آرایه‌های پویا برای وارد کردن در محلی دلخواه یا پاک کردن از جایگاهی اختیاری زمانی خطی نیاز دارند، چون همه عناصر بعدی باید یک عنصر جابه‌جا شوند، در حالیکه لینک لیست می‌تواند این عمل را در زمانی ثابت انجام دهد. به وسیلهٔ میانگیر وقفه و متغیرهای بردار صف شده این اشکال را برطرف کرده‌اند که در مورد آن در قسمت متغیرها بحث شده‌است. همچنین، ممکن است یافتن فضایی پیوسته در ناحیه یک حافظه بسیار قطعه بندی شده هزینه بر یا غیرممکن باشد، در
بسیار قطعه بندی شده هزینه بر یا غیرممکن باشد، در حالیکه لینک لیست‌ها نیازی ندارند همه داده ساختار به‌طورپیوسته در حافظه ذخیره شود. متغیرها. میانگیرهای وقفه شبیه آرایه‌های پویا هستند ولی اجازه می‌دهند عملگرهای کارای درج و حذف نزدیک محل اختیاری مشابه جمع شوند. برخی از پیاده‌سازی‌های صف دو سر از آرایه‌های صف دو سر استفاده می‌کنند، که اجازه درج/جابجایی در هر دو سر، به جای یک طرف می‌دهد. Goodrich الگوریتمی از آرایه‌های پویا به نام "Tiered Vectors" ارائه کرد که کارایی آن برای درج و حذف از وسط آرایه با حفظ ترتیب
آن برای درج و حذف از وسط آرایه با حفظ ترتیب n۱/۲ O(است. درخت آرایه‌ای درهم یک الگوریتم آرایهٔ پویا است که توسط Sitarski در سال ۱۹۹۶ ساخته شده‌است. درخت آرایه‌ای درهم حافظه‌ای از مرتبه n۱/۲ هدر می‌دهد، که n تعداد عناصر آرایه‌است. وقتی دنباله‌ای از اشیا به انتهای درخت آرایه‌ای درهم می‌افزاییم، کارکرد سرشکن الگوریتم O(۱) است. در سال ۱۹۹۹ Brodnik et al. در مقاله‌ای یک داده ساختار آرایه پویای صفی توصیف کرد، که در هر نقطه‌ای از زمان تنها n۱/۲ فضا برای n عنصر هدر می‌داد، و آن‌ها کران پایینی را ثابت کردند که نشان
می‌داد، و آن‌ها کران پایینی را ثابت کردند که نشان می‌داد در هر آرایه پویایی اگر عملگرها می‌خواهند زمان ثابت سرشکنی بگیرند حداقل به این مقدار فضا نیاز هست. بعلاوه، برای مواردی که رشد کردن و جمع شدن میانگیرنه تنها درحالت سرشکن بلکه در بدترین حالت ثابت باشد، متغیری ارائه کردند. در سال ۲۰۰۲ Bagwell الگوریتم Vlist را ارائه کرد، که می‌تواند برای پیاده‌سازی آرایه پویا اقتباس شود. زبان‌های پشتیبانی‌کننده. در C++, Std::vector یک نمونه پیاده‌سازی برای آرایه‌های پویا است، همان‌طور که کلاس‌های ArrayList توسط API java
است، همان‌طور که کلاس‌های ArrayList توسط API java و.NET Framework عرضه شده‌است. کلاس نوعی List&lt;&gt; نیز توسط version 2.0 of the.NET Framework عرضه شده، پیاده‌سازی دیگری برای آرایه‌های پویا است. Delphiو Dآرایه‌های پویا را در هسته زبان پیاده‌سازی کرده‌اند. بسیاری از زبان‌های مستند مانند Perl و PHP پیشنهاد می‌دهند آرایه‌های پویا جزو ساختمان و به عنوان گنه داده‌های اولیه در نظر گرفته شوند. منابع. Wikipedia contributors, "Dynamic array," Wikipedia, The Free Encyclopedia,
array," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Dynamic_array&amp;oldid=290138184 (accessed May 15, 2009).
مرتب‌سازی انتخابی یکی از انواع الگوریتم مرتب‌سازی می‌باشد که جزو دستهٔ الگوریتم‌های مرتب‌سازی مبتنی بر مقایسه‌است. این الگوریتم دارای پیچیدگی زمانی از درجهٔ است که به همین دلیل اعمال آن روی مجموعهٔ بزرگی از اعداد کارا به نظر نمی‌رسدو به‌طور عمومی ضعیفتر از نوع مشابهش که مرتب‌ساز درجی است عمل می‌کند. این مرتب‌سازی به دلیل سادگی اش قابل توجه‌است. کارایی آن برحسب تعداد ورودی‌ها در نمودار زیر نشان داده شده‌است. مرتب‌سازی انتخابی. نحوه عملکرد. این الگوریتم این‌گونه عمل می‌کند: ابتدا کوچکترین عنصر مجموعه اعداد را
عمل می‌کند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا می‌کنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا می‌کنیم و این روند را برای n-1 عدد اول تکرار می‌کنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم می‌کنیم. زیرلیست اول که قبلاً مرتب کرده‌ایم و سایر اعضای لیست که هنوز مرتب نشده‌است. در جدول زیر مثالی از پیاده‌سازی این روال بر روی ۶ عدد آمده‌است. پیاده سازی الگوریتم در زبان های برنامه نویسی. الگوریتم در پایتون. A = [64, 25, 12, 22, 11] for i in range(len(A)): min_idx =
25, 12, 22, 11] for i in range(len(A)): min_idx = i for j in range(i+1, len(A)): if A[min_idx] &gt; A[j]: min_idx = j A[i], A[min_idx] = A[min_idx], A[i] print ("Sorted array") for i in range(len(A)): print("%d" % A[i], end="\t") الگوریتم در جاوا. private static void selectionSort(double arr[]) for(int i= 0; i &lt; arr.length - 1; i++) // (could i &lt; arr.length - 1 because single element is also min element) for(int j= i + 1; j &lt; arr.length; j++) if(arr[i] &gt; arr[j]) double temp= arr[i]; arr[i]=
&gt; arr[j]) double temp= arr[i]; arr[i]= arr[j]; arr[j]= temp; تحلیل مرتبه الگوریتم. تحلیل الگوریتم مرتب‌سازی انتخابی برخلاف بسیاری از مرتب‌سازی‌های دیگر بسیار ساده‌است. زیرا که هیچ‌کدام از حلقه‌های آن به اعداد موجود در لیست ورودی بستگی ندارد. در مرحلهٔ اول به دست آوردن کمینه در لیست n عنصری نیاز به پیمودن کل n عدد و n – 1 مقایسه دارد و سپس باید کمینهٔ به‌دست آمده با اولین عدد جابجا شود. در مرحلهٔ بعدی به دست آوردن دومین کمینه در لیست 1 - n عنصری نیاز به پیمودن کل 1 - n عدد و 2 - n مقایسه دارد و کمینهٔ
پیمودن کل 1 - n عدد و 2 - n مقایسه دارد و کمینهٔ به‌دست آمده بادومین عدد جابجا شودو این روند ادامه پیدا می‌کند. پس کلاً تعداد مقایسه‌ها عبارتست از: ("n" − 1) + ("n" − 2) +... + 2 + 1 = "n"("n" − 1) / 2 ∈ Θ("n"2) مرتبهٔ این الگوریتم به دلیل عدم وابستگی آن به نحوهٔ ترتیب اعداد در بهترین، بدترین و حالت متوسط یکسان و برابر(Θ("n"2 است. ویژگی‌های مرتب‌سازی انتخابی. ۱-با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملاً مرتب، نامرتب تصادفی و مرتب
برای داده‌های کاملاً مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد؛ بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت متوسط نیز (Θ(n2 است. ۲- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد. ۳- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود. در نتیجه ترتیب آن‌ها به هم می‌خورد؛
منتقل می‌شود. در نتیجه ترتیب آن‌ها به هم می‌خورد؛ بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای&gt; از =&gt; استفاده کنید، مرتب‌سازی پایدار خواهد شد. مقایسه با سایر الگوریتمهای مرتب‌سازی. این الگوریتم بین الگوریتم‌های با مرتبهٔ مرتب‌ساز انتخابی از مرتب‌ساز حبابی و مرتب‌ساز گورزاد (در حالت متوسط) بهتر عمل می‌کند. اما عموماً ضعیفتر ازمرتب‌ساز درجی است. یکی از شباهتهای مرتب‌ساز درجی به مرتب‌ساز انتخابی این است که در هر دو
درجی به مرتب‌ساز انتخابی این است که در هر دو پس از پیمایش Kام مجموعه اعداد kعنصر اول در جای صحیح خود قرار گرفته‌اند. فایدهٔ مرتب‌ساز درجی این است که برای پیدا کردن عنصر x هر تعداد از اعداد را که نیاز است بررسی می‌کند. حال آنکه مرتب ساز انتخابی همه عناصر باقی‌مانده را بررسی می‌کند. به هر حال هر دو آن‌ها روی لیستهای کوچک بسیار سریع هستند. در نهایت اعمال مرتب‌ساز انتخابی روی لیستهایی با اندازه بزرگ به مراتب از مرتب‌ساز حبابی که روی ان لیستها با پیچیدگی زمانی ("Θ("n" log "n عمل می‌کند ضعیف‌تر است. سورس
زمانی ("Θ("n" log "n عمل می‌کند ضعیف‌تر است. سورس مرتب‌سازی انتخابی (Selection sort). مثال. این سورس یک عدد گرفته و به تعداد همان عدد از ورودی دریافت می‌کند و آن‌ها را با روش. Selection sort مرتب می‌کند.
احمد نوری‌زاده (آبان ۱۳۳۰ – ۱ شهریور ۱۴۰۰) ادیب، مترجم و پژوهشگر ایرانی بود. وی بنیانگذار ارمنی‌شناسی فارسی در ایران بود. نوری‌زاده تنها شاعر غیرارمنی جهان بود که به زبان ارمنی نیز شعر می‌سرود. زندگی‌نامه. وی در آبان ماه سال ۱۳۳۰ در خانواده‌ای پرجمعیت، در غازیان، بندرانزلی روستای سهلک از توابع بخش کوهستان به دنیا آمد. نوری‌زاده در کمتر از ۶ ماه نزد «آرشی بابایان» شاعر ارمنی، الفبای این زبان را آموخت وی همچنین در نزد خاژاک در-گریگوریان، رئیس «دانشکده ارمنی‌شناسی» دانشگاه اصفهان، مدتی را به آموزش زبان ارمنی
دانشگاه اصفهان، مدتی را به آموزش زبان ارمنی گذراند. احمد نوری‌زاده در سال‌های ۱۳۴۹–۱۳۴۸ کار ترجمه و معرفی آثار شاعران ارمنی را آغاز کرد. در ارمنستان، از او به عنوان «فرزند پارسی‌گوی ملت ارمنی» یاد می‌شود و «جایزه سپاس» را از انجمن نویسندگان ارمنستان دریافت کرد. بیماری و درگذشت. وی در ساختمان گل یاس یکی از ساختمان‌های آسایشگاه کهریزک مخصوص بیماران ام‌اس، تحت مراقبت‌های پزشکی و اجتماعی بود. وی در صبح روز دوشنبه ۱ شهریور ۱۴۰۰ در سن ۶۹ سالگی درگذشت. جوایز. نوری‌زاده به پاس چهل سال تلاش بی‌وقفه در شناساندن
نوری‌زاده به پاس چهل سال تلاش بی‌وقفه در شناساندن فرهنگ و ادب ارمنی جوایز جهانی بسیاری نیز کسب کرده است که از جمله مهم‌ترین آن‌ها عبارتند از:
جمهوری فدرال برزیل از ۲۷ واحد فدرال تشکیل شده‌است که این واحدها از ۲۶ ایالت و یک منطقه فدرال که شهر پایتخت، برازیلیا را شامل می‌شود، تشکیل شده‌اند.
در علوم رایانه پشته‌های دوجمله‌ای (Binomial heaps) داده‌ساختارهایی مشابه با پشته‌های دودویی هستند که قادر به پشتیبانی از عمل ادغام سریع دو Heap نیز هستند. که این عمل با استفاده این داده ساختار، از درخت دو جمله‌ای حاصل می‌شود. درخت دو جمله‌ای. یک پشته دو جمله‌ای با استفاده از مجموعه‌ای از درخت‌های دو جمله‌ای ساخته می‌شود(همان گونه که پشته دودویی از درخت دودویی ساخته می‌شود). یک درخت دو جمله‌ای به صورت بازگشتی، همانند زیر تعریف می‌شود: یک درخت دو جمله‌ای از مرتبه "k" دارای ۲k رأس، و ارتفاع "k" می‌باشد. به
مرتبه "k" دارای ۲k رأس، و ارتفاع "k" می‌باشد. به خاطر ساختار خاص درخت دو جمله‌ای، می‌توان هر درخت از مرتبه "k" را از وصل کردن دو درخت از مرتبه "k"-۱ ساخت، به این ترتیب که ریشه یکی از این درخت‌ها را به عنوان چپ‌ترین فرزند به ریشه درخت دیگر وصل کرد. این ویژگی در انجام عمل ادغام روی Heapهای دو جمله‌ای اهمیت دارد که یکی از دلایل برتری آن‌ها بر Heapهای معمولی است. ساختار پشته‌های دوجمله‌ای. یک Heap دو جمله‌ای با استفاده از مجموعه‌ای از درخت‌های دو جمله‌ای پیاده‌سازی می‌شود که دارای "خصوصیات Heap دو جمله ای"
می‌شود که دارای "خصوصیات Heap دو جمله ای" است: خصوصیت اول تضمین می‌کند که ریشه هر درخت دارای کوچکترین کلید موجود در آن درخت است، که به تمام Heap تعمیم پیدا می‌کند. خاصیت دوم نتیجه می‌دهد که هر Heap با "n" عنصر حد اکثر از log "n" + ۱ تشکیل شده‌است. در واقع تعداد و مرتبه هر یک از این درخت‌ها به‌طور منحصر به فرد توسط تعداد عناصر درخت "n" مشخص می‌شود: هر درخت دودویی متناظر است با رقم یک در نمایش دودویی "n". برای مثال عدد ۱۳ در مبنای دو دارای نمایش ۱۱۰۱ می‌باشد، formula_1 در نتیجه یک پشته دو جمله‌ای با ۱۳ عنصر
formula_1 در نتیجه یک پشته دو جمله‌ای با ۱۳ عنصر از سه درخت دوجمله‌ای با مرتبه‌های ۰، ۲ و ۳ تشکیل شده‌است(همانند شکل). یک پشته دو جمله‌ای شامل ۱۳ عنصر نا مساوی پیاده‌سازی. به این دلیل که انجام هر یک از عملیات نیاز به دسترسی تصادفی به ریشه‌های درخت‌های دودویی ندارد، ریشه درخت‌ها را می‌توان به ترتیب مرتبه در یک لیست پیوندی() ذخیره کرد. ادغام. همان طور که قبلاً نیز گفته شد مهم‌ترین عملیات در پشته‌های دو جمله‌ای، ادغام دو درخت دو جمله‌ای از یک مرتبه در دو پشته دو جمله‌ای می‌باشد. به این منظور از آنجایی که ریشه
جمله‌ای می‌باشد. به این منظور از آنجایی که ریشه یک درخت کوچکترین عضو آن درخت می‌باشد با مقایسه کلید ریشه‌های دو درخت، کلیدی که کوچکتر است عضو مینیمم است به عنوان ریشه درخت جدید انتخاب می‌شود و ریشه دیگر زیر درخت آن می‌شود. این رویه پایه کامل کردن عملیات ادغام دو پشته دو جمله‌ای است. function mergeTree(p, q) if p.root &lt;= q.root return p.addSubTree(q) else return q.addSubTree(p) منابع. Wikipedia contributors, «Binomial heap,» Wikipedia, The Free Encyclopedia,
heap,» Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Binomial_heap&amp;oldid=290139444 (accessed May 15, 2009).
در نظریه گراف ، گراف پترسن گرافی غیر جهت دار، با ۱۰ راس و ۱۵ یال است. این گراف، گرافی کوچک می‌باشد که به عنوان مثالی مفید و همچنین مثال نقض در بسیاری از مسائل نظریه گراف به کار می‌رود.یولیوس پترسن(۱۸۳۹-۱۹۱۰) دانشمندی دانمارکی بود که در سال ۱۸۹۸ گرافی را، که به نام خودش ثبت شد، به عنوان کوچکترین گراف مکعبی (گرافی که هر راس آن از درجه ۳ باشد.) بدون پل ساخت. در واقع این گراف مثال نقضی برای این ادعا بود که یک گراف مکعبی بدون پل متصل، داری یک رنگ آمیزی یالی با ۳ رنگ است. در حالی که این گراف دارای این رنگ آمیزی
رنگ است. در حالی که این گراف دارای این رنگ آمیزی با ۴ رنگ می‌باشد. با این که این گراف به‌طور عمومی به یولیوس پترسن نسبت داده می‌شود، ولی درحقیقت برای اولین بار ۱۲ سال زودتر از ساختن آن توسط وی، در سال ۱۸۸۶ به وجود آمده بود.دونالد نوث اذعان می‌کند که گراف پترسن، شکل و پیکری قابل توجه‌است که به عنوان مثالی نقض برای بسیاری از اسناد و اثبات‌های خوش بینانه دربارهٔ این که چه چیزهایی ممکن است به‌طور عمومی برای گراف‌ها درست باشد، به کار می‌رود. ساختار. گراف پترسن، گراف مکمل برای گراف خط، K۵ است. همچنین گراف کنسر
گراف مکمل برای گراف خط، K۵ است. همچنین گراف کنسر KG۵٬۲ هم می‌باشد. این بدان معنا است که اگر برای هر کدام از زیرمجموعه‌های دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعه‌های نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته می‌شود. گراف پترسن، گرافی غیر مسطح است. هر گراف غیر مسطح زیر گرافی دارد که با گراف کامل K۵ یا گراف دو بخشی کامل K۳٬۳ هم ریخت یا هومئومورف است. حال آن که پترسن با هر دو گراف هم ریخت می‌باشد. خواص عمومی. دقیقاً ۱۹ گراف مکعبی متصل با ۱۰ یال وجود دارد.
دقیقاً ۱۹ گراف مکعبی متصل با ۱۰ یال وجود دارد. گراف پترسن یکی از همین ۱۹ گراف می‌باشد. این گراف تنها گرافی با ۱۰ یال از این دسته‌است که دارای قطر برابر ۲ و تنها گراف بدون پل با اندیس رنگی ۴ می‌باشد. و نهایتاً تنها گراف بدون پل با ۱۰ یال است که همیلتنی نیست. متداول‌ترین و متقارن‌ترین شکل گراف پترسن که یک پنج ضلعی با یک ستارهٔ پنج رأس درون آن است که هر یک از رأس‌هایش به رأس‌های پنج ضلعی با یک یال وصل می‌شود، دارای ۵ نقطه تقاطع می‌باشد(شکل(۱)).این روش ترسیم بهترین روش برای کمینه کردن تعداد تقاطع‌ها نیست. روشی
روش برای کمینه کردن تعداد تقاطع‌ها نیست. روشی دیگر برای کشیدن گراف پترسن با دو نقطهٔ تقاطع وجود دارد.(شکل(۲)) بنابراین عدد تقاطع گراف پترسن ۲ است. همچنین گراف پترسن می‌تواند به گونه‌ای رسم شود که یال‌ها دارای طول برابر واحد باشند. این نوع، یک گراف به طول واحد است.(شکل(3))فاصله هر دو راس غیرمجاور برابر با 2 میباشد دور و مسیر همیلتونی. گراف پترسن دارای مسیر همیلتونی است ولی دور همیلتونی ندارد. همچنان که در بالا ذکر شد این گراف کوچکترین گراف مکعبی بدون پل است که دور همیلتونی ندارد. در نتیجه گراف همیلتونی
است که دور همیلتونی ندارد. در نتیجه گراف همیلتونی نیست. ولی این گراف، شبه همیلتونی است، بدان معنی که با وجود این که دور همیلتونی ندارد ولی با حذف کردن هر یال آن تبدیل به گراف همیلتونی می‌شود و ضمناً کوچترین گراف شبه همیلتونی نیز می‌باشد.(شکل(۴)) گراف پترسن یکی از ۵ گراف متصل راس-ترایا است که دور همیلتونی ندارد. رنگ آمیزی. گراف پترسن دارای شماره رنگی ۳ است. این بدان معنا است که راس‌های آن می‌توانند با ۳ رنگ، اما نه با ۲، رنگ شوند به طوری که هیچ یالی دو راس همرنگ را متصل نکند.(شکل(۵)) همچنین دارای اندیس رنگی
را متصل نکند.(شکل(۵)) همچنین دارای اندیس رنگی ۴ می‌باشد که یعنی برای رنگ کردن یال‌ها به ۴ رنگ نیاز داریم. جدول خصوصیات. در جدول زیر بعضی از خواص این گراف به‌طور خلاصه آمده‌است:
صف اولویت‌دار از جمله ساختمان‌های داده بسیار پرکاربرد است. در صف عادی از روش خروج به ترتیب ورود (FIFO) استفاده می‌شود. در این تکنیک مثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند؛ بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود. اما در صف اولویت‌دار برای هر داده اولویتی - نه لزوماً منحصربه‌فرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم‌عامل کامپیوتر هم برای مدیریت پردازش‌ها از
سیستم‌عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت استفاده می‌کند. عملیات‌ها. صف‌های اولویت حداقل از ۲ عملیات زیر پشتیبانی می‌کنند: عملیات زیر هم با توجه به کاربردهای فراوانی که دارد اغلب اوقات پیاده‌سازی می‌شود: پیدا کردن عنصر با بالاترین اولویت در پیاده‌سازی‌های پیشرفته تر مربوط به این ساختار عملیات‌های زیر نیز می‌توانند وجود داشته باشند: شباهت با صف معمولی (بدون اولویت). صف اولویت دار همانند صف معمولی است با این تفاوت که در هنگام خروج، عنصری که بالاترین اولویت را دارد، از لیستمان خارج
عنصری که بالاترین اولویت را دارد، از لیستمان خارج می‌گردد. صف معمولی حالت خاصی از صف اولویت‌دار است که در آن اولویت عناصر به‌ترتیب اضافه شدنشان کاهش پیدا می‌کند پس عنصری که در اول لیست است، بالاترین اولویت را داراست. ساختن درخت Heap. ساختن یک درخت heap در واقع وارد کردن متوالی گره‌ها در آن است. برای وارد کردن یک گره به درخت heap، طی دو مرحله به صورت زیر عمل می‌کنیم: ۱- گره مفروض را در محلی از درخت که شرط کامل بودن آن به هم نخورد (بدون در نظر گرفتن شرط max-heap یا min-heap بودن) درج می‌کنیم. ۲- اگر گره
یا min-heap بودن) درج می‌کنیم. ۲- اگر گره مذکور بر اساس موقعیت خود در درخت، شرط max-heap یا min-heap بودن را نقض نکند، نیاز به انجام کاری نیست و عملیات درج تمام شده‌است. در غیر اینصورت، با جابجا کردن گره با والد خود، درخت جدیدی حاصل می‌شود که باید مرحله ۲ در مورد آن تکرار شود. پیاده‌سازی صف اولویت‌دار. برای پیاده‌سازی صف اولویت‌دار عموماً از آرایه استفاده می‌شود. ما در اینجا سه روش مختلف را شرح می‌دهیم. پیاده‌سازی با استفاده از آرایه نامرتب. در این روش زمانی که داده‌ای وارد صف می‌شود همچون صف عادی در
زمانی که داده‌ای وارد صف می‌شود همچون صف عادی در انتهای آن قرار می‌گیرد. به عنوان نمونه داده‌های مثال زمانبندی CPU به صورت زیر در آرایه قرار می‌گیرند: شماره پردازش: ۱ ۲ ۳ ۴ ۵ ۶ الویت: ۴ ۲ ۱ ۳ ۵ ۴ درج و حذف یک عنصر در این روش، از نظر زمانی به ترتیب (۱)O و (O(n است. توجه داشته باشید که هر عنصر آرایه ساختمانی مرکب از دو عنصر شماره پردازش و اولویت آن است. هر پردازش جدید به انتهای صف اضافه می‌شود، که از مرتبه (O (۱ است. اما زمانی که قرار است پردازشی از آن خارج شود باید تک تک عناصر بررسی شوند، تا پردازشی با
شود باید تک تک عناصر بررسی شوند، تا پردازشی با بیشترین اولویت انتخاب شود. این فرایند از مرتبه (O (n است. پیاده‌سازی با استفاده از آرایه مرتب. در این روش بر خلاف روش قبلی آرایه بر اساس اولویت‌ها مرتب شده‌است. شماره پردازش:۵ ۶ ۱ ۷ ۴ ۲ ۳ الویت:۵ ۴ ۴ ۳ ۳ ۲ ۱ شماره پردازش: ۱ ۲ ۳ ۴ ۵ ۶ ۷ الویت:۴ ۲ ۱ ۳ ۵ ۴ ۳ زمانی که داده‌ای وارد صف می‌شود، بر اساس اولویت خود در محل مناسب قرار می‌گیرد. در این حالت پردازش با بیشترین اولویت همواره در انتهای صف قرار دارد و هزینه استخراج آن (O (۱ است. این مسئله در مقایسه با آرایه
آن (O (۱ است. این مسئله در مقایسه با آرایه نامرتب یک برتری است. اما در این روش هزینه درج (O(n است که در مقایسه با روش قبلی اصلاً بهینه نیست. در کل می‌توان گفت روش آرایه مرتب و نامرتب هم ارز یکدیگر بوده و از لحاظ عملکرد تفاوت چندانی با هم ندارند. درج و حذف یک عنصر در این روش، از نظر زمانی به ترتیب (O(n و (۱)O است. پیاده‌سازی با استفاده از آرایه نیمه مرتب (درخت heap). در این درخت heap، داده‌ها را بر اساس اولویت آن‌ها در یک درخت مکس-هیپ همانند شکل وارد می‌کنیم. اعداد داخل گره‌ها اولویت و اعداد خارجی شماره
اعداد داخل گره‌ها اولویت و اعداد خارجی شماره پردازش هستند. درخت فوق در نمایش آرایه‌ای به صورت شکل نشان داده شده، خواهد شد. در یک درخت min-heap عنصری با کوچکترین کلید همواره در ریشه قرار دارد (چرا!؟). در نتیجه عمل حذف گره ریشه از درخت min-heap کوچکترین عنصر آن را به ما می‌دهد. این عمل از مرتبه (O (logn است. عمل درج در min-heap هم همان‌طور که می‌دانید از همین مرتبه‌است. مقایسه ۳ روش پیاده‌سازی صف اولویت‌دار. عملیات درج و حذف روی یک صف اولویتی که با استفاده از آرایه مرتب یا نامرتب ساخته شده باشد روی هم رفته
آرایه مرتب یا نامرتب ساخته شده باشد روی هم رفته از مرتبه (O (n است. اما در روش آرایه نیمه مرتب این مرتبه به (O (logn کاهش می‌یابد. پس می‌توان گفت که روش درخت هیپ برای پیاده‌سازی صف اولویتی کارایی بسیار بهتری دارد. ارتباط صف اولویت‌‌دار با الگوریتم‌های مرتب‌سازی. هنگامی که عناصر را در یک صف اولویت‌دار که با استفاده از آرایه مرتب پیاده‌سازی شده است، درج کنیم و پس از آن یکی یکی آن‌ها را از لیست حذف کنیم؛ عناصر به صورت مرتب شده قرار می‌گیرند. این روشی است که در چندین الگوریتم مرتب‌سازی به کار می‌رود: منابع.
در چندین الگوریتم مرتب‌سازی به کار می‌رود: منابع. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html http://en.wikipedia.org/wiki/Priority_queueویکی‌پدیای انگلیسی
بازگشت در علوم رایانه، روشی برای حل یک مسئله است که در آن راه‌حل مسئله به راه‌حل هایی در نمونه های کوچکتر از همان مساله وابسته می باشد. به نظر می‌رسد ترجمه «بازگشت» بیشتر مناسب کلمه انگلیسی Return باشد تا کلمه Recursion ؛ به همین دلیل بعضی از اساتید عبارت «توابع خوداتکاء» را برای نامیدن این‌گونه توابع به کار می‌برند. همچنین از آنجایی که ریشهٔ این کلمه در زبان انگلیسی فعل Recur به معنای "اتفاق افتادن مجدد" می‌باشد ترجمه‌های مناسب دیگر می توانند "توابع بازوقوع" و "توابع بازفراخوانی شونده" باشند، که همگی قطعا
و "توابع بازفراخوانی شونده" باشند، که همگی قطعا بهتر از ترجمهٔ مشهور و ضعیف آن(توابع بازگشتی) می‌باشند. به هر حال، نگرش خوداتکاء یا بازگشتی در علم کامپیوتر یک روش فکر کردن برای حل مسائل است. در واقع خوداتکایی یا بازگشت یکی از ایده‌های اصلی علم کامپیوتر است. حل یک مسئله به روش خوداتکاء/بازگشتی بدین معناست که راه حل بستگی به مدل کوچکتری از صورت مسئله داشته باشد. "قدرت بازگشت قطعاً در این نهفته‌است که دسته‌ای نامتناهی از اشیا را بوسیلهٔ یک عبارت متناهی تعریف می‌کند. به معنای دیگر یک عدد نامتناهی در محاسبات
می‌کند. به معنای دیگر یک عدد نامتناهی در محاسبات می‌تواند بوسیلهٔ یک برنامهٔ متناهی بازگشتی تعریف شود حتی اگر این برنامه هیچ تکرار واضحی نداشته باشد ". اکثر زبان‌های برنامه نویسی سطح بالا عمل بازگشت را به این صورت تعریف می‌کنند که یک تابع خودش را فراخوانی کند. زبان‌های دستوری ساختارهای حلقه‌ای مثل codice_1 یا codice_2 را برای انجام کارهای تکراری به کار می‌گیرند. بعضی از زبان‌های تابعی هیچ ساختار حلقه‌ای تعریف نمی‌کنند اما بر خود بازگشت تکیه دارند که کد را به‌طور مکرر فراخوانی کند. نظریهٔ رایانش‌پذیری ثابت
مکرر فراخوانی کند. نظریهٔ رایانش‌پذیری ثابت کرده‌است که این زبان‌های فقط بازگشتی از نظر ریاضی برابر زبان‌های دستوری هستند، یعنی اینکه مسائل را بدون نیاز به codice_1 و codice_2 حل می‌کنند. الگوریتم‌های بازگشتی. در ریاضیات کاربردی و به خصوص کامپیوتر، مسائل فراوانی وجود دارد که حل آن‌ها را به سادگی می‌توان به صورت یک الگوریتم بازگشتی نشان داد. یک الگوریتم بازگشتی مانند یک تابع یا یک دنباله بازگشتی تعریف می‌شود فرمان‌های الگوریتم به‌طور مکرر و با پارامترهای مختلف اجرا می‌شوند تا به فرمان بنیادی الگوریتم برسیم.
اجرا می‌شوند تا به فرمان بنیادی الگوریتم برسیم. آنگاه تمام مقادیری را که محاسبهٔ آن‌ها انجام نشده‌است را به صورت بازگشتی محاسبه می‌نماییم تا فرمان مورد نظر اجرا شود. یک روش متداول برای آسان‌سازی مسائل این است که آن‌ها را به زیر مسائلی از همان نوع تقسیم بندی کنیم. این روش با نام گویشی کردن شناخته می‌شود. به عنوان یک تکنیک برنامه نویسی کامپیوتر، به این روش تقسیم و غلبه گفته می‌شود. و کلید راه حل تعداد زیادی از مسائل کامپیوتری مهم است و یک بخش اساسی می‌باشد. تمام زبان‌های برنامه‌نویسی که امروز مورد
می‌باشد. تمام زبان‌های برنامه‌نویسی که امروز مورد استفاده‌اند تعریفی مستقیم از توابع بازگشتی در خود دارند. وقتی چنین تابعی فراخوانی می‌شود، کامپیوتر(برای اکثر زبان‌هایی که پشته دارند) یا خود کد زبان instanceهای مختلف تابع را (با فراخوانی پشته، هر چند روش‌های دیگر هم مورد استفاده قرار می‌گیرند). برعکس آن همهٔ توابع بازگشتی می‌توانند به کمک پشته به یک تابع غیر بازگشتی تبدیل شوند. اکثر توابع و روش‌هایی که می‌توانند بوسیلهٔ کامپیوتر ارزشیابی شوند بدون استفاده از غیر بازگشتی کردن قابل بازگشتی شدن هستند.
از غیر بازگشتی کردن قابل بازگشتی شدن هستند. برنامه‌نویسی بازگشتی. بعضاً الگوریتم‌های بازگشتی را می‌توان به کمک زبان‌های برنامه‌نویسی پیاده‌سازی کرد که به این برنامه‌ها برنامه‌های بازگشتی گفته می‌شود. مانند الگوریتم‌های مرتب سازی، فاکتوریل، یافتن ب.م.م، و ... . در زیر به چند نمونه از برنامه‌های بازگشتی معروف اشاره می‌کنیم: نمونه‌های برنامه‌های بازگشتی. فاکتوریل. یک مثال متداول برای برنامه‌های بازگشتی، محاسبهٔ فاکتوریل برای اعداد طبیعی است: این تابع می‌تواند به شکل یک رابطه‌ی بازگشتی نیز نوشته شود: formula_2