title: کشتی با چوخه

text: مسابقه کشتی با چوخه در اصل رقابتی بدون مدت زمانی مشخص و وزن ورزشکاران بوده است و وقتی فردی در آن پیروز میدان اعلام می‌شده که بتواند ۲ بار پشت یا شانه‌های حریفش را به زمین برساند. اما اولین مقرراتی که برای کشتی با چوخه تدوین و ثبت شده است، مربوط به نشست ده تن از صاحب‌نظران و منتخبین پیشکسوتان ورزشی در خراسان بزرگ است که در روزهای دهم تا دوازدهم اردیبهشت سال ۱۳۵۶ در شهرستان مشهد برگزار شده است و این قوانین و مقررات تا سال ۱۳۹۵ با اصلاحات و تغییراتی به‌مورد اجرا گذاشته می‌شد. این قوانین و مقررات در تاریخ نوزدهم آذرماه سال ۱۳۹۵ در بجنورد و سپس در چهارم مرداد سال ۱۳۹۸ در مشهد به اهتمام انجمن چوخه کشور مجموعا با حضور حدود ۲۰۰ نفر از اساتید ورزشی، پیشکسوتان و صاحب‌نظران این رشته ورزشی در مجمع بازنگری در قوانین و مقررات کشتی‌با‌چوخه مورد بازبینی و بازنگری قرار گرفت. قوانین و مقررات چوخه؛ شامل ۳۷ ماده و ۳۲ تبصره پس از برگزاری مجامع بازنگری و تشکیل جلسات کارگروه‌های تخصصی با صرف ۵۰۰ نفر ساعت در جلسات شورای راهبردی انجمن چوخه کشور با کسب نظرات کارشناسی واحد دپارتمان ورزش‌های سنتی تطبیق شد و پس از تصویب فدراسیون ورزش روستایی و بازی‌های بومی‌محلی جمهوری اسلامی ایران جهت اجرا به ادارات کل ورزش و جوانان استان های کشور به شرح ذیل ابلاغ شده است و متن کامل آخرین قوانین و مقررات مصوب کشتی باچوخه که امروز با نام چوخه شناخته می شود؛ برای نخستین بار در این سایت منتشر می شود به شرح زیر است:


title: کشتی با چوخه

text: ماده ۱ ) اصطلاحات در این ورزش از اصطلاحات؛ چوخه، چوخه‌کار، لباس‌چوخه، کمربند‌چوخه، شلوارک‌چوخه، تشک‌چوخه، زمین‌چوخه، فنون‌چوخه، تکنیک‌چوخه، مربی‌چوخه، داور‌چوخه، جدول‌نویس‌چوخه، لیگ‌چوخه و مسابقات‌چوخه استفاده می‌شود.


title: کشتی با چوخه

text: ماده ۲ ) محدوده اجرا این مقررات مخصوص برگزاری مسابقات چوخه در سطح شهرستان، استان و کشور می باشد.


title: کشتی با چوخه

text: ماده ۳ ) مسئولیت برگزاری مسابقات مسئولیت برگزاری مسابقات چوخه در حوزه‌های جغرافیایی استان ها و شهرستان ها به ترتیب بر عهده رؤسای انجمن‌ها/کمیته‌های چوخه استان ها/شهرستان ها و برگزاری مسابقات چند‌جانبه بین استان‌ها، کشوری و لیگ بر عهده فدراسیون ورزش روستایی و انجمن چوخه کشور می باشد.


title: کشتی با چوخه

text: تبصره ۱: مسئول برگزاری مسابقات موظف است تمام قوانین و مقرات چوخه را رعایت کند.


title: کشتی با چوخه

text: تبصره ۲: ابلاغ مسئولین برگزاری در مسابقات چند جانبه بین استان‌ها و کشوری از سوی فدراسیون ورزش روستایی و انجمن چوخه کشور صادر می‌شود و در مسابقات داخل استانی از سوی انجمن/کمیته چوخه استان و در مسابقات داخل شهرستان از سوی انجمن/کمیته چوخه شهرستان صادر می‌شود.


title: کشتی با چوخه

text: تبصره ۳: مربیان، سرپرستان تیم‌ها و چوخه‌کاران شرکت کننده در مسابقات نمی‌توانند و نباید در کادر برگزاری همان دوره از مسابقات، دخالت نموده مسئولیت و حتی عضویت داشته باشند.


title: کشتی با چوخه

text: ماده ۴ ) ناظرین مسابقات نظارت بر حسن برگزاری مسابقات و رعایت کامل قوانین و مقررات این رشته ورزشی در مسابقات چند‌جانبه بین استان‌ها، مسابقات لیگ و مسابقات کشوری برعهده نمایندگان فدراسیون ورزش روستایی/انجمن چوخه کشور می باشد و در سایر مسابقات، حسب مورد برعهده هیئت‌های ورزش روستایی استان ها و شهرستان ها و انجمن‌ها/کمیته‌های چوخه شهرستان‌ها می‌باشد.


title: کشتی با چوخه

text: ماده ۵ ) کادر برگزاری مسابقات عبارتند از: – مسئول برگزاری مسابقات – سرپرست فنی مسابقات – مسئول کمیته فنی – مسئول کمیته اجرایی – مسئول کمیته داوران – مسئول کمیته انتظامات – مسئول نیروهای انتظامی – مسئول جدول مسابقات – مسئول اکیپ پزشکی یا پزشک‌یار – مسئول اکیپ فیلم‌برداری و بازبینی – مسئول اسکوربرد و وقت‌نگهدار


title: کشتی با چوخه

text: ماده ۶ ) زمین یا تشک مسابقه مسابقات چوخه در فضاها و سالن‌های سرپوشیده یا در فضاهای ورزشی روباز و روی زمین یا تشک‌چوخه در ابعاد ۱۰×۱۰ و یا ۱۲×۱۲ متر‌مربع ( به‌اضافه حداقل ۲ متر از طرفین برای فضای امن ) برگزار می‌شود و درصورتی‌که امکانبرگزاری مسابقات در چنین فضاهایی وجود نداشته باشد، مسابقات می‌تواند در روی زمین پوشیده از چمن طبیعی یا زمین پوشیده از مخلوط ماسه بادی و خاک اره / خاک نرم سرند شده و خط‌کشی‌شده برگزار می شود.


title: کشتی با چوخه

text: ماده ۷ ) لباس چوخه چوخه کار باید شخصا زیرپوش، بالاپوش چوخه، شال چوخه و شلوارک چوخه را تهیه نموده و با پوشیدن لباس استاندارد چوخه در مسابقات حضور یابد.


title: کشتی با چوخه

text: تبصره ۱: داور وسط باید در طول مسابقه بر سلامتی ظاهری و پوشش صحیح لباس چوخه کاران دقت کامل داشته باشد تا در زمان مسابقه؛ شال کمر باز یا پاره نشود، پارچه شلوارک چوخه پایین نیامده و دچار پارگی نگردد و بخش تاخورده‌ی بالاپوش نیز باز نشده و دچار پارگی نشود. تبصره ۲: در صورت پارگی و یا نقص موثر لباس‌چوخه‌کار شامل: بالاپوش،شلوارک و شال‌کمر بایستی با موافقت و دستور داور وسط نسبت به رفع نقص و یا تعویض فوری(حداکثر در مدت دو دقیقه)، اقدام گردد، در غیر این‌صورت حریف او برنده می‌باشد.


title: کشتی با چوخه

text: تبصره ۳: به همراه داشتن انگشتر و اشیاء فلزی چوخه‌کاران در مسابقات ممنوع است.


title: کشتی با چوخه

text: تبصره ۴ : لباس چوخه‌کار باید تمیز، خشک و بدون بو باشد.


title: کشتی با چوخه

text: تبصره ۵ : پوشیدن کفش در مسابقات چوخه ممنوع است.


title: کشتی با چوخه

text: تبصره ۶ : بهداشت فردی چوخه‌کاران باید رعایت شده و ناخن‌های دست و پای آنان کوتاه باشد.


title: کشتی با چوخه

text: الف ) بالاپوش‌چوخه: از جنس جاجیم یا پارچه ضخیم و پردوام به رنگ آبی و قرمز می‌باشد و بلندی آن تا پشت ران (که از سر زانو بلندتر نیست) و دارای آستین کوتاه حدفاصل آرنج و شانه با گشادی حداقل پنج سانتی‌متر می باشد به طوری‌که دست حریف (انگشتان دست)، به‌راحتی در آن جا گیرد و آستین کت تا بازو بالا کشیده و تا شود.


title: کشتی با چوخه

text: ب ) شلوارک‌چوخه : این بخش از لباس چوخه کار از جنس پارچه مقاوم، پردوام، به رنگ سیاه با بند پنبه‌ای دوخته می شود که باید روی شورت پوشیده و لبه‌ی شلوارک تا بیخ ران تا زده شود به‌طوری‌که بشود با انگشتان دست حریف گرفته شود.


title: کشتی با چوخه

text: پ ) زیرپوش (عرق‌گیر): پوشیدن زیرپوش به رنگ سفید و آستین‌دار تا بالای آرنج و بدون تبلیغات در زیر بالا‌پوش‌چوخه برای چوخه کاران الزامی است.


title: کشتی با چوخه

text: ث ) شال‌کمر‌چوخه: چوخه کاران باید ۲ عدد شال به رنگ آبی و قرمز از جنس نخ محکم و فشرده به عرض ۴۰ سانتی‌متر و طول ۲ متر که «دو لا» دوخته شده باشد تهیه نمایند به طوری که دست چوخه کاران را بدون آسیب پر نماید.


title: کشتی با چوخه

text: ماده ۸ ) گروه‌های سنی الف ) گروه سنی نوجوانان: ( داشتن ۱۴ سال تمام تا ۱۷ سال تمام )


title: کشتی با چوخه

text: ب ) گروه سنی جوانان: ( از شروع ۱۸ سالگی تا ۲۰ سال تمام )


title: کشتی با چوخه

text: پ ) گروه سنی بزرگسال: از شروع ۲۱ سالگی به بالا (جوانان دارای ۱۸ سال تمام و بالاتر هم مجاز به مسابقه در این گروه هستند).


title: کشتی با چوخه

text: تبصره ۱: چوخه‌کاران گروه سنی نوجوانان و جوانان می بایست رضایت‌نامه‌محضری جهت شرکت در مسابقات را به سرپرست مسابقات ارائه نمایند.


title: کشتی با چوخه

text: تبصره ۲: داشتن رضایت‌نامه‌محضری برای چوخه‌کار زیر ۱۸ سال که بخواهد در مسابقات گروه سنی بزرگسالان شرکت نماید، الزامی است.


title: کشتی با چوخه

text: ماده ۹) وزن‌ها الف ) نوجوانان : ۵۰- ، ۵۵- ، ۶۱- ، ۶۸- ، ۷۶- ، ۹۰- کیلوگرم.


title: کشتی با چوخه

text: تبصره: چوخه‌کاران می توانند در مسابقات گروه سنی نوجوانان شرکت کنند که سن آنها کمتر از ۱۴سال تمام و بیشتر از ۱۷ سال تمام نباشد و وزن آنها نیز کمتر از ۴۵ کیلوگرم و بیشتر از ۹۰ کیلوگرم نباشد.


title: کشتی با چوخه

text: ب ) جوانان : ۵۵- ، ۶۰- ، ۶۶- ، ۷۴- ، ۸۴-، ۱۰۵- کیلوگرم.


title: کشتی با چوخه

text: تبصره: چوخه کاران می توانند در مسابقات گروه سنی جوانان شرکت کنند که سن آنها کمتر از ۱۷ سال تمام و بیشتر از ۲۰ سال تمام نباشد و وزن آنها نیز کمتر از ۵۰ کیلوگرم و بیشتر از ۱۰۵ کیلوگرم نباشد.


title: کشتی با چوخه

text: پ ) بزرگسالان : ۶۶- ، ۷۴- ، ۸۴- ، ۹۶- و ۹۶+ کیلوگرم.


title: کشتی با چوخه

text: تبصره ۱: چوخه کارانی می توانند در مسابقات گروه سنی بزرگسالان شرکت کنند که سن آنها بیشتر از ۱۸ سال تمام و وزن آنها کمتر از ۶۰ کیلوگرم نباشد.


title: کشتی با چوخه

text: تبصره ۲: هر چوخه‌کار در صورت درخواست کتبی خود می‌تواند فقط در یک وزن، بالاتر از وزن خود در مسابقات شرکت کند.


title: کشتی با چوخه

text: ماده ۱۰ ) آوانس یا ارفاق وزن در تمام وزن‌های مسابقات کلیه گروههای سنی مختلف، هیچ‌گونه ارفاق و آوانسی وجود ندارد.


title: کشتی با چوخه

text: ماده ۱۱ ) شرایط شرکت چوخه کاران در مسابقات ورزشکارانی مجاز به شرکت در مسابقات چوخه می باشند که توسط انجمن / کمیته چوخه استان یا شهرستان، به اداره کل ورزش و جوانان استان یا اداره ورزش و جوانان شهرستان معرفی شده و سپس با معرفی‌نامه عکس‌دار از اداره کل یا اداره ورزش و جوانان، به سرپرست مسابقات معرفی شوند.


title: کشتی با چوخه

text: تبصره ۱: هر استان یا شهرستان برای شرکت در مسابقات استانی و شهرستانی می‌تواند یک‌نفر سرپرست، یک‌نفر مربی، یک‌نفر راننده و در هر وزن حداکثر دو نفر چوخه‌کار جهت هر دوره از مسابقات معرفی نماید.


title: کشتی با چوخه

text: تبصره ۲: هر چوخه کار در طول سال (از ابتدای فروردین تا پایان اسفند همان سال) فقط می‌تواند از یک شهرستان یا استان توسط ادارات کل ورزش و جوانان استان یا اداره ورزش و جوانان شهرستان به مسابقات مختلف معرفی شود.


title: کشتی با چوخه

text: تبصره ۳: چوخه کارانی که به‌عنوان عضو یک تیم ورزشی چوخه در یک باشگاه ورزشی، قرارداد منعقد می‌کنند می توانند در قالب مسابقات لیگ چوخه در کلیه مسابقات باشگاهی شرکت نمایند.


title: کشتی با چوخه

text: تبصره ۴: داشتن و ارائه اصل کارت ملی و اصل کارت بیمه ورزشی معتبر


title: کشتی با چوخه

text: ماده ۱۲ ) داوران مسابقات هر زمین/تشک مسابقه توسط ۳ نفر داور و یک‌نفر داور وقت نگهدار با ترکیب زیر اداره می شود : – یک‌نفر داور وسط – دو نفر داور کنار ( رئیس تشک و قاضی مسابقه) – یک نفر وقت نگه‌دار با پوشش متفاوت از لباس داوران.


title: کشتی با چوخه

text: تبصره ۱: انتخاب داوران مسابقات چوخه کشوری،استانی و شهرستانی به عهده رئیس کمیته داوران مربوط به آن مسابقه می باشد.


title: کشتی با چوخه

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


title: کشتی با چوخه

text: تبصره ۴: رقابت‌های حساس و رده‌بندی و فینال چوخه کاران توسط زودتر این داوران شوخ داوری می‌شود. تبصره ۵: افرادی‌که مدرک داوری چوخه ندارند نمی‌توانند و نباید در هیچ‌یک از مسابقات چوخه داوری کنند. تبصره ۶: تعداد داوران مورد نیاز هر مسابقات بر اساس تعداد هر تشک چوخه یا زمین مسابقه در طول یک روز، بین ۶ تا ۸ نفر داور و یک‌نفر وقت نگهدار تعیین می‌گردد.


title: کشتی با چوخه

text: ماده ۱۳ ) لباس داوران لباس داوران چوخه در سطح کشور یکسان می باشد و شامل: تی‌شرت سفید با آرم فدراسیون ورزش روستایی و انجمن چوخه کشور، کفش کتانی سفید و شلوار سورمه‌ای به‌همراه سوت و مچ بند با دو رنگ آبی و قرمز است که بایستی توسط هر یک از داوران چوخه تهیه گردد.


title: کشتی با چوخه

text: ماده ۱۴ ) موقعیت و وظایف داور وسط داور وسط اصولاً روی تشک یا زمین مسابقه مستقر می‌شود و مسابقه را مدیریت می کندو از سوت و مچ‌بند (به رنگ آبی و قرمز) استفاده می‌کند و همواره فاصله خود را به‌طور فعال و مستمر با چوخه‌کاران حفظ می‌کند و از این‌که تماشاگران، عوامل اجرایی و انتظامی، خبرنگاران و تصویربرداران در وضعیتی قرار گرفته باشند که مزاحم مبارزه چوخه کاران نباشند، اطمینان حاصل می‌نماید.


title: کشتی با چوخه

text: ماده ۱۵ ) وضعیت آراء داوران الف) رئیس تشک‌چوخه یا زمین‌مسابقه باید رای خود را بعد از رای داور وسط و قاضی تشک اعلام نماید. ب ) در صورت اختلاف نظر بین داور وسط و قاضی، تایید کننده نهایی رای، رئیس تشک است و دو داور کناری باید ضمن اعلام برنده مسابقه، فرم مخصوص داوری را تکمیل، امضاء و به سرپرست فنی مسابقات تحویل نمایند.


title: کشتی با چوخه

text: پ ) قاضی مسابقه ضمن نظارت بر مسابقه و تغییرات تابلو امتیازات (اسکوربرد) نتایج را در برگ داوری ثبت می‌کند و هنگامی که داور وسط امتیازی به چوخه‌کار می دهد، رای خود را به رئیس تشک اعلام می‌کند. ث ) داور وسط با دو داور کناری (رئیس تشک و قاضی) در قضاوت هماهنگ می باشد و سه نفر اعضای کمیته فنی نیز باید تسلط کامل بر مسابقه داشته و در طول مسابقه نیز کاملاً بر اجرای فنون و امتیازات رد و بدل شده، تسلط کامل داشته باشند.


title: کشتی با چوخه

text: ماده ۱۶ ) جدول نویسی سرپرست مسابقات؛ یک نفر از افراد متخصص در امر جدول نویسی را به همراه دو نفر دیگر برای جدول‌نویسی مسابقات تعیین می کند تا زیر نظر مستقیم وی و با همکاری سرپرست فنی مسابقات، جدول مسابقات را به‌صورت یک‌حذفی تنظیم کند و به کمک همکاران خود نسبت به ثبت نتایج و تکمیل جدول رقابت‌های چوخه‌کاران، از ابتدا تا انتهای مسابقات اقدام نماید.


title: کشتی با چوخه

text: ماده ۱۷ ) کمیته فنی مسابقات سرپرست مسابقات؛ یک نفر از افراد معتمد و متخصص در رشته ورزشی چوخه را که دارای عناوین قهرمانی باشد و بتواند وظیفه نظارت فنی بر مسابقات را به خوبی انجام دهد به عنوان مسئول کمیته فنی و دو نفر دیگر از پیشکسوتان این رشته ورزشی را به عنوان اعضای کمیته فنی انتخاب می کند تا زیر نظر مستقیم وی انجام وظیفه نمایند.


title: کشتی با چوخه

text: ماده ۱۸ ) وظایف کمیته فنی الف ) اعضای کمیته فنی بر کلیه امور فنی مسابقات و رقابت‌های چوخه‌کاران نظارت می نمایند.


