Payamvdn/NorthPersian_fa_wiki huggingface dataset:
اشت ژن ها در این گونه تحقیقات به عنوان نشانه گذار با دقت بالا مورد استفاده قرار می گیرند. تعداد زیاد اس ان پی ها و باثباتی به ارث رسیدن اس ان پی ها در طول نسل ها آنها را برای این کار مناسب کرده است. پزشکی قانونی: اس ان پی ها نخستین بار برای انطباق دادن نمونه دی ان ای پزشکی قانونی با نمونه دی ان ای مظنون مورد استفاده قرار می گرفتند؛ اما با پیدایش انگشت نگاری دی ان ای با روش های مبتنی بر تکرار پشت سرهم کوتاه (به انگلیسی: )، این کاربرد آنها به تدریج کم رنگ شد. در آینده ممکن است اس ان پی ها در پزشکی قانونی برای پیدا کردن سرنخ هایی مثل رنگ چشم، رنگ مو، قومیت و غیره مورد استفاده قرار گیرند. آقای Kidd و دیگران با مطالعه روی ۴۰ گروه جمعیتی نشان داده اند که یک دنباله با ۱۹ اس ان پی می تواند گروه قومیتی صاحبش را با احتمال انطباق زیاد (احتمال خطای ۷-^۱۰) شناسایی کند. یک مثال از اینکه اس ان پی ها چگونه می توانند مفید باشند در حوزه بازسازی هنری چهره پیش از مرگ بقایای اسکلت انسان های ناشناس است. هرچند بازسازی چهره تنها با استفاده از جنبه های مردم شناسی هم به طور قابل قبولی دقیق انجام می شود، اما داده های دیگر امکان رسیدن ب
ه نمایش دقیق تری از رنگ چشم، پوست، مو، و غیره را می دهند. در وضعیتی که مقدار نمونه های پزشکی قانونی کم است یا نمونه آسیب دیده است، روش های اس ان پی می توانند جایگزین خوبی برای روش های تکرار پشت سرهم کوتاه باشند. دلیل این امر وفور نشانه گذارهای احتمالی، قابلیت اتوماتیک شدن و کاهش طول قسمت دی ان ای مورد نیاز تا حد تنها ۶۰ الی ۸۰ جفت باز است. مطالعات مربوط به اس ان پی ها همچنین در محصولات دامی و برنامه های مربوط به آن ها نیز مهم است. برای جزئیات بیشتر در مورد روش های مختلف مشخص کردن اس ان پی ها قسمت را ملاحظه بفرمایید. آنها معمولاً دو اللی هستند و بنابراین مورد سنجش قرار می گیرند. اس ان پی ها معمولاً به صورت فردی عمل نمی کنند، بلکه با دیگر اس ان پی ها همکاری می کنند تا شرط یک مریضی را بازنمود کنند، مثلاً در پوکی استخوان، چنین اتفاقی رخ می دهد. یک روش پیدا کردن اس ان پی، استفاده از واکنش های زنجیره ای پلیمراز با محوریت آلل هاست. در این واکنش ها هر کدام از انواع آلل ها پس از گرم شدن و جدا شدن دو رشته شان از هم با نوع خاصی از پرایمرها جفت می شوند و با انواع دیگر پرایمرها به طور چشمگیری کمتر جفت می شوند، بنابراین بر
اساس فراوانی پرایمرهای محلول و میزان تکثیر شدن الل ها می توان انواع اس ان پی ها را تشخیص داد. پایگاه های داده. زمانی بود که وجود یک منبع موثق، جامع و عمومی از گوناگونی های ژنتیکی قطعیت نداشت. در حال حاضر پایگاه داده های متعددی وجود دارند (بیش از ۸۰۰ تا، که البته چندتای محدود مورد استفاده گسترده اند) که مهم ترین آنها به نام متعلق به مرکز ملی اطلاعات زیست فناوری آمریکا است. یک پایگاه داده خوب دیگر هم پروژه بین المللی هپ مپ (به انگلیسی ) است که تلاشی برای بررسی الگوهای تکرر الل ها و اختلال توازن ارتباطی (به انگلیسی: ) بین گونه های ژنتیکی انسان ها در جوامع مختلف جهان می باشد. نیز یک پایگاه داده اس ان پی چندرگه ای با فرمت ویکی است. پایگاه دادهٔ نیز روابط بین چند ریختی ها را توضیح می دهد. پایگاه دادهٔ جهشهای ژنی انسان جهش هایی که با امراض ارثی انسان رابطه دارند یا علت آن ها هستند و همچنین اس ان پی های وظیفه ای را فراهم می کند. به کاربر امکان می دهد که به صورت شهودی روابط را در سطح خلاصه روی یک یا چند مطالعه ژنتیکی مورد بررسی قرار دهد. نام گذاری. نام گذاری اس ان پی ممکن است کمی گیج کننده باشد. حالات گوناگونی برای یک
اس ان پی خاص می توانند موجود باشند و هنوز توافق عمومی روی این مسئله انجام نشده است. یک راه حل این است که اس ان پی ها با یک پیشوند نوشته شوند. به عنوان مثال c.76A&gt;T. باز هم مشکلاتی برای فعالیت های بیوانفورماتیک در زمینه اس ان پی وجود دارند که یکی از اساسی ترین آنها نیاز به به روزرسانی مرتب پایگاه داده ها و ابزارهای اس ان پی هاست. برای شناسایی هر اس ان پی به آن یک شناسه اس ان پی یا rsID می دهند، اما با کشف شدن اس ان پی های جدید و بهبود یافتن تناظرهای بین اس ان پی ها و در نتیجه گسترش یافتن پایگاه دادهٔ dbSNP، بعضاً مشاهده می شود که یک اس ان پی چندین شناسه داشته است؛ بنابراین بسته به اینکه از چه نرم افزار و کدام نسخه پایگاه داده استفاده می شود، ممکن است جستجو در پایگاه داده همه نتایج مرتبط را به ما ندهد. یک ابزار متکی به وب به نام SNAP، شناسه های مستعار را هم در نظر می گیرد و به کاربران اجازه می دهد که تبدیل لیست های شناسه ها بین نسخه های مختلف dbSNP را ببینند.
اسپرغم یا سپرغم یا اسپرم یا اسپرهم یا سپرهم یا سپرم شاه یا اسپرم شاه یا سپرغم شاه یا شاه اسفرهم گیاهی است که آن را ریحان یا نازبو یا ضیمران گویند و به روایت بندهشن به امشاسپند شهریور اختصاص دارد. گاه به طور کلی بر «هر گیاه خوشبو» گفته می شود. ابوعلی بلعمی آورده که چون خداوند توبهٔ آدم را بپذیرفت، از شادی گریستن به آدم افتاد و صد سال از خرمی و شکر همی گریست و از آن آب چشم، که از پس توبهٔ آدم بیرون آمد، همه گل و اسپرغم ها و بوهای خوش برست.
پرچم کامرون با تناسب ۲:۳ در ۲۰ مه ۱۹۷۵ پذیرفته شد. این پرچم که در آن از رنگ های پان آفریقایی سبز، زرد و قرمز استفاده شده است از سه نوار عمودی هم اندازهٔ سبز (در بخش اهتزاز پرچم)، سرخ و زرد تشکیل یافته و ستارهٔ زردرنگ پنج پری نیز در میان پرچم و نوار سرخ رنگ قرار دارد. نوع قرارگیری و اندازهٔ نوارها در پرچم کامرون یادآور پرچم فرانسه است که در دوران استعمار و پیش از استقلال یافتن کامرون بیشتر قلمرو آن را در اختیار خود داشت. نمادشناسی. در پرچم کامرون:
باباشَمَل عنوان منصبی است از مناصب رایج در میان لوطی ها و داش مشدی های طهران قدیم. باباشمل همچنین می تواند به هریک از موارد زیر اشاره داشته باشد:
باباشمل در طهران قدیم به فردی خاص از بین لوطی ها و داش های شناخته شدهٔ محله های مختلف شهر گفته می شد که پس از گذراندن مراحلی چند به منصب باباشملی نائل می گردید. باباشمل های واقعی در طهران قدیم، گروهی معدود و انگشت شمار بودند که دستورها و اراده و امر آنان، بدون هرگونه گفتگو و بدون قید و شرط لازم الاجرا بود. معنای باباشمل. لغتنامه دهخدا در تعریف باباشمل آورده است: در این مقاله بیشتر معنای اول مدّنظر بوده است. انتخاب باباشمل. باباشمل ها در طهران قدیم، از داش ها و لوطی ها بالاتر بودند و معمولاً از میان افراد این دو طبقه انتخاب می شدند. بدین ترتیب که داش ها و لوطی های طهران قدیم پس از گذراندن چند مرحله و سربلند درآمدن از همگی این مراحل، به منصب باباشملی نائل می شدند. از جمله مواردی که داش ها و لوطی های تهران قدیم برای ترقی از مقام داشی به مقام باباشملی و رسیدن به عنوان باباشمل، ناگزیر از طی آن مراحل بودند، می توان به موارد زیر اشاره کرد: معمولاً طی کردن تمامی این مراحل و پذیرفته شدن به عنوان باباشمل، بسیار دشوار بود و هر لوطی و داشی قادر نبود تا تمامی معیارهای مربوط به منصب باباشملی را در خود گرد آورده و به باباشم
ل تبدیل شود. اختیارات و توانائی ها. داشی که به منصب باباشملی می رسید و باباشمل خوانده می شد، در نزد رؤسای تمامی محلات به رسمیت شناخته می شد و حرف و دستورش، بدون هرگونه قید و شرط لازم الاجرا بود. بدین ترتیب تمامی افراد محلات، مطیع و فرمانبر باباشمل می شدند و هیچ کس برخلاف امر و ارادهٔ او، حق نداشت اقدامی انجام دهد یا رفتاری را عرضه نماید. ناصر نجمی در کتاب طهران عهد ناصری، دربارهٔ باباشمل ها می نویسد:
هری پاتر و یادگاران مرگ - قسمت دوم فیلمی در ژانر فانتزی و معمایی و محصول مشترک انگلیس و آمریکا در سال ۲۰۱۱ می باشد. این فیلم در واقع قسمت دوم از هفتمین فیلم مجموعهٔ فیلم های هری پاتر است که در تاریخ ۱۵ ژوئیه ۲۰۱۱ اکران شد. این فیلم هشتمین قسمت از مجموعه فیلم های دنیای جادوگری جی.کی. رولینگ است. این فیلم بر اساس رمانی با همین نام نوشتهٔ جی.کی. رولینگ و به کارگردانی دیوید ییتس ساخته شده است. این فیلم هشتمین و آخرین فیلم از سری فیلم های "هری پاتر" است که فیلم نامه اش توسط استیو کلاوز نوشته شده و تهیه کنندگانش دیوید هیمن، دیوید بارون و رولینگ بوده اند. بازیگران اصلی این فیلم دنیل ردکلیف در نقش هری پاتر، روپرت گرینت در نقش رون ویزلی و اما واتسون در نقش هرماینی گرنجر هستند. هری پاتر و قدیسان مرگبار-قسمت دوم با استقبال بسیار بالای منتقدان و تماشاگران همراه بود. فیلم از نظر منتقدان سایت متاکریتک و راتن تومیتوز جزو ده فیلم برتر سال ۲۰۱۱ می باشد. این فیلم با فروش بیش از ۱٫۳ میلیارد دلار است. این فیلم همچنین پر فروش ترین فیلم سال ۲۰۱۱ نیز بود. هری پاتر یادگاران مرگ-قسمت دوم از نظر کاربران سایت IMDB یکی از ۲۵۰ فیلم برتر
تاریخ سینماست. این فیلم در روز اول اکران خود توانست چیزی حدود ۴۵۰ میلیون دلار در گیشه فروش بدست آورد و تا سال ۲۰۱۵ در رکورد فروش افتتاحیه یک فیلم در یک روز رکورد دار بود. این فیلم تا اکنون پر فروش ترین فیلم تاریخ برادران وارنر است این فیلم نیز در سال۲۰۱۱ که اکران شد بعد از دو اثر جیمیز کامرون یعنی آواتار و تایتانیک در مقام سوم پر فروش ترین فیلم های جهان قرار گرفت ولی در سال ۲۰۱۲ فیلم انتقام جویان توانست با فروش حدود ۱ میلیارد و ۵۲۰ میلیون دلار در مقام سوم قرار بگیرد و فیلم هری پاتر یادگاران مرگ ۲ تا پایان سال ۲۰۱۴ در مقام چهارم بود. هری پاتر اکنون در مقام ۱۳ پرفروش ترین فیلم های جهان قرار دارد چیزی حدود ۹۵۰ میلیون دلار این فیلم توانست در سایر کشورهای جهان به فروش گیشه دست پیدا کند اما در آمریکا فروش این فیلم چیزی معادل ۴۰۰ میلیون دلار بوده است. داستان. داستان در ادامه هری پاتر و یادگاران مرگ - قسمت اول ادامه می یابد. هری پاتر و دو دوستش هرماینی گرنجر و رون ویزلی در یک ویلا به سر می برند. آن ها در ویلا از یک جن به نام گریپهوک تقاضای کمک برای سرقت از بانک گرینگوتز را می کنند. گریپهوک نیز شرطی برای آن ها می گذار
د او خواهان شمشیر گریفندور است آن ها نیز قبول می کنند که اگر گریپهوک در پیداکردن جان پیچ به آن ها کمک کند شمشیر را به او خواهند داد. آن ها با قیافه های مبدل وارد بانک می شوند، اما طی اتفاقاتی به حالت عادیشان بازمی گردند. آن ها فنجان جان پیچ را پیدا می کنند اما گریپهوک به آن ها خیانت می کند و آن ها مجبور می شوند سوار بر یک اژدها از بانک فرار کنند. همزمان لرد ولدمورت نیز از گم شدن جان پیچ با خبر می شود و تمام جن های بانک گرینگوتز را قتل عام می کند. همزمان هری و دو دوستش در جستجوی جان پیچی دیگر به هاگوارتز می روند اما توسط مرگ خوارها محاصره می شوند اما توسط ابرفورت دامبلدور برادر کوچک آلبوس دامبلدور نجات میابند. ابرفورت ان ها ترغیب به فرار می کند اما آن ها قبول نمی کنند و ابرفورت آن ها را به هاگوارتز می فرستد آن ها در اتاق ضروریات ظاهر می شوند و مورد استقبال دوستانشان قرار میگرند. آن ها دنبال جان پیچی دیگرند اما نمی دانند آن چیست و دقیقاً کجاست. در همین حال سوروس اسنیپ مدیر مدرسه هاگوارتز دانش آموزان را احضار می کند تا اگر از محل اختفای هری پاتر چیزی می دانند به او بگویند. اما در همان هنگام گروهی از محفل ققنوس ا
ز راه می رسند نبرد سختی بین ارتش مرگ خواران و مدرسه هاگوارتز درمی گیرد. هری نیز در جستجوی جان پیچ به سراغ بانوی خاکستری یا هلنا ریونکلا می رود هلنا نیز اطلاعات مهمی را در اختیار او می گذارد. در همین هنگام رون و هرماینی به تالار اسرار می روند و به وسیلهٔ نیش باسیلیسک فنجان را نابود می کنند هری نیز تاج ریونکلا را میابد اما در همین هنگام دراکو مالفوی و کراب و گویل برای کشتن هری به اتاق می آیند اما رون و هرماینی نیز به کمک هری می آیند اما ناگهان کراب دریایی از آتش را در اتاق می سازد اما نمی تواند آن را قطع کند؛ هری و رون و هرماینی به کمک جاروهای پرنده از اتاق خارج می شوند و جان پیچ نیز در اتاق می سوزد اکنون ولدمورت بسیار ترسیده و بسیار مراقب مار خود نجینی است که آخرین جان پیچ اوست اما ابر چوبدستی به ولدمورت عمل نمی کند او سیوروس اسنیپ را احضار می کند او می گوید که تنها راه وفاداری ابرچوبدستی به من نابودی اوست زیرا او دامبلدور را کشته است. هری و رون و هرماینی شاهد نابودی اسنیپ هستند اسنیپ در لحظه آخر عمرش بخشی از خاطراتش را در اختیار هری می گذارد. در این لحظه ولدمورت اعلام عقب نشینی می کند تا ارتش هاگوارتز بتواند
به مرده ها سرو سامان بدهد. هری نیز به قدح اندیشه می رود؛ و در خاطرات اسنیپ او متوجه میشود که اسنیپ به هیج وجه انسان بدی نبود بلکه مرگ دامبلدور تصمیمی بود که باهم گرفتند. همچنین متوجه می شود که خود نیز یک جان پیچ است و باید به دست ولدمورت کشته می شود. او شجاعانه به سوی جنگل می رود اما وقتی طلسم ولدمورت به او می خورد تنها جان پیچ درون وجود هری از بین می رود و خود هری زنده می ماند. ولدمورت به خیال اینکه پیروز شده به تحقیر معلمان و جنگجویان هاگوارتز می پردازد. اما هری بلند می شود و فرار می کند و پس از چند درگیری، افعی ولدمورت نگینی، بدست نویل لانگ باتم که شمشیر گریفیندور را در دست دارد، کشتهکه می شود و تنها خود ولدمورت می ماند که هری در یک دوئل نهایی، او را خلع سلاح و نابود می کند. نوزده سال بعد، هری و جینی پاتر، هرماینی، رون ویزلی و دراکو مالفوی و همسرش فرزندان خودشان را به هاگوارتز می فرستند. پذیرش. واکنش منتقدان. فیلم نقدهای خوبی دریافت کرد. در نوامبر سال ۲۰۱۲ سایت راتن تومیتوز مبنی بر ۳۰۵ رای درجه ۹۶٪ و با نمره ۸٫۳ از ۱۰ را دریافت کرد. این سایت این طور توضیح داد: «هیجانی، بازی های قوی و جلوه های بصری خیره کنن
د، همه مجموعه هری پاتر را به اثری زضایت بخش و پایان جادویی مناسب تبدیل می کند.» در متاکریتیک که بر اساس امتیاز منتقدان از ۱۰۰ است، فیلم نمره خوب ۸۷ را بر اساس ۴۱ نقد به دست آورد که تحسین جهانی به حساب می آید. گیشه. "هری پاتر و یادگاران مرگ قسمت دوم" ۳۸۱٫۰۱۱٫۲۱۹ میلیون دلار در آمریکا و کانادا فروش داشت و ۹۶۰٫۵۰۰٫۰۰۰ میلیون دلار در بازار جهانی فروش داشت و در کل ۱٬۳۴۱٬۵۱۱٬۲۱۹ فروخت. این فیلم هشتمین فیلم پرفروش تاریخ، پرفروش ترین فیلم سال ۲۰۱۱ شد، پرفروش ترین فیلم بین سری هری پاتر و پرفروش ترین فیلم اقتباسی از کتاب کودکان است. این فیلم رکورد فروش در روز افتتاحیه را از آن خود کرد. در فروش جهانی این فیلم رکورد سریع ترین فروش را به طوری که ۴۰۰ میلیون دلار (۵ روز)، ۵۰۰ میلیون دلار (۶ روز)، ۶۰۰ میلیون دلار (۸ روز)، ۷۰۰ میلیون دلار (۱۰ روز)، ۸۰۰ میلیون دلار (۱۲ روز)، ۹۰۰ میلیون دلار (۱۵ روز) و در نهایت ۱٬۳۴۱٬۵۱۱٬۲۱۹ دلار.
قهوه خانه قنبر، عنوان یکی از قهوه خانه های بسیار معروف و قدیمی تهران است، که در خیابان ناصریه تهران واقع بود. قهوه خانه قنبر از فرط شهرت، به متل ها و ضرب المثل های ایرانی راه پیدا کرده و به طور معمول به محلی که به صورت پاتوق افراد زیادی درآمده و افراد در آن به تفریح و گپ زدن مشغول باشند، قهوه خانه قنبر گفته می شود. شرح. قهوه خانه قنبر از قهوه خانه های معتبر و معروف در تهران قدیم بود، که در خیابان ناصریه قرار داشت. ظاهراً صاحب این قهوه خانه فردی به نام قنبر بوده است. بر اساس نوشته ناصر نجمی در کتاب تهران عهد ناصری، از جمله شاخص ترین ویژگی های این قهوه خانه قنبر این بود که در آن روزنامه خواندن را منع می کردند. اما در عوض فردی به نام درویش مرحب، هر شب و هر روز در آنجا به نقالی می پرداخت و داستان های شاهنامه را برای مشتریان این قهوه خانه، نقل می کرد. همچنین از دیگر برنامه های رایج در این قهوه خانه، اجرای تیاتر توسط پهلوان کچل و گل بدن خانوم بود، که این برنامه را با تردستی و مهارت بسیار، به اجرا میگذاشتند و هر بار قصه شیرینی را نمایش می دادند. افزون براین، لوطی عظیم و لوطی غلامحسین نیز، که هر دو از لوطی ها و کشتی
گیران معروف تهران بودند، بسیاری از اوقات در محوطه پشت قهوه خانه قنبر معرکه می گرفتند و بدینوسیله مردم را شاد و سرگرم می کردند.
ورزشگاه یووا بهراتی کریرانگان بیش تر به عنوان ورزشگاه سالت لیک شناخته می شود، یک ورزشگاه چند کاره در بیدانگر، کلکته، بنگال غربی، هند است. اطلاعات. این ورزشگاه برای مسابقات فوتبال و دو و میدانی استفاده می شود. ساخت ورزشگاه در سال ۱۹۸۴ به پایان رسید و گنجایش ۸۵،۰۰۰ هزار نفر را دارا است. ورزشگاه کم و بیش در ۱۰ کیلومتری شرق کلکته، در مرکز شهر واقع شده است و شکل ورزشگاه بیضی است. سقف ورزشگاه از لوله های فلزی و ورق آلومینیوم و بتن ساخته شده است. دو تابلوی نتایج الکترونیکی و اتاقهای کنترل در ورزشگاه تعبیه شده است. روشنایی یکنواخت در ورزشگاه برای سادگی در برگزاری مسابقات ورزشی در شب قرار دارد. ورزشگاه با مساحت ۷۶٫۴۰ هکتار (۳۰۹،۲۰۰ متر۲). در ژانویه ۱۹۸۴ گشایش یافت. فوتبال. فوتبال ورزش اصلی در این ورزشگاه است. ورزشگاه سالت لیک میزبان بازی های خانگی از باشگاه های محلی موهان باگان، بنگال شرقی، و محمدان، سه تا از باشگاه های بزرگ فوتبال در هند است.
قهوه خانه تنبل، عنوان قهوه خانه ای از قهوه خانه های تهران قدیم است که در چهارراه سوسکی واقع بوده است. این قهوه خانه در کنار قهوه خانه های دیگری همچون: قهوه خانه قنبر، قهوه خانه عرش، قهوه خانه باغ اناری، قهوه خانه سرگذر، و... معروفترین و معتبرترین قهوه خانه های تهران در عهد قاجار بودند. ناصر نجمی در کتاب طهران عهد ناصری نوشته است که قهوه خانه تنبل، مرکز تجمع باباشمل ها و کلاه نمدی ها و لوطی های شهر تهران بود.
در علوم رایانه و ریاضیات، برنامه ریزی پویا یا داینامیک، روشی کارآمد برای حل مسائل جستجو و بهینه سازی با استفاده از دو ویژگی زیرمسئله های هم پوشان و زیرساخت های بهینه است. برخلاف برنامه ریزی خطی، چارچوب استانداردی برای فرموله کردن مسائل برنامه ریزی پویا وجود ندارد. در واقع، آنچه برنامه ریزی پویا انجام می دهد ارائه روش برخورد کلی جهت حل این نوع مسائل است. در هر مورد، باید معادلات و روابط ریاضی مخصوصی که با شرایط آن مسئله تطبیق دارد نوشته شود. تاریخچه. این روش در سال ۱۹۵۳ توسط ریاضی دانی به نام ریچارد بلمن معرفی شد. برنامه ریزِی پویا در ریاضی و علوم رایانه روشی شناخته شده است که از آن در نوشتن الگوریتم های بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده می شود. تعریف برنامه ریزی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده است که روش علوم رایانه ای برای برنامه ریزی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می کند در حالی که در روش ریاضی برنامه ریزی پویا امکان کاهش فضای حافظه بیشتر است. برنامه ریزی پویا شبیه روش تقسیم و حل، مسائل را با استفاده از ترکیب کردن جواب زیرمسئله ها ح
ل می کند. الگوریتم تقسیم و حل، مسئله را به زیر مسئله های مستقل تقسیم می کند و پس از حل زیر مسئله ها به صورت بازگشتی، نتایج را با هم ترکیب کرده و جواب مسئله اصلی را به دست می آورد. به عبارت دقیق تر، برنامه ریزی پویا بهتر است در مسائلی استفاده شود که زیرمسئله ها مستقل نیستند؛ یعنی زمانی که زیرمسئله ها، خود دارای چندین زیر مسئلهٔ یکسان هستند. در این حالت روش تقسیم و حل با اجرای مکرر زیرمسئله های یکسان، بیشتر از میزان لازم محاسبات انجام می دهد. یک الگوریتم برنامه ریزی پویا زیرمسئله ها را یک بار حل و جواب آن ها را در یک جدول ذخیره می کند و با این کار از تکرار اجرای زیرمسئله ها در زمانی که مجدداً به جواب آن ها نیاز است جلوگیری می کند. مثلا اگر مسئله فیبوناچی با برنامه ریزی پویا حل شود باعث اجرای مکرر یک زیرمسئله نمی شود. مثلا برای محاسبه f(5) مقادیر f(4) و f(3) تنها یک بار محاسبه می شوند. ولی اگر از روش تقسیم و حل استفاده شود. f(3) دو بار محاسبه می شود که سربار محاسباتی است. ویژگی ها. یک مسئله باید دارای دو مشخصهٔ کلیدی باشد تا بتوان برنامه نویسی پویا را برای آن به کار برد: زیرساختار بهینه و زیرمسئله های هم پوشان.
در طرف مقابل، به حل یک مسئله با ترکیب جواب های بهینهٔ زیرمسئله های ناهم پوشان، «تقسیم و حل» گفته می شود. به همین علت است که مرتب سازی ادغامی و سریع به عنوان مسائل برنامه نویسی پویا شناخته نمی شوند. اصل بهینگی. اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله ها را ایجاب می کند. پس می توان از روش برنامه نویسی پویا استفاده کرد. حل بهینه، سومین مرحله از بسط یک الگوریتم برنامه نویسی پویا برای مسائل بهینه سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است: تمام مسائل بهینه سازی را نمی توان با برنامه نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند. اصل بهینگی در یک مسئله صدق می کند اگر یک حل بهینه برای نمونه ای از مسئله، همواره حاوی حل بهینه برای همهٔ زیر نمونه ها باشد. در روش برنامه نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیرمسائل به صورت جزء به کل حل می شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده اند محاسبه می شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده اند
محاسبه می شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می شوند که قبلاً محاسبات آن ها صورت گرفته، و نتایج آن ها در آرایه ذخیره شده اند. در نتیجه نیاز به محاسبه مجدد آن ها نیست. به همین ترتیب در مرحله بعد زیرمسائل با چهار ماتریس محاسبه می شوند، و الی آخر. درختهای جستجوی دودویی بهینه درخت جستجوی دودویی یک درخت دودویی از عناصر است که معمولاً کلید نامیده می شوند به قسمی که: زیرسازه بهینه. زیرساختار بهینه به این معناست که جواب یک مسئلهٔ بهینه سازی را بتوان از ترکیب جواب های بهینهٔ زیرمسئله های آن به دست آورد. چنین زیرساختارهای بهینه ای معمولاً با رویکرد بازگشتی به دست می آیند؛ برای مثال، در گراف "(G=(V,E"، کوتاه ترین مسیرِ م از رأس آ به رأس ب، زیرساختار بهینه از خود نشان می دهد: هر رأس میانیِ ث از مسیرِ م را در نظر بگیرید. اگر م واقعاً کوتاه ترین مسیر باشد، آنگاه می توان آن را به دو زیرمسیر م۱ از آ تا ث و م۲ از ث تا ب در نظر گرفت، به نحوی که هر کدام از این ها کوتاه ترین مسیر بین دو سر خود هستند (به همان طریق برش و چسباندن کتاب مقدمه ای بر الگوریتم ها). بر این اساس، می توان جواب را به صورت بازگش
تی بیان کرد، درست مانند الگوریتم های بلمن-فورد و فلوید-وارشال. استفاده از روش زیرسازه بهینه به این معناست که مسئله را به زیرمسئله هایی کوچک تر بشکنیم و برای هر یک از این زیرمسئله ها پاسخی بهینه بیابیم و پاسخ بهینه مسئلهٔ کلی را از کنار هم قرار دادن این پاسخ های بهینهٔ جزئی به دست آوریم. مثلاً در هنگام حل مسئلهٔ یافتن کوتاه ترین مسیر از یک رأس یک گراف به رأسی دیگر، می توانیم کوتاه ترین مسیر تا مقصد از همهٔ رئوس مجاور را به دست آوریم و از آن برای جواب کلی استفاده کنیم. به طور کلی حل مسئله از این روش شامل سه مرحله است. زیرمسئله های هم پوشان. زیرمسئله های هم پوشان به معنای کوچک بودن فضای زیرمسئله هاست، به این معنا که هر الگوریتم بازگشتی برای حل این مسئله، باید به جای ایجاد زیرمسئله های جدید، زیرمسئله های تکراری را بارها حل کند. برای مثال، به فرمول بازگشی دنبالهٔ فیبوناچی دقت کنید: "Fi = Fi−1 + Fi−2"، با حالات پایهٔ "F"1 = "F"2 = ۱. آنگاه "F"43 = "F"42 + "F"41، و "F"42 = "F"41 + "F"40. اکنون "F"41 در زیردرخت های هر دوی "F"43 و "F"42 محاسبه می شود. در صورت اتخاذ چنین رویکرد ساده انگارانه ای، نهایتاً زیرمسئله های یک
سانی را بارها حل می کنیم، در صورتی که تعداد کل زیرمسئله ها در واقعیت کم است (تنها ۴۳تا). برنامه نویسی پویا به این حقیقت دقت می کند و هر زیرمسئله را تنها یک بار حل می کند. گفته می شود مسئله ای دارای زیرمسئله های هم پوشان است، اگر بتوان مسئله را به زیرمسئله های کوچکتری شکست که پاسخ هرکدام چند بار در طول فرایند حل مورد استفاده قرار بگیرد. برنامه ریزی پویا کمک می کند تا هر کدام از این پاسخ ها فقط یک بار محاسبه شوند و فرایند حل از بابت دوباره کاری هزینه ای را متحمل نشود. برای مثال در دنباله فیبوناچی برای محاسبهٔ عدد چهارم دنباله به دانستن عدد سوم نیاز داریم. برای محاسبهٔ عدد پنجم هم باز به عدد سوم نیاز داریم. حال اگر مثلاً در شرایطی بخواهیم عدد ششم دنبالهٔ فیبوناچی را حساب کنیم، در این محاسبه هم مقدار عدد پنجم را می خواهیم و هم مقدار عدد چهارم را. اگر تصمیم بگیریم اعداد چهارم و پنجم را به نوبت حساب کنیم در هنگام محاسبهٔ هرکدام به مقدار عدد سوم نیاز پیدا می کنیم و باید دوباره آن را محاسبه کنیم. برای جلوگیری از این محاسبات چندباره، الگوریتمهایی که مبتنی بر برنامه ریزی پویا هستند، معمولاً یکی از دو راه زیر را استفاده
می کنند. گراف زیرمسئله ها. زمانی که به یک مسئلهٔ برنامه نویسی پویا می اندیشیم، باید مجموعهٔ زیرمسئله های موجود و چگونگی وابستگی آن ها را درک کنیم. گراف زیرمسئله ها دقیقاً همین اطلاعات را برای یک مسئله در بر می گیرد. تصویر ۱ گراف زیرمسئله های دنباله های فیبوناچی را نشان می دهد. گراف زیرمسئله ها یک گراف جهت دار، شامل یک رأس به ازای هر زیرمسئلهٔ متمایز است و در صورتی یک یال جهت دار از رأس زیرمسئلهٔ x به رأس زیرمسئلهٔ y دارد که برای تعیین یک جواب بهینه برای زیرمسئلهٔ x مستقیماً نیاز به در نظر گرفتن یک جواب بهینه برای زیرمسئلهٔ y داشته باشیم. برای نمونه، گراف زیرمسئله دارای یک یال از x به y است، در صورتی که یک رویهٔ (procedure) بازگشتی بالا به پایین برای حل x، مستقیماً خود را برای حل y صدا بزند. می توان گراف زیرمسئله ها را یک نسخهٔ کاهش یافتهٔ درخت بازگشتی برای روش بازگشتی بالا به پایین در نظر گرفت، به گونه ای که همهٔ رئوس مربوط به یک زیرمسئله را یکی کنیم و یال ها را از والد به فرزند جهت دار کنیم. روش پایین به بالا برای برنامه نویسی پویا رئوس گراف زیرمسئله ها را به ترتیبی در نظر می گیرد که همهٔ زیرمسئله های مجاور
یک زیرمسئله، پیش از آن حل شوند. در یک الگوریتم برنامه نویسی پویای پایین به بالا، رئوس گراف زیرمسئله ها را به صورتی در نظر می گیریم که «معکوس مرتب توپولوژیکی» یا «مرتب توپولوژیک وارون» زیرگراف مسئه ها است. به زبان دیگر، هیچ زیرمسئله ای تا زمانی که همهٔ زیرمسئله هایی که به آن ها وابسته است حل نشده اند، در نظر گرفته نمی شود. به طور مشابه، می توانیم رویکرد بالا به پایین (همراه به خاطرسپاری) برای برنامه نویسی پویا را به شکل جستجوی ژرفانخست گراف زیرمسئله ها ببینیم. اندازهٔ گراف زیرمسئله ها می تواند ما را در تعیین زمان اجرای الگوریتم برنامه نویسی پویا یاری کند. از آنجایی که هر زیرمسئله را فقط یک بار حل می کنیم، زمان اجرا برابر است با مجموع تعداد بارهایی که نیاز است هر زیرمسئله را حل کنیم. به طور معمول، زمان محاسبهٔ جواب یک زیرمسئله، متناسب با درجهٔ رأس متناظر در گراف، و تعداد زیرمسئله ها برابر با تعداد رئوس گراف است. مثال. یک پیاده سازی ساده از یک تابع برای یافتن عدد فیبوناچی nام می تواند به شکل زیر باشد. function fib(n) if n = 0 return 0 if n = 1 return 1 return fib(n − 1) + fib(n − 2) برای مثال اگر از چنین تابعی
codice_1 را بخواهیم، تابع هایی که صدا می شوند به شکل زیر خواهند بود. مشخص است که چنین فرایندی پر از محاسبات تکراری است. مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب شده است. در محاسبات بزرگ تر چنین تکرارهایی برنامه را به شدت کند می کنند. این الگوریتم دارای پیچیدگی زمانی نمایی است. حال فرض کنید ما یک آرایه دوتایی map داریم که عدد n را به مقدار عدد فیبوناچی nام مربوط کرده و ذخیره می کند. پیچیدگی زمانی چنین الگوریتمی n خواهد بود. همچنین میزان فضای اشغال شده اش هم از مرتبه n خواهد بود. var m := map(0 → 1, 1 → 1) function fib(n) if map m does not contain key n m[n] := fib(n − 1) + fib(n − 2) return m[n] این نمونه ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکستیم و بعد به محاسبه و ذخیرهٔ پاسخ زیرمسئله ها پرداختیم. در فرایند پایین به بالا برای حل چنین مسئله ای از عدد فیبوناچی یکم شروع می کنیم تا به عدد خواسته شده برسیم. با این کار باز هم پیچیدگی زمانی از مرتبه n است. function fib(n) var previousFib := 0, currentFib := 1 if n = 0 return 0 if n = 1 return 1 repeat n − 1 times var newFib := previousFib + curren