Payamvdn/NorthPersian_fa_wiki huggingface dataset:
ته اند. در آنندراج در مورد ختن و یارکند آمده است که: تاریخچه معاصر. ولایت مدرن کاشغر، در سال ۱۹۱۳ میلادی، دومین سال حاکمیت جمهوری چین تشکیل شد. ولایت کاشغر در آن زمان شامل اراضی امروزی این ولایت، علاوه بر ولایت ختن و ولایت خودمختار قزل سو قرقیز (بجز شهرستان آقچی) بود. ولایت کاشغر شامل ۱۲ شهرستان بود، منجمله شهرستان یارکند. در سال ۱۹۲۲، شهرستان پوسکام از بخشهایی از این شهرستان در ولایت کاشغر ایجاد شد. در سالهای ۱۹۳۳ و ۱۹۳۴ میلادی، در منطقهٔ کاشغر که در آن زمان شامل ولایت خودمختار قزل سو نیز می شد، در طی شورشی علیه حکومت استانی وفادار به جمهوری چین، کشور جدیدی به طول دو سال با نام جمهوری اسلامی ترکستان شرقی اعلام شده بود. در سال ۱۹۴۳، سه شهرستان پوسکام، ماکیت، و یارکند از ولایت کاشغر با شهرستان کارگیلیک از ولایت ختن، ترکیب شده و ولایت یارکند، به مرکزیت یارکند تاسیس شد. بین سالهای ۱۹۵۴ و ۱۹۵۶ میلادی، «ولایت خودمختار جنوب سین کیانگ» (مشابه ولایت خودمختار ایلی قزاق) با تحت مدیریت داشتن ولایات کاشغر، یارکند، آق سو، ختن، و ولایت خودمختار قزل سو قرقیز ایجاد شد. بین سال های ۱۹۵۵ و ۱۹۵۶، ولایت کاشغر منحل شده، و شهرستان
های آن، تحت تابعیت مستقیم «ولایت خودمختار جنوب سین کیانگ» قرار گرفت. در سال ۱۹۵۶، «ولایت خودمختار جنوب سین کیانگ» منحل شد. در این سال، ولایت کاشغر باز دوباره تاسیس شد. در همین سال، ولایت یارکند نیز منحل شده و ۴ شهرستان آن به ولایت کاشغر پیوستند.
در علم کامپیوتر یک الگوریتم قطعی الگوریتمی است که در شرایط غیررسمی رفتاری قابل پیش بینی دارد، با دادن یک ورودی خاص، همیشه خروجی خاصی را ایجاد کند و ماشین اساسی آن همیشه از مسیری یکسان برای دنباله های وضعیت مشابه عبور کند. الگوریتم قطعی تا حد زیادی مورد مطالعه قرارگرفته و آشناترین نوع الگوریتم است، همچنین یکی از عملی ترین الگوریتم ها محسوب می شود، چرا که آن ها را می توان به طور کارآمدی بر روی ماشین های واقعی اجرا کرد. به طور رسمی یک الگوریتم قطعی یک تابع ریاضی را محاسبه می کند. یک تابع برای هر ورودی یک مقدار منحصربه فرد دارد، و الگوریتم فرایندی است که این مقدار منحصربه فرد را به عنوان خروجی را تولید می کند. تعریف رسمی. الگوریتم قطعی می تواند به عنوان یک ماشین حالت تعریف شود. "حالت"، فعالیت ماشین در یک لحظه خاص را توصیف می کند. ماشین حالت با روش های مجزایی از حالتی به حالت دیگر می رود. درست بعد از این که ما ورودی دادیم، ماشین در "حالت ابتدایی" یا "حالت شروع" قرار می گیرد. ماشین قطعی ماشینی است که از نقطه شروع به بعد، حالت فعلی آن حالت بعدی را تعیین می کند و جریان بین مجموعه حالت های آن از پیش تعیین شده است. توج
ه داشته باشید که یک ماشین می تواند قطعی باشد اما پایان نپذیرد یا متوقف نشود که در این صورت در تولید خروجی شکست می خورد. ماشین تورینگ و ماشین های تعین پذیر حالات متناهی نمونه هایی از ماشین قطعی انتزاعی هستند. چه چیز الگوریتم را غیرقطعی می کند؟. عوامل و متغیرهای زیادی می توانند باعث شوند که یک الگوریتم به صورت تصادفی یا غیرقطعی رفتار کند مانند: هرچند به ندرت برنامه های واقعی کاملاً قطعی هستند امابرای انسان ها و دیگر برنامه ها ساده تر است که آن ها را استدلال کنند. به همین دلیل اکثر زبان های برنامه نویسی به خصوص زبان های برنامه نویسی تابعی، تلاش می کنند تا از اتفاقات بالا به جز در شرایط خارج از کنترل، جلوگیری کنند. فراگیری استفاده از پردازنده های چندهسته ای منجر به علاقه به قطعیت در برنامه نویسی موازی و چالش های غیرگرایی شد.. تعدادی از ابزارها برای کمک به مقابله با چالش ها، بن بست ها و شرایط مسابقه در بخش "منابع برای مطالعهٔ بیشتر" پیشنهاد شده است. مشکلات الگوریتم قطعی. متأسفانه برای برخی مسائل پیدا کردن الگوریتم قطعی سخت است. به عنوان مثال الگوریتم های ساده و کارآمدی مبتنی بر احتمالات وجود دارد که تعیین می کند ی
ک عدد داده شده اول است یا نه. این الگوریتم ها احتمال خطای بسیار اندکی دارندو از دهه 1970 میلادی شناخته شده اند. به عنوان مثالی دیگر، مسایل ان پی کامل که شامل بسیاری از مهم ترین مسایل عملی است را می توان با روشی به نام "ماشین تورینگ غیرقطعی" به سرعت حل کرد اما الگوریتم های کارای عملی برای هیچ یک از آن ها یافت نمی شود. در بهترین حالت ما می توانیم الگوریتم های تقریبی یا راه حل هایی برای موارد خاص پیدا کنیم. یکی دیگر از مشکلات عمده با الگوریتم قطعی این است که در برخی مواقع ما " نمی خواهیم " نتایج قابل پیش بینی باشند. برای مثال شما وقتی در حال انجام بازی " بلاک جک" به صورت برخط هستید و برای برزدن هر دست از تولید کننده اعداد تصادفی استفاده می کنید، یک قمارباز باهوش می تواند به طور دقیق عددی را که تولیدکننده انتخاب می کند، حدس بزند و محتوای هر دست را در زمان تعیین کند، که این در واقع اجازه تقلب را به او می دهد. برای مثال گروه امنیت نرم افزار در فناوری های نرم افزاری مطمئن توانستند این کار را برای "پوکر تگزاس" که توسط "AFS" انتشار یافته بود انجام دهند، چنان که خروجی هر دست را جلوتر از زمان پیش بینی کردند. اشکالی مشاب
ه در رمزنگاری رخ می دهد چرا که اغلب کلیدهای محرمانه با استفاده از چنین تولیدکننده هایی ساخته می شوند. از این گونه مشکلات می توان با استفاده از مولد عدد شبه تصادفی امن رمزنگارانه اجتناب کرد.
اندام مکنده بخشی از قارچ یا گیاه انگلی است که وارد ریشه گیاه میزبان می شود و مواد مغذی را جذب می کند.
بلام بلام شاب یک الگوریتم مولد اعداد شبه تصادفی می باشد که در سال ۱۹۸۶ توسط لنور بلام و مانوئل بلام و مایکل شاب ارائه شد. ساختار این الگوریتم به صورت زیر می باشد : که در آن "M=p*q" می باشد که p و q اعداد اول بزرگ می باشند. در هر مرحله از این الگوریتم مقدار خروجی در "x""n"+1 قرار گرفته می شود. و نتیجه این مولد می تواند از بیت همزادی زوج یا فرد یا بیت های کم ارزش این عدد به دست بیاید. یعنی همانطور که در مثال خواهید دید به ازای هر بیت یک عدد که قصد ساخت آن را داریم یک بار این رابطه را اجرا کنیم و با استفاده از عدد به دست آمده بیت مورد نظر را دریافت کنیم. عدد "x"0 که نیز به عنوان نقطه شروع برای این الگوریتم باید قرار داده شود باید نسبت به M اول باشد. همچنین ۱ نمی تواند به عنوان نقطه شروع در نظر گرفته شود. همچنین باید بزرگ ترین مقسوم علیه مشترک نتیجه تابع اویلر بر دو عدد p , q عددی کوچک شود. هر دو عدد p , q باید با عدد ۳ بهپیمانه ۴متجانس باشند. یکی از جذابیت های الگوریتم بلام بلام شام این است که عدد "x"i را می توان به طور مستقیم با استفاده از قضیه اویلر به دست آورد. که در آن formula_3 یک تابع کارمیکال می باشد. for
mula_4). امنیت. این روش برای تولید اعداد تصادفی برای مصارف شبیه سازی مناسب نمی باشد و تنها برای مصارف رمزنگاری مناسب می باشد. زیرا این الگوریتم بسیار کند می باشد. از آنجایی که پیچیدگی محاسباتی الگوریتم های تجزیه و شکستن آن ها به عوامل اول بالاست این الگوریتم از لحاظ امنیتی دارای رتبه بالایی می باشد. برای پیش بینی بیت های عددی که با استفاده از این الگوریتم به دست می آید باید محاسباتی با پیچیدگی معادل تجزیه عدد M به عوامل اول را انجام داد. از آنجایی که با رشد M پیچیدگی محاسباتی افزایش میابد می توان نتیجه گرفت که برای مقادیر بزرگ M نمیتوان روشی غیر تصادفی که اعدادی معادل خروجی این الگوریتم به ما بدهد یافت. این روش امنیتی در امنیت روش های رمز نگاری دیگر مانند رمز نگاری آر اس ای را دارا می باشد. مثال. formula_5، formula_6 formula_7 برای شروع هسته انجام عملیات را برابر ۳ قرار میدهیم که x0 در مرحله اول از همین هسته تولید خواهد شد. میتوانیم انتظار سیکل تولید اعداد تصادفی طولانی را با همین اعداد p , q کوچک داشته باشیم زیرا : formula_8. formula_9، formula_10، formula_11 formula_12 = 9, 81, 82, 36, 42, 92 منابع. بلام بل
ام شاب ()
چاووشی یا چاوشی (در زبان محلی "چوش")، آواز مذهبی شیعی مخصوص بدرقه یا پیشباز زائران اماکن زیارتی است. رسم چاوشی خوانی برای زائرین کربلا یا مشهد از دورهٔ صفویان و قاجاریان مرسوم شده و در سدهٔ اخیر مورد توجه فراوان قرار گرفته است. رسم چاوشی خوانی، علاوه بر استان بوشهر در استان های دیگر مثل استان خوزستان، استان هرمزگان، جنوب استان فارس و استان های شمالی ایران مثل استان مازندران نیز معمول است. تاریخچه. این سنت به قبل از دوران صفویه بازمی گردد. علامه ی مجلسی را پایه گذار این سنت نام برده اند. معنی. «چاووش» واژه ای ترکی است، به معنای جارچی، پیک، پیشرو کاروان، کسی که دعوت رفتن به زیارت عتبات عالیات و خانه خدا کند. در اصطلاح روستاییان خراسان، چاووش، کسی بوده که در فصل مناسبِ زیارت، در دهات و روستاها، سواره یا پیاده به راه می افتاده و روستاییان را به وسیله جارزدن و خواندن اشعار نغز و دلکش ـ در مدح و منقبت امامان معصوم علیهم السلام ـ برای رفتن به زیارت تشویق می کرده است. در فرهنگ دهخدا، واژه «چاو» به، «بانگ و سر و صدای گنجشک، هنگامی که از بیم دزدیده شدن جوجه اش بانگ برمی آورد» معنا شده است. در بوشهر وسیلهٔ خبردادن به مر
دم محل یا شهر از سفر زیارتی، چاوشی خوانی بود که امروز نیز کم و بیش اجرا می گردد. چاوش با خواندن چاوشی هم حاضران را سرگرم می کرد و هم غایبین را به حضور در مجلس دعوت می کرد. اشعار چاوشی بیش تر ساختهٔ ذوق و تخیل علاقه مندان است و سرایندگان آن ها اغلب نامعلوم هستند؛ به همین سبب است که بعضی از اشعار چاوشی فاقد قافیهٔ مرتب است. چاووشی معمولاً در دستگاه «چهارگاه» از موسیقی ردیف ایرانی است و بدون همراهی ساز، اجرا و معمولاً توسط چند نفر خوانده می شود. دو یا چند خواننده اشعار چاووشی را با آوازی مشخص بین یکدیگر مبادله و بهم جواب می دهند. حتی ممکنست زنان نیز در این هم خوانی با مردان همراه شوند. در امتداد هر چاووشی (دوبیت)، خواننده در فرود آواز خود، با خواندن بیتی مانند: که خدا فرموده بر همه آیات به غریب خاک خراسان رضا، صلوات یا: که خدا فرموده بر همه آیات به قد موزون علی نور محمد، صلوات پایان کار خود را اعلام می کند. حاضران نیز درپاسخ اشعار او، صلواتی بر محمد و خاندانش می فرستند. اشعار چاووش خوانی در بوشهر، دوبیتی هایی است که اغلب بروزن فاعلاتن فاعلاتن فاعلاتن فاعلن (بحر رمل مثمن محذوف) سروده شده است. نمونه ها. زیارت کربل
ا. ای موالی موسم فصل بهار کربلاست لاله باید چید هرکس دوست دار کربلاست موسم گل چیدن است ای عند لیبان چمن این کاروان سالار ره شهریار کربلاست که خدا فرموده در همه آیات به دست های سقای لب تشنگان ابوالفضل عباس صلوات فرموده حسین که اشتران بار کنید هفتاد و دوتن جمله خبر دار کنید چاوشی های حماسی. افتخار ما بود نام نکویت یا حسین آبروی ما بود از آبرویت یا حسین جان فدایت تربت و پاک نکویت یا حسین روز عاشورا شها اندر لب شط فرات نایاب شد ز بهر وضویت یاحسین آب کوثر رشحه ای از آب جویت یاحسین یک جهان ز قیام پرشکوهت رونق گرفت آبروی ما بود از آبرویت یا حسین که خدا فرموده در همه آیات به سربریده صحرا کربلا حسین صلوات زیارت مکه. که خدا فرموده در همه آیات به میم اول نام محمد صلوات زیارت مدینه. که خدا فرموده در همه آیات به میم اول نام محمد صلوات زیارت نجف. که خدا فرموده در همه آیات به شهسوار عرب علی مرتضی صلوات
باشگاه الشباب (به عربی:نادی الشباب) یک باشگاه فوتبال از کویت است و در لیگ برتر کویت بازی می کند. باشگاه الشباب کویت ۱۵ دسامبر ۱۹۶۳ در جنوب کویت تأسیس شده است. این باشگاه سابقهٔ قهرمانی در لیگ دسته ۱ کویت را دارد.
شورای عالی نیروهای مسلح نهادی متشکل از ۲۱ فرمانده ارشد ارتش مصر است. در جریان انقلاب ۲۰۱۱ مصر پس از استعفای حسنی مبارک این شورا اختیارات رئیس جمهور را به دست آورده و به عالی ترین قدرت مصر تبدیل شد و این موقعیت را تا ۳۰ ژوئن ۲۰۱۲ که قدرت را به محمد مرسی رئیس جمهور جدید واگذار کرد در اختیار داشت. ریاست این شورا به طور طبیعی بر عهده رئیس جمهور است. ۱۰ فوریه سال ۲۰۱۱ اولین باری بود که این شورا بدون ریاست رئیس جمهور تشکیل شد و برای اولین بار یک بیانیه خبری را منتشر کرد. فردای آن روز حسنی مبارک از مقام خود استعفا داده و اختیاراتش را به این شورا واگذار کرد. محمدحسین طنطاوی فرمانده کل نیروهای مسلح مصر و وزیر دفاع کشور بعد از استعفای حسنی مبارک تا انتخاب محمد مرسی ریاست این شورا را در اختیار داشت. عبدالفتاح خلیل السیسی فرمانده نیروهای مسلح و وزیر دفاع و صدقی صبحی رئیس ستاد مشترک از دیگر اعضای مهم این شورا هستند. انحلال پارلمان مصر و برگزاری انتخابات پارلمانی جدید در نوامبر ۲۰۱۱، تعلیق قانون اساسی و به همه پرسی گذاشتن قانون اساسی جدید در مارس ۲۰۱۱، قول برگزاری انتخابات آزاد ریاست جمهوری تا پایان سال میلادی و انتخاب ۱۵
فرماندار برای استان های مصر که ۱۱ نفر آن ها به تازگی به این پست رسیده اند از مهمترین فعالیت های شورای عالی نیروهای مسلح در طول حکومت چند ماهه خود بر مصر بوده است.
هاگ داران یا اَپی کامپلکسا (Apicomplexa) یک گروه بزرگ از حبابچه داران رنگی (آغازیان) می باشند که اغلب دارای یک اندامک منحصر به فرد به نام اَپی کامپلاست و یک مجموعه ساختار رأسی که برای نفوذ به یاخته میزبان است، می باشد. منابع. ویکی پدیا انگلیسی
باشگاه ورزشی الاهلی (به عربی: النادی الاهلی الریاضی) یک باشگاه ورزشی در شهر دوحه و در کشور قطر می باشد که تیم فوتبال آن در لیگ ستارگان قطر بازی می کند. این باشگاه در سال ۱۹۵۰ میلادی تأسیس شده است. باشگاه الاهلی یک بار به مقام نایب قهرمانی در لیگ ستارگان قطر و ۴ بار به مقام قهرمانی جام امیر قطر رسیده است. دست آوردها. جام امیر قطر جام شیخ جاسم عملکرد در ادوار جام در جام آسیا. عملکرد آسیایی این تیم تاکنون در جام باشگاه ها و لیگ قهرمانان آسیا (سطح اول فوتبال باشگاهی قاره) تجربه حضور نداشته ولی دو بار در سال ۱۹۹۳ و ۱۹۹۵ در جام در جام آسیا حضور داشته که به ترتیب در دور اول و دوم برابر الاتحاد عربستان و العربی کویت کنار رفت وبهترین عملکرد آنها در جام در جام تساوی برابر النجم لبنان است.
الگوریتم مرتب سازی تیم ، ترکیبی از دو الگوریتم مرتب سازی است به نام های مرتب سازی ادغامی و مرتب سازی درجی. این طراحی بر روی بسیاری از انواع داده ها در جهان واقعی بسیار خوب عمل می کند. این الگوریتم اولین بار توسط تیم پیترز در سال ۲۰۰۲ برای استفاده در پایتون بیان شد. الگوریتم برای پیدا کردن زیر مجموعه ای از داده ها که جستجو را بهینه تر کنند، طراحی شد. به وسیلهٔ مرتب سازی ادغامی زیر مجموعه مشخص می شود. این زیر مجموعه یک run نامیده می شود. از این runها به تعدادی پیدا می شود که معیارهای لازم برآورده شود. مرتب سازی تیم، مرتب سازی استاندارد پایتون از مدل ۲٫۳ است. هم اکنون در جاوا ۷ و همچنین در اندروید برای مرتب سازی آرایه ها از این مرتب سازی استفاده می شود. الگوریتم چگونه کار می کند؟. الگوریتم برای استفاده از این مزیت که داده ها به طور جزئی مرتب شده اند، طراحی شده است. جستجوی تیم، کار خود را با پیداکردن runها در داده ادامه می دهد. یک run یک زیرآرایه از آرایهٔ اصلی داده ها می باشد که حداقل دارای دو عنصر می باشد که غیر نزولی یا نزولی اکید باشد. اگر زیر مجموعه نزولی باشد باید نزولی اکید باشد زیرا این run می تواند با جا
بجایی ساده عناصر از دو طرف که به وسط همگرا می شوند، معکوس شود. این الگوریتم اگر عناصر آن اکیداً نزولی باشد پایدار است. بعد از به دست آوردن یک run در آرایهٔ داده شده، عملیات خود را روی آن انجام می دهد و بعد از آن کار خود را با run بعدی ادامه می دهد. یک run به طور طبیعی یک زیرآرایه است که مرتب شده است. runهای طبیعی در داده های واقعی می توانند در اندازه های مختلفی وجود داشته باشند. این الگوریتم به صورت بهینه نوع خاصی از مرتب سازی که به طول run بستگی دارد (به طور مثال اگر اندازهٔ آن از مقدار خاصی کمتر باشد از مرتب سازی درجی استفاده می کند) بنابراین این مرنب سازی انطباقی نامیده می شود. اندازهٔ run با اندازهٔ کوچکترین run مقایسه می شود. اندازهٔ کوچکترین run که «minrun» نامیده می شود که به اندازهٔ آرایه بستگی دارد. برای آرایه هایی که اندازهٔ آن از ۶۴ کمتر باشد، اندازهٔ minrun به اندازهٔ خود آرایه می باشد و اساساً به مرتب سازی درجی تبدیل می گردد. برای آرایه های بزرگتر اندازهٔ minrun بین بازهٔ ۳۲ تا ۶۵ انتخاب می شود. الگوریتم نهایی برای انتخاب minrun، شش بیت قابل توجه اندازهٔ آرایه را در نظر می گیرد. اگر هر کدام از بی
ت های باقی مانده یک بودند، یک اضافه می کند و از آن به عنوان minrun استفاده می کند. این روش برای همهٔ آرایه هایی که سایز آن ها از ۶۴ کمتر است و شامل یک هستند، درست عمل می کند. مرتب سازی درجی. هنگامی که یک آرایه به صورت رندم باشد، با احتمال زیادی یک run طبیعی تعداد عناصر کمتری از minrun دارد. در این موارد تعداد مناسبی از عناصر در نظر گرفته می شوند و از مرتب سازی درجی برای مرتب کردن آن ها استفاده می شود. سپس اندازهٔ آن افزایش می یابد تا به اندازهٔ minrun بشود. مرتب سازی ادغامی. عملیات ادغام معمولاً روی دو run پیاپی انجام می شود. برای این کار سه run بالای پشته را که مرتب نشده اند را در نظر می گیرد. اگر طول این سه run را x، y، z در نظر بگیریم، الگوریتم طوری آن ها را ادغام می کند که دو شرط زیر برقرار شود. این دو قانون باعث می شود که طول runها نزدیک به هم نگه داشته شوند و بازدهی الگوریتم بالاتر باشد. رویهٔ ادغام کردن. ادغام کردن دو run همسایه به کمک یک حافظهٔ کمکی انجام می شود. اندازهٔ این حافظه به اندازهٔ run کوچکتر می باشد. الگوریتم آرایهٔ کوچکتر را در حافظه کپی می کند و سپس برای ذخیرهٔ run نهایی از حافظهٔ اصلی و
حافظهٔ run بزرگتر استفاده می کند. کارایی الگوریتم. طبق نظریه اطلاعات هیچ الگوریتم مرتب سازی مقایسه ای نمی تواند کارایی بهتر از formula_1 در حالت میانگین داشته باشد. در داده های واقعی الگوریتم تیم معمولاً با تعداد مقایسه های کمتر از formula_1 مرتب سازی را انجام می دهد زیرا از این مزیت که زیر مجموعه ای از داده ها مرتب هستند. در مواردی که هیچ زیر مجموعه ای از داده ها مرتب شده نیستند الگوریتم نمی تواند از این مزیت استفاده کند و با کارایی formula_1 کار می کند. در جدول زیر کارایی الگوریتم با دیگر الگوریتم های مقایسه ای مقایسه شده است. در جدول زیر انواع مختلف الگوریتم ها بر اساس پیچیدگی مقایسه شده اند.
حبابچه دارن (همراه با حفره) (Alveolate) فرمانرو بزرگی از جانداران هستند که در گذشته در دسته آغازیان طبقه بندی می شدند. اما اکنون که مشخص شده است آغازیان دارای منشاء مشترکی نبودند، حبابچه داران خود فرمانرویی جداگانه شمرده می شوند. این گروه پنج شاخه دارد: منابع. Wikipedia contributors, "Alveolate," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/w/index.php?title=Alveolate&amp;oldid=679155201 (accessed September 6, 2015).
در نظریه گراف، شاخه ای از ریاضیات، الگوریتم ادمون برای پیدا کردن انشعاب بهینهٔ بیشینه یا کمینه به کار می رود. زمانی که راس ها با یال های وزن دار و جهت دار به یکدیگر متصل شده باشند، دیگر نمی توانیم از الگوریتم درخت پوشای کمینه استفاده کنیم. بنابراین از الگوریتم انشعاب بهینه استفاده می کنیم که در سال ۱۹۶۷ توسط ادمون ارائه شد. برای یافتن مسیر با طول بیشینه، ابتدا یال ها بر اساس وزن شان مرتب می شوند. از بزرگترین یال شروع کرده و آن یال بین دو راس قرار می گیرد. بعد از آن به سراغ یال بزرگتر بعدی رفته و همین کار برای باقی یال ها نیز انجام می شود. اگر یالی باعث ایجاد دور در گراف شود، آن یال حذف می شود. برای پیدا کردن مسیر با طول کمینه نیز، یال ها از کوچک به بزرگ مرتب می شوند و کار با یال کوچکتر شروع می شود. زمان اجرا. زمان اجرای این الگوریتم برابر با formula_1 است. پیاده سازی سریعتری از این الگوریتم، توسط روبرت تارجان ارائه شد که زمان اجرای آن برای یک گراف نا متراکم formula_2 و برای گراف متراکم برابر با formula_3 است. زمان اجرای آن به تندی الگوریتم پریم، برای یافتن درخت پوشای کمینهٔ بدون جهت است. بعدها در سال ۱۹۸۶، گا
بو، گلیل، اسپنسر، و تارجان پیاده سازی سریعتری را ارائه کردند که زمان اجرای آن برابر است با formula_4. الگوریتم. تابعی مانند formula_5 را در نظر می گیریم که به عنوان ورودی، یک گراف وزن دار و جهت دار formula_6 و یک راس formula_7 به عنوان ریشه می گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با ریشهٔ formula_7، به ما می دهد. توصیف دقیق الگوریتم در ادامه آمده است. با گرفتن یک گراف وزن دار و جهت دار مانند formula_6، با ریشهٔ formula_7، به این صورت عمل می کنیم که در ابتدا، مجموعهٔ یال های موازی(یال هایی که بین دو راس یکسان قرار دارند و دارای یک جهت می باشند) را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال های موازی است، جایگزین می کنیم. توصیف. این الگوریتم یک توصیف شهودی بازگشتی دارد. تابعی مانند formula_5 را در نظر می گیریم. این تابع به عنوان ورودی، گراف وزن دار و جهت دار formula_6، با یک راس formula_7 به عنوان "ریشه" را می گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با کمترین هزینه، می دهد. توصیف دقیق الگوریتم در ادامه آمده است. با گرفتن یک گراف وزن دار و جهت دار formula_6 با ریشهٔ formula_7، در ابت
دا به این صورت عمل می کنیم که مجموعه ای از یال های موازی (یال های بین دو راس یکسان که دارای یک جهت هستند)را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال های موازی است، جایگزین می کنیم. حالا برای هر راس formula_16 به جز ریشه، یال ورودی به آن راس که دارای کمترین هزینه است را علامت(به طور قراردادی) می زنیم. راسی که در سر دیگر این یال قرار دارد را با formula_17 مشخص می کنیم. اگر یال های علامت زده شده، تشکیل یک SRT(درخت فراگیر ریشه دار) را می دادند، یعنی تابع formula_18 این SRT را مشخص کرده است. در غیر این صورت، مجموعه یال های علامت زده شده، تشکیل حداقل یک دور را می دهند. یکی از دورها را (به صورت دلخواه) formula_19 بنامید. حالا ما یک گراف وزن دار و جهت دار formula_20 که دارای ریشه formula_21 است را تعریف می کنیم. به این صورت که، راس های formula_20 مانند راس های formula_6 هستند نه formula_19، به اضافه یک راس "جدید" که با formula_25 مشخص می شود. اگر formula_26 یالی در formula_6 باشد، با این شرط که formula_28، یال formula_29 را به صورت شرح داده شده در زیر به formula_20 اضافه می کنیم. اگر formula_31، formula_3
2 و formula_33 در غیر این صورت، اگر formula_34، formula_35 و and formula_36. ما هیچ یال دیگری را به formula_20 اضافه نمی کنیم. ریشهٔ formula_21 در formula_20، همان ریشهٔ formula_7 در formula_6. است. با صدا کردن تابع formula_42، یک SRT در formula_20 می یابیم. در نظر داشته باشید که در این SRT، یال ورودی (یکتا) به formula_25، یال formula_45 است. این یال می تواند از زوج مرتب هایی مانند formula_26 با شرط formula_28 و formula_31 باشد. علامت formula_49 را بردارید و formula_26 را علامت بزنید. حالا مجموعه یال های علامت زده شده، یک SRT می سازند که ما می توانیم آن را مقدار تابع formula_18 در نظر بگیریم. دقت کنید که تابع formula_18 به وسیله تابع formula_42 تعریف شده است. و تابع formula_20 که یک گراف وزن دار، جهت دار و ریشه دار است، نسبت به گراف formula_6 به شدت تعداد راس هایش کمتر است و استفاده از formula_18 برای یک گراف تک راس، کاری بیهوده است. پیاده سازی. BV را یک مجموعه ای برای رئوس و BE را مجموعه ای برای یال ها در نظر بگیرید. اگر "V" را یک راس در نظر بگیرید و "e" هم یالی با بیشترین وزن مثبت و متصل به "V" باشد، Ci یک
دور خواهد بود. G۰ = (V۰,E۰) گراف اصلی است و "ui" یک راس جانشین برای Ci است. codice_1
حمام توقف، محلولی شیمیایی است که معمولاً در ظهور فیلم و کاغذ عکاسی، پس از اتمام مرحله ظهور مورد استفاده قرار می گیرد. هدف از حمام توقف، توقف عمل ظهور با خنثی کردن باقی مانده داروی ظهور، بر روی فیلم یا کاغذ است. این عمل سابقاً با آب ساده صورت می گرفت، اما روند ظهور همچنان تا خنثی شدن داروی ظهور در طی لحظاتی (هر چند در سطح بسیار پایین) ادامه می یافت. بدین منظور برای توقف سریع عمل ظهور از حمام اسیدی با اسیدیته پائین (محلول ۳۰% اسید استیک) استفاده می کنند.
در هندسه محاسباتی، الگوریتم چان که به افتخار Timothy M. Chan و پس از او نامگذاری شد، الگوریتمی بهینه و حساس به خروجی است که پوش محدب در مجموعه ای از n نقطه که در فضای دو یا سه بعدی قرار دارند را محاسبه می کند. این الگوریتم از مرتبهٔ (O(n log h زمان می گیرد که در آن h، تعداد راس های خروجی (پوش محدب) است. در حالت مسطح، این الگوریتم، الگوریتمی از مرتبه پیچیدگی (O(n log n (مانند جستجوی گراهام) را با الگوریتم بسته بندی هدیه هدیه ترکیب می کند تا در زمان بهینه اجرا شود.این الگوریتم از آن جهت که بسیار ساده تر از الگوریتم نهایی پوش محدب برای سطح است و به طور طبیعی هم قابلیت تعمیم به فضای 3 بعدی را دارد، مورد توجه قرار گرفته است. الگوریتم. در ابتدا فرض می کنیم که عدد h را داریم و بنابراین پارامتر m را برابر h تعریف می کنیم. این فرض شاید به نظر واقعی نرسد، اما بعداً این فرض را از الگوریتم حذف خواهیم کرد.این الگوریتم در ابتدا با تقسیم دلخواه مجموعه نقاط(P) به حداکثر 1+n/m زیر مجموعه که در هر یک از آن ها حداکثر m نقطه وجود دارد، شروع می شود. سپس با استفاده از الگوریتم پوش محدب، می توان در هر یک از این زیر مجموعه ها با زما
ن (O(n log n، پوش محدب را محاسبه کرد.توجه کنید که از آنجا که (O(n/m زیر مجموعه که هر یک شامل(O(m نقطه است وجود دارد، این مرحله حداکثر (O(n/m)O(m log m) = O(n log m زمان می گیرد. در مرحله دوم از مسئله بسته بندی کادو استفاده می شود. همچنین برای افزایش سرعت اجرا، در این مرحله از مقادیر از پیش محاسبه شده پوش های محدب استفاده می شود. در هر گام از اجرای الگوریتم بسته بندی، نقطه ای مانند "pi" در پوش محدب فرض می شود و الگوریتم به دنبال این است که نقطه ای مانند (pi+1 = "f(pi,P" پیدا کند با این ویژگی که بقیه نقاط در P، در سمت راست خط گذرنده از "pi" و"pi+1" قرار گیرند. اگر پوش محدب را برای m نقطه که در مجموعه Q قرار دارند مشخص باشد، می توان "(f(pi,Q" را با استفاده از جستجوی دودویی، در زمان (O(log m محاسبه کرد.همچنین می توان (f(pi,Q را برای هر یک از (O(n/m زیر مجموعه P حساب کرد. این کار از مرتبه زمانی (O(n/m log m طول می کشد. سپس با استفاده از همین تکنیک، "(f(pi,P"' محاسبه می شود. اما این کار فقط نقاطی را در نطر می گیرد که زیر مجموعه ای مانند Qاز P وجود داشته باشد که برای آن نقطه "(f(pi,Q" را حساب کرده باشد. همان گونه که
الگوریتم بسته بندی هدیه این فرایند را (O(h بار تکرار می کند، مرحله دوم این الگوریتم هم به اندازه (O(n log m زمان می برد و چنانچه m=h باشد، (O(n log h زمان می برد. با اجرای دو مرحله اول الگوریتم مطابق آنچه در بالا توصیف شد، می توان پوش محدب را برای n نقطه، با این فرض که مقدار h از قبل مشخص است، در زمان (O(n logh محاسبه کرد. با فرض اینکه m&lt;h باشد، آنگاه می توان اجرای الگوریتم را پس از m+1 گام متوقف کرد. بنابراین اجرای آن تنها به اندازه (O(nlog m، البته بدون محاسبه پوش محدب، زمان می گیرد. می توانیم در ابتدا، m را ثابت کوچکی در نطر بگیریم و سپس مقدار آنرا افزایش دهیم تا زمانی که m&gt;h شود.در این حالت، پوش محدب به عنوان خروجی بدست می آید.ثابت اولیه m را نیز در فرض های خود 2 در نظر می گیریم اما در عمل عددی حدود 5 بهتر عمل می کند. اگر مقدار m خیلی آرام افزایش یابد، ممکن است الگوریتم مراحل بالا را دفعات زیادی تکرار کند و این باعث می شود زمان اجرا بسیار زیاد شود. از طرف دیگر، اگر مقدار m به سرعت افزایش یابد، ممکن است m ناگهان از h خیلی بیشتر شود و این امر خود باعث افزایش زمان اجرا می شود. الگوریتم چان، مقدار m را
در هر تکرار مربع می کند و هر بار اطمینان حاصل می کند که مقدار m هیچگاه از n بیشتر نشود.به عبارت دیگر در تکرار tام(که t از صفر شروع می شود)، formula_1. زمان اجرای کل الگوریتم برابر است با: formula_2 برای تعمیم این روش به فضای 3 بعدی، باید به جای الگوریتم جستجوی گراهام، از الگوریتم با زمان اجرای (O(n log n برای محاسبه پوش محدب در فضای 3 بعدی استفاده شود. همچنین به جای الگوریتم مارش برای بسته بندی هدیه، باید از نسخه 3بعدی آن استفاده کنیم. با این تغییرات، پیچیدگی اجرای الگوریتم همچنان (O(n log h باقی می ماند. پیاده سازی. در مقاله چان، روش های پیشنهادی زیادی برای بهبود عملی کارایی الگوریتمش آمده است که بعضی از آنها عبارتند از: