Payamvdn/NorthPersian_fa_wiki huggingface dataset:
الگوریتم ادموندز کارپ : در علوم کامپیوتر و نظریه گراف الگوریتمEdmonds_Karp پیاده سازی ای برای الگوریتم فورد–فالکرسون برای محاسبهٔ مسئله بیشینه جریان در شبکه شاره در زمان formula_1 است. این الگوریتم از الگوریتم ارسال-برچسب که در زمان formula_2 انجام می شود سریع تر است. این الگوریتم اولین بار توسط دانشمند شوروی Yefim (Chaim) Dinic در سال ۱۹۷۰ منتشر شد؛ و به طور مستقل توسط جک ادموند و ریچارد کارپ در سال ۱۹۷۲ با کاهش زمان الگوریتم قبلی به formula_1 انتشار یافته است. الگوریتم. در این الگوریتم می خواهیم بیشینه شاره را از مبدأ s تا مقصد t پیدا کنیم این الگوریتم شبیه به الگوریتم الگوریتم فورد–فالکرسون است و تفاوتش این است که در این الگوریتم محدودیت الگوریتم فورد–فالکرسون بهبود می یابد چرا که که محاسبهٔ مسیر افزایشی را با جستجوی سطح اول پیاده سازی می کنیم. حال آنکه در الگوریتم فورد–فالکرسون جستجوی عمق اول را اجرا می کردیم و به محدودیت زمانی بیشتری نیاز داشت. مسیر پیدا شده باید کوتاه ترین مسیر باشد که ظرفیت آماده ای دارد؛ که توسط جستجوی سطح اول پیدا می شود؛ که ما اجازه می دهیم یال ها اندازهٔ واحدی داشته باشند. بیشترین
شاره معادل با برش کمینه است. ویژگی دیگر این الگوریتم این است که طول کوتاه ترین مسیر هر سری افزایش می یابد. اثبات را می توان ار منبع ذکر شده مشاهده کرد کاری که در این الگوریتم می کنیم این است که با جستجوی سطح اول مسیر افزایشی را می یابیم و هر سری اگر که مسیر افزایشی (مسیری که یال پر ندارداین مسئله هم در کد سطح اولی که در زیر آمده مشخص است) داشتیم کمترین ظرفیت را پیدا می کند و مینیمم ظرفیت را به جریان همهٔ یال ها اضافه می کند و از آن کم می کند. به این صورت بیشینه شار بین مبدأ و مقصد را پیدا می کند که معادل با برش کمینه است. در کد زیر نحوهٔ انجام این الگوریتم نشان داده می شود. ورودی الگوریتم: ورودی این الگوریتم یک گراف است که یک راس مبدأ s دارد و یک راس مقصد t و روی همهٔ یال ها ظرفیت هر یال نوشته شده است. خروجی الگوریتم: بیشترین جریان از s به t تا زمانی که مسیر افزایشی با ویژگی های بالا وجود دارد. پیچیدگی الگوریتم. زمان اجرای این الگوریتم formula_1 است. به این علت که هر مسیر در زمان اجرای formula_5 به دست می آید. در هر زمان حداقل یکی از E یال سیر می شوند؛ که فاصله از یال سیر شده تا مبدأ باید طولانی تر از آخرین ب
اری باشد که سیر شده و این طول حداکثر برابر با V تعداد راس ها است. پیاده سازی. algorithm EdmondsKarp input: C[1..n, 1..n] (Capacity matrix) E[1..n, 1.. ?](Neighbour lists) s (Source) t (Sink) output: f (Value of maximum flow) F (A matrix giving a legal flow with the maximum value) f:= 0 (Initial flow is zero) F:= array(1..n, 1..n) "(Residual capacity from u to v is C[u,v] - F[u,v]) forever m, P:= BreadthFirstSearch(C, E, s, t, F) if m = ۰ break f:= f + m (Backtrack search, and write flow) v:= t while v ≠ s u:= P[v] F[u,v]:= F[u,v] + m F[v,u]:= F[v,u] - m v:= u return (f, F) algorithm BreadthFirstSearch input: C, E, s, t, F output: M[t] (Capacity of path found) P (Parent table) P:=array(1..n) for u in 1..n P[u]:= -۱ P[s]:= -2(make sure source is not rediscovered) M:=array(1..n)(Capacity of found path to node) M[s]:= ∞ Q:= queue() Q.push(s) while Q.size()&gt; ۰ u:= Q.pop() for v in E[u] (If there is available capacity, and v is not seen before in search) if C[u,v] - F[u,v]&gt; 0 and P[v] = -۱ P[v]:= u M[v]:= min
(M[u], C[u,v] - F[u,v]) if v ≠ t Q.push(v) else 'return M[t], P return 0, P مثال. در شکل زیر گرافی داده شده است که روی یال هایش ظرفیت هر یالی قرار دارد و جریان اولیهٔ گذر کرده از یال ها برابر با ۰ است می خواهیم جریان بیشینه که از A به G می رود را پیدا کنیم. در شکل های زیر مراحل مختلف الگوریتم قرار گرفته و در هر شکل یک مسیر با ویژگی های ذکر شده با جستجوی عمق اول پیدا شده و در زیر هر شکل مراحل مختلف مربوط به آن قرار گرفته. در زیر هر شکل ظرفیت باقی مانده محاسبه شده که برابر با (cf(u,v) = c(u,v) − f(u,v است و طبق الگوریتم بالا بین ظرفیت های باقی ماندهٔ یال های الگوریتم مقدار حداقلی یافت می شود. در آخر می خواهیم بیشینه جریان را پیدا کینم. می دانیم که جریان بیشینه برابر با برش کمینه است. در این شکل یک برش کمینه وجود دارد که راس ها را به راس های A B C E وو D F G تقسیم می کند با ظرفیت زیر: c(A,D)+c(C,D)+c(E,G)=۳+۱+۱=۵
تعداد متفاوتی الگوریتم برای حل مسئلهٔ مارپیچ وجود دارد که آن ها، روش های خودکاری برای حل مارپیچ ها هستند. الگوریتم های موشی تصادفی، دنبال کنندهٔ دیوار، تضمینی و الگوریتم تریماکس برای این طراحی شده اند که درون مارپیچ و توسط سیاری استفاده شوند که هیچ دانش قبلی نسبت به توپولوژی مارپیچ ندارد، در حالی که پر کردن بن بست و الگوریتم های کوتاه ترین راه برای این طراحی شده اند که به وسیلهٔ شخص یا برنامهٔ رایانه ای که می تواند در لحظه کل مارپیچ را ببیند، استفاده شوند. مارپیچ هایی که هیچ حلقه ای ندارد به مارپیچ های استاندارد یا کامل شناخته می شوند و با مفهوم درخت در نظریهٔ نظریه گرافها هم ارزهستند. به همین دلیل بسیاری از الگوریتم های حل مارپیچ به نظریهٔ گراف مربوط هستند. به طوری که اگر کسی مسیرهای مارپیچ را در جهت درست بکشد، نتیجهٔ حاصل می تواند تبدیل به یک درخت شود. الگوریتم موشی تصادفی. این یک روش بدیهی برای این مسئله است که توسط یک روبات غیر هوشمند یا شاید یک موش می تواند پیاده سازی شود و آن به سادگی حرکت کردن در یک مسیر مستقیم تا رسیدن به یک تقاطع است و بعد انتخاب یک مسیر به صورت تصادفی است تا در آن جهت حرکت شود. گرچه
چنین روشی همواره در نهایت به یک پاسخ درست می رسد، اما این الگوریتم می تواند بسیار کند باشد. دنبال کننده دیوار. دنبال کنندهٔ دیوار، معروف ترین قاعده در طی کردن مارپیچ است که به آن قاعدهٔ دست چپ یا قاعدهٔ دست راست نیز می گویند. اگر مارپیچ یک فضای همبند ساده باشد، یعنی تمام دیوارهایش به هم یا به دیوارهٔ خارجی مارپیچ متصل باشند، با گرفتن یک دست به یک دیوار مارپیچ تضمین می شود که بازی کننده گم نمی شود و اگر که خروجی وجود داشته باشد به خروجی می رسد؛ در غیر این صورت، او دوباره به ورودی بازمی گردد در حالی که هر تونل مارپیچ را حداقل یک بار طی کرده باشد. یک دیدگاه دیگر برای این که چرا دنبال کنندهٔ دیوار نتیجه می دهد، دیدگاه توپولوژی است. اگر دیوارها متصل باشند، ممکن است به صورت یک حلقه یا دایره تغییر شکل دهند آنگاه دنبال کردن دیوار به حرکت کردن دور دایره از نقطهٔ آغاز تا پایان خلاصه می شود. برای پیشبرد این ایده ملاحظه شود که با گروه کردن مؤلفه های همبند دیوارهای مارپیچ، مرزهای آن ها به طور دقیق همان جواب هستند، حتی اگر بیش از یک جواب وجود داشته باشد. (شکل های سمت راست) اگر مارپیچ پیوستهٔ ساده نباشد (یعنی اگر نقطهٔ شرو
ع یا نقاط پایان در مرکز ساختار مارپیچ باشد یا مسیرها از رو یا زیر هم بگذرند.) این روش تضمینی ندارد که در رسیدن به هدف کمک کند. دنبال کردن دیوار می تواند در مارپیچ های سه بعدی یا با بعدهای بیش تر انجام شود اگر امکانش باشد که به صورت قطعی مسیرهای آن روی صفحهٔ ۲بعدی تصویر شود. برای مثال در یک مارپیچ ۳ بعدی می توان مسیرهایی که به سمت خارج می آیند را به سمت شمال غربی و مسیرهایی که به داخل می روند را به سمت شمال شرقی در نظر بگیریم. الگوریتم تضمین کننده. مارپیچ های نا پیوسته را نیز می توان با الگوریتم دنبال کننده دیوار حل کرد به شرط اینکه درگاه های ورود و خروج در دیواره بیرونی مارپیچ قرار داشته باشند. اما اگر به طور مثال نقطه شروع در داخل صفحه باشد، ممکن است در یک بخش جدا از بخش خروجی باشد ؛ در این صورت تعقیب کننده دیوار به طور دائمی به دور خود خواهد گشت. الگوریتم تضمینی (به نام Jon Pledge این نام گذاری شده است) این مشکل را حل خواهد کرد. الگوریتم تضمینی طوری طراحی شده است که موانع احتمالی را رفع می کند و نیازمند انتخاب یک جهت دلخواه حرکت است. هنگامی که یک مانع دیده می شود یک دست را (برای مثال دست راست) به طور ثابت ب
ه دیواره مانع گرفته و حرکت می کنیم و به ازای تمام چرخش ها زاویهٔ چرخش را به مجموع زوایای چرخش اضافه می کنیم و هنگامی که به جهت حرکت اولیه بازگشتیم و مجموع زوایای چرخش صفر شد، یعنی مانع را دور زده ایم و مسیر را ادامه می دهیم. در این الگوریتم هنگامی دست را از دیوار برمی داریم که مجموع زوایای چرخش و جهت فعلی(نسبت به جهت اولیه) برابر صفر شده باشد. این کار این امکان را به الگوریتم می دهد که در مسیرهای تله دار به شکل حرف "G" گیر نیفتد. فرض کنید که الگوریتم(در حرکت روی G) از دیوار اولی به سمت چپ بپییچد آنگاه به وسیلهٔ دیوارها مجبور می شود۳۶۰ درجه بچرخد. الگوریتمی که تنها جهت فعلی را دنبال کند در حلقه بی نهایت می افتد. این چنین که هنگامی که راست ترین دیوار پایین را ترک کند، دوباره وارد بخش منحنی سمت چپ می شود. الگوریتم تضمین کننده راست ترین دیوار را به دلیل اینکه مجموع زوایای چرخش در آن نقطه صفر نشده، ترک نمی کند و دیوار را همچنان دنبال می کند تا در نهایت با حرکت به سمت چپ و دقیقاً زیر شکل حرف از آن خارج می شود. ین الگوریتم به یک فرد به همراه قطب نما این امکان را می دهد که از هر نقطه درونی، بدون در نظر گرفتن مکان اول
یه، به یک خروجی در بیرون هر مارپیچ متناهی دوبعدی راه یابد. اما قابلیت یافتن مسیر برای حالاتی که نقطه شروع خارج صفحه و نقطه پایان داخل صفحه باشد را دارا نیست. الگوریتم تریماکس. الگوریتم تریماکس که توسط چارلز پیر ترماکس معرفی شده، یک روش بهینه برای پیدا کردن راه خروجی مارپیچ است که لازمهٔ آن کشیدن خط هایی روی زمین است که مسیری را مشخص کند و تضمین شده است که برای تمام مارپیچ هایی که مسیرهای خوش تعریفی دارند کار می کند. یک مسیر یا هنوز بازدید نشده یا یک بار علامت زده شده یا دو بار. هر بار مسیری انتخاب می شود با زدن علامت روی زمین (از انشعاب تا انشعاب) مشخص می شود. از ابتدا یک مسیر اتفاقی انتخاب می شود (اگر بیش از یک مسیر وجود داشته باشد) در هنگام رسیدن به انشعابی که هنوز بازدید نشده (هیچ مسیر علامت داری نیست) یک مسیر اتفاقی انتخاب می شود (و مسیر را علامتگذاری می کنیم). در هنگام رسیدن به انشعاب علامت دار، اگر مسیر کنونی یک علامته باشد مسیر رفته را برمی گردیم (و مسیر بازگشت را برای بار دوم علامت گذاری می کنیم) اگر این حالت نبود مسیری که کمترین علامت دارد را انتخاب می کنیم (و طبق معمول آن را علامت گذاری می کنیم)، وق
تی بالاخره به نتیجه رسیدیم مسیرهایی که دقیقاً یک بار علامت گذاری شده اند یک مسیر مشخص به شروع را نشان می دهند. اگر خروجی وجود نداشته باشد، این روش، مسیر را تا شروع نشان می دهددر حالی که تمام مسیرها دو علامته هستند. در این حالت هر مسیر دقیقاً دو بار طی می شود، در هر جهت یک بار. نتیجهٔ این حرکت ردیابی ۲طرفه نام دارد. این الگوریتم در حقیقت نوعی از الگوریتم جستجوی عمق اول است. الگوریتم پر کردن بن بست. پرکردن بن بست ها الگوریتمی است برای حل مارپیچ ها که در آن تمام مسیرهای بن بست غیر از مسیر درست پر می شود. برای مواقعی که مارپیچ بر روی کاغذ است یا توسط رایانه قصد حل آن را از این روش می توان استفاده کرد . در این الگوریتم تمام صفحه مارپیچ یکجا دیده می شود بنابراین برای فردی که داخل یک مارپیچ نامعلوم قرار دارد مفید نمی تواند باشد . روش کلی کار این است که اول تمام بن بست ها را پیدا کرده و سپس از یک بن بست تا اولین انشعاب را پر می کند. ویدئوی اجرای عملی این روش در اینجا قابل مشاهده است.. الگوریتم پرکردن بن بست نمی تواند به طور اتفاقی یک مسیر را از ابتدا حذف کند و باید برای تمام بن بست ها اجرا شود زیرا در هر مرحله توپولو
ژی مارپیچ حفظ می شود. علاوه برآن، این رویه به دلیل اینکه پاسخ نهایی نمی تواند هیچ بن بستی را شامل شود طولانی!!!! خواهد بود . اگر این الگوریتم بر روی مارپیچی کامل (مارپیچی که دور نداشته باشد) اجرا شود، جوابی یکتا خواهد داد اما در صورت وجود دور تنها می تواند مسیرهای احتمالی مسئله را به ما بدهد. الگوریتم کوتاه ترین مسیر. هنگامی که یک مارپیچ چند راه حل داشته باشد، ممکن است حل کننده بخواهد کوتاه ترین مسیر از ابتدا تا انتها را پیدا کند. یک الگوریتم ممکن کوتاه ترین مسیر را با پیاده سازی الگوریتم جستجوی اول سطح پیدا می کند. در حالی که الگوریتمی دیگر، الگوریتم جستجوی آ*، از روش های اکتشافی استفاده می کند. الگوریتم جستجوی سطح اول از یک صف استفاده می کند که خانه ها را به ترتیب بر اساس فاصلهٔ آن ها از ابتدا تا انتها بازدید می کند. هر خانهٔ بازدید شده باید اطلاعات مربوط به فاصلهٔ خودش از نقطهٔ شروع یا اینکه کدام یک از همسایگانش که به شروع نزدیک تر است باعث شده که به صف اضافه شود را نگه دارد. هنگامی که مکان انتهایی پیدا شود مسیر خانه ها بازمی گردیم تا به نقطهٔ شروع برسیم که این مسیر کوتاه ترین مسیر است منابع. Charles Trema
ux (° 1859 - † 1882) École Polytechnique de Paris (X:1876), French engineer of the telegraph
سِر جان فردریک ویلیام هرشل (زادهٔ ۷ مارس ۱۷۹۲ – درگذشتهٔ ۱۱ مهٔ ۱۸۷۱) ریاضیدان، ستاره شناس، شیمیدان، عکاس و مخترع تجربی بود. او چند سال نیز در کار گیاه شناسی فعالیت داشت. جان پسر ماری بالدوین و منجم سرشناس، فردریک ویلیام هرشل، و پدر ۱۲ فرزند بود. هرشل بنیادگذار استفاده از سیستم روز جولین در ستاره شناسی است. او هفت قمرِ زحل و چهار قمرِ اورانوس را نامگذاری کرده است. جان خدمات زیادی به علم عکاسی عرضه داشته و بررسی کوررنگی و تأثیر شیمیایی پرتو فرابنفش از کارهای اوست. زندگی. هرشل در اسلاو، باکینگهام شایر متولد شد، وی پسر مری بالدوین و ستاره شناس ویلیام هرشل بود. وی مدت کوتاهی در کالج ایتن و کالج سنت جان، کمبریج تحصیل کرد و در سال ۱۸۱۳ فارغ التحصیل شد.
الگوریتم نیدلمن وانچ یک همترازی سراسری بر دو ترتیب متوالی (مانند A و B) انجام می دهد. معمولاً در بیوانفورماتیک برای همترازی توالی های پروتئینی یا نوکلئوتیدی کاربرد دارد. این الگوریتم در سال ۱۹۷۰ توسط سول نیدلمن و کریستین وانچ ارائه شد. این الگوریتم نمونه ای از برنامه ریزی پویا است و اولین کاربرد برنامه ریزی پویا در مقایسهٔ توالی های زیستی است. مقدمه. این الگوریتم را می توان برای هرجفت رشته ای به کار برد. در راهنمای زیر از دو توالی دی ان ای کوتاه به عنوان مثال استفاده می شود: GCATGCT GATTACA ساخت جدول. ابتدا جدولی مانند زیر بسازید: در سطر اول، جدول رشته اول قرار می گیرد و محل شروع این رشته ستون سوم است. هم چنین رشته دوم در ستون اول قرار گرفته و محل شروع آن از سطر سوم است. در ابتدا هیچ عددی در جدول وجود ندارد. انتخاب سیستم امتیاز دهی. هنگام هم تراز سازی دو رشته، ممکن است سه حالت برای حروف رخ دهد: به هر یک از این حالات یک امتیاز اختصاص داده می شود و امتیاز یک هم تراز سازی از جمع امتیاز های هر جفت از حروف متناظر به دست می آید. سیستم های متفاوتی برای امتیاز دهی وجود دارند که تعدادی از آن ها در بخش سیستم های امتیاز
دهی ذکر شده اند. سیستم استفاده شده در اینجا، همان سیستم الگوریتم نیدلمن-وانچ است که در آن امتیاز تطابق 1+ و امتیاز عدم تطابق، درج یا حذف 1- می باشد. به طور مثال امتیاز هم ترازی زیر برابر 2- است زیرا: GCATG-CT GATT-ACA +1-1-1+1-1-1+1-1=3-5=-2 پر کردن جدول. از ستون دوم سطر دوم شروع کنید و در آن مقدار 0 را قرار دهید. سپس سطر به سطر پیش روید و امتیاز هر خانه را محاسبه کنید. این امتیاز از اضافه کردن امتیاز خانه مجاور سمت چپ، بالا یا بالا چپ (به صورت قطری) به امتیاز مناسب برای تطابق، عدم تطابق یا درج-حذف به دست می آید. در واقع برای محاسبه امتیاز 3 گزینه وجود دارد: در نهایت امتیاز نهایی این خانه با بیشترین امتیاز در میان سه امتیاز به دست آمده برابر است. با توجه به اینکه خانه های سطر دوم دارای خانه بالا یا بالا-چپ نیستند، پس تنها خانه سمت چپ می تواند برای محاسبه امتیاز استفاده شود. به این ترتیب سطر دوم به ترتیب از چپ دارای امتیاز های 0، 1-، 2-، 3-،...،7- می شود. استدلالی مشابه برای ستون دوم نیز به کار می رود که در نتیجه آن جدولی به شکل زیر حاصل می شود. حال برای محاسبه امتیاز خانه سطر سوم و ستون سوم، 3 حالت وجود دارد
: در نهایت بیشترین امتیاز در میان این 3 یعنی عدد 1 وارد این خانه می شود. هم چنین باید پیکان مربوط را ذخیره کرد که یک پیکان قطری از خانه(3,3) به خانه (2,2) است. به همین ترتیب تمامی خانه های جدول پر می شوند تا امتیاز نهایی بهترین هم ترازی به دست آید. کامل شده این جدول در شکل 1 آمده است و طبق آن امتیاز بهترین هم ترازی این دو رشته برابر با 0 است. بازگشت به مبداء. به وسیله تعدادی پیکان مسیری را از گوشه پایین-راست جدول به گوشه بالا-چپ جدول نشان دار کنید. سپس از طریق این مسیر و طبق قوانین زیر توالی متناظر مسیر را بسازید: پیکان افقی یک جای خالی("-") را با حرف ستون متناظر مبدا پیکان و پیکان عمودی حرف سطر متناظر مبدا پیکان را با یک جای خالی تراز می کند. با توجه به قواعد بالا و طبق شکل 1، یکی از بهترین هم ترازی ها برای دو رشته ذکر شده در زیر آمده است: GCA-TGCT G-ATTACA سیستم های امتیاز دهی. سیستم پایه. ساده ترین سیستم امتیاز دهی به هر یک از سه حالت تطابق، عدم تطابق و درج-حذف یک مقدار نسبت می دهد. به عنوان مثال ممکن است امتیاز تطابق برابر 1 و امتیاز عدم تطابق یا درج-حذف 1- در نظر گرفته شود. که در این حالت بیشترین امتیاز
مربوط به کمترین فاصله ویرایش است. به عنوان مثالی دیگر ممکن است به تطابق امتیاز 0 و به عدم تطابق و درج-حذف امتیاز 1- نسبت داده شود. که در این حالت امتیاز یک هم ترازی در واقع فاصله ویرایش میان دو رشته است. سیستم های امتیاز دهی متفاوت برای شرایط مختلف طراحی شده اند. به عنوان مثال اگر وجود فاصله را اتفاق بدی در هم ترازی در نظر بگیریم، میتوانیم از امتیاز بندی مانند مثال زیر استفاده کنیم: امتیاز تطابق =1+ امتیاز عدم تطابق=1- امتیاز فاصله=7- ماتریس مشابهت. سیستم های امتیاز دهی پیچیده تر، نه تنها برای نوع جایگزینی بلکه برای حروف مختلف نیز امتیاز های متفاوتی در نظر میگیرند. به عنوان مثال، ممکن است به تطابق بین 2 حرف A امتیاز 1 و به تطابق بین 2 حرف G امتیاز 3 داده شود. که این به معناست که تطابق G ها از اهمیت بیشتری برای هم تراز سازی برخوردار است. از این روش امتیاز دهی برای عدم تطابق نیز می توان بهره گرفت. به عنوان مثال ممکن است به دو حرف A,G امتیاز 1- و به دو حرف T,G امتیاز 2- اختصاص داده شود. برای نمایش همه حالات ممکن امتیاز دهی از ماتریس مشابهت استفاده می شود. ماتریس زیر نمونه ای از ماتریس های مشابهت برای مثال بالاست
: به عنوان مثال، ماتریس زیر، ماتریس مشابهت امتیاز گذاری مورد استفاده در شکل 1 است: با توجه به اینکه امتیاز عدم تطابق دو حرف مثلا A و T با امتیاز عدم تطابق T و A برابر است، ماتریس مشابهت ماتریسی متقارن است. ماتریس های امتیاز دهی مختلف برای دادن وزن های متفاوت و مناسب شرایط به حالات مختلفی که ممکن است رخ دهند، ساخته می شوند. این ماتریس های وزن دار به ویژه در هم تراز سازی توالی های پروتئینی کاربرد دارند زیرا فراوانی آمینو اسید های مختلف با یکدیگر متفاوت است. بلوسام(BLOSUM) و PAM دو نمونه پر کاربرد از این ماتریس های وزن دار هستند. جریمه پرش. هنگام هم ترازی توالی ها معمولا درج-حذف به وجود می آید که گاهی تعداد زیادی از آن ها پشت سر هم قرار میگیرند. از نظر زیستی، یک فاصله بزرگ با احتمال بیشتری از یک حذف بزرگ ناشی می شود تا از چندین حذف کوچک. در نتیجه امتیاز 2 درج-حذف کوچک باید بدتر از یک درج-حذف بزرگ باشد. راه ساده و معمول این امتیاز دهی این است که برای شروع یک فاصله که در واقع یک درج-حذف جدید است یک جریمه بالا و برای گسترش فاصله که در واقع گسترش درج-حذف هاست جریمه پایین تری در نظر بگیریم. برای مثال، برای درج-حذف جد
ید می توان امتیاز 6- و برای گسترش آن امتیاز 1- را در نظر گرفت. مثلا هم ترازی زیر CTTTTTTG C-T-T--G که پیش ازاین دارای چندین هم ترازی معادل بود، اکنون به شکل زیر هم تراز می شود: CTTTTTTG CTT----G زیرا فاصله به طول 4 بر چندین فاصله با طول کمتر ارجحیت دارد. یک ارائهٔ جدید. امتیازها برای کارکترهای همتراز شده توسط ماتریس تطابق مشخص می شود. در اینجا formula_1 تطابقی برای کارکترهای a و b به شمار می رود که از یک جریمه پرش خطی، که اینجا d نامیده می شود. برای نمونه، اگر ماتریس تطابق این باشد: همترازی آن: AGACTAGTTAC CGA‒‒‒GACGT با جریمه پرش ۵-، امتیاز زیر را خواهد داشت: formula_2 formula_3 در طی پردازش الگوریتم، formula_4 به عنوان امتیاز بهینه برای همترازی اولین formula_5 کارکتر در A و اولین formula_6 کارکتر در B، در نظر گرفته می شود. اصل بهینه سازی به صورت زیر آورده شده است. Basis: formula_7 formula_8 Recursion, based on the principle of optimality: formula_9 کد زیر برای محاسبه ماتریس F به کار می رود: for i=0 to length(A) F(i,0) ← d*i for j=0 to length(B) F(0,j) ← d*j for i=1 to length(A) for j=1 to length(B) Match ←
F(i-1,j-1) + S(Ai, Bj) Delete ← F(i-1, j) + d Insert ← F(i, j-1) + d F(i,j) ← max(Match, Insert, Delete) زمانی که ماتریس F محاسبه شد، مقدار درایه formula_10، بیشترین امتیاز در بین همترازی ها را به ما می دهد. برای محاسبهٔ یک همترازی که دقیقاً این امتیاز را دهد، باید از خانهٔ پایین-راست جدول شروع کنید و مقدار آن را با سه منبع ممکن(تطبیق، درج و حذف) مقایسه کنید تا بفهمید هر یک از کدام منبع به دست آمده است. اگر از طریق تطابق به دست آمده بود، formula_11 و formula_12 با هم همترازند. اگر از طریق حذف به دست آمده است، formula_11 با یک پرش همتراز شده است و اگر از طریق درج به دست آمده بود formula_12 نیز با یک پرش همتراز شده است.(عموماً برای یک مقدار، بیش از یک انتخاب داریم که همه آن ها می توانند ما را به سمت همترازی بهینه هدایت کنند) AlignmentA ← " AlignmentB ← " i ← length(A) j ← length(B) while (i&gt; 0 and j&gt; ۰) Score ← F(i,j) ScoreDiag ← F(i - 1, j - 1) ScoreUp ← F(i, j - 1) ScoreLeft ← F(i - 1, j) if (Score == ScoreDiag + S(Ai, Bj)) AlignmentA ← Ai + AlignmentA AlignmentB ← Bj + AlignmentB i ← i - 1 j ← j - 1 el
se if (Score == ScoreLeft + d) AlignmentA ← Ai + AlignmentA AlignmentB ← «-» + AlignmentB i ← i - 1 otherwise (Score == ScoreUp + d) AlignmentA ← «-» + AlignmentA AlignmentB ← Bj + AlignmentB j ← j - 1 while (i&gt; ۰) AlignmentA ← Ai + AlignmentA AlignmentB ← «-» + AlignmentB i ← i - 1 while (j&gt; ۰) AlignmentA ← «-» + AlignmentA AlignmentB ← Bj + AlignmentB j ← j - 1 پیچیدگی. محاسبه امتیاز هر خانه از جدول دارای پیچیدگی formula_15 است. در نتیجه پیچیدگی زمانی الگوریتم برای دو توالی به طول formula_16 و formula_17 ، formula_18 است. ثابت شده است که با استفاده از می توان زمان اجرا را به formula_19 بهبود بخشید. با توجه به اینکه الگوریتم جدولی formula_20 را پر می کند، پیچیدگی حافظه آن formula_18 می باشد. یادداشت های تاریخی. نیدلمن و وانچ، الگوریتم خود را برای حالتی که تنها از طریق تطابق و عدم تطابق، دارای جریمه هستیم و پرش ها هیچ گونه جریمه ای را ایجاد نمی کنند("d"=۰)، به طور واضح توصیف کردند. اویلین انتشار عمومی آن ها در سال ۱۹۷۰، به راه حلی بازگشتی اشاره داشت. &lt;math&gt;F_{ij} = max_{h. یک الگوریتم بهتر برای هم
ان مسئله(بدون جریمه پرش) که باز هم از روش برنامه نویسی پویا استفاده کرده است و زمان اجرای آن درجه دو است، در سال ۱۹۷۲ توسط دیوید سنکوف ارائه شد. الگوریتم های دیگری با همان درجه زمان اجرا، توسط وینتسیوک، در سال ۱۹۶۸ برای پردازش گفتار، و روبرت ونگر و مایکل فایکر، در سال ۱۹۷۴ برای تطابق رشته ای ارائه شده است. وانچ و نیدلمن، الگوریتم خود را به صورت بیشینه شباهت، فرموله کردند. یک امکان دیگر، کمینه کردن تغییرات بین دو توالی است. که ولادمیر لونشتین آن را معرفی کرد. در سال ۱۹۷۴، پیتر سلرز نشان که این دو الگوریتم در واقع معادل همند. امروزه «نیدلمن-وانج» به یک الگوریتم همترازی سراسری اشاره می کند که برای جریمه پرش های خطی، زمان اجرایی از درجه دو دارد.
شیشه مات شیشه ایست که سطح آن به وسیلهٔ پاشیدن ماسه که با فشار زیادی (سند پلاست) انجام می گیرد، مات شده باشد. سطوح شیشه مات، استفاده های گسترده ای، اعم از: تزئینات صرف بر روی پنجره ها، ظروف، علم اپتیک و ظروف آزمایشگاهی دارد. کاربرد در عکاسی. در عکاسی، در هر دوربینی، برای نمایان شدن تصویر یک ورقه شیشه مات وجود دارد.
نانایا یا نانای ایزدبانو عشق سومر و اکد بود که ارتباط نزدیکی با اینانا دارد. آیین او در اعصار پیش از تاریخ به ماوراءالنهر رفته بود، و در زمان اشکانیان هنوز در آن مناطق ستایش می شد در زمان اشکانیان در شهر نسا معبدی داشت و هنوز در این زمان آیین های کهن از جمله روسپیگری در معبد، زنده بود.
زبان بَلتی شاخه ای از لَداخی-بلتی است که آن هم بخشی از زبان تبتی به شمار می رود. زبان بلتی در ایالت گلگت-بلتستان در شمال شرق پاکستان و در قلمرو اتحادیه لَداخ هندوستان رواج دارد.
ایزو/آی ئی سی ۲۷۰۰۱ یک استاندارد امنیت اطلاعات از مجموعه مجموعه ایزو ۲۷۰۰۰ است که آخرین نسخه آن در سپتامبر ۲۰۱۳ منتشر شد. این استاندارد توسط سازمان بین المللی استانداردسازی(ISO)و کمیسیون الکتروتکنیکی بین المللی(IEC) تدوین شده است.
تیلت آپ، تیلت اسلب یا تیلت وال، نوعی ساختمان یا یک تکنیک ساخت و ساز با استفاده از بتن است. این روش روشی مقرون به صرفه و مؤثر در ساخت است. در این روش اجزای بتنی (یعنی دیوارها، ستون ها، تکیه گاهها سازه ای، و غیره) بر روی دال بتنی شکل می گیرند. از روش اجرای تیلت آپ اغلب برای اجرای ساختمان هایی با کاربری انباری، تجاری (مراکز خرید) و اداری که در آن ها سرعت اجرا و مسائل اقتصادی اهمیت دارد، استفاده می شود. این روش، عمدتاً برای ساخت ساختمان های کوتاه مرتبه حداکثر تا چهار طبقه به کار می رود. اگرچه اکثر ساختمان های ساخته شده با این روش یک یا دو طبقه هستند و تعداد معدودی ساختمان بیش از چهار طبقه نیز به این روش ساخته شده اند. تاریخچه. روش تیلت آپ در اوایل قرن بیستم ابداع شد و اوج شکوفایی آن، حوالی نیمه قرن بیستم، پس از جنگ جهانی دوم بود، که نیاز شدیدی به اجرای سریع ساختمان وجود داشت. ایده اصلی ساخت دیوار به صورت افقی بر روی زمین و بلند کردن آن به حالت قائم به عنوان عضوی از ساختمان ایده تازه ای نیست. اسناد موجود حاکی از آن است که این روش در رم باستان و خاورمیانه مورد استفاده قرار می گرفته است. ساکنان ایالات متحده آمریکا د
ر ابتدای قرن نوزدهم میلادی با ساخت دیوارهای چوبی بر روی زمین و برپا کردن آن ها به حالت قائم، خانه ها و انبارهای خود را می ساخته اند. در اوایل قرن بیستم میلادی، این روش برای دیوارهای بتن مسلح پیش ساخته مورد استفاده قرار می گرفت. کلنل رابرت آیکن (Colonel Robert Aiken)، به عنوان اولین سازنده این سیستم، تعداد زیادی از سازه ها را به این روش در بین سال های ۱۹۰۵ تا ۱۹۱۰ در ایالت ایلینوی و اوهایو با استفاده از یک قالب به عرض ۲۳ متر و ارتفاع ۲/۸ متر ساخت. کلیسای یادبود زیون (صهیون) در ایلینوی نیز که در سال ۱۹۱۰ به این شیوه ساخته شده است، تاکنون پابرجاست. با این حال، استفاده از روش فوق تا پایان جنگ جهانی دوم مقبولیت چندانی در بین مجریان ساختمان پیدا نکرد. از ۱۹۵۰ میلادی با ظهور جرثقیل های متحرک و بتن آماده، استفاده از این روش شتابی روزافزون به خود گرفت. هم اکنون سالیانه حدود ۷۰۰۰ ساختمان در بیش از ۱۰۰ کشور جهان به این روش ساخته می شوند. استفاده از روش تیلت آپ در ایالات متحده، استرالیا و نیوزیلند متداول بوده است. این شیوه اجرا، در سال های اخیر در انگلستان و ایرلند نیز رایج شده است. انواع سیستم های سازه ای تیلت آپ. به طو