title: کشتی با چوخه

text: ب ) مسئول کمیته فنی در هنگام بازبینی فیلم مسابقات، تصمیم‌گیری در مورد تقلب احتمالی چوخه‌کار در وزن کشی و همچنین در مورد تبانی و تمارض احتمالی چوخه‌کاران به عنوان عضو هیئت سه نفره داوری خواهد بود.


title: کشتی با چوخه

text: پ ) کمیته فنی می‌تواند در تنش‌های احتمالی طرف مشورت سرپرست مسابقات قرار گرفته و به ایجاد آرامش و حفظ آن در مسابقات کمک نمایند.


title: کشتی با چوخه

text: ت ) انتخاب فنی‌ترین چوخه‌کار و با اخلاق‌ترین چوخه‌کار مشترکان به عهده سرپرست فنی مسابقات، مسئول کمیته فنی مسابقات و مسئول کمیته داوران مسابقات می باشد .


title: کشتی با چوخه

text: ث ) اخطار سوم به چوخه‌کار با تایید کمیته فنی داده خواهد شد.


title: کشتی با چوخه

text: ج ) چنانچه هر سه داور مسابقه، هم‌رای باشند، کمیته فنی، حق دخالت در آن مسابقه را ندارد.


title: کشتی با چوخه

text: ماده ۱۹ ) بازبینی فیلم مسابقات وجود دوربین‌های فیلم‌برداری و مانیتور متناسب با تعداد تشک الزامی است و مسئول بازبینی فیلم مسابقات می‌تواند با استفاده صحیح و به‌موقع از این تجهیزات، نقش مهمی در رفع ابهامات داوران و رفع اعتراضات احتمالی مربیان، چوخه‌کاران و طرفداران آنها در مسابقات را ایفا نمایند.


title: کشتی با چوخه

text: الف ) سرپرست فنی مسابقات در صورت اعتراض مربی چوخه‌کار و درخواست بازبینی فیلم مسابقه به همراه مسئول کمیته فنی و مسئول کمیته داوران (به‌عنوان اعضای هیات سه نفری داوری مسابقات)، فیلم مسابقه‌ی مورد اختلاف را بازبینی نموده و نتیجه داوری را جهت اعمال رای، به داور وسط ابلغ می نماید.


title: کشتی با چوخه

text: ب ) در صورت رد اعتراض مربی، به حریف مقابل یک امتیاز داده خواهد شد.


title: کشتی با چوخه

text: ماده ۲۰ ) انضباط مسابقات هرگونه بی‌نظمی و اخلال در مسابقات توسط هر یک از مسئولین و اعضای کادر برگزاری مسابقات، چوخه‌کاران و تماشاگران تیم‌ها و سایر افراد، موجب اخذ تصمیمات و محرومیت ها توسط کمیته انظباطی می‌گردد.


title: کشتی با چوخه

text: ماده ۲۱ ) محرومیت‌ها الف ) چوخه کاری که به هر دلیل از تصمیمات داوران سرپیچی کند و طبق نظریه کمیته فنی و کمیته انضباطی و تایید سرپرست مسابقات، هتک حرمت نماید از مسابقات حذف می شود و برایش توسط کمیته انظباطی از ۲ ماه تا ۶ ماه محرومیت از شرکت در کلیه مسابقات ورزشی در نظر گرفته می‌شود.


title: کشتی با چوخه

text: ب ) اهانت چوخه‌کار به رقیب و تماشاگران بر اساس نظر کمیته فنی و کمیته انضباطی و تایید سرپرست مسابقات با ۲ ماه تا ۶ ماه محرومیت از شرکت در مسابقات ورزشی مواجه خواهد شد.


title: کشتی با چوخه

text: پ ) درصورتی‌که چوخه‌کاران تبانی کنند و آن‌طوری که وظیفه دارند، مبارزه نکنند و یا به‌طور ساختگی زورآزمایی کنند و یا بدون آسیب‌دیدگی که کتباً مورد تأیید پزشک یا پزشک‌یار مسابقات باشد، مسابقه را به حریف ببازند، به‌منزله‌ی تبانی در مسابقات تلقی خواهد شد و بر پایه‌ی تصمیم هیات سه نفری داوری مسابقات شامل: سرپرست فنی مسابقات به‌عنوان رئیس و مسئول کمیته فنی و مسئول کمیته داوران به‌عنوان اعضای این هیات، بازنده و از ادامه‌ی مسابقات محروم می‌شوند و توسط کمیته انضباطی برای این‌گونه افراد، بین ۲ ماه تا ۶ ماه محرومیت از شرکت در مسابقات ورزشی در نظر گرفته خواهد شد.


title: کشتی با چوخه

text: ت ) ورزش‌کاران و چوخه‌کارانی که آزمایش دوپینگ آن‌ها توسط فدراسیون پزشکی ورزشی کشور مثبت اعلام شده باشد و یا اعلام شود.


title: کشتی با چوخه

text: ث ) تقلب در وزن‌کشی.


title: کشتی با چوخه

text: ماده ۲۲ ) هیات داوری مسابقات الف ) ترکیب اعضاء هیئت سه نفره داوری مسابقات از سه نفر با ترکیب زیر تشکیل می شود و تصمیمات آن با حداقل دو رای از سه رای اجرا می گردد: ۱. سرپرست فنی مسابقات به عنوان رئیس هیئت داوری. ۲. مسئول کمیته فنی و مسئول کمیته داوران به عنوان دو عضو دیگر این هیات. ب ) وظایف هیات داوری: ۱. بازبینی فیلم مسابقات طبق بند الف ماده ۱۹ و اعلام رای خود به داور وسط. ۲. بررسی مسائل تبانی و تمارض احتمالی چوخه‌کاران و اعلام رای خود به کمیته انضباطی مسابقات جهت اعمال محرومیت‌های قانونی. ۳. بررسی شکایات احتمالی در خصوص تقلب در وزن کشی‌ها و اعلام به کمیته انضباطی مسابقات جهت اعمال محرومیت‌های قانونی. ۴. انتخاب فنی‌ترین چوخه‌کار و با اخلاق‌ترین چوخه‌کار


title: کشتی با چوخه

text: ماده ۲۳ ) اکیپ پزشکی یا پزشک‌یار حضور اکیپ پزشکی یا پزشک‌یار به همراه کیف اورژانس امدادگری و کمک‌های اولیه در تمام مسابقات چوخه الزامی است و برگزاری مسابقات بدون حضور پزشک یا پزشک‌یار و آمبولانس، ممنوع است. ماده ۲۴ ) شرایط برد با ضربه فنی الف) سایه انداختن شانه‌ها و تماس شانه‌های چوخه کار با زمین یا تشک. ب ) چرخش حول محور شانه‌ها روی آرنج با تماس باسن. پ ) تکیه دادن به آرنج‌ها در شرایطی که چوخه کار با باسن روی زمین یا تشک قرار گیرد. ت ) لحظه‌ای که فنی از سر پا اجرا گردد و حریف به خاک بیفتد ولی بلافاصله، فنی بدون عوض شدن دست اجرا گرددکه منجر به ضربه فنی شود، ضربه فنی پذیرفته است. ث ) سه اخطاره شدن.


title: کشتی با چوخه

text: ماده ۲۵ ) شرایط برد با امتیاز فنی الف ) در صورتی که چوخه‌کار با اجرای فم، حریف را به روی شکم ببرد و اصطلاحا او را خاک نمایدو تسلط بر او پیدا کند مجری فن یک امتیاز کسب می‌کند.


title: کشتی با چوخه

text: ب ) چنانچه فن در داخل تشک اجرا شود و حریف در خارج از محدوده‌ی تشک یا زمین‌چوخه ضربه فنی شود، دو امتیاز به مجری فن داده می‌شود.


title: کشتی با چوخه

text: پ ) در صورت کم‌کاری و هل‌دادن، دفاع و نافرمانی از دستورات داور وسط، به چوخه‌کار کم‌کار و خاطی برای بار اول تذکر و در صورت تکرار اخطار داده می‌شود و به حریفش نیز یک امتیاز داده خواهد شد.


title: کشتی با چوخه

text: ت ) چنانچه چوخه‌کار در جریان مسابقه بعد از سوت داور تکنیک و فن اجرا کند هیچ‌گونه امتیازی به مجری فن داده نمی‌شود و داور بایستی به چوخه‌کاری که بعد از سوت داور اجرای فن کرده، تذکر دهد.


title: کشتی با چوخه

text: ث ) اگر چوخه کار در جریان مسابقه، هم‌زمان با سوت داور یا قبل از آن، تکنیک و فن اجرا کند، درست می‌باشد و داور باید امتیاز اجرای فن را بدهد.


title: کشتی با چوخه

text: ج ) اگر زمان اجرای فن با پایان مسابقه تلاقی کند و منجر به امتیاز فنی شود، امتیاز داده خواهد شد در غیر این‌صورت حالت اجرا، منجر به کسب امتیاز نخواهد شد.


title: کشتی با چوخه

text: چ ) اگر اختلاف امتیاز بین دو چوخه‌کار به عدد ۶ برسد مبارزه تمام و چوخه‌کار دارای شش امتیاز بیشتر به‌عنوان برنده با ضربه فنی اعلام می‌گردد .


title: کشتی با چوخه

text: ماده ۲۶ ) زمان و شرایط وزن‌کشی الف ) وزن‌کشی در مسابقات استانی و کشوری از ساعت ۱۷ الی ۲۰ روز قبل از مسابقات انجام می‌شود.


title: کشتی با چوخه

text: تبصره ۱: در مواردی که به تشخیص سرپرست مسابقات و مسئول کمیته فنی و مسئول کمیته داوری مسابقات به زمان بیشتری برای وزن‌کشی نیاز باشد؛ ساعت وزن کشی تا ۲ ساعت قابل افزایش است.


title: کشتی با چوخه

text: تبصره ۲: وزن‌کشی از افرادی‌که مروج تبلیغ فرهنگ مغایر با فرهنگ پهلوانی و ارزش‌های دینی و ملی باشند و یا بر روی بدن خود خال‌کوبی و آرایش‌های نامتعارف داشته باشند، ممنوع است.


title: کشتی با چوخه

text: ب ) وزن‌کشی از افرادی‌که دارای اصل معرفی‌نامه عکس‌دار از اداره کل یا اداره ورزش و جوانان ممهور به مهر این ادارات باشند، انجام می‌شود.


title: کشتی با چوخه

text: تبصره ۳: قرعه‌کشی چوخه‌کاران؛ هم‌زمان با وزن‌کشی و برداشتن شماره تصادفی توسط آنان با حضور اکثریت سرپرستان تیم‌های شرکت کننده در مسابقات انجام می‌شود.


title: کشتی با چوخه

text: تبصره ۴ : نتایج حاصل از قرعه کشی به امضای اکثریت سرپرستان تیم‌های شرکت‌کننده در قرعه‌کشی می‌رسد و نسخه ای از آن در اختیار سرپرستان کلیه تیم ها، سرپرست فنی، رئیس کمیته فنی، رئیس کمیته داوران و رئیس کمیته انظباطی مسابقات قرار داده می شود.


title: کشتی با چوخه

text: ماده ۲۷ ) شروع مسابقه مسابقه ابتدا با کسب اجازه داور وسط از کادر داوری و سپس سوت داور وسط شروع خواهد شد.


title: کشتی با چوخه

text: ماده ۲۸ ) مدت مسابقه الف ) نوجوانان : مدت مسابقه نوجوانان یک وقت چهار دقیقه‌ای می‌باشد که در صورت عدم نتیجه یا تساوی، دو دقیقه وقت اضافه با سی ثانیه استراحت، منظور می‌گردد و با کسب اولین امتیاز توسط هر یک از چوخه‌کاران، مبارزه قطع و چوخه‌کاری که در طی این دو دقیقه، اولین امتیاز را کسب کند، برنده‌ی مسابقه خواهد بود.


title: کشتی با چوخه

text: تبصره : اگر در پایان رقابت، هر دو حریف از نظر امتیازات مساوی باشند یا هیچ امتیازی را به دست نیاورند هر کدام از حریفان که سبک‌تر باشند، برنده مسابقه اعلام می‌گردد.


title: کشتی با چوخه

text: الف ) جوانان و بزرگ‌سالان: مدت مسابقه جوانان و بزرگ‌سالان یک وقت پنج دقیقه‌ای می‌باشد که در صورت عدم نتیجه یا تساوی، دو دقیقه وقت اضافه با سی ثانیه استراحت، منظور می‌گردد و با کسب اولین امتیاز توسط هر یک از چوخه‌کاران، مبارزه قطع و چوخه‌کاری که در طی این دو دقیقه، اولین امتیاز را کسب کند، برنده‌ی مسابقه خواهد بود.


title: کشتی با چوخه

text: ماده ۲۹ ) واگذاری یا انصراف از مسابقه چوخه‌کاران به‌هیچ‌وجه حق بخشیدن مسابقه و یا انصراف از مسابقه به‌نفع حریف را ندارند و باید مبارزه کنند، چوخه کار بازنده باید در میدان با لباس کامل این رشته ورزشی حضور یابد تا برنده مشخص شود.


title: کشتی با چوخه

text: ماده ۳۰ ) عدم حضور در میدان مسابقه چنانچه ورزشکاری بعد از سه مرتبه اعلام مجری مسابقات در میدان مسابقه حاضر نشود بازنده اعلام می‌گردد و کمیته انظباطی بایستی برایش از ۲ ماه تا ۶ ماه محرومیت در نظر بگیرد.


title: کشتی با چوخه

text: تبصره : درصورتی‌که چوخه‌کاری بدون تایید کتبی آسیب‌دیدگی توسط پزشک یا پزشک‌یار مسابقات در میدان مسابقه حاضر نشود و مبارزه نکند به منزله تبانی تلقی خواهد شد و کمیته انضباطی برای ورزشکار خاطی از ۲ ماه تا ۶ ماه محرومیت در نظر خواهد گرفت.


title: کشتی با چوخه

text: ماده ۳۱ ) موارد اخطار و تذکر الف ) اجرای کلیه فنونی که از زانو به پایین با دست اجرا گردد از جمله: ۱. انواع زیرگیری از زانو به پایین ۲. انواع بز کشی و گرفتن زیر یک خم یا دو خم از ناحیه زانو به پایین.


title: کشتی با چوخه

text: ب ) اجرای میان‌کوب پایین‌تر از زانو و قرار دادن ساق پای حریف بین دو ران.


title: کشتی با چوخه

text: پ ) گذاشتن کف پا روی ران و یا روی پای حریف به منظور متوقف نمودن مبارزه.


title: کشتی با چوخه

text: ت ) گرفتن یقه‌ی حریف به‌صورت ضربدری و کشیدن بالاپوش چوخه بر سر حریف جلوگیری از دید حریف و یا یک دست هر دو یقه‌ی حریف را از ناحیه گلو گرفتن.


title: کشتی با چوخه

text: ث ) گرفتن پنجه دست و زدن به سر و صورت حریف.


title: کشتی با چوخه

text: ج ) اجرای کلیه فنونی که بر خلاف جهت مفاصل باشد از جمله گرفتن و پیچاندن انگشتان بر خلاف مفصل.


title: کشتی با چوخه

text: چ ) اجرای فنون غیرمجاز و ضربه زدن عمدی مثل گرفتن گردن حریف با یک دست یا دو دست.


title: کشتی با چوخه

text: ح ) کم‌کاری و فرار کردن چوخه‌کار.


title: کشتی با چوخه

text: ماده ۳۲ ) ورود و خروج از میدان مسابقه الف) اگر ورود چوخه‌کار رقیب به میدان مسابقه و خروج آنها از میدان با اجازه و سوت داوری انجام نشود، اخطار دارد.


title: کشتی با چوخه

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


title: کشتی با چوخه

text: ت ) اگر چوخه‌کاران در زمان هماوردی و اجرای تکنیک و فن به بیرون از زمین مسابقه بروند اخطار ندارد.


title: کشتی با چوخه

text: ماده ۳۳ ) اخطار کم‌کاری و هل‌دادن وقتی‌که داور می‌خواهد به یکی از چوخه‌کاران تذکر دهد با اشاره‌ی دست نسبت به تذکر کم‌کاری، هل‌دادن و مانند آن اقدام می‌نماید.


title: کشتی با چوخه

text: ماده ۳۴ ) وقت تلف شده زمان‌های تلف شده بین مسابقه ( توقف‌های غیر قابل قبول) جزء زمان مسابقه محسوب نمی‌شود.


title: کشتی با چوخه

text: ماده ۳۵) پایان مسابقه و اعلام نتیجه پایان هر مسابقه با ضربه فنی یا امتیاز بیشتر توسط داور وسط مشخص می‌گردد و داور وسط با بلند کردن دست برنده مسابقه، وی را در دو جهت میدان معرفی می‌کند.


title: کشتی با چوخه

text: ماده ۳۶ ) آسیب‌دیدگی زمان درمان چوخه‌کار آسیب‌دیده حداکثر دو دقیقه اعلام می‌شود و درصورتی‌که پزشک یا پزشک‌یار مسابقه تشخیص دهد که چوخه‌کار مصدوم نمی‌تواند و یا نباید به مسابقه ادامه دهد، نتیجه به نفع حریف او مقابل اعلام می شود.


title: کشتی با چوخه

text: ماده ۳۷ ) وظایف میزبان مسابقات مسئولیت تهیه و تامین کلیه وسایل مورد نیاز مسابقات و انجام کلیه امور پشتیبانی اعم از اسکان و تغذیه و ایاب و ذهاب چوخه کاران شرکت‌کننده در مسابقات، سرپرستان، مربیان و کادر برگزاری مسابقات، از محل اسکان آن‌ها به محل‌های وزن‌کشی مسابقات و پذیرایی به عهده میزبان است.


title: کشتی با چوخه

text: تبصره : نظارت بر حسن انجام وظایف میزبانی حسب مورد بر عهده نماینده فدراسیون ورزش روستایی، انجمن چوخه کشور، انجمن/کمیته چوخه استان و شهرستان می باشد.


title: کشتی با چوخه

text: جوایز کشتی با چوخه نیز به سبب ماهیت سنتی و ملی اش متفاوت است. در اصطلاح به فاتحان میدان چوخه «قند» اهدا می‌شود، کسی که نفر اول شود قند اول را به او می‌دهند و نفرات دوم و سوم هم به تناسب قندهای دیگر می‌گیرند. در کنار قند، هدایایی نظیر شتر، قوچ، قالی و گوسفند، لوازم منزل، وجه نقد و سکه عاید پهلوانان این مسابقات می‌شود. غالباً به‌طور سنتی جوایز کشتی با چوخه از نمادهای زندگی عشایری و روستایی در نظر گرفته می‌شود. گاهی اوقات نیز از دست بافته‌های عشایر نظیر قالی و جاجیم و گلیم استفاده می‌شود. البته این جوایز می‌تواند در مناطق مختلف متفاوت باشد، مهم این است که جوایز متناسب با شأن این ورزش بوده و پشتوانه‌ای برای کشتی‌گیر باشد.


title: کشتی با چوخه

