لینک پرداخت و دانلود در "پایین مطلب"
فرمت فایل: پاورپوینت
تعداد اسلاید: 7
با کلیک بر روی هر دکمه، مراحل الگوریتم غربال را به ترتیب اجرا کنید تا فقط اعداد اول باقی بمانند.
تهیه کننده: ابوبکر ملازهی دبیر ریاضی مدرسه راهنمایی حمیدرضا زارع خاش
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 27
چکیده : در این گزارش ما به بررسی ویژگی های الگوریتمهای کنترل همروندی توزیعی که بر پایه مکانیزم قفل دو مرحله ای(2 Phase Locking) ایجاد شده اند خواهیم پرداخت. محور اصلی این بررسی بر مبنای تجزیه مساله کنترل همروندی به دو حالت read-wirte و write-write میباشد. در این مقال، تعدادی از تکنیکهای همزمان سازی برای حل هر یک از قسمتهای مساله بیان شده و سپس این تکنیکها برای حل کلی مساله با یکدیگر ترکیب می‌شوند.
در این گزارش بر روی درستی و ساختار الگوریتمها متمرکز خواهیم شد. در این راستا برای ساختار پایگاه داده توزیعی یک سطحی از انتزاع را در نظر می‌گیریم تا مساله تا حد ممکن ساده سازی شود.
1. مقدمه : کنترل همروندی فرآیندی است که طی آن بین دسترسی های همزمان به یک پایگاه داده در یک سیستم مدیریت پایگاه داده چند کاربره هماهنگی بوجود می‌آید. کنترل همروندی به کاربران اجازه می‌دهد تا در یک حالت چند برنامگی با سیستم تعامل داشته باشند در حالیکه رفتار سیستم از دیدگاه کاربر به نحو خواهد بود که کاربر تصور می‌کند در یک محیط تک برنامه در حال فعالیت است. سخت ترین حالت در این سیستم مقابله با بروز آوری های آزار دهنده ای است که یک کاربر هنگام استخراج داده توسط کاربر دیگر انجام می‌دهد. به دو دلیل ذیل کنترل همروندی در پایگاه داده های توزیعی از اهمیت بالایی برخوردار است:
کاربراان ممکن است به داده هایی که در کامپیوترهای مختلف در سیستم قرار دارند دسترسی پیدا کنند.
یک مکانیزم کنترل همروندی در یک کامپیوتر از وضعیت دسترسی در سایر کامپیوترها اطلاعی ندارد.
مساله کنترل همروندی در چندین سال قبل کاملا مورد بررسی قرار گفته است و در خصوص پایگاه‌داده‌های متمرکز کاملا شناخته شده است. در خصوص این مسال در پایگاه داده توزیعی با توجه به اینکه مساله در حوزه مساله توزیعی قرار می‌گیرد بصورت مداوم راهکارهای بهبود مختلف عرضه میشود. یک تئوری ریاضی وسیع برای تحلیل این مساله ارائه شده و یک راهکار قفل دو مرحله ای به عنوان راه حل استاندارد در این خصوص ارائه شده است. بیش از 20 الگوریتم کنترل همروندی توزیعی ارائه شده است که بسیاری از آنها پیاده سازی شده و در حال استفاده می‌باشند.این الگوریتمها معمولا پیچیده هستند و اثبات درستی آنها بسیار سخت میباشد. یکی از دلایل اینکه این پیچیدگی وجود دارد این است که آنها در اصطلاحات مختلف بیان می‌شوند و بیان های مختلفی برای آنها وجود دارد. یکی از دلایل اینکه این پیچدگی وجود دارد این است که مساله از زیر قسمتهای مختلف تشکیل شده است و برای هر یک از این زیر قسمتها یک زیر الگوریتم ارائه میشود. بهترین راه برای فائق آمدن بر این پیچدگی این است که زیر مساله ها و الگوریتمهای ارائه شده برای هر یک را در ی.ک سطح از انتزاع نگاه داریم.
با بررسی الگوریتمهای مختلف می‌توان به این حقیقت رسید که این الگوریتمها همگی ترکیبی از زیر الگوریتمهای محدودی هستند. در حقیقت این زیر الگوریتمها نسخه‌های متفاوتی از دو تکنیک اصلی در کنترل همروندی توزیعی به نامهای قفل دو مرحله ای و ترتیب برچسب زمانی می‌باشند.
همانطور که گفته شد، هدف کنترل همروندی مقابله با تزاحمهایی است که در اثر استفاده چند کاربر از یک سری داده واحد برای کاربران بوجود می‌آید است. حال ما با ارائه دو مثال در خصوص این مسائل بحث خواهیم نمود. این دو مثال از محک معروف TPC_A مقتبس شده اند. در این مثالها، یک سیستم اطلاعات را از پایگاه داده ها استخراج کرده و محاسبات لازم را انجام داده و در نهایت اطلاعات را در پایگاه داده ذخیره می‌نماید.
حالت اول را می‌توان بروزآوری از دست رفته نامید. حالتی را تصور کنید که دو مشتری از دو سیستم مجزا بخواهند از یک حساب مالی برداشت نمایند. در این حالت فرض کنید در غیاب سیستم کنترل همروندی، هر دو با هم اقدام به خواندن اطلاعات و درج اطلاعات جدید در سیستم میکنند. در این حالت در غیاب سیستم کنترل همروندی تنها آخرین درج در سیستم ثبت میشود. این حالت در شکل 1 نشان داده شده است.
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 13
مقدمه :
الگوریتم مرتب‌سازی، در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از داده‌ها را به ترتیبی مشخص می‌چیند.
پر استفاده‌ترین ترتیب‌ها، ترتیب‌های عددی و لغت‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریم‌هایی که به لیست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.
از ابتدای علم کامپیوتر مسائل مرتب‌سازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده‌است. برای مثال مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد).
مبحث مرتب‌سازی در کلاس‌های معرفی علم کامپیوتر بسیار پر کاربرد است، مبحثی که در آن وجود الگوریتمهای فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتمهای مختلف کمک می‌کند؛ مانند تحلیل الگوریتم، داده‌ساختارها، الگوریتمهای تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.
در علم کامپیوتر معمولاً الگوریتمهای مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:
پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده میکنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتمهای مرتب‌سازی «در جا[1]» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتمها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
پایداری[2] : الگوریتمهای مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ میکنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نامهای الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.
روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.
الگوریتمهای مرتب سازی
[ویرایش] مرتب سازی حبابی
(به انگلیسی: Bubble Sort)
فرض کنید n داده داریم که می‌خواهیم به صورت صعودی مرتب شوند. عنصر اول رو با دومی مقایسه ، و در صورتی که اولی بزرگتر باشد جاهاشون رو عوض می‌کنیم. همین کار رو با عناصر دوم و سوم انجام می‌دهید و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تموم شد بزرگترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگه از اول این کار رو انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام مرحله اول جای خودش رو پیدا کرده). باز هم این کار رو تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند. مثلا:
۰ - ۰) ۵ ۶ ۴ ۲
۱ - ۱) ۵ ۶ ۴ ۲
۱ - ۲) ۵ ۴ ۶ ۲
۱ - ۳) ۵ ۴ ۲ ۶
۲ - ۱) ۴ ۵ ۲ ۶
۲ - ۲) ۴ ۲ ۵ ۶
۳ - ۱) ۲ ۴ ۵ ۶
مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:
۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴
۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴
۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴
۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷
فرمت فایل: word (قابل ویرایش) تعداد صفحات : 11 صفحه
الگوریتم بانکدار
برگرفته ازWikipedia دایرهامعارف مجانی.
این صفحه باعث اجتناب از بن بست در ارتباط است. برای گرد کردن به نزدیک ترین حالت، به بخش گردکردن بانکدار مراجعه کنید.
الگوریتم بانکدار ، الگوریتم اجتناب از بن بست و مقدار منبع می باشد که توسط Edsger Dijkstra ارائه شده است. این الگوریتم توسط شبیه سازی حداکثر مقدار ممکن از پیش تعیین شده منابع، ایمنی منابع را مورد آزمایش قرار می دهد و سپس قبل از تصمیم در مورد اینکه آیا این مقدار اختصاص یافته مجاز به ارائه است یا نه ف یک وضعیت ایمنی را به منظور آزمایش شرایط بن بست موجود بری کلیه فعالیتهای معلق ، ایجاد می نماید.
انتخاب نام برای الگوریتم:
این الگوریتم در قرایند طراحی برای سیستم عامل THE ارائه شده بود که البته در EWD108 به طور مفصل به زبان آلمانی توضیح داده شده است. این نام از مقایسه آن با شیوه ای است که بانکداران برای محدودیتهای بازپرداختی استفاده می کنند.
فرمت فایل : power point (لینک دانلود پایین صفحه) تعداد اسلایدها 27 اسلاید
بخشی از اسلایدها:
مرتب سازی:
کاربرد های دیگر پردازش همزمان (Co-sequential processing) کدامند؟
الگوریتم ادغام چندتایی (K-way Merge) چگونه است؟
روش مرتب سازی Selection Tree چیست؟
روش مرتب سازی Heap Sort چگونه است؟
روش Overlapping در Heap Sort چگونه است؟
مرتب سازی فایلهای بزرگ چه مشکلاتی دارد؟
روش مرتب سازی Merge-Sort چیست؟
کاربرد های دیگر پردازش همزمان (Co-sequential processing) کدامند؟
الگوریتم ادغام چندتایی (K-way Merge) چگونه است؟
روش مرتب سازی Selection Tree چیست؟
روش مرتب سازی Heap Sort چگونه است؟
روش Overlapping در Heap Sort چگونه است؟
مرتب سازی فایلهای بزرگ چه مشکلاتی دارد؟
روش مرتب سازی Merge-Sort چیست؟
الگوریتم Remove در Heap Sort چگونه است؟
کوچکترین کلید که در گره Root میباشد خارج میشود.
بزرگترین کلید (آخرین گره) به گره Root منتقل میگردد.
کلید آن با کوچکترین کلید فرزند مقایسه می شود و اگر بیشتر بود جای آن دو تعویض میشود.
در صورت لزوم عمل 3 تا آخر Heap تکرار میگردد.
روش مرتب سازی Merge-Sort چیست؟
چرا از Merge برای مرتب سازی فایلهای بزرگ استفاده میشود؟
مرتب سازی فایلهای بزرگ چه مشکلاتی دارد؟
مثال:
فایلی با مشخصات زیر در نظر می گیریم:
تعداد رکوردها: 8000000
طول هر رکورد: 100 بایت
طول کلید: 10 بایت
فرض کنیم که حافظه قابل استفاده برای sort محدود به 10 مگا بایت باشد