payamvha/North_RAG huggingface dataset:
مختلفی می‌توان پرسش ذکر شده را اجرا کرد که در اینجا به دو روش اشاره می‌کنیم: روشن است که خروجی هر دو روش یکسان است اما روش اول به مراتب منابع بیشتری برای اجرا نیاز دارد (نگهداری ۱۰۰٬۰۰۰ سطر حافظه بیشتری نسبت به ۲۰٬۰۰۰ سطر نیاز دارد) و زمان پردازش آن نیز بیشتر خواهد بود. این مثال لزوم انتخاب روش درست برای اجرای پرسش را تأیید می‌کند. به‌طور کلی، کاربران نمی‌توانند به شکل مستقیم به بهینه‌ساز پرسش دسترسی داشته باشند. البته بعضی از سیستم‌های مدیریت پایگاه داده اجازه راهنمایی بهینه‌ساز را توسط راهنماها می‌دهند.
راهنمایی بهینه‌ساز را توسط راهنماها می‌دهند. راهنما یک دستورالعمل اضافه نسبت به زبان SQL استاندارد است که به بهینه‌ساز در جهت بدست آوردن بهترین روش اجرای پرسش کمک می‌کند. از آنجایی که ساختار پایگاه‌های داده پیچیده‌است، به جز در پرسش‌های ساده نیاز است تا اطلاعات مورد نیاز برای پرسش از راه‌های مختلفی تأمین گردد، به عنوان نمونه از جداول مختلف، از داده ساختارهای مختلف، از داده‌ها با ترتیب‌های مختلف؛ و هر راه هم‌زمان اجرای خاص خود را دارد. همان گونه که در مثال بالا نشان داده شد برای یک پرسش واحد زمان پردازش
بالا نشان داده شد برای یک پرسش واحد زمان پردازش می‌تواند از کسری از ثانیه تا چندین ساعت متغیر باشد و این زمان بستگی به روش اجرای پرسش دارد. هدف بهینه‌سازی پرسش به عنوان یک فرایند خودکار پیدا کردن راهی است که بتوان پرسش را در حداقل زمان ممکن اجرا کرد. همان‌طور که ذکر شد بازه زمانی اجرای پرسش می‌تواند خیلی متغیر باشد و این موضوع لزوم بهینه‌سازی پرسش را برای رسیدن به بهینه‌ترین راه اجرا تأیید می‌کند. از آنجایی که پیدا کردن راه بهینه از میان تمام راه‌های ممکن خیلی پیچیده‌است و زمان صرف شده برای این موضوع خیلی
پیچیده‌است و زمان صرف شده برای این موضوع خیلی مهم است و همین زمان باعث می‌شود از لحاظ عملی بررسی تمام راه‌ها برای اجرای پرسش غیرممکن باشد؛ بنابراین در بهینه‌سازی پرسش تلاش می‌کنیم تا به شکل تقریبی نقشه‌های اجرایی را برای پرسش بدست آوریم که از لحاظ زمانی قابل قبول بوده و تفاوت زیادی با زمان بهینه نداشته باشد. تبدیل پرسش به جبر رابطه ای. همان‌طور که قبلاً گفته شد هر پرسش می‌تواند از راه‌های متفاوتی با هزینه‌های متفاوت اجرا شود. دو عبارت جبر رابطه ای را یکسان گوییم هرگاه خروجی‌های آن دو عبارت با یکدیگر برابر
گوییم هرگاه خروجی‌های آن دو عبارت با یکدیگر برابر باشد. در نظر داشته باشید در این تعریف ترتیب سطرهای خروجی مهم نیست. در این مقاله از نمادهای زیر استفاده می‌کنیم: برای بیان شرط‌ها از نمادهای formula_1استفاده می‌کنیم. برای بیان صفات رابطه از نمادهای formula_2استفاده می‌کنیم و برای بیان عبارت‌های جبر رابطه ای از نمادهای formula_3استفاده می‌کنیم. قوانین برابری جبر رابطه ای. قوانین برابری جبر رابطه ای بیان می‌کنند چگونه دو عبارت با هم برابر هستند و می‌توان آنها را به جای یکدیگر استفاده کرد. formula_5 formula_6
را به جای یکدیگر استفاده کرد. formula_5 formula_6 formula_8 این عبارت formula_9را می‌توان به شکل formula_10نوشت. formula_11 از این قوانین می‌توان برای بدست آوردن درخت پرسش استفاده کرد و نقشه‌های اجرا را بدست آورد. اجزای بهینه‌ساز. در سیستم‌های مدیریت پایگاه‌های داده ممکن است اجزای متفاوتی وجود داشته باشد، اما می‌توان به‌طور کلی گفت همه آن‌ها دارای اجزا زیر هستند (این اجزا به ترتیب مرحله اجرا ذکر شده‌اند). تبدیل کننده پرسش. در این مرحله تشخیص داده می‌شود آیا بازنویسی پرسش به شکلی که خروجی با پرسش اولیه
آیا بازنویسی پرسش به شکلی که خروجی با پرسش اولیه یکسان باشد مفید است یا خیر. مثال زیر می‌تواند این موضوع را روشن کند. پرسش اولیه به شکل زیر به پایگاه داده فرستاده می‌شود. هدف از این پرسش بدست آوردن اسم درس و نمرات دو دانشجو با شماره دانشجویی‌های ۱۲۳ یا ۲۳۴ است. select course.name , course.grade from course where course.stuID = '123' or course.stuID='234' این پرسش پس از گذر از تبدیل کننده پرسش به شکل زیر در خواهد آمد. select course.name , course.grade from course where course.stuID = '123' union select
course where course.stuID = '123' union select course.name , course.grade from course where course.stuID='234' با استفاده از دستور UNION، پرسش به شکل معادل خود تبدیل شده‌است. تخمین زننده. تخمین زننده از سه معیار برای انجام کار خود استفاده می‌کند. تولیدکننده نقشه پرسش. کم هزینه‌ترین نقشه اجرا برای یک بلاک از پرسش را انتخاب می‌کند. برای درک بهتر این موضوع در نظر بگیرید برای یک عملیات join می‌توان از سه روش متفاوتnested loop joint,sort merge یا hash join استفاده کرد. برای هر کدام از این روش‌ها زمان‌های زیر
کرد. برای هر کدام از این روش‌ها زمان‌های زیر تخمین زده شده‌است. Best Nested Loop join cost: 13.17 Sort Merge cost: 6.08 Hash join cost: 4.57 Best:: JoinMethod: Hash مشاهده می‌شود که کمترین زمان اجرا متعلق به روش hash join است، پس از این روش برای اجرای نقشه پرسش استفاده می‌شود. ملاحظات عمومی. همیشه یک معامله بین زمان صرف شده برای بدست آوردن بهترین نقشه اجرای پرسش و کیفیت نقشه انتخاب شده وجود دارد. بهینه‌ساز مستقلاً نمی‌تواند بهترین انتخاب را داشته باشد. سیستم‌های مدیریت پایگاه داده متفاوت راه‌های متفاوتی
مدیریت پایگاه داده متفاوت راه‌های متفاوتی برای ایجاد تعادل بین دو فاکتور ذکر شده دارند. بهینه‌سازهای هزینه محور میزان استفاده پرسش را از منابع سیستم ارزیابی می‌کنند و آن را به عنوان مبنایی برای انتخاب یک نقشه اجرا در نظر می‌گیرند. این مدل از بهینه‌سازها به هر نقشه ممکن برای اجرای پرسش یک هزینه تخمین می‌زنند و سپس کمترین آنها را انتخاب می‌کنند. هزینه‌هایی که برای تخمین زدن زمان اجرای یک پرسش در نظر گرفته می‌شوند عبارتند از تعداد عملیات‌های I/O مورد نیاز، میزان دستور مورد نیاز به زبان ماشین برای اجرای پرسش،
دستور مورد نیاز به زبان ماشین برای اجرای پرسش، میزان حافظه بافر مورد نیاز از دیسک، زمان مورد نیاز دیسک و عامل‌های دیگر که توسط فرهنگ داده مشخصی می‌شود. دو نوع بهینه‌سازی وجود دارد. بهینه‌ساز منطقی -که زنجیره ای از جبر رابطه ای برای اجرای پرسش تولید می‌کند-و بهینه‌سازی فیزیکی برای مشخص کردن مجری هر عملیات استفاده می‌شود. پیاده‌سازی. تعداد زیادی از بهینه‌سازهای پرسش، نقشه‌های پرسش را به شکل درختی نشان می‌دهند که از تعدادی گره تشکیل شده‌است. هر گره این درخت یک عملیات مورد نیاز برای اجرای نقشه پرسش را نشان
یک عملیات مورد نیاز برای اجرای نقشه پرسش را نشان می‌دهد. این گره‌ها به شکل یک درخت مرتب شده‌اند که برای به دست آوردن نتیجه نهایی باید گره‌های درخت را به ترتیب از پایین به بالا اجرا کنیم و نتیجه هر گره را به عنوان ورودی گره پدر در نظر بگیریم. تعداد بچه‌های هر گره می‌تواند صفر یا بیشتر باشد به عنوان مثال یک گره که حاوی دستور join است دو بچه دارد که شامل عملوندهای ورودی آن است ولی یک دستور sort صرفاً یک ورودی (ورودی که می‌خواهیم مرتب شود) دارد. برگ‌های درخت گره‌هایی هستند که نتایج را با پویش دیسک انجام
گره‌هایی هستند که نتایج را با پویش دیسک انجام می‌دهند. برای مثال این گره‌ها می‌توانند اینکار را با index scan یا sequential scan انجام دهند. یک نمونه :جبر رابطه‌ای عبارت formula_12 است. تخمین هزینه. یکی از دشوارترین مسائل در بهینه‌سازی پرسش، تخمین دقیق هزینه برای نقشه‌های پرسش است. بهینه‌سازها هزینه نقشه‌های پرسش را با استفاده از مدل‌های ریاضی که شدیداً به اندازه یا تعداد زوج‌ها (سطرها) که در یال‌های درخت اجرای پرسش قرار دارد وابسته است تخمین می‌زنند. تخمین اندازه بستگی به تخمین (درصد یا کسری از رکوردها در
اندازه بستگی به تخمین (درصد یا کسری از رکوردها در یک فایل که با رکوردهای یک فایل دیگر پیوند(join) می‌شود) در گزاره‌های پرسش دارد. سیستم‌های پایگاه‌های داده قدیمی تعداد منتخب‌ها را از طریق آمارهای جزئی توزیع مقادیر در هر ستون مثل نمودارهای histogram تخمین می‌زنند. این روش برای تخمین منتخب‌های یک گزاره خوب کار می‌کند. اگرچه تعداد زیادی از پرسش‌ها چندین شرط را تواماً با هم دارند به‌طور مثال: select student.ID ,student.name ,student.last_name from student where student.name= 'ali' and student.major = "cs"
student.name= 'ali' and student.major = "cs" بهینه‌سازی هزینه محور. یک بهینه‌ساز پرسش تنها به درخت پرسش وابسته نیست، بهینه‌ساز پرسش هزینه اجرای یک پرسش را با رویکردها و الگوریتم‌های مختلف تخمین زده و مقایسه می‌کند و در نهایت رویکردی را انتخاب می‌کند که کمترین هزینه را داشته باشد. برای اینکه این دیدگاه بتواند درست کار کند باید بتوان تخمین دقیقی از هزینه اجرای پرسش بدست آورد تا در نهایت رویکردهای مختلف اجرای پرسش عادلانه و واقع گرایانه مقایسه شوند. همچین باید این نکته را در نظر گرفت بهینه‌ساز باید تعداد
باید این نکته را در نظر گرفت بهینه‌ساز باید تعداد محدودی رویکرد اجرای پرسش را بررسی کند در واقع اگر قرار باشد تمام حالت‌های اجرا را در نظر بگیرد زمان زیادی از دست می‌رود. بنابر این دیدگاه بهینه‌سازی هزینه محور مناسب پرسش‌های کامپایل شده‌است. تصمیم‌گیری در فرایند بهینه‌سازی پرسش ساده و چالش‌های زیاده دارد. فرایند کلی بهینه‌سازی هزینه محور را می‌توان به شکل زیر خلاصه کرد: اجزای هزینه در بهینه‌سازی پرسش. هزینه انتقال (خواندن یا نوشتن) بلاک‌های اطلاعات بین دیسک حافظه ثانویه و بافرهای حافظه اصلی. این هزینه به
حافظه ثانویه و بافرهای حافظه اصلی. این هزینه به اسم هزینه ورودی و خروجی دیسک ((disk I/O (input/output) هم شناخته می‌شود. هزینه جستجوی یک فایل در دیسک به نوع دسترسی به آن فایل بستگی دارد به‌طور مثال آیا فایل مرتب شده‌است؟ در هم سازی صورت گرفته‌است؟ اندیس گذاری انجام شده‌است؟ و… عوامل مختلف دیگر. هزینه ذخیره‌سازی هر فایل میانی که با اجرای پرسش تولید شده‌است برروی دیسک را گویند. این هزینه شامل هزینه انجام عملیات روی رکوردهای حافظه اصلی در طول اجرای پرسش است. این هزینه شامل عملیاتی است که در داخل حافظه انجام
این هزینه شامل عملیاتی است که در داخل حافظه انجام می‌شود مثل:جستجو، مرتب‌سازی، ادغام چند رکورد برای یک عملیات join. این هزینه به اسم CPU cost(واحد پردازش مرکزی) هم شناخته می‌شود. این هزینه مربوط به تعداد بافر مورد نیاز از حافظه در طول اجرای پرسش می‌باشد. هزینه انتقال پرسش و نتایج آن از محل پایگاه داده به محل یا ترمینالی که پرسش از آنجا فرستاد شده‌است. در :پایگاه داده توزیع‌شده، این هزینه شامل هزینه انتقال جدول‌ها و نتایج آن بین کامپیوترهای مختلف در طول ارزیابی پرسش است.
خلیل‌بیگ خاصمحمدف () سردمدار و دیپلمات آذربایجانی بود. وی زمامداری وزارت‌های دادگستری و داخله (کشور) در جمهوری دمکراتیک آذربایجان را در سال ۱۹۱۸ بر عهده داشت. زندگی‌نامه. خلیل‌بیگ خاصمحمدف در سال ۱۸۷۳، در خانواده ای وکیل در شهر گنجه به دنیا آمد. وی دانش‌آموخته رشته حقوق از دانشگاه دولتی مسکو در سال ۱۸۹۵ بود. خلیل‌بیگ تأثیرات زیادی در رابطه با شکل‌گیری جهان‌بینی خود از «اسمائیل‌بیگ گاسپیرانلی» گرفت. شروع فعالیت سیاسی خلیل‌بیگ خاصمحمدف به دوران دانشجویی اش برمی گردد؛ زمانی که وی عضو «سازمان هم‌میهنان مسلمان
گردد؛ زمانی که وی عضو «سازمان هم‌میهنان مسلمان قفقاز» بود. او سپس به عنوان وکیل مدافع در دادگاههای منطقه ای کراسنودار و گنجه کار کرد. کارنامه سیاسی. خلیل‌بیگ خاصمحمدف در پاییز سال ۱۹۰۵، همراه با برادرش «علی اکبر» در تأسیس سازمان «دفاعی» حضور پیدا کردن؛ سازمانی سیاسی که در گنجه فعال بود. این گروه که شامل روشنفکرانی نظیر نصیب بیگ یوسف بیگلی، «اسماعیل زیادخانف» و احمدبیگ آقایف بود، با هدف مقابله با فعالیت‌های فدراسیون انقلابی ارمنی پایه‌گذاری شده بود. خاصمحمدف نماینده دوره اول و دوم دومای روسیه بود. در نوامبر
نماینده دوره اول و دوم دومای روسیه بود. در نوامبر ۱۹۱۱، وی به همراه ۵ نماینده آذربایجانی دیگر در سخنرانی کم سابقه ای در دومای روسیه، سیاست تبعیضآمیزی را که، آذربایجانیان و سایر مردمان مسلمان قفقاز را با تحمیل پرداخت مالیات از گذراندن خدمت سربازی در نیروهای مسلح این امپراتوری منع می‌کرد، به باد انتقاد شدید گرفت. او به عنوان عضو حزب مساوات، فعالانه در جنبش ملی آذربایجان برای تأسیس جمهوری خودمختار در داخل مرزهای امپراتوری روسیه مشارکت داشت. خلیل‌بیگ خاصمحمدف در تأسیس جمهوری دمکراتیک آذربایجان به سال ۱۹۱۸ نقش
تأسیس جمهوری دمکراتیک آذربایجان به سال ۱۹۱۸ نقش چشمگیری ایفا نمود. او نماینده شورای ملی و از امضاکنندگان اعلامیهٔ استقلال جمهوری دمکراتیک آذربایجان در ۲۸ ماه مه سال ۱۹۱۸ در شهر تفلیس بود. در دوره جمهوری دمکراتیک آذربایجان، خواصمحمدف به ترتیب سکانداری چند وزارت را در ۴ کابینه دولت از مجموع ۵ کابینه بر عهده داشت. او در ۲۸ ماه مه سال ۱۹۱۸، به عنوان وزیر دادگستری منصوب شده و تا ۱۷ ژوئن همان سال در این سمت باقی ماند. از ۲۶ دسامبر ۱۹۱۸ تا ۱۶ ژوئن ۱۹۱۹ سکان هدایت وزارت داخله در دست او بود. این سیاستمدار
هدایت وزارت داخله در دست او بود. این سیاستمدار آذربایجانی در ۲۴ دسامبر ۱۹۱۹ مجدداً به زمامداری وزارت دادگستری رسید، که تا ۱ آوریل ۱۹۲۰، یعنی پایان هیئت دولت پنجم عهده‌دار آن شد. وی در دوران ریاست خود بر چند وزارتخانه مختلف، همکاری قوی ای بین وزارت‌های دفاع، امنیت ملی و کشور نسبت به تهدیدهای خارجی علیه حاکمیت ملی و دولت‌داری ایجاد کرد. در اویل ماه آوریل سال ۱۹۲۹، خواصمحمدف به عنوان سفیر جمهوری دمکراتیک آذربایجان در ترکیه تعیین شد؛ ولی از آنجا که همزمان با ورود او به استانبول، دولت متبوعش به دست بلشویکها
ورود او به استانبول، دولت متبوعش به دست بلشویکها سقوط کرد، تا آخر عمرش در این کشور پنادنده شد و در سال ۱۹۴۵ درگذشت.
روش تنظیم برنده یا برنده تنظیم شده الگوریتمی است برای تقسیم formula_1 کالا بین دو گروه به منصفانه‌ترین شکل ممکن. این روش توسط (به انگلیسی: Steven Brams) و (به انگلیسی: Alan D. Taylor) طراحی شده‌است. این الگوریتم formula_1 کالا را به گونه ای بین دو گروه تقسیم می‌کند که: با گذشت بیش از نیم قرن از تولد نظریه بازی‌ها به عنوان یک رشته دانشگاهی، همچنان بسیاری از مذاکره کنندگان و واسطه‌های با تجربه بدون استفاده از نظریهٔ بازی‌ها و موضوعات مربوط به آن به کار خود ادامه می‌دهند. در دهه‌های گذشته امیدها افزایش
خود ادامه می‌دهند. در دهه‌های گذشته امیدها افزایش یافته‌است که روش‌های ریاضی برای تقسیم منصفانه بتواند این فاصله را کم کند. از این روش می‌توان برای حل و فصل اختلاف‌های بین‌المللی، فسخ مشارکت و همچنین در زمینه طلاق استفاده کرد. توصیف الگوریتم. هدف، تقسیم مجموعه ای از اشیا، اجناس، ابزار و هر چیز مورد اختلاف بین دو نفر به منصفانه‌ترین شکل ممکن است. حل یک مثال. فرض کنیم علی و رضا می‌خواهند مجموعه ای از دارایی‌ها را با استفاده از این روش بین خود تقسیم کنند. این دارایی‌ها شامل خانه، قایق، کلبه کوهستانی و
این دارایی‌ها شامل خانه، قایق، کلبه کوهستانی و آپارتمان ساحلی است. فرض کنیم هر کدام صد امتیاز را مطابق جدول زیر بین چهار مورد ذکر شده تقسیم کرده باشند: در مرحله اول هر یک از دارایی‌ها به کسی تعلق می‌گیرد که مقدار ارزش بیشتری برای آن تعیین کرده باشد. پس در مرحله اول داریم: همان‌طور که در شکل بالا می‌بینید، جمع امتیازها برابر نیست. چون این مقدار برای علی بیشتر از رضا است پس لازم است از دارایی فعلی علی کسر و به دارایی رضا اضافه کنیم. برای این که تصمیم بگیریم کدام شی را منتقل کنیم، نسبت امتیاز علی به امتیاز
کدام شی را منتقل کنیم، نسبت امتیاز علی به امتیاز رضا را برای «خانه» و «کلبه» که فعلاً در جمع دارایی‌های علی است، به دست می‌آوریم: این نسبت، میزان اهمیت شی برای افراد نسبت به یکدیگر را اندازه‌گیری می‌کند. همان‌طور که می‌بینید این عدد برای «خانه» به نسبت «کلبه» عدد کوچکتری است؛ به این معنا که «خانه» نسبت به «کلبه» برای علی ارزش کمتری دارد برای همین ابتدا خانه را از علی گرفته به رضا می‌دهیم: با این کار این بار جمع امتیاز رضا بیشتر از علی می‌شود پس باید «خانه» را به علی بازگردانیم و این بار کسری از «خانه» را
را به علی بازگردانیم و این بار کسری از «خانه» را از علی به رضا منتقل کنیم به طوریکه جمع امتیاز آنان پس از این انتقال برابر شود. چون مقدار امتیازها قرار است برابر شود، معادله زیر برقرار خواهد بود: formula_3 با انتقال formula_4 از سهم «خانه» به رضا، مجموع امتیاز هر دو طرف برابر formula_5 خواهد شد و کار تقسیم به پایان می‌رسد. با این روش هر دو به میزان برابری از رضایتمندی رسیده‌اند. چالش. در استفاده از این روش اگر یکی از طرف‌ها ارزش گذاری طرف مقابل را از قبل بداند و مطمئن باشد که طرف مقابل طبق همان ارزش گذاری
و مطمئن باشد که طرف مقابل طبق همان ارزش گذاری عمل می‌کند، می‌تواند تقلب کند و با استفاده از این اطلاعات ارزش گذاری خود را به گونه ایxvhpd ;vni تا سهم بیشتری را از آن خود کند. به عنوان نمونه مثال زیر را در نظر بگیرید: فرض کنید جدول ارزش گذاری نسبی زیر را داشته باشیم: طبق روش تنظیم برنده ، formula_6 ،formula_7 و formula_8 از formula_9 به نفر اول و formula_10 ،formula_11 و formula_12 از formula_9 هم به نفر دوم می‌رسد و مجموع امتیاز برای هر کدام برابر formula_14 خواهد بود. اگر نفر اول از ارزش گذاری نفر دوم با
خواهد بود. اگر نفر اول از ارزش گذاری نفر دوم با خبر باشد، می‌داند که formula_6 و formula_7 به او می‌رسد پس کافی است امتیاز آن دو را تنها به میزان خیلی کمی بیشتر از امتیاز نفر دوم ارزش گذاری کند و باقی امتیاز خود را به اشیا دیگری که تمایل به گرفتن آنها دارد، اضافه کند. برای مثال می‌تواند به formula_6 عدد formula_18 و به formula_7 عدد formula_20 را نسبت دهد. بدین شکل formula_21 امتیاز اضافه برای او باقی می‌ماند که می‌توانند آن را بین بقیه اشیا مورد علاقه اش توزیع کند. اگر به شی formula_9 سه امتیاز بیشتر، به
کند. اگر به شی formula_9 سه امتیاز بیشتر، به شی formula_10 دو امتیاز بیشتر و به formula_11 نه امتیاز بیشتر بدهد، آنگاه داریم: اگر روش تنظیم برنده را برای این مقادیر جدید اجرا کنیم formula_6 ،formula_7 و formula_27 از formula_9 به نفر اول و formula_10 ،formula_11 و formula_31 از formula_9 به نفر دوم می‌رسد و این بار مجموع امتیاز برای هر کدام برابر formula_33 خواهد بود که به نسبت قبل عدد کمتری است ولی نفر اول با اعمال این تغییرها درصد بیشتری از formula_9 را به نسبت قبل از آن خود کرده‌است و برای نفر اول این
به نسبت قبل از آن خود کرده‌است و برای نفر اول این نتیجه در حقیقت رضایتمندی و مطلوبیت بهتری دارد که ناشی از دانستن اطلاعات توزیع امتیازهای نفر مقابل بوده‌است. محدودیت‌ها. این روش تنها برای تقسیم بین دو نفر پاسخ گو خواهد بود و برای تعداد افراد بیشتر، نتیجه یک تقسیم عادلانه نخواهد بود. به مثالی از کتاب تقسیم عادلانهتوجه کنید: برای این که تقسیم به گونه ای باشد که میزان رضایتمندی سه طرف برابر باشد و نیز کارایی پارتو را داشته باشد باید formula_10 را به نفر سوم، formula_6 را به نفر دوم و formula_9 را به نفر اول
formula_6 را به نفر دوم و formula_9 را به نفر اول بدهیم؛ ولی با این کار نتیجه، حسادت برانگیز خواهد بود؛ زیرا شی formula_6 برای فرد سوم نسبت به نفر دوم ارزشمندتر است. برای این مسئله نمی‌توان با استفاده از این روش یک تقسیم عادلانه ارائه داد و باید از روش‌های جایگزین دیگری استفاده کرد.
در مبحث محاسبات، الگوریتمهای حافظه خارجی (الگوریتم‌های خارج از هسته) به الگوریتم‌هایی می‌گویند که به منظور پردازش داده‌هایی طراحی می‌شوند که به دلیل حجم بالا، در حافظه اصلی رایانه گنجانده نمی‌شوند. این الگوریتم‌ها باید به گونه‌ای طراحی شوند که در بهترین زمان بتوانند به داده‌های درون حافظه‌های کمکی مانند هارد درایودسترسی داشته باشند و آن‌ها را استخراج کنند. الگوریتم‌های حافظه خارجی، در مدل حافظه خارجی بررسی می‌شوند. مدل. مدل حافظه خارجی (مدل I/O یا مدل disk access) یک نوع مدل محاسبه ایده‌آل شده‌است که منظور
یک نوع مدل محاسبه ایده‌آل شده‌است که منظور آنالیز الگوریتم حافظه خارجی به کار می‌رود. این مدل یک ماشین انتزاعیمانند مدل ماشین RAM می‌باشد با این تفاوت که علاوه بر حافظه اصلی حافظه cache هم وجود دارد. زمان اجرای یک الگوریتم در مدل حافظه خارجی را تعداد خواندن و نوشتن‌هایی که بر روی حافظه انجام می‌شود تعیین می‌کند. این مدل همچنین بیان می‌کند که خواندن و نوشتن از حافظه cache بسیار سریع تر از حافظه اصلی است. مدل حافظه خارجی نخستین بار از سوی الوک آگاروال و جفری ویتر در سال ۱۹۸۸ معرفی شد. این مدل کمی مرتبط با
ویتر در سال ۱۹۸۸ معرفی شد. این مدل کمی مرتبط با مدل cache-oblivious می‌باشد ولی الگوریتم‌ها در مدل حافظه خارجی ممکن است هم، اندازه بلاک و هم، اندازه حافظه cache را بدانند به همین دلیل گاهی از این مدل تحت عنوان مدل cache-aware یاد می‌کنند. این مدل شامل یک پردازنده و حافظه داخلی می‌باشد و همچنین یک حافظه cache در این مدل وجود دارد که اندازه آن را M در نظر می‌گیریم. این cache به یک حافظه خارجی بدون محدودیت متصل است. هردو حافظهٔ داخلی و خارجی بهبلاک‌هایی با اندازه B تقسیم می‌شوند. یک عملیات ورودی/خروجی یا
اندازه B تقسیم می‌شوند. یک عملیات ورودی/خروجی یا انتقال حافظه در واقع انتقال یک بلاک شامل B عنصر پیوسته از حافظه خارجی به حافظه داخلی می‌باشد و زمان اجرای این الگوریتم با استفاده از تعداد این عملیات‌ها بدست می‌آید. الگوریتم. الگوریتم‌ها در مدل حافظه خارجی این مزیت را دارند که با بدست آوردن یک شیء از حافظهٔ خارجی می‌توان کل بلاک آن شیء را بدست آورد. پیدا کردن یک عنصر میان N عنصر در این مدل با استفاده از یک درخت بی امکان‌پذیر است؛ که در این درخت هر یک از عملیات پیدا کردن، درج کردن و حذف کردن در زمان
از عملیات پیدا کردن، درج کردن و حذف کردن در زمان formula_1 انجام می‌شود. مرتب‌سازی خارجی، یک نوع مرتب‌سازی است که روی حافظه خارجی صورت می‌گیرد. این مرتب‌سازی را می‌توان با استفاده از مرتب‌سازی تجمعی که مشابه مرتب‌سازی سریع است انجام داد. زمان این مرتب‌سازی برای مرتب کردن N عنصر formula_2 می‌باشد. کاربردها. این مدل برای تحلیل و بررسی داده‌هایی که به دلیل حجم بالا در حافظه داخلی جا نمی‌شوند بسیار مناسب است. برای مثال در سیستم‌های جغرافیایی، به خصوص سیستم‌های مدلسازی ارتفاعات که حجم داده‌ها از چندین گیگابایت
مدلسازی ارتفاعات که حجم داده‌ها از چندین گیگابایت و حتی ترابایت نیز بیشتر می‌شود از مدل حافظه خارجی استفاده می‌شود.
الگوریتم جابه‌جایی یای انحصاری، الگوریتمی است که با استفاده از عملگر بیتی یای انحصاری مقدار دو متغیر را بدون استفاده از متغیر دیگری یا تغییر نوع متغیرها با یکدیگر جابه‌جا می‌کند. الگوریتم. الگوریتم به شرح زیر است: X := X XOR Y Y := Y XOR X X := X XOR Y این الگوریتم معادل ۳ دستور در زبان ماشین است. همچنین چون یای انحصاری خاصیت جابه‌جایی دارد، دو عبارت X XOR Y و Y XOR X برابرند. این الگوریتم در حالتی که دو متغیر X و Y برابر باشند (منظور از برابری دو متغیر، یکی بودن آدرس آن‌هاست نه یکی بودن مقادیر آن‌ها)، به
بودن آدرس آن‌هاست نه یکی بودن مقادیر آن‌ها)، به درستی کار نمی‌کند زیرا پس از خط اول مقدار X برابر 0 شده و چون آدرس X و Y یکی است، مقدار Y هم برابر 0 می‌شود و دو متغیر مقادیر واقعی خود را از دست می‌دهند. اثبات درستی الگوریتم. با استفاده از ویژگی‌های یای انحصاری. ویژگی‌های یای انحصاری عبارتند از: فرض کنید ثباتهای R۱ و R۲ به ترتیب دارای مقادیر A و B باشند، الگوریتم را برای R۱ و R۲ مرحله به مرحله اجرا می‌کنیم: با استفاده از جبر خطی. یای انحصاری را می‌توان به عنوان جمع دودویی و ۲ بیت را به عنوان یک بردار در
عنوان جمع دودویی و ۲ بیت را به عنوان یک بردار در میدان ۲ در نظر گرفت. در این‌صورت الگوریتم را می‌توان با ضرب یک ماتریس ۲ formula_12۲ در میدان ۲ معادل کرد. برای سادگی فرض می‌کنیم X و Y یک بیت باشند. در این‌صورت مرحله اول الگوریتم معادل خواهدبود با: X := X XOR Y Y := Y که معادل ماتریسی آن formula_13است. داریم: formula_14 دنباله دستورات الگوریتم را می‌توان به صورت ضرب ماتریس‌های ۲ formula_12۲ نشان داد: formula_16 برای تعمیم به وقتی که X و Y برادارهای بیتی به طول n اند، یای انحصاری معادل ماتریس ۲n formula_12۲n
n اند، یای انحصاری معادل ماتریس ۲n formula_12۲n formula_18است. باید توجه کرد که این ماتریس بر روی متغیرها (که در حافظه آدرس دارند) اعمال نمی‌شوند بلکه بر روی مقادیر اعمال می‌شوند. نمونه کد. کد زیر، کد الگوریتم به زبان C است: void xorSwap (int *x, int *y) if (x != y) *x ^= *y; *y ^= *x; *x ^= *y; باید توجه‌کرد که کد ابتدا بررسی می‌کند که آیا آدرس دو متغیر یکی است یا خیر زیرا اگر یکی باشد، همان‌گونه که پیش از این گفته‌شد مقدار متغیر ۰ خواهدشد. همچنین می‌توان الگوریتم را به صورت یک ماکرو تعریف کرد: /* درصورتی
را به صورت یک ماکرو تعریف کرد: /* درصورتی که دو متغیر برابر باشند، به درستی کار نمی‌کند. */ /* ابتدا یکی نبودن آدرس‌ها را بررسی می‌کند، سپس دو متغیر را جابه‌جا می‌کند. */ دلایل استفاده از الگوریتم. در بیشتر موارد در عمل استفاده از یک ثبات دیگر برای جابه‌جایی بهینه‌تر است و در موارد محدودی جابه‌جایی با یای نحصاری ممکن است در عمل به کار بیاید مانند: دلایل عدم استفاده از الگوریتم. بیشتر کامپایلرهای جدید متغیرهای موقت را پس از استفاده، آزاد می‌کنند لذا از نظر حافظه و زمان الگوریتم جابه‌جایی سه طرفه با این
حافظه و زمان الگوریتم جابه‌جایی سه طرفه با این الگوریتم تفاوتی ندارد. ضمن آنکه این الگوریتم برای کسی که با روش آن آشنا نباشد نامفهوم است. در کامپوترهای جدید، الگوریتم جابه‌جایی یای انحصاری از الگوریتم جابه‌جایی سه طرفه کنتر است. از پردازنده‌های x۸۶ اینتل و ای‌ام‌دی به بعد، جابه‌جایی بین ثبات‌ها بدون تأخیر انجام می‌شود. حتی اگر ثباتی برای استفاده نباشد، دستور XCHG حداقل به اندازه سه عملیات یای انحصاری سریع خواهدبود. دلیل دیگر آن است که پردازنده‌ها حتی‌الامکان دستورات را موازی اجرا می‌کنند. در الگوریتم یای
دستورات را موازی اجرا می‌کنند. در الگوریتم یای انحصاری، ورودی‌های هر عملگر به خروجی مرحله قبل بستگی دارد لذا نمی‌توان مراحل آن را موازی اجرا کرد. تعمیم به دیگر عملگرها. در این الگوریتم، یای انحصاری می‌تواند با هر عملگری که ۴ خاصیت گفته‌شده را داشته‌باشد، جایگزین شود. با جایگزین کردن یای انحصاری با جمع و تفریق خواهیم‌داشت: void addSwap (unsigned int *x, unsigned int *y) if (x != y) *x = *x + *y; *y = *x - *y; *x = *x - *y; برخلاف یای انحصاری، در این نوع پردازنده یا زبان برنامه‌نویسی استفاده‌شده باید از
پردازنده یا زبان برنامه‌نویسی استفاده‌شده باید از هم‌نهشتی یا اعداد بزرگ استفاده کنند تا بتوان مطمئن شد که عملگرها سرریز ندارند؛ لذا کاربرد این از کاربرد یای انحصاری کمتر خواهدبود.
پمپ یونی نوعی پمپ خلاء است که در شرایط ایدئال به کمک آن می‌توان تا فشارهای formula_1میلی بار را ایجاد کرد. پمپ یونی به کمک یک ولتاژ نسبتاً بالا، در حدود ۳ تا ۷ کیلوولت، گازهای درون محفظه خلاء را یونیزه می‌کند، که اینکار باعث می‌شود یون‌ها شتاب پیدا کرده و توسط یک الکترود صلب جذب شوند. انواع. سه گونه عمده از پمپ‌های یونی وجود دارد: مدل استاندارد و متعارف آن یعنی پمپ دیودی، پمپ دیودی خاص (noble diode pump) و پمپ تریود (triode pump).
ضرب ماتریس یکی از اعمال پایه در بسیاری از الگوریتم‌های آنالیز عددی محسوب می‌شود به همین دلیل در راستای بهبود زمان آن تلاش‌های بسیاری انجام شده‌است. کاربردهای ضرب ماتریس در بسیاری از زمینه‌های مختلف همچون علم محاسبه، بازشناخت الگو ، پردازش تصویر ، کار با نرم افزارهای ۳ بعدی و حتی زمینه‌های به ظاهر بی‌ربط مانند شمردن تعداد گشت‌ها در یک گراف دیده می‌شود. الگوریتم‌های بسیاری برای این‌ کار روی سیستم‌های رایانش موازی طراحی شده‌ است که در آن چند هسته به صورت همزمان و موازی عملیات را انجام می‌دهند. اگر از تعریف ضرب