text: مسابقات کشتی با چوخه خراسان قبل از آمدن روی تشک در سرای خان‌ها، عروسی‌ها، روز عید فطر و ۱۴ فروردین روی چمن و خاک نرم برگزار می‌شد. کشتی با چوخه از دیرباز معمولاً در دل طبیعت و محیط‌های باز برگزار می‌شده‌است. چنانچه اکثر گودهای کشتی با چوخه کنونی که از قدیم دایر بوده‌اند، مانند گود پهلوان ججو در ریواده، گود زیارتگاه سلطان زیرابه در روستای امام وردی خان قوچان، گود روستای رهورد در قوچان، گود زینل خان در اسفراین، گود امام مرشد در فاروج و دیگر گودها که در مناطق تفریحی و دامان طبیعت قرار دارند.


title: کشتی با چوخه

text: کشتی روی خاک نرم یا چمن و با حضور انبوه تماشاگرانی از زن و مرد و پیر و جوان برگزار می‌شود. امروزه این مسابقات در اواسط زمستان و در بهمن ماه در مانه و سملقان، هشتم فروردین در ریواده، ۱۲ فروردین هر سال در شیروان، ۱۳ فروردین در بجنورد به صورت استانی با حضور پهلوانان نامدار این خطه برگزار می‌شود. اما رقابت‌های اصلی و ملی همه ساله در روز ۱۴ فروردین در گود زینل خان شهرستان اسفراین برگزار می‌شود.پشم چینی گوسفندان در خراسان شمالی بین کردها به پز برین معروف است در این میان به وسیلهٔ "هورینگ" یا همان قیچی پشم زنی، به سراغ بره‌هایی که پشم حنایی و زیبا دارند می‌روند، به پشم چیده شده که اولین بار بدست ممی آید "لواگ می‌گویند. سایر پشم‌هایی که چندین بار از بدن گوسفندان بزرگتر چیده می‌شود "هری" می‌نامند. لوا بدست آمده شسته، سپس حلاجی و «تیت» شده آنگاه به وسیلهٔ دوک یا تشی آن پشم‌ها را می‌ریسند تا توپ نخ و گریف بدست آید. سپس دار یا «تون» آماده می‌شود و نخ‌ها در کنار هم یکرنگ و همدست بافته می‌شوند و پارچه‌ای که از لوا یا هری بود ساخته می‌شود و به این پارچه چوخ گفته می‌شود. پارچه چوخ «توک» یاپرز داده می‌شود پس از پایان کار جوانان و پهلوانان که عموماً ورزشکار هستند پارچه چوخ را برای تبدیل شدن به پالتو، کت و شلوار و پاتابه به دست خیاط می‌دهند. کشتی گیران و پهلوانان می‌بایست پالتوی چوخ را در هنگام مبارزه کشتی به تن می‌کردند و این از قوانین اولیه کشتی محسوب می‌شد و از این لحاظ کشتی را چوخه نام نهادند و این کشتی به کشتی چوخه شهرت یافت. لباس چوخه در آن روزگار مقوام‌ترین لباس عشایر کرد شمال خراسان بود به‌طوری‌که هیچ پارچه دیگری مثل پارچه چوخه در مبارزه کشتی گیران دوام نمی‌آورد.


title: کشتی با چوخه

text: میدان کُشتی که دایره‌ای با قطر ۱۰ متر است و کشتی در آنجا برگزار می‌شود. اجرای کشتی به شکل سنتی و بدون کلیشه (کشتی روی خاک و با سرنا و دهل) انجام می‌شود. تمام زیبایی کشتی با چوخه برگزاری آن به شکل سنتی است که می‌تواند برای تمام قشرها و رده‌های سنی جذابیت داشته باشد. کشتی با چوخه همیشه در فضای باز و دل طبیعت و اماکن تفریحی و روی خاک نرم یا چمن برگزار می‌شده‌است. ضروری است در حال حاضر نیز تا جایی که امکان دارد این امر لحاظ شود. دست دادن قبل از کشتی نیز از زیبایی‌های این ورزش است. گودهای کشتی سنتی و معروف در شهرهایی مثل قوچان، اسفراین و ریواده نظیر گودهای رهورد و سلطان زیرابه و چشمه زینل خان و ججو الگوهای بسیار بارزی برای این مورد است.


title: کشتی با چوخه

text: با نواختن دهل و سرنا (زورنه) توسط بخشی‌ها، چوخه‌کاران حول میدان مسابقات به حرکت در می‌آیند و خود را گرم می‌کنند و برای مسابقه آماده می‌شوند. نوای دهل و سورنا بانگ آوازی نیز برای خبر کشتی است و از مردم می‌خواهد که جمع شوند و با دل و جان به تماشای کشتی بنشینند. موسیقی کردی که با تم‌های سنگین و رزمی نواخته می‌شود. دو نوازنده سرنا و دهل با نواختن موسیقی حال و هوای خاصی به ورزش کشتی می‌دهند، در حین مسابقات نوای سرنا و دهل یا قشمه و دهل بخشی‌ها با ریتم خاصی شروع شده و به تدریج که کشتی اوج می‌گیرد ریتم آن نیز تندتر می‌شود و وقتی زورآزمایی چوخه‌کاران به اوج می‌رسد و بر سرعت چوب طبل و سرنا می‌افزایند.


title: راست (زبان برنامه‌نویسی)

text: راست یک زبان برنامه‌نویسی ترجمه‌شده، عام منظوره و چند الگویی است که توسط تحقیقات موزیلا توسعه یافته‌است. این زبان طراحی شده‌است تا یک زبان مطمئن، همسو و عملی باشد که مدل‌های تابعی خالص، امری-رویه‌ای و شی گرا را پشتیبانی می‌کند. زبان از یک پروژهٔ شخصی توسط توسعه‌دهندهٔ Graydon Hoare به‌وجود آمد، که او کار بر روی آن را در سال ۲۰۰۶ آغاز کرد؛ کارفرمای او موزیلا، در سال ۲۰۰۹ درگیر این پروژه شد و رسماً آن را برای اولین بار در سال ۲۰۱۰ پرده برداری کرد. در همان سال، کار از کامپایلرهای اولیه (نوشته شده در OCaml) خود را به کامپایلر خود میزبان نوشته‌شده در Rust تغییر داد. چیزی که به‌عنوان rustc شناخته شد، با موفقیت خود را در سال ۲۰۱۱ کامپایل کرد. کامپایلر خود میزبان از LLVM به عنوان backend استفاده می‌کند.


title: راست (زبان برنامه‌نویسی)

text: اولین نسخه از کامپایلر Rust، که آلفا نام گذاری شد در ژانویه ۲۰۱۲ منتشر شد. نسخه فعلی (نسخه ۰٫۸)، در سپتامبر ۲۰۱۳ منتشر شده‌است.


title: راست (زبان برنامه‌نویسی)

text: Rust به‌طور کامل در بازخورد باز و همکاری و کمک از جامعه توسعه یافته‌است. طراحی این زبان از طریق تجربه حاصل از نوشتن موتور چیدمان Servo اصلاح شده و Rust خودش را کامپایل کرده‌است. اگر چه توسعه آن با حمایت مالی موزیلا و سامسونگ بوده‌است، اما یک پروژهٔ اجتماعی است. بخش بزرگی از تصدیقات نسخهٔ فعلی از اعضای جامعه می‌باشد.


title: راست (زبان برنامه‌نویسی)

text: هدف Rust این است که یک زبان خوب برای ایجاد مجموعهٔ بزرگی از مشتری‌ها و سرور برنامه‌هایی که بر روی اینترنت اجرا می‌شوند باشد.این امر زبان را به یکی از ویژگی‌های مجموعه با تأکید بر ایمنی، کنترل از طرح حافظه و همزمانی هدایت می‌کند. اگر عملکرد زبان تنها عامل مورد توجه باشد، عملکرد قابل اطمینان بودن کد همان‌طور که انتظار می‌رود آن را کندتر از ++C می‌کند اما پیشگیری‌های از پیش تعریف شده در Rust با احتساب اقدامات محتاطانه‌ای که زبان ++C به‌طور دستی انجام می‌دهد، از نظر سرعت برابری می‌کند (و یا حتی سریعتر است)نحو زبان Rust مشابه C و ++C است؛ با بلاک‌هایی از کد که بین آکولادها محدود شده‌است و کلمات کلیدی کنترل جریان مانند while ,do ,else ,if و for. البته تمام کلمات کلیدی C و ++C وجود ندارد اما به هر حال دیگران (مانند تطابق واژه کلیدی برای انشعاب چند جهت) برای برنامه‌نویسانی که از این زبان‌ها می‌آیند کمتر آشنا خواهد بود. با وجود شباهت نحوی، Rust از نظر معنایی با C و ++C متفاوت است.


title: راست (زبان برنامه‌نویسی)

text: پروژه‌های توسعه یافته در Rust شامل:


title: راست (زبان برنامه‌نویسی)

text: مبتنی بر مرورگر: مبتنی بر ابزار ساخت: پروژه‌های دیگر:


title: راست (زبان برنامه‌نویسی)

text: نمونه کد زیر برای Rust نسخه ۰٫۸ معتبر می‌باشد. نحو و معناشناسی ممکن است در نسخه‌های بعدی تغییر یابد.برنامه Hello World: fn main() {


title: راست (زبان برنامه‌نویسی)

text: دو نمونه از تابع فاکتوریل در ساختارهای بازگشتی و ترتیبی :


title: راست (زبان برنامه‌نویسی)

text: /* The branches in this function exhibit Rust's optional implicit return fn recursive_factorial(n: int) -> int {


title: راست (زبان برنامه‌نویسی)

text: fn iterative_factorial(n: int) -> int {


title: راست (زبان برنامه‌نویسی)

text: fn main() {


title: راست (زبان برنامه‌نویسی)

text: یک نمایش ساده از قابلیت همزمانی ساده از Rust: /* This function creates ten "tasks" that all execute concurrently. Run it fn main() { یک نمایش ساده از اشاره‌گرهای هوشمند یگانی همراه با tagged unions و روش‌ها: use IntList::{Node, Empty};


title: راست (زبان برنامه‌نویسی)

text: // This program defines a recursive data structure and implements methods upon it. // Recursive data structures require a layer of indirection, which is provided here // by a unique pointer, constructed via the `Box::new` constructor. These are // analogous to the C++ library type `std::unique_ptr`, though with more static // safety guarantees. fn main() {


title: راست (زبان برنامه‌نویسی)

text: // `enum` defines a tagged union that may be one of several different kinds of values at runtime. // The type here will either contain no value, or a value and a pointer to another `IntList`. enum IntList {


title: راست (زبان برنامه‌نویسی)

text: // An `impl` block allows methods to be defined on a type. impl IntList {


title: الگوریتم تارژان مؤلفه‌های قویا همبند

text: الگوریتم تارژان (نامگذاری: مبدع، رابرت تارژان)، از الگوریتم‌های تئوری گراف است که برای پیدا کردن مؤلفه‌های قویاً همبند در یک گراف استفاده می‌شود. با وجود اینکه، این الگوریتم از نظر زمانی مقدم بوده‌است، می‌توان دید که نسخهٔ بهبود یافته الگوریتم کساراجو و از نظر کارایی (بازده) با الگوریتم مؤلفه قوی مبتنی بر مسیر قابل مقایسه است.


title: الگوریتم تارژان مؤلفه‌های قویا همبند

text: الگوریتم به عنوان ورودی گراف جهت داری را می‌گیرد، و افرازی از رئوس گراف به مؤلفه‌های قویاً همبند تولید می‌کند. هر راسی (گره) از گراف، دقیقاً یک بار در مؤلفه‌های همبند ظاهر می‌شود. هر راس که در یک دور جهت دار نیست، خودش به عنوان یک مؤلفه‌های قویاً همبند انتخاب می‌شود: برای مثال، راسی که درجه ورودی و درجه خروجی آن صفر باشد، یا هر راس از گراف بدون دور به تنهایی یک مؤلفهٔ قویاً همبند حساب می‌شوند. ایدهی ابتدایی این الگوریتم: الگوریتم جستجو عمق اول با راس دلخواه شروع می‌کند (و جستجوی بعدی عمق اول، بر روی راس‌هایی اعمال می‌شود که دیده نشدهاند). با الگوریتم جستجوی عمق اول، جستجو، هر راسی گراف را دقیقاً یک بار می‌بیند؛ بنابراین، مجموعه ی درخت جستجو، یک جنگل پوشا از گراف است. مؤلفه‌های قویاً همبند، به عنوان زیردرختهای معین این درخت پوشا، به دست خواهد آمد. ریشهی این زیردرختها را، ریشهی مؤلفه‌های قویاً همبند می‌گویند. هر راسی از مؤلفه‌های قویاً همبند ممکن است به عنوان ریشه به کار گرفته شود، اگر اولین راسی باشد که از آن مؤلفه دیده می‌شود.


title: الگوریتم تارژان مؤلفه‌های قویا همبند

text: راس‌ها به ترتیبی که دیده می‌شوند در داخل پشته جای می‌گیرند. زمانی که جستجوی عمق اول به صورت بازگشتی، راسی V و فرزاندانش را ملاقات کند، آن راس‌ها، نباید تا قبل از بازگشت این فراخوانی بازگشتی از پشته، POP شوند. خاصیت یکسانی (ثابت)، این است که، یک راس بعد از پیمایش، بر روی پشته باقی می‌ماند، اگر و تنها اگر مسیری به برخی از راس‌های پایین‌تر در پشه وجود داشته باشد. بعد از اتمام فراخوانی ای که V و فرزاندان آن را پیدا می‌کند، ما می‌دانیم که آیا V به هر راسی قبل از خودش در پشته مسیر دارد یا خیر. اگر چنین بود فراخوانی بازمی‌گردد. V را در پشته به عنوان ثابت، نگاه می‌دارد. اگر نه، V باید ریشهی مؤلفه‌های قویاً همبند باشد که شامل V و راس‌های بعدی در پشته است. (راس‌هایی که به V مسیر دارند ولی به ماقبل V مسیری ندارند). تمام مؤلفه‌ها، POP می‌شود و ثابت را نگه می‌دارد.


title: الگوریتم تارژان مؤلفه‌های قویا همبند

text: هر راسی v به یک عدد صحیح، v.index اختصاص داده می‌شود که اعداد راس‌ها بصوت متوالی، بترتیبی که پیدا شدهاند، قرار داده می‌شود. همچنین یک مقدار، v.lowlink که کوچکترین اندیس هر راسی شناخته شدهی قابل دسترس از v، شامل خود v را نمایش می‌دهد، نگه داشته می‌شود؛ بنابراین، v باید سمت چپ پشته باشد اگر v.lowlinke الگوریتم جستجوی اول عمق می‌باشد. S پشتهٔ راس‌ها می‌باشد که در ابتدا خالی می‌باشد و برای ذخیره‌سازی راس‌هایی که دیده شده‌اند ولی هنوز به مؤلفه‌های قویاً همبند ملحق نشده‌اند می‌باشد. ذکر این نکته مهم است که این پشته همان پشتهٔ جستجوی اول عمق نمی‌باشد در واقع با خروج آن راس در الگوریتم جستجوی اول عمق از پشته حذف نمی‌شود و تنها در صورتی راس‌ها حذف می‌شوند که یک مؤلفهٔ قویاً همبند پیدا شود تا تمامی رأس‌های آن حذف شود. بیرونی‌ترین حلقه در کد بالا در بین راس‌هایی که هنوز دیده نشده‌اند جستجو می‌کند تا تضمین کند که راس‌هایی که از راس اول قابل دسترسی نیستند نیز دیده خواهند شد. تابع strongconnect یک جستجوی اول عمق را انجام می‌دهد که تمامی فرزندان راس v را می‌بیند و تمامی مؤلفه‌های قویاً همبند آن زیر گراف را پیدا می‌کند. هنگامی که هر راسی تابع بازگشتی جستجوی اول عمقش تمام می‌شود اگر مقدار lowlink آن برابر اندیس آن باشد یعنی آن راس ریشهٔ یک مؤلفهٔ قویاً همبند شامل تمام راس‌های بالاتر از آن درون پشته خواهد بود. الگوریتم تمامی راس‌های بالاتر از انرا از پشته خارج می‌کند و همهٔ آنهارا به عنوان یک مؤلفه در نظر می‌گیرد.


title: مسئله پایان خوش

text: مسئلهٔ پایان خوش (که توسط پل اردیش نامگذاری شده‌است، چرا که به ازدواج جورج سیکریس و استر کلاین منجر شد) گزارهٔ ذیل است:


title: مسئله پایان خوش

text: این قضیه یکی از نتایج اصلی است که منجر به ظهور نظریهٔ رمزی شد.


title: مسئله پایان خوش

text: قضیهٔ پایان خوش، با تحلیل یک حالت ساده اثبات می‌شود: اگر چهار یا تعداد بیش‌تری نقطه، رأس‌های یک بدنهٔ محدب باشند، هر چهار نقطه‌ای به این شکل می‌توانند انتخاب شوند. از طرفی دیگر، اگر مجموعهٔ نقاط به فرم یک مثلث با دو نقطه درون آن باشند، دو نقطهٔ درونی و یکی از اضلاع مثلث می‌توانند انتخاب شوند. برای توضیح مصور این اثبات، پترسون (۲۰۰۰) را ببینید و برای بررسی دقیق‌تر این مسئله نسبت به آنچه اینجا ارائه شده‌است، موریس و سالتن (۲۰۰۰) را ببینید.


title: مسئله پایان خوش

text: تخمین اردوش-سیکریس رابطهٔ کلی بین تعداد نقاطی که در یک مجموعهٔ نقاط با موقعیت عمومی هستند و بزرگ‌ترین چندضلعی محدب آن را به‌طور دقیق بیان می‌کند. این مسئله اثبات‌نشده باقی می‌ماند، اما مرزهای دقیق کم‌تری شناخته شده‌است.


title: مسئله پایان خوش

text: دو دانشمند به نام‌های اردوش و سیکریس این قضیه را به صورت زیر تعمیم داده‌اند:


title: مسئله پایان خوش

text: اثبات قضیه اردیش–ژکرس در مقاله‌ای که قضیهٔ زیردنباله‌های یکنواخت در دنباله‌های عددی را اثبات می‌کند آمده است.


title: مسئله پایان خوش

text: فرض کنید ("f"("N" کمترین مقدار "M" را نشان دهد که برای هر مجموعه از "M" نقطه در موقعیت عمومی یک "N"ضلعی محدب وجود داشته باشد. داریم:


title: مسئله پایان خوش

text: بر مبنای مقادیر مشخص ("f"("N"، یعنی برای N" = ۳, ۴, ۵"، اردوش و سیکریس در مقالهٔ اصلی خود رابطهٔ زیر را تخمین زدند: به ازای هر N" ≥ ۳"


title: مسئله پایان خوش

text: بعدها این دو نفر با زدن مثال‌های خارجی دیگر ثابت کردند که:


title: مسئله پایان خوش

text: اما بهترین کران بالا برای حالت‌هایی که N" ≥ ۷" است، به صورت زیر است:


title: مسئله پایان خوش

text: ممکن است سؤال پیش بیاید که آیا برای هر مجموعهٔ کافی از نقاط در موقعیت عمومی دارای یک چهارضلعی، پنج‌ضلعی و.. هست یا نه، به این معنی که نیاز به نقطه ورودی جدید نداشته باشد. راه حل اصلی مسئلهٔ پایان خوش را می‌توان طوری تطابق داد که نشان دهد به ازای هر پنج نقطه با وضعیت موقعیت عمومی در صفحه یک چهارضلعی محدب خالی وجود دارد، همان‌طور که در تصویر نشان داده شده، و به ازای هر ده نقطه با شرایط فوق یک پنج‌ضلعی محدب خالی وجود دارد. اگرچه مجموعه‌های بزرگ و دلخواهی از نقاط با موقعیت عمومی ممکن است وجود داشته باشند که هیچ هفت‌ضلعی خالی برای آن‌ها یافت نشود. برای مدت طولانی این سؤال که آیا شش‌ضلعی خالی وجود دارد یا نه، بدون پاسخ ماند، ولی نیکولاس (۲۰۰۷) و گرکن (۲۰۰۸) ثابت کردند که به ازای هر مجموعهٔ کافی از نقاط با موقعیت عمومی در صفحه یک شش‌ضلعی محدب خالی وجود دارد. به صورت خاص، گرکن نشان داد که تعداد نقاط مورد نیاز بیشتر از (f"(۹" نیست. ("f" در بالا تعریف شده) درحالیکه نیکولاس نشان داد این مقدار حداکثر به اندازهٔ (f"(۲۵" است. (Valtr(۲۰۰۶ اثبات گرکن را ساده می‌کند و نشان می‌دهد که به نقاط بیشتری از (f"(۹"، یعنی به اندازهٔ (f"(۱۵" که برابر ۳۰ نقطه می‌شود، نیاز داریم، چرا که یک مجموعه از ۲۹ نقطه در موقعیت عمومی در صفحه وجود دارد که برای آن شش‌ضلعی محدب خالی وجود ندارد.


title: مسئله پایان خوش

text: مسئلهٔ پیدا کردن مجموعه‌عای شامل "n" نقطه به طوری که تعداد چندضلعی‌های محدب را کمینه کند، مشابه کمینه‌کردن تعداد عبور در یک ترسیمِ خطِ مستقیمِ یک گراف کامل است. تعداد چندضلعی‌ها باید متناسب با توان چهارم "n" باشد، اما مقدار ثابت دقیقی، مشخص نیست. به‌طور سرراست می‌توان نشان داد که در فضای اقلیدسی با ابعاد بالاتر، مجموعه‌های به اندازهٔ کافی بزرگ از نقاط، یک زیرمجموعه از "k" نقطه خواهند داشت که رأس‌های یک چندبر محدب را تشکیل می‌دهند، برای هر "k" بزرگ‌تر از بُعد: این مسئله خیلی سریع از موجود بودن "k"-ضلعی محدب در مجموعه‌های نقاط مسطح به اندازهٔ کافی بزرگ پیروی می‌کند، به این صورت که مجموعه نقاط با ابعاد بالاتر را در یک شبه فضای دوبعدی اختیاری طراحی می‌کند. اما تعداد نقاط لازم برای پیدا کردن "K" نقطه در حالت محدب ممکن است در ابعاد بالاتر نسبت به حالتی که در صفحه است، کم‌تر باشد، و همچنین پیدا کردن زیرمجموعه‌هایی که محدودتر هستند، امکان‌پذیر است. به‌طور مشخص، در "d" بعد، هر d" + ۳" نقطه در موقعیت عمومی، یک زیرمجموعه از d" + ۲" نقطه دارد که رئوس یک چندبر چرخه‌ای را تشکیل می‌دهند. در حالت کلی‌تر، برای هر "d" و "k"> "d"، عدد ("m"("d", "k" وجود دارد به گونه‌ای که هر مجموعه از ("m"("d", "k" نقطه در موقعیت عمومی یک زیر مجموعه از "k" نقطه خواهد داشت که رئوس یک چندبر همسایگی را تشکیل می‌دهد.


title: گراف وتری

text: در ریاضیات، حوزهٔ نظریهٔ گرافها، گراف وتری گرافی است که هر دور به طول چهار یا بیشتر از آن شامل وتر باشد. (وتر: یالی است که دو رأس از دور که در دور شرکت نکرده باشند را به هم وصل می‌کند). به عبارت دیگر، هر دور القایی در گراف می‌بایست حداکثر سه رأس داشته باشد. گراف‌های وتری زیرمجموعه‌ای از گراف‌های آرمانی می‌باشند که در مدت زمانی چندجمله‌ای شناسایی می‌شوند. اگر ورودی مسایلی همچون رنگ‌آمیزی گراف، گرافی وتری باشد در مدت زمانی چندجمله‌ای حل می‌شوند.


title: گراف وتری

text: formula_1 یک ترتیب طرد آرمانی از رئوس گراف است به طوری‌که به ازای هر راس formula_2، زیرگراف القایی ناشی از رئوس formula_2 وهمسایه‌های آن در زیرگراف القایی ناشی از formula_4 گرافی کامل باشد. نشان دادند که یک ترتیب طرد آرمانی از گرافی وتری را می‌توان به‌طور بهینه با الگوریتمی به نام پیدا کرد.


title: گراف وتری

text: کاربرد دیگر ترتیب طرد آرمانی پیدا کردن خوشهٔ فرین در یک گراف وتری در مدت زمانی چندجمله‌ای است، در حالی‌که این مسئله در حالت کلی از مسائل NP-complete است. در حالت کلی یک گراف وتری تعدادی خطی خوشهٔ فرین دارد در حالی‌که این تعداد در گراف‌های دیگر می‌تواند نمایی باشد. برای بدست آوردن خوشه‌های فرین از گراف وتری، ابتدا یک ترتیب طرد آرمانی (در صورت وجود) پیدا می‌کنیم. سپس از ابتدای این ترتیب شروع کرده و به ازای هر رأس formula_2 زیرگراف القایی ناشی از این رأس و رئوس قبلی آن در ترتیب را (که تشکیل خوشه می‌دهند) را در نظر می‌گیریم. خوشهٔ با اندازهٔ بیشینه در میان این خوشه‌ها، خوشهٔ فرین خواهد بود. از آنجا که گراف وتری آرمانی است، اندازهٔ خوشهٔ فرین، همان عدد رنگی گراف خواهد بود. گراف‌های وتری، هستند: با اعمال رنگ‌آمیزی حریصانه بر روی ترتیب معکوس طرد آرمانی می‌توان به‌طور بهینه آن را رنگ کرد.


title: گراف وتری

text: در هر گراف، مجموعه‌ای از رئوس است که با حذف آن‌ها گراف ناهمبند می‌شود. جداساز مینیمال است اگر هیچ زیرمجموعهٔ محضی از آن این ویژگی را نداشته باشد. برطبق قضیهٔ در گراف‌های وتری، هر جداساز مینیمال یک خوشه است. Dirac با این ویژگی آرمانی بودن گراف‌های وتری را اثبات کرد. گراف‌های وتری به‌طور استقرایی توسط گراف‌هایی تعریف می‌شوند که رئوس آن‌ها به سه زیرمجموعهٔ ناتهی formula_6 افراز شوند، به طوری‌که formula_7 و formula_8 هردو تشکیل یک زیرگراف القایی وتری دهند، formula_9 خوشه باشد و هیچ یالی بین formula_10 و formula_11 نباشد.


title: گراف وتری

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


title: گراف وتری

text: "مکمل وتری" گراف دلخواه formula_12، گرافی وتری است که formula_12 زیرگراف آن باشد. اگر formula_14 "مکمل وتری" گراف formula_12 با عدد خوشه‌ای (تعداد رئوس خوشهٔ بیشینه گراف) کمینه باشد، در آن صورت پهنادرخت formula_12 یکی کمتر از عدد خوشه‌ای formula_14 است. " k-درخت" گرافی است که افزودن یک یال به آن، پهنادرخت آن را بزرگتر از k می‌کند. بنابراین " k-درخت" مکمل وتری خودش است و رده‌ای از گراف‌های وتری را تشکیل می‌دهد.


title: ساموئل ماریل وودبریج

text: ساموئل ماریل وودبریج (زاده ۵ آوریل ۱۸۱۹ و در گذشته ۲۳ ژوئن ۱۹۰۵ میلادی) روحانی، کشیش و استاد دانشگاه اهل آمریکا بود. وی اهل گرینفیلد، ماساچوست بود. ساموئل ماریل وودبریج از دانش‌آموختگان دانشگاه نیویورک بود و در دانشگاه راتگرز تدریس می‌کرد.


title: درخت تنره

text: درخت تِنِرِه ، ، یک درخت تنهای آکاسیا (سَمُر) یا آکاسیای چتری بود که روزگاری به عنوان تنهاترین و دورافتاده‌ترین درخت جهان به حساب می‌آمد. (نزدیک‌ترین درخت، حدود ۴۰۰ کیلومتر از آن فاصله داشت) مکان این درخت در روزگاران پیش، محل توقف کاروان‌های عازم منطقه تنره در صحرای بزرگ آفریقا در شمال‌شرقی نیجر بود. این درخت و درخت "آربر پِردو" (درخت گم‌شده) تنها درختانی هستند که در نقشه‌ای با مقیاس ۱:۴۰۰٬۰۰۰ دیده می‌شوند.


title: درخت تنره

text: این درخت در سال ۱۹۷۳ توسط یک رانندهٔ کامیون احتمالاً مست زیر گرفته شد و از بین رفت.


title: درخت تنره

text: درخت تنره، آخرین درخت از درختانی بود که روزگاری که هنوز صحرا چون امروز نبود در مکان فعلی قرار داشتند. در طول زمستان ۱۹۳۸–۱۹۳۹، چاهی در کنار این درخت حفر شد و متوجه شدند که ریشه‌های این درخت تا عمق ۳۳–۳۶ متری (۱۰۸ تا ۱۱۸ فوت) پیش رفته و به داخل سطح ایستابی رسیده‌است.


title: درخت تنره

text: در کتاب L'épopée du Ténéré، هنری لوت، نژادشناس و جهانگرد فرانسوی، به شرح دو دیدار خود از درخت تنره پرداخته‌است. او ابتدا در سال ۱۹۳۴ به‌طور تصادفی در سفر خود با اتومبیل از جانت به اغادیز، درخت تنره را دید و آنرا "یک درخت آکاسیا با بدنی پوسیده که مریض به نظر می‌آید اما با این حال برگ‌های سبز زیبا و گل‌های زرد دارد" توصیف کرد. او ۲۵ سال بعد در ۲۶ نوامبر ۱۹۵۹ در طی عملیات برلیت-تنره از درخت تنره دوباره بازدید کرد اما درخت را از برخورد یک ماشین بسیار آسیب‌دیده یافت.


title: درخت تنره

text: گفته می‌شود که درخت تنره در سال ۱۹۷۳ توسط یک راننده کامیون مست لیبیایی سرنگون شد. در ۸ نوامبر ۱۹۷۳، درخت مرده را به "موزه ملی نیجر" در نیامی منتقل کردند و به جای آن یک میله فلزی به عنوان یادبود قرار دادند.


title: الگوریتم‌های پوش محدب

text: الگوریتمی که پوش محدب اشیای مختلف را به دست می‌دهد کاربردهای وسیعی در ریاضیات و علوم کامپیوتر دارد. در هندسه محاسباتی، الگوریتم‌های متعددی با پیچیدگی‌های محاسباتی گوناگون برای محاسبه پوش محدب مجموعه‌ای محدود از نقاط مطرح شده‌است. محاسبه پوش محدب به معنی ارائه نمایشی نامبهم و کارا از شکل مطلوب می‌باشد. پیچیدگیهای الگوریتم‌های مربوطه معمولاً بر حسب n، تعداد نقاط ورودی، و h، تعداد نقاط درون پوش محدب، سنجیده می‌شوند.


title: الگوریتم‌های پوش محدب

text: اگر همهٔ نقاط روی یک صفحه نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می‌شود که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. معمولترین نمایش پوشه محدب به صورت لیستی از رأس‌های آن می‌باشد که ترتیب آن بر اساس پیمایشی ساعتگرد یا پادساعتگرد بر روی مرز پوش محدب می‌باشد. در بعضی از کاربردها نمایش این چندظلعی محدب به صورت اشتراک تعدادی نیم صفحه مناسب تر می‌باشد.


title: الگوریتم‌های پوش محدب

text: کران پایین محاسباتی برای پیدا کردن پوش محدب و نمایش آن به صورت چند ضلعی محدب، مشابه این کران برای مرتب‌سازی می‌باشد و به سادگی می‌توان این مطلب را با کاهش نشان داد. برای نقاط formula_1 که می‌خواهیم مرتب کنیم، نقاط formula_2 را بر روی صفحه در نظر بگیرید. حال چون این نقاط بر روی سهمی که منحنی محدب است قرار دارند به راحتی می‌توان دید که پیمایش بر روی مرز پوش محدب آن‌ها ترتیب مرتب شدهٔ این اعداد را می‌دهد. به وضوح زمان خطی برای تبدیل اعداد به نقاط و سپس به دست آوردن ترتیب مرتب شده، نیاز می‌باشد. از این رو به دست آوردن پوش محدب n نقطه نمی‌تواند سریعتر از مرتبسازی عمل کند.


title: الگوریتم‌های پوش محدب

text: کران پایین محاسباتی استاندارد به کمک مدل درخت تصمیمformula_3 می‌باشد که البته در این مدل تنها مقایسه انجام می‌شود و نه عملیات محاسباتی. به هر حال پوش محدب در این مدل نمی‌تواند محاسبه شود. مرتب‌سازی در مدلدرخت تصمیم جبری نیز از formula_3 می‌باشد که این مدل برای پوش محدب مناسبتر می‌باشد که در این مدل نیز به دست آوردن پوش محدب‌ها زمانی از formula_3 می‌خواهد. هر چند در مدل‌هایی که اجازه می‌دهند که اعداد سریعتر از formula_6 مرتب شودند، برای نمونه الگوریتم هایinteger sorting، پوش محدب نیز می‌تواند سریعتر محاسبه شود: الگوریتم پیمایش گراهام شامل یک مرحله سادهٔ مرتب‌سازی است که به دنبال مقداری کار اضافه که در زمان خطی انجام می‌شوند امده‌اند.


title: الگوریتم‌های پوش محدب

text: همان که در بالا ذکر شد پیچیدگی پیدا کردن پوش محدب به صورت تابعی از تعداد نقاط ورودی formula_3 می‌باشد. هر چند که پیچیدگی بعضی از الگوریتم‌های پوش محدب بر حسب سایز ورودی n و سایز خروجی h (تعداد نقاط روی پوش محدب) عنوان می‌شود. این گونه الگورتم‌ها حساس به خروجی نامیده می‌شوند. این الگوریتم‌ها ممکن است به‌طور مجانبی کارا تر از formula_3 باشند در حالتی که formula_9


title: الگوریتم‌های پوش محدب

text: کران پایین در بدترین حالت زمانی الگوریتم‌های مربوط به پوش محدب حساس به خروجی در حالت دوبعدی formula_3می‌باشد.الگوریتم‌های متعددی وجود دارند که این پیچیدگی بهینه را به دست می‌دهند. اولین آن‌ها در سال ۱۹۸۶ توسط Kirkpatrick و Seidel معرفی شد (که آن را الگوریتم نهایی پوش محدب نامیدند.)الگوریتم ساده‌تر توسط Chan در ۱۹۹۶ داده شد که الگوریتم چان نامیده شد.


title: الگوریتم‌های پوش محدب

text: الگوریتم‌های شناخته شدهٔ مربوط به پوش محدب در زیر لیست شده‌اند که آن‌ها را بر اساس اولین تاریخ انتشار مرتب کرده‌ایم. پیچیدگی زمانی این الگوریتم‌ها بر اساس تعداد نقاط ورودی n و تعداد نقاط روی پوش محدب h بیان شده‌اند. توجه شود که در بدترین حالت h ممکن است به بزرگی n باشد. یکی از ساده‌ترین (اگر چه مؤثرترین در بدترین حالت نمی‌باشد) الگوریتم‌های صفحه‌ای می‌باشد که به‌طور مستقل توسط Chand و Kapur در ۱۹۹۰ و R.A.Jarvis در ۱۹۷۳ کشف شد. این الگوریتم دارای پیچیدگی زمانی formula_11 می‌باشد و در بدترین حالت این پیچیدگی از مرتبه formula_12 است. یک الگوریتم با کمی پیچیدگی بیشتر ولی کاراتر که در سال ۱۹۷۲ توسط رونالد گراهام انتشار یافت. اگر نقاط قبلاً بر اساس یکی از مؤلفه‌های مختصاتشان یا بر اساس زاویه با برداری ثابت مرتب شده باشند آنگاه این الگوریتم از formula_13 می‌باشد. به‌طور مستقل توسط W.Eddy در ۱۹۷۷ و A.Bykat در ۱۹۷۸ کشف شد. درست مانند مرتب‌سازی سریع به‌طور میانگین ازformula_14 است ولی ممکن است در بدترین حالت به formula_15 برسد. الگوریتم دیگری از formula_6 که در سال ۱۹۷۷ توسطPreparata و Hong انتشار یافت. این اگوریتم برای حالت سه بعدی نیز قابل اجرا می‌باشد. در سال ۱۹۷۹ توسط A.M.Andrew انتشار یافت. به این الگوریتم می‌توان به دید تغییر شکل یافتهٔ Graham scan نگاه کرد که در آن نقاط بر اساس مؤلفه هایشان مرتب می‌شوند. اگر نقاط ورودی از قبل مرتب شده باشند این الگوریتم از formula_13 خواهد بود. منشتر شده در سال ۱۹۸۴ توسط Michael Kallay. اولین الگوریتم بهینه حساس به خروجی که در آن از تکنیک marriage-before-conquest استفاده می‌شود. در سال ۱۹۸۶ توسطKirkpatrick و Seidel انتشار یافت. الگوریتم بهینه و ساده‌تر حساس به خروجی که در سال ۱۹۹۶ توسط Chan کشف شد.


title: الگوریتم‌های پوش محدب

text: ابتکار ساده‌ای که در ادامهٔ کار می‌آید اغلب اولین مرحله در پیاده‌سازی الگوریتم پوش محدب برای بهبود کارایی آن می‌باشد. پایهٔ آن بر اساس اگوریتمی کارا که در سال ۱۹۷۸ توسطSelim Akl و G.T.Toussaint ارائه شد. ایدهٔ کار به این صورت است که به‌طور سریع نقاطی که به هیچ وجه نمی‌توانند در پوش محدب باشند را حذف کنیم. این روش بر مبنای آن است که در ادامه می‌آید. دو نقطه‌ای را که دارای کمترین و بیشترین مختصات x می‌باشند و به همین ترتیب دو نقطه‌ای که دارای کمترین و بیشترین مختصات y اند را پیدا می‌کنیم.(این کار در formula_13 انجام می‌شود.)این چهار نقطه تشکیل یک چهار ظلعی محدب را می‌دهند و تمام نقاطی که در این چهار ظلعی قرار می‌گیرند (غیر از چهار نقطهٔ ابتدایی) نمی‌توانند درون پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این چهار ظلعی قرار می‌گیرند نیز formula_13 هزینه می‌برد، پس در کل تا اینجا از formula_13 هزینه کرده‌ایم. به‌طور دلخواه نقاط با کمترین و بیشترین مجموع x,y و نقاط با کمترین و بیشترین تفاضل x,y را نیز می‌توانند به چهار ظلعی قبلی اضافه شوند تا این نقاط بر روی هم یک ۸ ظلعی محدب را به وجود آورند که نقاط درون آن به راحتی می‌توانند حذف شوند. اگر نقاط ورودی به صورت رندم انتخاب شوند آنگاه برای کلاسی گسترده از تابع‌های چگالی احتمال، این دور انداختن بعضی از نقاط در پیش پردازش باعث می‌شود که الگوریتمی که اجرا می‌شود دارای پیچیگی زمانی باشد که امید ریاضی آن خطی باشد، حتی اگر در بدترین حالت از formula_23 باشد.


title: الگوریتم‌های پوش محدب

text: در بحثهای بالا فرض بر آن است که تمامی نقاط از قبل به ما داده شده‌است. اما ممکن است کسی به این دو حالت بپردازد. درج یک نقطه به تعداد ضلع‌های پوش محدب حداکثر یک واحد اضافه می‌کند در حالی که عمل حذف می‌تواند یک پوش سه راسی را به یک پوش n-۱ راسی تبدیل کند.


title: الگوریتم‌های پوش محدب

text: در نوع برخط با اضافه شدن هر نقطهformula_24 هزینه شده که به‌طور مجانبی بهینه است. در نوع داینامیک هر عملیات درformula_25 انجام می‌شود.


title: الگوریتم‌های پوش محدب

text: McCallum و Avis اولین نفراتی بودند که پوش محدب برای یک چندظلعی ساده با رأس‌های را درformula_13) ساختند. ایدهٔ اصلی بسیار ساده است. چپترین نقطه روی پوش محدب می‌باشد و ما آن را با formula_27 مشخص می‌کنیم. دومین نقطه را نیز به عنوان کاندیدی برای راس پوش فرض می‌کنیم. در هر مرحله به سه راس متوالی نگاه می‌کنیم که دو تای اول به عنوان رأس‌های موقت پوش اختصاص داده شده‌اند و راس سوم هنوز پردازش نشده‌است که ما آن‌ها را به صورتformula_28 مشخص می‌کنیم. اگر زاویهٔ بین آن‌ها محدب بود انگاه formula_29 و این سه تایی با یک انتقال یک راسی سه تایی بعدی را مشخص می‌کند. اما اگر زاویهٔ ایجاد شده مقعر باشد آنگاه نقطه میانی(formula_30) پاک شده و این تست برای سه تایی formula_31 تا تکرار می‌کنیم تا این که یا به زاویهٔ محدب رسیده یا این که به و بعد از نقطهٔ بعدی به سه تایی برای تست شدن اضافه می‌شود و این روند تکرار می‌شود. هر چند که در تعدادی از مقالاتی که در گذشته انتشار یافته‌اند از امکان خود متقاطع شدن چند ضلعی در حین حذف رءوس صحبت شده که دلیلی بر نامعتبر بودن روند این الگوریتم می‌باشد. خوشبختانه، این مورد نیز به صورت کارا مدیریت می‌شود. بعداً Tor و Middleditch و به صورت مستقل Melkman رویکردی ساده‌تر با پیچیدگی زمانی یکسان ارائه کردند.


title: الگوریتم‌های پوش محدب

text: شماری از الگوریتم‌ها برای سه بعد وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید به:https://web.archive.org/web/20070609032115/http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html


title: الگوریتم‌های پوش محدب

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


title: قضیه ویزینگ

text: در نظریه گراف، قضیه ویزینگ (به نام وادیم ویزینگ نامگذاری شده که آن را در سال ۱۹۶۴ منتشر کرد) بیان می‌کند که یال‌های هر گراف ساده را می‌توان با حداکثر یکی بیشتر از بیشترین درجه رئوس گراف رنگ کرد.


title: قضیه ویزینگ

text: همواره حداقل رنگ لازم است، بنابراین گراف‌های ساده را می‌توان به دو رده افراز کرد: گراف‌های «ردهٔ اول» آنهایی هستند که رنگ، برای رنگ‌آمیزی آن‌ها کافی است و گراف‌های «ردهٔ دوم» آن‌هایی هستند که رنگ، برای رنگ‌آمیزی آن‌ها لازم است.


title: قضیه ویزینگ

text: هنگامی که است، گراف خود یک تطابق است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی آن یک است. پس، تمام گراف‌های با جزء گرافهای ردهٔ اول هستند.


title: قضیه ویزینگ

text: هنگامی که است، گراف اجتماع مجموعه‌های مجزای مسیرها و دورها است. اگر همهٔ دورها زوج باشند، آن‌ها می‌توانند ۲-رنگ پذیر یالی باشند با تغییر تناوبی دو رنگ، پیرامون هر دور. هر چند، اگر حداقل یک دور فرد وجود داشته باشد، هیچ ۲-رنگ آمیزی یالی ممکن نیست. پس، یک گراف با جزء گراف‌های ردهٔ اول است اگر و تنها اگر دوبخشی باشد.


title: قضیه ویزینگ

text: قضیهٔ ویزینگ در حالت کلی برای گراف‌های چندگانه برقرار نمی‌باشد. برای مثال، گراف چندگانهٔ حاصل از مضاعف کردن هر یال یک مثلث، بیشینه درجهٔ چهار دارد اما نمی‌توان آن را با کمتر از شش رنگ، رنگ‌آمیزی کرد.


title: قضیه ویزینگ

text: چندین نویسنده شرایطی را برای رده‌بندی برخی گراف‌ها به ردهٔ اول یا ردهٔ دوم ارائه کرده‌اند اما رده‌بندی کاملی ارائه نشده‌است. برای مثال اگر مجموعهٔ رئوس با بیشینه درجهٔ در گراف یک مجموعه مستقل باشد، یا به‌طور کلی‌تر زیرگراف القایی این رئوس یک جنگل باشد، آنگاه باید جزء گراف‌های ردهٔ اول باشد.


title: قضیه ویزینگ

text: اردوش و ویلسون (۱۹۷۷) نشان دادند که تقریباً همهی گراف‌ها جزء ردهٔ اول هستند. پس، در مدل اردوش-رنیِ گراف‌های تصادفی، که تقریباً تمام گراف‌های -راسی برابر هستند، را احتمال کشیده شدن یک گراف -راسی از توزیع گراف‌های ردهٔ اول تعریف می‌کنیم، در نتیجه اگر به بینهایت میل کند به یک نزدیک می‌شود. برای حدود بهتری که به یک همگرا باشد، به رجوع شود.


title: قضیه ویزینگ

text: ویزینگ (۱۹۶۵) نشان داد که هر گراف مسطح جزو گراف‌های ردهٔ اول است اگر بیشترین درجهٔ رئوس گراف حداقل هشت باشد. در مقابل او مشاهده کرد که به ازاء هر بیشترین درجهٔ بین دو تا پنج، گراف مسطحی وجود دارد که جزو گراف‌های ردهٔ دوم باشد. برای درجهٔ دو، هر دور فردی چنین گراف است و برای درجهٔ سه و چهار و پنج گراف‌های مورد نظر از اجسام افلاطونی با جایگزین کردن یک یال به جای دو یال مجاور می‌توانند ساخته شوند.


title: قضیه ویزینگ

text: در حدس گراف‌های مسطح ویزینگ، ویزینگ (۱۹۶۵) بیان می‌کند که گراف‌های سادهٔ مسطح که بیشترین درجهٔ رئوس آن‌ها شش یا هفت است، جزء گراف‌های ردهٔ اول هستند، و این موارد ممکن باقی‌مانده را تمام می‌کند. سندرز و ژاو (۱۹۶۵) با نشان دادن ردهٔ اول بودن تمام گراف‌های مسطح با بیشترین درجهٔ رئوس هفت، تقریباً حدس گراف‌های مسطح ویزینگ را اثبات کردند. بنابراین، تنها حالت حدس که حل نشده باقی‌مانده این است که بیشترین درجه، شش باشد. این حدس شامل دلایلی برای حدس رنگ‌آمیزی کامل گراف است.


title: قضیه ویزینگ

text: گراف‌های مسطح ردهٔ دوم که با زیربخش‌های اجسام افلاطونی ساخته می‌شوند منظم نیستند: آن‌ها رئوس درجهٔ دو دارند همانطور که رئوس با درجهٔ بالاتر دارند. قضیه چهاررنگ، روی رنگ‌آمیزی راسی گراف‌های مسطح، معادل این گزاره است که هر گراف ۳-منظمِ مسطحِ بدون یال برشی جزء گراف‌های ردهٔ اول هستند (تایت ۱۸۸۰). این گزاره بعد از اثبات قضیه چهار رنگ توسط اپل و هاکن (۱۹۷۶) درست شناخته شد.


title: قضیه ویزینگ

text: در سال ۱۹۶۹، برانکو گرانبام حدس زد که تمام گراف‌های ۳-منظم با برازش چندوجهی روی هر خمینهٔ جهت‌دار دو بعدی مانند چنبره، باید جزو گراف‌های ردهٔ اول باشد. در این زمینه، برازش چندوجهی یک برازش گراف است که در آن هر ناحیه از برازش از نظر توپولوژیکی یک دیسک است و به طوری که گرافِ دوگانِ برازش ساده است، بدون حلقه و یال چندگانه. در صورت درست بودن، این حدس یک تعمیم قضیهٔ چهار رنگ است که توسط تایت، نشان داده شد معادل این گزاره است که گراف‌های ۳-منظم با برازش چندوجهی روی یک کره، جزء رده اول هستند. اگرچه کُچُل (۲۰۰۹) نشان داد که حدس غلط است اگر اسنارکی که دارای برازش چندوجهی بر روی رویهٔ جهت‌دار بالادسته وجود داشته باشد. بر این اساس، او همچنان نشان داده است که دانستن اینکه برازش چندوجهی جزو گراف‌ها ردهٔ اول است، ان‌پی کامل است.


title: قضیه ویزینگ

text: میسرا و گرایز (۱۹۹۲) یک الگوریتم با زمان چندجمله‌ای برای رنگ‌آمیزی هر گراف با رنگ ارائه کردند، که بیشینه درجهٔ گراف است. پس، الگوریتم برای گراف‌های ردهٔ دوم از تعداد رنگ‌های بهینه استفاده می‌کند، و حداکثر یکی بیشتر از تعداد رنگ‌های مورد نیاز برای همهٔ گراف‌ها. الگوریتم آن‌ها از روشی یکسان با اثبات اصلی ویزینگ برای قضیه‌اش پیروی می‌کند: این الگوریتم از یک گراف رنگ نشده شروع می‌کند، و سپس به‌طور مکرر راهی را برای رنگ‌آمیزی دوباره گراف پیدا می‌کند تا تعداد یال‌های رنگ شده را یک عدد افزایش دهد.


title: قضیه ویزینگ

text: به‌طور خاص‌تر، فرض کنید که یک یال رنگ نشده در یک گراف نیمه رنگ شده باشد. الگوریتم میسرا و گرایز ممکن است به عنوان ساخت یک شبه جنگل جهت‌دار (یک گراف که هر رأس آن حداکثر یک یال خارج‌شونده دارد.) روی همسایه‌های تفسیر شود: برای هر همسایهٔ از ، الگوریتم یک رنگ را می‌یابد که توسط هیچ یک از یال‌های مجاور استفاده نشده‌است، رأس را می‌یابد (در صورت وجود) که یال رنگ را دارد و را به عنوان یک یال به اضافه می‌کند. دو حالت وجود دارد:


title: قضیه ویزینگ

text: با برخی از ساختمان داده‌های ساده برای پیگیری رنگ‌هایی استفاده شده و قابل استفاده در هر رأس، می‌توان ساختن و گام‌های رنگ‌آمیزی دوباره الگوریتم را با زمان پیاده‌سازی کرد، که تعداد رئوس گراف ورودی است. چون در هر تکرار این گام‌ها تعداد یال‌های رنگ شده یکی افزایش می‌یابد، باید این گام‌ها را بار تکرار کرد، پس زمان مجموع برابر است با .


title: قضیه ویزینگ

text: در یک گزارش فنی منتشر نشده، گابو و همکاران (۱۹۸۵) ادعای ارائهٔ یک محدودیت زمانی formula_1 سریع‌تر را برای مسئلهٔ رنگ‌آمیزی یکسان با رنگ را کردند.


title: قضیه ویزینگ

text: در هر دو گوتین و تافت (۲۰۰۰) و سافیر (۲۰۰۸)، ویزینگ اشاره کرد که کارش انگیخته شده توسط یکی از قضایای شانون (۱۹۴۹) است که نشان می‌دهد گراف‌های چندگانه می‌توانند با حداکثر رنگ، رنگ‌آمیزی شوند. هر چند حالا قضیه ویزینگ جزء مواد استاندارد بسیاری از کتاب‌های نظریه گراف است، ویزینگ در ابتدا برای انتشار نتایجش مشکل داشت، و مقاله‌اش در یک مجلهٔ گمنام به نام Diskret. Analiz. چاپ شد.


title: فهرست مسائل کوله‌پشتی

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


title: فهرست مسائل کوله‌پشتی

text: چیزی که در تمام نسخه‌های این مسئله مشترک است، وجود مجموعه‌ای با n عضو است، که هر عضو با اندیس j که formula_1، یک ارزش formula_2 و وزن formula_3 دارد. متغیر دودویی تصمیم formula_4 برای انتخاب کردن اشیا به کار میرود. هدف برداشتن تعدادی از اعضا است، به طوری که ارزش کلشان بیشینه شود و در عین حال بیشینه مجموع وزن اشیا انتخاب‌شده از formula_5 تجاوز نکند. در حالت کلی، این ضرایب در عددی ضرب می‌شوند (مقیاس می‌شوند) تا به اعداد صحیح تبدیل شوند و همیشه فرض می‌شود که این ضرایب عدد طبیعی هستند.


title: فهرست مسائل کوله‌پشتی

text: مسئله کوله‌پشتی در ساده‌ترین شکل به صورت زیر است:


title: فهرست مسائل کوله‌پشتی

text: formula_6 را بیشینه کنید، به طوری‌که formula_7،formula_8،formula_9.


title: فهرست مسائل کوله‌پشتی

text: یک شکل رایج این مسئله این است که هر عضو بتواند چندین بار انتخاب شود. مسئله کوله‌پشتی محدود برای هر عضو formula_10، یک کران بالای formula_11 (که می‌تواند یک عدد صحیح مثبت یا بی‌نهایت باشد.) که تعداد دفعاتی است که عضو formula_10ام انتخاب شده‌است را مشخص می‌کند:


title: فهرست مسائل کوله‌پشتی

text: formula_6 را بیشینه کنید، به طوری‌که formula_7، formula_15 و formula_4 برای هر formula_10 عددی صحیح است.


title: فهرست مسائل کوله‌پشتی

text: مسئله کوله‌پشتی نامحدود (که گاهی اوقات مسئله کوله‌پشتی صحیح نیز خوانده می‌شود) برای تعداد تکرارهای یک عضو کران بالایی قرار نمی‌دهد:


title: فهرست مسائل کوله‌پشتی

text: formula_6 را بیشینه کنید، به طوری‌که formula_7 و formula_20، formula_21 برای هر j عددی صحیح است.


title: فهرست مسائل کوله‌پشتی

text: در سال 1975 لوکر ثابت کرد که نوع نامحدود مسئله ان‌پی کامل است. هر دو نوع محدود و نامحدود این مسئله یک FPTAS دارند (در اصل شبیه به همان است که در مسئله کوله‌پشتی 0-1 استفاده شد).


title: فهرست مسائل کوله‌پشتی

text: اگر اعضا در "k" دسته که با formula_22 نشان داده می‌شوند طبقه بندی شوند، و دقیقاً از هر کلاس یک عضو انتخاب شود آنگاه با مسئله کوله‌پشتی چند گزینه ای روبرو هستیم:


title: فهرست مسائل کوله‌پشتی

text: formula_23 را بیشینه کنید، به طوری‌که formula_24 ؛ formula_25، برای هر formula_26 و formula_27، برای هرformula_26 و هر formula_29.


title: فهرست مسائل کوله‌پشتی

text: اگر برای هر عضو ارزش و وزنش یکسان باشند، با مسئله جمع زیرمجموعه ها روبرو هستیم (اغلب مسئله تصمیم که متناظر با آن است به جای آن داده می‌شود):


title: فهرست مسائل کوله‌پشتی

text: formula_6 را بیشینه کنید، به طوری‌که formula_31، formula_8.


title: فهرست مسائل کوله‌پشتی

text: اگر "n" عضو و "m" کوله‌پشتی با ظرفیت formula_33 داشته باشیم،با مسئله کوله‌پشتی چندگانه روبرو هستیم:


title: فهرست مسائل کوله‌پشتی

text: formula_34 را بیشینه کنید، به طوریکه formula_35، برای هر formula_36


title: فهرست مسائل کوله‌پشتی

text: و formula_37، برای هر formula_1


title: فهرست مسائل کوله‌پشتی

text: و formula_27، برای هر formula_1 و هر formula_36.


title: فهرست مسائل کوله‌پشتی

text: به عنوان یک حالت خاصِ مسئله کوله‌پشتی چندگانه، هنگامی که ارزش‌ها با وزن‌ها برابر و همه صندوق‌ها حجم برابر داشته باشند، با مسئله حاصل جمع زیرمجموعه‌های چندگانه روبرو هستیم:


title: فهرست مسائل کوله‌پشتی

text: مسئله کوله‌پشتی درجه دوم:


title: فهرست مسائل کوله‌پشتی

text: formula_42 را بیشینه کنید، به طوری‌که formula_7، formula_8 برای هر formula_1.


title: فهرست مسائل کوله‌پشتی

text: مسئله کوله‌پشتی مجموعه-اجتماع(SUKP):


title: فهرست مسائل کوله‌پشتی

text: SUKP توسط Kellerer و همکارانش ( در صفحه 423) همانطور که در ادامه آمده تعریف شده‌است:


title: فهرست مسائل کوله‌پشتی

text: مجموعه formula_46 شامل formula_47 عضو و formula_48 شامل formula_49 عضو داده شده است، هر عضو formula_10 به یک زیرمجموعه formula_51 از مجموعه formula_52 مربوط میشود. برای هرformula_53 ، عضو formula_10ام ارزش نامنفی formula_2 دارد، و برای هر formula_56 ، عضو formula_57 ام وزن نامنفی formula_58 دارد. وزن کلی یک مجموعه از اعضا برابر با مجموع وزن اعضای متناظر آن در مجموعه است. هدف پیدا کردن زیرمجموعه ای از عضوها است که وزن کلی آن از حجم کوله‌پشتی بیشتر نشود و ارزش بیشینه را داشته باشد.


title: فهرست مسائل کوله‌پشتی

text: اگر بیشتر از یک محدودیت وجود داشته‌باشد (برای مثال هم محدودیت حجمی و هم محدودیت وزنی داشته‌باشیم، در حالی‌که حجم و وزن هر شی هیچ رابطه‌ای با یکدیگر ندارند)، به مسئلهٔ کوله‌پشتی با شرایط چندگانه، مسئله کوله‌پشتی چند بعدی، یا مسئله کوله‌پشتی m- بعدی می‌رسیم (توجه کنید که "بُعد" در این‌جا هیچ ارتباطی به شکل اشیا ندارد). این مسئله انواع 0-1، محدود و نامحدود دارد که نوع نامحدود آن در زیر نشان داده شده‌است:


title: فهرست مسائل کوله‌پشتی

text: formula_6 را بیشینه کنید، به طوریکه formula_60 ، برای هر formula_61


title: فهرست مسائل کوله‌پشتی

text: formula_62، formula_4 برای هر formula_64 عددی صحیح باشد.


title: فهرست مسائل کوله‌پشتی

text: در حدود سال 1980 نشان داده شد که نوع 0-1 مسئله (برای هر formula_65 ثابت) ان‌پی کامل است و به‌طور قویتر FPTAS ندارد مگر اینکه P = NP.


title: فهرست مسائل کوله‌پشتی

text: انواع محدود و نامحدود مسئله نیز (برای هرformula_65 ثابت) درجه سختی مشابه دارند.


title: فهرست مسائل کوله‌پشتی

text: برای هر formula_65 ثابت، این مسائل یک (مشابه مسئله کوله‌پشتی اصلی) و یک PTAS دارند.


title: فهرست مسائل کوله‌پشتی

text: اگر ارزش همهٔ اشیا یک باشد می‌توانیم تلاش کنیم تا تعداد اشیایی که کوله‌پشتی را کاملاً پر می‌کنند، کمینه کنیم:


title: فهرست مسائل کوله‌پشتی

text: formula_68 را کمینه کنید، به طوریکه formula_69 و formula_8، formula_71.


title: فهرست مسائل کوله‌پشتی

text: اگر تعدادی جعبه (با سایز یکسان) داشته باشیم و هدف قرار دادن همهٔ n شی در حداقل تعداد جعبه ممکن باشد به مسللهٔ (بسته بندی جعبه ها) می‌رسیم که با متغیرهای شاخص مدل می‌شود و formula_72 است اگر و تنها اگر جعبهٔ "i"م استفاده شود:


title: فهرست مسائل کوله‌پشتی

text: formula_73 را کمینه کنید، به طوریکه formula_74، formula_75


title: فهرست مسائل کوله‌پشتی

text: و formula_76، formula_77


title: فهرست مسائل کوله‌پشتی

text: و formula_78، formula_75


title: فهرست مسائل کوله‌پشتی

text: و formula_27، formula_81.


title: فهرست مسائل کوله‌پشتی

text: مسئلهٔ مشابه مسئلهٔ است، اما از آن‌جا که نمونه‌های عملی انواع کمتری از اعضا دارند، اغلب از فرمول دیگری استفاده می‌شود. عضو "j"م formula_82 مرتبه نیاز است، هر الگویی از اعضا که برای یک کوله‌پشتی مناسب باشد یک متغیر formula_83 دارد("m" الگو وجود دارد) و الگوی "i" عضو "j" را formula_84 بار استفاده می‌کند:


title: فهرست مسائل کوله‌پشتی

text: formula_85 را کمینه کنید، به طوریکه formula_86 برای هر  formula_1 و formula_88 برای هر formula_89.


title: فهرست مسائل کوله‌پشتی

text: اگر برای مسئله کوله‌پشتی چندگزینه‌ای که در آن‌ها چند انتخاب وجود دارد، این محدودیت که در آن سایز هر زیرمجموعه "n" باشد را اضافه کنیم و محدودیت بر روی وزن کلی را حذف کنیم، به مسئلهٔ assignment می‌رسیم که مسئلهٔ پیدا کردن یک بیشینه نیز است:


title: فهرست مسائل کوله‌پشتی

text: formula_90 را بیشینه کنید، به طوریکه formula_76 برای هر  formula_1


title: فهرست مسائل کوله‌پشتی

text: و formula_93 برای هر formula_94


title: فهرست مسائل کوله‌پشتی

text: و formula_27 برای هر formula_26 و برای هر formula_29.


title: فهرست مسائل کوله‌پشتی

text: در مسئله کوله‌پشتی با چگالی بیشینه وزن اولیه formula_98 است و ما تراکم اشیای انتخابی را تا زمانی‌که با محدودیت‌های ظرفیت مغایرت نداشته باشد، زیاد می‌کنیم:


title: فهرست مسائل کوله‌پشتی

text: formula_99 را بیشینه کنید، به طوریکه formula_7 و formula_8، formula_71.


title: فهرست مسائل کوله‌پشتی

text: تعداد دیگری مسئله‌های مشابه کوله‌پشتی نیز وجود دارند که البته نسبت به مسئله‌های ذکرشده کمتر متداول هستند، شامل:


title: فهرست مسائل کوله‌پشتی

text: سه مسئلهٔ آخر در مرجع کار Kellerer و همکارانش، Knapsack Problems، مورد بحث و بررسی قرار گرفته‌اند.


title: قلاب

text: قلاب به یکی از موارد زیر اشاره دارد:


title: چنگک (ابهام‌زدایی)

text: چنگک به یکی از موارد زیر اشاره دارد:


title: ونسا کارلتن

text: ونسا لی کارلتن (زاده ۱۶ اوت ۱۹۸۰) خواننده و آهنگساز آمریکایی است. نخستین تک‌آهنگ او به نام یک‌هزار مایل در سال ۲۰۰۱ در جایگاه پنجم ۱۰۰ آهنگ داغ بیلبورد قرار گرفت و موجب شهرت وی گردید. کارلتن تا سال ۲۰۱۱ چهار آلبوم استودیویی منتشر کرد.


title: ونسا کارلتن

text: کارلتن در جریان رژه دگرباشان نشویل در سال ۲۰۱۰ اعلام کرد که دوجنس‌گراست و به این موضوع افتخار می‌کند.


title: بتا اسکلت

text: در هندسۀ محاسباتی و نظریۀ گراف هندسی، بتا اسکلت یک گراف بدون جهت است که بر روی مجموعه‌ای از نقاط هندسۀ اقلیدسی تعریف می‌شود. دو نقطۀ p و q در صورتی توسط یک یال به یکدیگر متصل می‌شوند که همۀ زاویه‌های "prq" از آستانۀ تعیین شده توسط پارامتر عددی "β" کمتر باشد.


title: بتا اسکلت

text: اگر "β" یک عدد حقیقی مثبت باشد، زاویۀ "θ" با استفاده از فرمول زیر بدست می‌آید:


title: بتا اسکلت

text: برای هر دو نقطۀ "p" و "q" در صفحه، "R" را مجموعه‌ای از نقاط در نظر بگیرید به‌طوری‌که زاویۀ "prq" از "θ" بزرگتر باشد. در این صورت به ازای "β" ≥ 1 و "θ" ≤ π/2 مجموعۀ "R" به صورت اجتماع دو دایره با اندازۀ قطر "βd"("p","q") در خواهد آمد و به ازای "β" ≤ 1 و "θ" ≥ π/2 مجموعۀ "R" به صورت اشتراک دو دایره به قطر "d"("p","q")/"β" خواهد شد. در صورتی که "β" = 1 باشد هر دو فرمول بالا جواب "θ" = π/2 را خواهند داد و مجموعۀ "R" به صورت یک دایره به قطر "pq" خواهد شد.


title: بتا اسکلت

text: اگر "S" یک مجموعۀ مجزا از نقاط در صفحۀ هندسۀ اقلیدسی باشد، بتا اسکلت آن یک گراف بدون جهت است که در آن دو نقطۀ "p" و "q" در صورتی با یال "pq" به یکدیگر متصل می‌شوند که "R" حاوی هیچ یک از نقاط مجموعۀ "S" نباشد. در حقیقت بتا اسکلت یک گراف ناحیه خالی می‌باشد که با ناحیه‌های "R" تعریف شده‌اند. هنگامی که مجموعۀ "S" شامل نقطۀ "r" باشد به‌طوری‌که زاویۀ "prq" بزرگتر از "θ" باشد، "pq" یال بتا اسکلت نخواهد بود؛ بتا اسکلت شامل آن جفت "pq"هایی می‌باشد که همچین نقطۀ "r" ای برای آن‌ها وجود نداشته باشد.


title: بتا اسکلت

text: بعضی از نویسنده‌ها تعریف دیگری را بیان می‌کنند که در آن ناحیه‌های خالی "R" به ازای "β" > 1 اجتماع دو دایره نیستند بلکه عدسی می‌باشند (در این متن به آن‌ها هلال می‌گوییم )، یعنی اشتراک دو دایرۀ متناجس به قطر "βd"("p,q") هستند به‌طوری‌که پاره خط "pq" بر روی شعاع هر دو دایره قرار می‌گیرد و همچنین دو نقطۀ "p" و "q" روی مرز تقاطع دایره‌ها قرار خواهند گرفت. همانند تعریف مبتنی بر دایره، بتا اسکلت مبتنی بر هلال نیز، در صورتی دارای یال "pq" می‌باشد که ناحیۀ "R" از نقاط دیگر خالی باشد. با توجه به این تعریف، گراف همسایۀ مرتبط یک حالت خاص از بتا اسکلت با "β" = 2 می‌باشد. هر دو تعریف مبتنی بر دایره و مبتنی بر هلال به ازای "β" ≤ 1 یکسانند اما برای مقادیر بزرگ‌تر "β"، تعریف بتا اسکلت مبتنی بر دایره زیر گرافی از بتا اسکلت مبتنی بر هلال می‌باشد.


title: بتا اسکلت

text: یک تفاوت مهم میان بتا اسکلت مبتنی بر دایره و هلال در این است که به ازای هر مجموعه نقاطی که روی یک خط قرار نداشته باشند، همیشه یک مقدار به اندازۀ کافی بزرگ برای "β" وجود دارد که بتا اسکلت مبتنی بر دایرۀ آن یک گراف تهی باشد. در مقابل اگر یک جفت نقاط "p" و "q" دارای این ویژگی باشند که برای همۀ نقاط "r" دیگر، یکی از دو زاویۀ "pqr" و "qpr" منفرجه شود، در آن صورت بدون توجه به این‌که "β" چقدر بزرگ باشد بتا اسکلت مبتنی بر هلال حتماً حاوی یال "pq" خواهد بود.


title: بتا اسکلت

text: بتا اسکلت اولین بار توسط به عنوان یک گونۀ مستقل از مقیاس از شکل‌های آلفای مطرح شد. نام “بتا اسکلت” به این علت ایجاد شده‌است که بتا اسکلت از بعضی جهات شکل یک مجموعه نقاط را شرح می‌دهد به همان طریقی که اسکلت توپولوژی شکل ناحیه‌های دوبعدی را بیان می‌کند. انواع بسیار دیگری از گراف‌های بتا اسکلت وجود دارند که با ناحیه‌های خالی دیگر تعریف می‌شوند.


title: بتا اسکلت

text: اگر β به صورت پیوسته از 0 تا ∞ تغییر کند، β-اسکلت‌های مبتنی بر دایره دنباله‌ای از گراف‌ها را، از گراف کامل تا گراف تهی، تشکیل می‌دهند. حالت خاصّ β=1 گراف گابریل را نتیجه می‌دهد که شامل درخت پوشای کمینۀ اقلیدسی است. بنابراین، زمانی که β≤1، یک β-اسکلت شامل گراف گابریل و درخت پوشای کمینه هم هست.


title: بتا اسکلت

text: برای هر β ثابت، می‌توان از یک ساختار فراکتال که نمایانگر نسخۀ مسطح برف‌دانۀ کخ باشد برای مشخص کردن دنباله‌ای از گروه نقطه‌ها که β-اسکلت‌های آن‌ها مسیرهایی به طول دلخواه در یک مربع واحد است، استفاده کرد. بنابراین، برخلاف مسئلۀ مرتبطِ مثلث‌بندی دیلانی، β-اسکلت‌ها پوشای هندسی نیستند.


title: بتا اسکلت

text: یک الگوریتم بدیهی که برای هر سه‌تایی formula_2، formula_3 و formula_4 عضویت formula_4 را در محدودۀ formula_6 بررسی می‌کند، می‌تواند برای هر مجموعۀ formula_7تایی از نقاط، β-اسکلت را در زمان formula_8 بسازد.


title: بتا اسکلت

text: به ازای β≥1، یک β-اسکلت (با هر یک از تعریف‌ها) زیرگرافی از گراف گابریل است که آن هم زیرگرافی از مثلث‌بندی دیلانی است. اگر formula_9 یکی از یال‌های مثلث‌بندی دیلانی باشد که به β-اسکلت تعلق ندارد، آن‌گاه نقطۀ formula_4، یکی از دو نقطه‌ای که در مثلث‌بندی دیلانی با formula_3 و formula_2 تشکیل مثلث می‌دهند، زاویۀ بزرگ formula_13 را درست می‌کند. در نتیجه، برای این مقادیر β، یک β-اسکلت مبتنی بر دایره با محاسبۀ مثلث‌بندی دیلانی و حذف کردن یال‌های اضافی با این آزمون برای یک مجموعۀ شامل formula_7 نقطه در زمان formula_15 ساخته می‌شود.


title: بتا اسکلت

text: به ازای β<1 الگوریتم دیگری از ساختن β-اسکلت را در زمان formula_16 ممکن می‌سازد. کران بالای بهتری برای زمان اجرا در بدترین حالت ممکن نیست. زیرا برای هر مقدار ثابت β در محدودۀ ۰ تا ۱، در حالت کلی مجموعه‌هایی از نقاط وجود دارند که β-اسکلت آن‌ها یک گراف کامل است که تعداد یال‌هایش با توان دوم تعداد نقاط متناسب است. همچنین تمام طیف β (دنبالۀ β-اسکلت‌های مبتنی بر دایره که از تغییر مقدار β به‌دست می‌آیند) در زمان مشابه (درجۀ دو) محاسبه می‌شود.


title: بتا اسکلت

text: از β-اسکلت مبتنی بر دایره می‌توان در آنالیز تصویر برای بازسازی شکل یک شیء دو بعدی با داشتن مجموعه‌ای از نقاط نمونه روی مرز آن شیء استفاده کرد.(شکل محاسباتی بازی وصل کردن نقاط، که در آن ترتیب نقطه‌ها در صورت مسئله نیست و باید توسط یک الگوریتم به دست آید.) اگرچه برای این کار باید مقدار مناسبی برای پارامتر β اتخاذ شود، ثابت می‌شود به ازای β=1.7، در صورتی که نسبت تراکم نمونه‌ها به انحنای موضعی سطح به اندازۀ کافی زیاد باشد، β-اسکلت تمام مرز هر سطح صاف را بازسازی می‌کند و هیچ یال اضافی‌ای تولید نمی‌کند. البته در عمل، مقدار β=1.2 در یک سامانه اطلاعات جغرافیایی برای بازسازی نقشۀ خیابان‌ها از روی مجموعه‌ای از نقاط که روی خط میانی خیابان‌ها بودند مناسب‌تر بود. برای حالت‌های تعمیم‌یافتۀ روش β-اسکلت برای بازسازی سطوح در سه بعد، را ببینید.


title: بتا اسکلت

text: از β-اسکلت‌های مبتنی بر دایره برای یافتن زیرگراف‌های مثلث‌بندی با وزن کمینه‌ی یک مجموعه از نقاط استفاده می‌شود: برای مقادیر به اندازۀ کافی بزرگ β، هر یال β-اسکلت به مثلث‌بندی با وزن کمینه تعلق دارد. اگر نقاط ورودی با این یال‌ها یک گراف همبند را تشکیل دهند، یال‌های باقی‌ماندۀ مثلث‌بندی با وزن کمینه با برنامه‌نویسی پویا در زمان چندجمله‌ای به دست می‌آیند. البته مسئلۀ مثلث‌بندی با وزن کمینه در حالت کلی ان‌پی-سخت است و یال‌های به دست آمده با این روش الزاماً یک گراف همبند درست نمی‌کنند.


title: بتا اسکلت

text: علاوه بر این، β-اسکلت‌ها در یادگیری ماشین برای حلّ مسائل شناسایی هندسی و در شبکه‌های بی‌سیم ادهاک به عنوان یک سازوکار برای کنترل پیچیدگی ارتباط، با انتخاب یک زیرمجموعه از جفت ایستگاه‌های بی‌سیم که توانایی ارتباط با یک‌دیگر را دارند، کاربرد دارند.


title: الگوریتم ایجاد هزارتو

text: الگوریتم‌های ایجاد هزارتو روش‌هایی خودکار برای تولید هزارتو (ماز) هستند.


title: الگوریتم ایجاد هزارتو

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


title: الگوریتم ایجاد هزارتو

text: این الگوریتم یک نسخه تصادفی از الگوریتم جستجوی عمق-اول است. این الگوریتم که غالباً توسط پشته پیاده‌سازی می‌شود یکی از ساده‌ترین راه‌ها برای تولید یک هزارتو توسط رایانه است. فضای هزارتو را یک شبکه بزرگ از خانه‌ها (مانند یک صفحه شطرنج) تصور کنید به‌طوری‌که هر خانه در آن با ۴ دیوار در اطراف آن وجود دارند. با آغاز از یک خانه تصادفی، برنامه یکی از همسایه‌های آن خانه را که تاکنون انتخاب نشده‌است به‌طور تصادفی انتخاب می‌کند. حال دیوار بین آن دو خانه برداشته می‌شود و خانه جدید به پشته اضافه می‌شود (این کار مشابه کشیدن یک خط روی زمین است). سپس برنامه با همین روند ادامه پیدا می‌کند، با رسیدن به خانه‌ای که هیچ همسایهٔ قابل عزیمتی ندارد (همه همسایه‌های آن دیده شده‌اند) برنامه به بن‌بست می‌رسد. در این مرحله مسیر طی شده در جهت عکس طی می‌شود تا اولین رأس با حداقل یک همسایه رویت نشده یافت شود. سپس مسیر با رویت این خانه جدید ادامه پیدا می‌کند (این کار معادل ساخت یک نقطه اتصال در هزارتو است). کار تا جایی ادامه پیدا می‌کند که تمامی خانه‌ها یک‌بار رویت شوند. در این حالت برنامه تمام مسیر را به سمت خانه اولیه بازمی‌گردد. این رویکرد، مشاهده تمام خانه‌های فضای هزارتو را تضمین می‌کند. همان‌طور که پیشتر بیان شد الگوریتم بسیار ساده عمل کرده و به تبع آن هزارتوهای بسیار پیچیده‌ای را هم تولید نمی‌کند. برخی اصلاحات مانند اصلاحات زیر می‌تواند به پیچیده‌تر کردن هزارتوهای ساخته شده کمک کند. همان‌طور که در بالا اشاره شد این الگوریتم دربردارنده یک روند بازگشتی عمیق است که در برخی معماری‌های رایانه می‌تواند موجب سرریز از پشته شود. می‌توان با ذخیره کردن اطلاعات حاصل از بازگشت از هر خانه بر روی هزارتو الگوریتم را به یک حلقه تغییر داد. این کار در عین حال یک راه سریع برای نشان‌دادن جواب را نیز ارائه می‌دهد:با شروع از هر خانه و بازگشت مسیر به سمت خانه خروج می‌توان مسیر موردنظر را تولید کرد. هزارتوهایی که با روش جستجوی عمق-اول ایجاد می‌شوند ضریب شاخه کمتری دارند (شکست‌های کمتری در هر شاخه به وجود می‌آورند) و راهروهای زیادی را دربردارند. این امر باعث می‌شود که الگوریتم جستجوی عمق-اول برای تولید هزارتو در بازی‌های ویدئویی مناسب باشد. با حذف کردن تصادفی تعدادی از دیوارها در هزارتوی تولید شده با این روش، می‌توان راهروهای طولانی و باریک را شاخه‌دارتر کرد. این روش برای تولید هزارتوهایی با درجه دشواری کمتر مناسب است. هم‌چنین این حالت نیز برای تولید بازی‌های ویدئویی مطلوب است.


title: الگوریتم ایجاد هزارتو

text: الگوریتم جستجوی عمق-اول در تولید هزارتو به‌طور معمول با استفاده از روش پس‌گرد پیاده‌سازی می‌شود.


title: الگوریتم ایجاد هزارتو

text: این الگوریتم نسخه تصادفی الگوریتم کروسکال است. داده ساختارهای متفاوتی وجود دارند که می‌توانند مجموعه‌هایی از خانه‌ها را شبیه‌سازی کنند. یک راه پیاده‌سازی کارا که توسط داده ساختار مجموعه‌های مجزا صورت می‌گیرد، می‌تواند هر عمل اجتماع و یافتن روی دو مجموعه را به‌طور سرشکن در زمان خطی انجام دهد (به‌طور دقیق تر زمان formula_1 ; formula_2 به ازای هر formula_3). بنابراین زمان اجرای این الگوریتم در اصل با تعداد دیوارهای موجود در هزارتو متناسب است. این مسئله که فهرست دیوارها ابتدا به‌طور تصادفی مقداردهی اولیه شود یا هر دیوار به‌طور تصادفی از بین فهرست غیرتصادفی از دیوارها انتخاب شود، اهمیت چندانی ندارد. هر کدام از این دو روش نیز در پیاده‌سازی در یک سطح از سادگی قرار دارند. از آنجا که نتیجه این الگوریتم، تولید درخت پوشای کمینه یک گراف با یال‌های هم‌وزن است، الگوریتم به سمت تولید الگوهای منظمی که به نسبت ساده‌تر حل می‌شوند، متمایل است.


title: الگوریتم ایجاد هزارتو

text: این الگوریتم نسخه تصادفی الگوریتم پریم است. مانند الگوریتم جستجوی عمق-اول، یافتن راه به سمت خانه اول معمولاً به نسبت ساده است اما به سمت دیگر خانه‌های هزارتو دشوار. توجه کنید که اجرای الگوریتم کلاسیک پریم بر روی یک گراف با وزن تصادفی هزارتوهایی با الگویی مشابه با هزارتوهای تولید شده در الگوریتم کروسکال ایجاد می‌کند. چرا که هر دو الگوریتم به یافتن درخت پوشای کمینه اختصاص دارند. در عوض، الگوریتم حاضر الگوی متفاوتی از هزارتوها را ایجاد می‌کند. چرا که یال‌های نزدیک‌تر به نقطه آغازین وزن مؤثر کمتری دارند.


title: الگوریتم ایجاد هزارتو

text: با وجود اینکه الگوریتم کلاسیک پریم فهرستی از یال‌ها را ذخیره می‌کند، برای تولید هزارتو می‌توان لیستی از خانه‌های مجاور به هر خانه را ذخیره کرد. اگر یک خانه تصادفی توسط چندین یال به هزارتو موجود متصل شود یکی از این یال‌ها به‌طور تصادفی انتخاب می‌شود. این روش تمایل بیشتری به ایجاد شاخه نسبت به روش بالا که مبتنی بر ذخیره یال بود دارد.


title: الگوریتم ایجاد هزارتو

text: هزارتوها می‌توانند از طریق تقسیمات بازگشتی ساخته شوند. یک الگوریتم برای این کار در زیر شرح داده شده‌است: از یک فضای بدون دیوار شروع کن و آن را یک اتاق بنام. اتاق را با دیوارهایی که به‌طور تصادفی قرار می‌گیرند تقسیم کن (برای هر دیوار یک دهانه برای شروع یک راهرو، در نقطه‌ای تصادفی روی آن دیوار قرار دارد). حال به‌طور بازگشتی همین عملیات را روی اتاق‌های درونی انجام بده تا زمانی که همه اتاق‌ها به اندازه کمینه برسند. این روش منجر به تولید هزارتوهایی می‌شود که در آن‌ها دیوارهای راست و طولانی عبور می‌کنند. این الگو هزارتوهایی تولید می‌کند که در آن‌ها نواحی‌ای که بهتر است از ورود به آن‌ها خودداری شود، ساده‌تر دیده می‌شوند. برای مثال، در یک هزارتو مستطیلی، در یک نقطه تصادفی از فضا دو دیوار که به یکدیگر عمود هستند را بسازید. این دو دیوار اتاق اولیه را به چهار اتاق کوچک‌تر تقسیم می‌کنند که توسط چهار دیوار از یکدیگر جدا شده‌اند. سه دیوار از این چهار دیوار را به‌طور تصادفی انتخاب کنید و یک روی هر کدام از آن‌ها و در نقطه‌ای تصادفی بر روی آن‌ها یک دهانه ورودی به عرض یک واحد ایجاد کنید. این روند را به‌طور بازگشتی ادامه دهید تا زمانی که تمامی اتاق‌ها عرضی برابر یک واحد در یکی از بعدهای خود داشته باشند.


title: الگوریتم ایجاد هزارتو

text: الگوریتم‌های دیگری نیز وجود دارند که تنها به میزان کافی حافظه برای ذخیره یک ردیف از یک هزارتو دوبعدی یا یک صفحه از یک هزارتو سه‌بعدی نیازمند هستند. این الگوریتم‌ها با ذخیره کردن خانه‌هایی در ردیف کنونی که به خانه‌هایی از ردیف قبل مسیر دارند، از ایجاد حلقه جلوگیری می‌کنند. اکثر الگوریتم‌های تولید هزارتو برای اطمینان از قابل حل بودن هزارتو نهایی، نیازمند نگه‌داری ارتباط میان خانه‌های درونی هستند. هرچند هزارتوهای معتبر و همبند تنها با تمرکز بر روی هر خانه قابل تولید هستند. هزارتو درخت دودویی، یک هزارتو استاندارد با خطوط عمود بر هم است که در آن هر خانه یک راهرو به سمت بالا یا چپ دارد اما هر دو آن‌ها را نمی‌تواند داشته باشد. برای ساخت یک هزارتو درخت دودویی، برای هر خانه با انداختن سکه تصمیم گرفته می‌شود که حرکت به سمت بالا یا چپ انجام شود. برای خانه‌های روی مرز همواره یک جهت اتخاذ می‌شود و نتیجه نهایی یک هزارتو معتبر همبند ساده خواهد بود که ظاهری مانند درخت دودوییای دارد که ریشه آن، خانه بالا سمت چپ است. جای‌گزین انداختن سکه برای هر خانه، ساخت یک عکس با استفاده از ترکیبی تصادفی از کاراکترهای ممیز و ممیز رو به عقب ("\") است. این روش یک هزارتو همبند ساده و معتبر را ایجاد نمی‌کند اما گروهی از حلقه‌های بسته را ایجاد می‌کند (راهنمای استفاده از کمودور ۶۴ یک برنامه پایه را با استفاده از این الگوریتم ارائه می‌دهد، با این تفاوت که از کاراکترهای مورب گرافیکی PETSCII برای یک نمایش گرافیکی روان‌تر استفاده می‌کند).


title: الگوریتم ایجاد هزارتو

text: انواع مشخصی از خودکاره‌های شبکه می‌توانند در تولید هزارتو مورد استفاده قرار گیرند. دو نوع مشهور از این خودکاره‌های شبکه، ماز و مازکتریک، دارای قوانین رشته‌ایB۳/S۱۲۳۴۵ و B۳/S۱۲۳۴ هستند. در حالت اول، این بدان معنی است که هر خانه به این شرط از یک مرحله به مرحله بعدی باقی می‌ماند که حداقل یک و حداکثر پنج همسایه داشته باشد. در حالت دوم، هر خانه با داشتن یک تا چهار همسایه باقی می‌ماند. اگر خانه‌ای دقیقاً سه همسایه داشته باشد متولد می‌شود. برای یک الگوی شروع تصادفی، این خودکاره‌های تولیدکننده هزارتو مشبک به تولید هزارتوهایی پیچیده منجر می‌شوند که دیوارهای راهروهای آن به‌طور غیرمبهمی ترسیم شده‌اند. مازکتریک که دارای قانون B۳/S۱۲۳۴ است، در مقایسه با ماز با قانون B۳/S۱۲۳۴۵ گرایشی به تولید راهروهای طولانی و باریک دارد. این یک عیب قابل توجه محسوب می‌شود چرا که این هزارتوها به نسبت قابل پیش‌بینی می‌شوند. مانند برخی از روش‌های مبتنی بر نظریه گراف که در بالا به تفصیل بیان شد، این خودکاره‌های مشبک عموماً هزارتوهایی از یک الگوی آغازین یکتا تولید می‌کنند؛ بنابراین معمولاً منجر به تولید هزارتوهایی می‌شوند که یافتن راه به خانه ابتدایی در آن‌ها به نسبت ساده است، حال آنکه راه‌یابی به دیگر خانه‌ها به نسبت دشوارتر است.


title: الگوریتم ایجاد هزارتو

text: class MazeBuilder implements Runnable {


title: زمان‌بندی مغازه کارها

text: زمان‌بندی مغازه کارها یا مسئلهٔ زمان‌بندی کار کارگاهی یا مسئلهٔ مغازۂ کارها یک مسئلهٔ بهینه‌سازی علوم رایانه و تحقیق در عملیات است که در آن شغل‌های ایده‌آل به منابع در زمان‌های خاصی نسبت داده می‌شوند. صورت اصلی آن در ادامه آمده‌است:


title: زمان‌بندی مغازه کارها

text: در این مسئله n شغل j1, j2, …, jn با اندازه‌های متفاوت که باید روی m ماشین یکسان زمان‌بندی شوند در تلاشند تا زمان کل(makespan) را به حداقل برسانند. زمان خالی مجموع زمان لازم برای انجام همهٔ شغل‌هاست (که همهٔ شغل‌ها تمام شده‌اند).


title: زمان‌بندی مغازه کارها

text: امروزه، این مسئله به عنوان یک مسئلهٔ پویا(dynamic scheduling) مطرح می‌شود، که با ارائه شدن هر شغل، الگوریتم پویا باید با اطلاعات موجود تصمیم‌گیری کند قبل از اینکه شغل بعدی مطرح شود.


title: زمان‌بندی مغازه کارها

text: این مسئله یکی از مشهورترین مسائل پویاست، و اولین مسئله‌ای بود که برای آن تحلیل رقابتی(competitive analysis) به وسیلهٔ Graham در سال ۱۹۶۶ مطرح شد. بهترین نمونه‌های مسئله برای مدل پایه با هدف بهینه‌سازی زمان کل به وسیلهٔ Taillard مطرح شد.این مسئله حداقل هفتاد سال قدمت دارد.


title: زمان‌بندی مغازه کارها

text: (disjunctive graph) یکی از بهترین مدل‌های مورد استفاده برای تشریح‌کردن سامانه‌های مختلف این مسئله است.


title: زمان‌بندی مغازه کارها

text: لیست الگوریتم‌های زمان‌بندی موجود در سال ۱۹۶۶ را گراهام از قبل آماده کرده بود، که تمامی آن‌ها (2-1/m)رقابتی بوده‌اند. منظور از m در این‌جا تعداد ماشین‌ها است. همچنین این امر که زمان‌بندی لیست، راه حل بهینه برای مسئلهٔ آنلاین ۲ یا ۳ ماشین است اثبات شده بود. در سال ۹۲ برای مشاغل یکسان طول، برای ۲ ماشین نیز بهینه و (2-2/m) رقابتی است. در سال ۱۹۹۲، بارتال، فیات، کارلفت و وهرا الگوریتمی ۱٫۹۸۶-رقابتی ارائه کردند. در سال ۱۹۹۴، کارگر، فیلیپس و تورنگ یک الگوریتم ۱٫۹۴۵ رقابتی ارائه دادند. در سال ۱۹۹۲، آلبرز یک الگوریتم جدید که ۱٫۹۲۳-رقابتی بود ارائه داد. در حال حاضر، بهترین پاسخ موجود، الگوریتمی از فلیشر و وهل می‌باشد که یک راه حل ۱٫۹۲۰رقابتی است.


title: زمان‌بندی مغازه کارها

text: یک حد پایین ۱٫۸۵۲-رقابتی نیز توسط آلبرز ارائه داده شد. نمونه‌های Taillard نقش مهمی در ایجاد زمان‌بندی مغازهٔ کار با اهداف مدت ایجاد(makespan objectives) ایفا می‌کنند.


title: زمان‌بندی مغازه کارها

text: در سال ۱۹۷۶ گری، اثبات کرد که این مسئله برای nهای بزرگ‌تر از ۲ یک مسئلهٔ است، به این معنا که برای بیش از ۳ ماشین، نمی‌توان راه‌حلی از زمان چندجمله ای برای حل این مسئله ارائه داد.


title: زمان‌بندی مغازه کارها

text: ساده‌ترین حالت مسئله حداقل‌کردن offline makespan برای مشاغل اتومیک می‌باشد، که در این مشاغل اتومیک، مشاغلی هستند که شغل قابلیت تقسیم‌شدن به مشاغل کوچکتر را ندارد. برای مثال، این مفهوم مشابه بسته‌بندی کردن چندین تکه با حجم‌های متفاوت درون تعداد ثابتی از صندوق‌ها، به گونه‌ای که بزرگترین حجم صندوق مورد نیاز، در کمترین حد ممکن باشد. (در صورتی که حالت برعکس این مورد، یعنی کمینه کردن تعداد صندوق‌ها و ثابت‌بودن سایز هر صندوق مد نظر باشد، این مسئله تبدیل به مسئلهٔ دیگری به نام می‌شود).


title: زمان‌بندی مغازه کارها

text: هاشبوم و یک را در سال ۱۹۸۷ ارائه دادند که یک راه حل تخمینی برای مسئله را با هر درجه‌ای از دقت که مد نظر باشد به دست می‌آورد.


title: زمان‌بندی مغازه کارها

text: حالت ابتدایی از زمان‌بندی کردن مشاغل با چندین عملیات(M)، بر روی چندین ماشین (M)، به گونه‌ای که تمامی عملیات اول باید روی ماشین اول اجرا شوند، تمامی عملیات دوم روی ماشین دوم و …. و چند شغل نمی‌توانند به صورت موازی اجرا شوند، به عنوان مسئله زمان‌بندی مغازهٔ باز شناخته می‌شوند. الگوریتم‌های مختلفی برای این سؤال موجود است، از جمله الگوریتم‌های ژنتیک.


title: زمان‌بندی مغازه کارها

text: برای حل حالتی از این مسئله که در آن ۲ ماشین وN شغل متفاوت موجود است و تمامی مشاغل باید به ترتیب مورد پردازش قرارگیرند، می‌توان از یک الگوریتم مکاشفه‌ای که توسط S.M. Johnson ایجاد شده‌است، استفاده کرد. قدم‌های مختلف این الگوریتم به صورت زیر است:


title: زمان‌بندی مغازه کارها

text: شغل Pi دارای دو عمل است، طول هرکدام از این عمل‌ها pi۱ و pi۲ است، که روی ماشین‌های M۱ و M۲ به همان ترتیب اجرا می‌شوند.


title: زمان‌بندی مغازه کارها

text: در صورتی که کمینه به Pk۱ تعلق داشته باشد، K را از لیست A حذف کنید، K را به انتهای لیست L۱ اضافه نمایید.


title: زمان‌بندی مغازه کارها

text: در صورتی که مقدار کمینه به Pk۲ تعلق داشته باشد،


title: زمان‌بندی مغازه کارها

text: روش جانسون، تنها در حالتی که دو ماشین داشته باشیم به صورت بهینه کار می‌کند. اما از آن جهت که این روش، روشی بهینه و ساده برای محاسبه است، بعضی از پژوهشگران در جهت تعمیم این الگوریتم به حالت M ماشین تلاش کرده‌اند.


title: زمان‌بندی مغازه کارها

text: ایده مورد نظر به صورت زیر است:


title: زمان‌بندی مغازه کارها

text: تصور کنید که هر شغل، نیاز به M عمل مختلف دنبال هم، روی M1, M2, M3, …, Mm دارد. ما به این گونه عمل می‌کنیم که m/۲ ماشین اول را به یک ماشین بزرگ (موهومی) تبدیل می‌کنیم و آن را MC۱ می‌نامیم. ماشین‌های باقی‌مانده دیگر را نیز به یک ماشین بزرگ دیگر به نام MC۲ تبدیل می‌کنیم.


title: زمان‌بندی مغازه کارها

text: در این صورت، زمان پردازش نهایی برای شغل P روی MC۱ برابر است با مجموع زمان عمل‌ها روی m/۲ ماشین اول و زمان پردازش نهایی شغل p روی MC۲ برابر با مجموع زمان عمل‌ها روی m/۲ ماشین آخر است.


title: زمان‌بندی مغازه کارها

text: در این صورت، ما توانستیم این مسئلهٔ m-machine را به یک مسئلهٔ برنامه‌ریزی ۲-machine کاهش دهیم. حال می‌توانیم با استفاده از الگوریتم جانسون، این مسئله را حل کنیم.


title: زمان‌بندی مغازه کارها

text: این‌جا یک مثال از مسئله زمان‌بندی مغازهٔ کارها که به صورت به عنوان یک مسئلهٔ محدودیت‌های نشانگر آورده شده‌است. param N_JOBS;


title: زمان‌بندی مغازه کارها

text: param N_MACHINES;


title: زمان‌بندی مغازه کارها

text: set JOBS ordered = 1..N_JOBS;


title: زمان‌بندی مغازه کارها

text: set MACHINES ordered = 1..N_MACHINES;


title: زمان‌بندی مغازه کارها

text: param ProcessingTime{JOBS, MACHINES}> 0;


title: زمان‌بندی مغازه کارها

text: param CumulativeTime{i in JOBS, j in MACHINES} = sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];


title: زمان‌بندی مغازه کارها

text: param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} = max {j in MACHINES}(CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);


title: زمان‌بندی مغازه کارها

text: var end>= ۰;


title: زمان‌بندی مغازه کارها

text: var start{JOBS}>= ۰;


title: زمان‌بندی مغازه کارها

text: var precedes{i1 in JOBS, i2 in JOBS: ord(i1) = start[i] + sum{j in MACHINES} ProcessingTime[i,j];


title: زمان‌بندی مغازه کارها

text: subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1)  start[i2]>= start[i1] + TimeOffset[i1,i2];


title: زمان‌بندی مغازه کارها

text: subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1)  start[i1]>= start[i2] + TimeOffset[i2,i1];


title: زمان‌بندی مغازه کارها

text: data;


title: زمان‌بندی مغازه کارها

text: param N_JOBS := ۴;


title: زمان‌بندی مغازه کارها

text: param N_MACHINES := ۳;


title: زمان‌بندی مغازه کارها

text: param ProcessingTime:


title: زمان‌بندی مغازه کارها

text: ۱ ۲ ۳ := ۱ ۴ ۲ ۱


title: زمان‌بندی مغازه کارها

text: ۲ ۳ ۶ ۲


title: زمان‌بندی مغازه کارها

text: ۳ ۷ ۲ ۳


title: زمان‌بندی مغازه کارها

text: ۴ ۱ ۵ ۸;


title: رنگ‌آمیزی فهرستی گراف

text: در نظریه گراف، که شاخه‌ای از ریاضیات است، رنگ‌آمیزی لیستی نوعی از رنگ‌آمیزی گراف است. در این رنگ‌آمیزی برای هرراس لیستی از رنگ‌ها وجود دارد که آن راس می‌تواند توسط یکی از رنگ‌های این لیست رنگ شود. این شاخه ابتدا توسط ویزینگ، اردوش، رابین و تیلور مورد مطالعه قرار گرفت و بنیان آن بنا شد.


title: رنگ‌آمیزی فهرستی گراف

text: G را یک گراف در نظر بگیرید و برای هر راس مانند v از گراف، (L(v را لیستی از رنگ‌های موجود برای آن رأس، تعریف کنید. رنگ‌آمیزی لیستی یک رنگ‌آمیزی انتخابی است که به هر راس مانند v یک رنگ دلخواه از لیست رنگ‌های آن راس ((L(v) متناظر می‌کند. به یک رنگ‌آمیزی لیستی خوب می‌گوییم هرگاه هیچ دو راس مجاوری همرنگ نباشند. یک گراف را k-لیست رنگ‌پذیر می‌نامیم هرگاه مستقل از این که لیست k رنگیِ رنگ‌های هر راس چیست، یک رنگ‌آمیزی لیستی خوب برای آن وجود داشته‌باشد. عدد رنگی لیستی ((ch("G") گراف "G"، کوچکترین عدد k است که گراف "k"، G رنگ‌پذیر است.


title: رنگ‌آمیزی فهرستی گراف

text: به بیان دقیق‌تری، برای یک تابع مانند f که به هر راس مانند v یک عدد صحیح مثبت، (f(v را نسبت می‌دهد، گراف "G" را f-لیست رنگ‌پذیر می‌نامند، هرگاه مستقل از این که لیست (f(v رنگیِ هر راس مانند v شامل چه رنگ‌هایی باشد، یک رنگ‌آمیزی لیستی خوب برای آن وجود داشته‌باشد. به‌طور خاص اگر برای هر راس مانند f(v) = k "،v" باشد، گراف k-لیست رنگ‌پذیر می‌باشد.


title: رنگ‌آمیزی فهرستی گراف

text: فرض کنید "q" یک عدد صحیح مثبت باشد و "G" یک گراف کامل دوبخشی "K" باشد. رنگ‌های موجود را با "q" عدد دو رقمی مختلف در مبنای q نمایش می‌دهیم. در بخشی از این گراف دو بخشی که "q" راس دارد، هر راس از گراف را متناظر با مجموعه‌ای از رنگ‌ها در نظر می‌گیریم که رقم باارزش آن‌ها یکسان است. برای مثال به راس شمارهٔ i ام مجموعه رنگ‌های {i0,i1, … ,iq} متناظر می‌کنیم. در بخش دیگر از این گراف دو بخشی، به هر راس از "q" راس این گراف یک مجموعه از رنگ‌ها مانند {... ,0a, 1b, 2c}، به طوری که رقم باارزش آن‌ها متفاوت باشد. به تعداد "q" تا مجموعه با چنین خاصیتی وجود دارد، زیرا تعداد q-تایی‌های (...,a,b,c) برابر با "q" است. برای مثال اگر q" = 2" باشد، گراف دو بخشی "K" خواهیم داشت. در این گراف دو راس واقع در یک بخش این گراف مجموعه رنگ‌های {00,01}, {10,11} و 4 راس واقع در بخش دیگر گراف مجموعه رنگ‌های {00,10}, {00,11}, {01,10}, {01,11} را دارند. تصویر روبرو یک مثال بزرگ‌تر را به ازای q" = 3" نشان می‌دهد.


title: رنگ‌آمیزی فهرستی گراف

text: عدد رنگی لیستی گراف "G" از "q" کوچک‌تر یا مساوی نیست. مستقل از این که چه رنگی برای هر راس انتخاب شود، در بخش بزرگ‌تر راسی که لیست رنگی آن برابر با مجموعه رنگ‌های بخش کوچک‌تر است، نمی‌تواند رنگ شود. برای مثال اگر راس با لیست رنگی {00,01} با 01 و راس با لیست رنگی {10,11} با 10 رنگ شود، سپس راس با لیست رنگی {01,10} با هیچ‌کدام از دو رنگ 01 و 10 نمی‌تواند رنگ شود. بنابراین عدد رنگی لیستی "G" حداقل "q" + 1 است.


title: رنگ‌آمیزی فهرستی گراف

text: به‌طور مشابه، اگر formula_1، گراف کامل دو بخشی"k"، "K"-لیست رنگ‌پذیر نیست. فرض کنید 2k-1 رنگ موجود باشد و در یک بخش از گراف هر راس با بقیه رئوس در یک "k"-تایی از این رنگ‌ها متفاوت باشد. پس هر بخش از گراف باید حداقل از "k" رنگ استفاده کند، در غیر این‌صورت، بعضی از راس‌ها، بی‌رنگ می‌مانند، اما این شرط باعث می‌شود که دو راس مجاور هم‌رنگ باشند. به‌طور خاص گراف مسئله سه روستا، 3-لیست رنگ‌پذیر و گراف کامل دوبخشی که هر بخش آن n رأس دارد ۴-لیست رنگ‌پذیر است. عدد رنگی لیستی (ch("G" از قواعد زیر برای گراف "G" با "n" راس، عدد رنگی ("X("G و بیشینه درجه (Δ("G" :


title: رنگ‌آمیزی فهرستی گراف

text: دو مسئله الگوریتمی که مطرح شده‌است: مسئلهٔ "k"-لیست رنگ‌پذیری در گراف‌های دوبخشی برای هر "k" ≥ 3 formula_3-کامل است، و به‌طور مشابه برای 4-لیست رنگ‌پذیری در گراف‌های مسطح، 3-لیست رنگ‌پذیری در گراف‌های بدون مثلثی، (2, 3)-لیست رنگ‌پذیری برای گراف‌های مسطح دوبخشی.


title: رنگ‌آمیزی فهرستی گراف

text: می‌توان در زمان خطی مشخص کرد که یک گراف 2-لیست رنگ‌پذیر است یا نه. برای این کار به‌طور مکرر راس‌های درجه صفر یا یک را حذف می‌کنیم تا جایی که به یک گراف با بیشینه درجه‌ی دو برسیم. گراف اولیه k-لیست رنگ‌پذیر است اگر و تنها اگر گراف ساده شده یک دور زوج یا یک گراف تتا باشد که از سه مسیر با نقطهٔ پایانی مشترک تشکیل شده‌باشد، که طول 2 تا از آن‌ها دو و طول سومی زوج باشد.


title: آبشاره‌سازی جزءبه‌جزء

text: در علوم رایانه، آبشاره‌سازی جزءبه‌جزء (Fractional cascading) روشی است که با آن می‌توان، دنبال‌های از جستجوهای دودویی را انجام داد و یک مقدار مشخص را از میان دنباله‌ای از ساختار داده‌های مرتبط به هم، با سرعت بالایی جستجوی دودویی کرد.


title: آبشاره‌سازی جزءبه‌جزء

text: اولین جستجو، بنا به حالت عادی یک جستجوی دودویی، در زمانی لگاریتمی انجام می‌شود، اما جستجوهای بعدی سریعتر خواهند بود. روش آبشاره‌سازی جزءبه‌جزء نخستین بار در سال ۱۹۸۶ توسط Chazelle Guibas , طی دو مقاله م(Chazelle & Guibas 1986a(Chazelle & Guibas ۱۹۸۶ ارائه شد. این روش، برگرفته از دو ایده بود: یکی ایدهٔ آبشاره‌سازی که از الگوریتم "جستجوی دامنه‌ای داده در داده ساختارهاً از لوکر (۱۹۷۸) و ویلارد (۱۹۷۸) برگرفته شده‌بود. دیگری ایده نمونه برداری جزء به جزء از (Chazelle (۱۹۸۳. بعد از آن افراد دیگری شکل‌های پیچیده تری از روش آبشاره‌سازی جزءبه‌جزء ارائه کردند. در این الگوریتم‌ها، داده ساختار، وقتی دنباله‌ای از عملیات حذف و درج روی آن انجام شود و داده‌ها تغییر کنند، همچنان معتبر است و امکان جستجوی سریع در آن وجود دارد.


title: آبشاره‌سازی جزءبه‌جزء

text: در فناوری اطلاعات، اصطلاحاً به ترتیب دادن یک سلسله فعالیت‌های پیوسته در پردازش داده‌ها که در آن انجام هر مرحله وابسته به وقوع مرحلهٔ قبل است آبشاره‌سازی می‌گویند.


title: آبشاره‌سازی جزءبه‌جزء

text: به عنوان یک مثال ساده از آبشاره‌سازی جزءبه‌جزء، این مسئله را در نظر بگیرید: تعداد k لیست مرتب شده از اعداد حقیقی به ما داده شده‌است. مجموع تعداد اعضای این لیست‌ها روی هم n است. یعنی اگر هر لیست را با Li نشان دهیم، Σ|Li|=n. می‌خواهیم این لیست‌ها را طوری پردازش کنیم که بتوانیم جستجوهای دودویی را به دنبال مقدار خواسته شدهٔ q در هر یک از این k لیست انجام دهیم. برای مثال، به ازای n = ۴ و k = ۱۷:


title: آبشاره‌سازی جزءبه‌جزء

text: L1 = ۲٫۴، ۶٫۴، ۶٫۵، ۸٫۰، ۹٫۳


title: آبشاره‌سازی جزءبه‌جزء

text: L2 = ۲٫۳، ۲٫۵، ۲٫۶


title: آبشاره‌سازی جزءبه‌جزء

text: L3 = ۱٫۳، ۴٫۴، ۶٫۲، ۶٫۶


title: آبشاره‌سازی جزءبه‌جزء

text: L4 = ۱٫۱، ۳٫۵، ۴٫۶، ۷٫۹، ۸٫۱


title: آبشاره‌سازی جزءبه‌جزء

text: ساده‌ترین راه حل برای این مسئلهٔ جستجو، ذخیره کردن هر لیست به طور جداگانه (در یک آرایه) است. در این صورت به حافظهٔ اضافی از مرتبهٔ n نیاز داریم. جستجو را در هر یک از این k لیست به طور جداگانه انجام می‌دهیم. بدترین حالت زمانی رخ می‌دهد که تعداد اعضای لیست‌ها برابر و به میزان n/k باشد. در این صورت زمان یک جستجو، در هر لیست از مرتبهٔ (log(n/k و در نتیجه زمان کلی یک جستجو از مرتبهٔ (klog(n/k خواهد بود.


title: آبشاره‌سازی جزءبه‌جزء

text: راه حل دوم جستجوهای سریع تری را ممکن می‌کند اما فضای بیشتری از حافظه می‌گیرد. ما می‌توانیم k لیست را در یک لیست بزرگ L با هم ادغام کنیم و به ازای هر مورد x از لیست L، نتایج جستجوهای x در لیست‌های کوچکتر Li را قرار دهیم. یک المان از لیست ادغام شده را با x[a, b, c, d] نشان می‌دهیم، که x یک مقدار، و a, b, c, d مکان‌های مقادیر عنصر بعدی x، در هر یک از لیست‌های ورودی است (فرض بر این است که نخستین مکان را با ۰ نشان می‌دهیم). با توجه به مرتب بودن لیست‌های ورودی، منظور از عنصر بعدی، عنصر بلافاصله بزرگ‌تر یا حد اقل مساوی با x است. (اگر چنین عنصری وجود نداشت، مکان بعد از آخرین خانهٔ لیست را، قرار داد می‌کنیم) در این صورت خواهیم داشت:


title: آبشاره‌سازی جزءبه‌جزء

text: L = ۱٫۱[۰٬۰٬۰٬۰], ۱٫۳[۰٬۰٬۰٬۱], ۲٫۳[۰٬۰٬۱٬۱], ۲٫۴[۰٬۱٬۱٬۱], ۲٫۵[۱٬۱٬۱٬۱], ۲٫۶[۱٬۲٬۱٬۱], ۳٫۵[۱٬۳٬۱٬۱], ۴٫۴[۱٬۳٬۱٬۲], ۴٫۶[۱٬۳٬۲٬۲], ۶٫۲[۱٬۳٬۲٬۳], ۶٫۴[۱٬۳٬۳٬۳], ۶٫۵[۲٬۳٬۳٬۳], ۶٫۶[۳٬۳٬۳٬۳], ۷٫۹[۳٬۳٬۴٬۳], ۸٫۰[۳٬۳٬۴٬۴], ۸٫۱[۴٬۳٬۴٬۴], ۹٫۳[۴٬۳٬۴٬۵]


title: آبشاره‌سازی جزءبه‌جزء

text: با این راه حل ادغامی یک پرس و جو در زمان (O(log n + k انجام می‌شود. زمان Log n برای جستجوی q در لیست n تایی L، و k برای گزارش کردن نتایج صرف می‌شود. با توجه به اینکه مکان هایx در هر لیست‌های ورودی، در لیست L عنصر x ذخیره شده‌اند، نتایج پس از جستجو بدست می‌آیند.


title: آبشاره‌سازی جزءبه‌جزء

text: این مدل، چنین مسئله‌های جستجویی را با صرف زمان (O(log n + kو حافظهٔ (O(n حل می‌کند. راه حل آبشاره‌سازی جزءبه‌جزء ذخیره کردن دنباله‌های جدیدی از لیست‌های Mi است. لیست نهایی در این دنباله Mk است که برابر است با Lk، و هر لیست قبلی از ادغام Li با هر یک از به ازای هر عنصر x در این لیست ادغامی، ما دو عدد ذخیره می‌کنیم: مکانی که از جستجوی x در Li به دست می‌آید، و مکانی که از جستجوی x در Mi+۱ بدست می‌آید. به ازای داده‌های بالا، چنین عملی، این لیست‌ها را به ما می‌دهد:


title: آبشاره‌سازی جزءبه‌جزء

text: M1 = ۲٫۴[۰، ۱], ۲٫۵[۱، ۱], ۳٫۵[۱، ۳], ۶٫۴[۱، ۵], ۶٫۵[۲، ۵], ۷٫۹[۳، ۵], ۸[۳، ۶], ۹٫۳[۴، ۶]


title: آبشاره‌سازی جزءبه‌جزء

text: M2 = ۲٫۳[۰، ۱], ۲٫۵[۱، ۱], ۲٫۶[۲، ۱], ۳٫۵[۳، ۱], ۶٫۲[۳، ۳], ۷٫۹[۳، ۵]


title: آبشاره‌سازی جزءبه‌جزء

text: M3 = ۱٫۳[۰، ۱], ۳٫۵[۱، ۱], ۴٫۴[۱، ۲], ۶٫۲[۲، ۳], ۶٫۶[۳، ۳], ۷٫۹[۴، ۳]


title: آبشاره‌سازی جزءبه‌جزء

text: M4 = ۱٫۱[۰، ۰], ۳٫۵[۱، ۰], ۴٫۶[۲، ۰], ۷٫۹[۳، ۰], ۸٫۱[۴، ۰]


title: آبشاره‌سازی جزءبه‌جزء

text: فرض کنید می‌خواهیم یک پرس و جو برای q=۵ انجام دهیم. ابتدا یک جستجوی دودویی به دنبال qدر M۱انجام می‌دهیم و مقدار ۶٫۴[۱٬۵]. را پیدا می‌کنیم. عدد «۱» در ۶٫۴[۱٬۵]. به ما می‌گوید که جستجوی q در L۱ باید L۱[۱] = ۶٫۴ را برگرداند. عدد ۵ نیز می‌گوید تخمین موقعیت q در M۲ مکان ۵ است. با دقت بیشتر، جستجوی دودویی برای q در M۲ مقدار ۷٫۹[۳، ۵] در موقعیت ۵ یا مقدار۶٫۲[۳، ۳] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با ۶٫۲ و مشاهده اینکه کوچکتر است، ما می‌یابیم که نتیجه درست در M۲ , ۶٫۲[۳، ۳] است. اولین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که جستجو برای qدر L۲ باید L۲[۳] را برگرداند. یک مقدار پرچم به معنی آن است که q از انتهای لیست L۲ گذشته‌است. دومین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که تخمین موقعیت qدر M۳ موقعیت ۳ است. به طور دقیق تر، جستجوی دودویی برای q در M۳ مقدار۶٫۲[۲، ۳] در موقعیت ۳ یا مقدار ۴٫۴[۱، ۲] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با مقدار کمتر ۶٫۲. به ما نشان می‌دهد که نتیجه درست در M۳ ،۶٫۲[۲٬۳] است. «۲» در۶٫۲[۲٬۳] به ما می‌گوید که جستجو برای qدر L۳ باید L۳[۲]=۶٫۲ را برگرداند و «۳» در ۶٫۲[۲٬۳] به ما می‌گوید که نتیجه جستجو برای q در M۴ برابر با M۴[۳] = ۷٫۹[۳٬۰] یا M۴[۲] = ۴٫۶[۲٬۰] است. با مقایسه q با ۴٫۶ نشان می‌دهد که نتیجه صحیح ۷٫۹[۳٬۰] است و نتیجه جستجو برای q در L۴ برابر L۴[۳] = ۷٫۹. است پس ما q را در هر یک از چهار لیست پیدا کردیم بوسیله جستجوی دوتایی در تک لیست M۱ همراه با یک مقایسه در هر لیست متواتر. به‌طور کلی تر برای هر ساختار داده از این نوع ما یک پرس و جو را بوسیله انجام یک جستجوی دودویی q در M۱ انجام می‌دهیم و با استفاده از مقدار نتیجه شده موقعیتq در L۱ را تعیین می‌کنیم.


title: آبشاره‌سازی جزءبه‌جزء

text: در مثال ما، لیست‌های آبشاره‌سازی جزءبه‌جزء شده، در مجموع ۲۵ عنصر دارند که مقداری کمتر از دو برابر ورودی اصلی است. به طور کلی سایز Mi در این داده ساختار حداکثر به این اندازه‌است: Lj| + ½| Li + ۱ | + ¼ | Li + ۲ | + … + ۱/ ۲j | Mi + j | +….


title: آبشاره‌سازی جزءبه‌جزء

text: که به سادگی اثبات می‌شود سایز داده ساختار حد اکثر ۲n است:


title: آبشاره‌سازی جزءبه‌جزء

text: (Σ|Mi| = Σ|Li|(۱ + ½ + ¼ +…) ≤ ۲n = O(n


title: آبشاره‌سازی جزءبه‌جزء

text: به طور کلی، آبشاره‌سازی جزءبه‌جزء با گراف کاتالوگ آغاز می‌شود. گراف کاتالوگ گرافی جهت دار است که هر رأس آن با یک لیست مرتب شده برچسب گذاری شده‌است. هر پرس و جو در این داده ساختار، شامل یک مسیر از این گراف و یک مقدار q است و به ازای این دو، داده ساختار باید مشخص کند q در هر یک از لیست‌های مرتب شده‌ای که در رئوس مسیر داده شده قرار دارند، چندمین عنصر است. به عنوان یک مثال ساده، گراف کاتالوگ مسیری است با چهار رأس. با استفاده از روش پویا (داینامیک)، امکان این وجود دارد که پاسخ رئوس بعدی یک مسیر را بر اساس نتایج جستجو در رئوس قبلی مسیر به دست آید.