مقاله کامل در مورد الگوریتم ها (پایگاه داده ها)

لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه: 27
فهرست مطالب:

چکیده :

مقدمه : مدل پردازش تراکنش:

3-تحلیل مساله کنترل همروندی :

4-مکانیزمهای کنترل همروندی بر پایه قفل دو مرحله‌ای :

5-پیاده سازی پایه قفل دو مرحله‌ای :

6-قفل دو مرحله‌ای با نسخه اولیه :

7-قفل دو مرحله‌ای با رای گیری

8- قفل دو مرحله‌ای متمرکز :

9-تشخیص و ترمیم بن بست :

   نتیجه گیری :.

   منابع و مآخذ :

چکیده :

در این گزارش ما به بررسی ویژگی های الگوریتمهای کنترل همروندی توزیعی که بر پایه مکانیزم قفل دو مرحله ای(2 Phase Locking)   ایجاد شده اند خواهیم پرداخت. محور اصلی این بررسی بر مبنای تجزیه مساله کنترل همروندی به دو حالت read-wirte و write-write می‌باشد. در این مقال، تعدادی از تکنیکهای همزمان سازی برای حل هر یک از قسمتهای مساله بیان شده و سپس این تکنیکها برای حل کلی مساله با یکدیگر ترکیب می‌شوند.

در این گزارش بر روی درستی و ساختار الگوریتمها متمرکز خواهیم شد. در این راستا برای ساختار پایگاه داده توزیعی یک سطحی از انتزاع را در نظر می‌گیریم تا مساله تا حد ممکن ساده سازی شود.

مقدمه :

کنترل همروندی فرآیندی است که طی آن بین دسترسی های همزمان به یک پایگاه داده در یک سیستم مدیریت پایگاه داده چند کاربره هماهنگی بوجود می‌آید. کنترل همروندی به کاربران اجازه می‌دهد تا در یک حالت چند برنامگی با سیستم تعامل داشته باشند در حالیکه رفتار سیستم از دیدگاه کاربر به نحو خواهد بود که کاربر تصور می‌کند در یک محیط تک برنامه در حال فعالیت است. سخت ترین حالت در این سیستم مقابله با بروز آوری های آزار دهنده ای است که یک کاربر هنگام استخراج داده توسط کاربر دیگر انجام می‌دهد. به دو دلیل ذیل کنترل همروندی در پایگاه داده های توزیعی از اهمیت بالایی برخوردار است: کاربراان ممکن است به داده هایی که در کامپیوترهای مختلف در سیستم قرار دارند دسترسی پیدا کنند.یک مکانیزم کنترل همروندی در یک کامپیوتر از وضعیت دسترسی در سایر کامپیوترها اطلاعی ندارد.

مساله کنترل همروندی در چندین سال قبل کاملا مورد بررسی قرار گفته است و در خصوص پایگاه‌داده‌های متمرکز کاملا شناخته شده است. در خصوص این مسال در پایگاه داده  توزیعی با توجه به اینکه مساله در حوزه مساله توزیعی قرار می‌گیرد بصورت مداوم راهکارهای بهبود مختلف عرضه می‌شود. یک تئوری ریاضی وسیع برای تحلیل این مساله ارائه شده و یک راهکار قفل دو مرحله ای به عنوان راه حل استاندارد در این خصوص ارائه شده است. بیش از 20 الگوریتم کنترل همروندی توزیعی ارائه شده است که بسیاری از آنها پیاده سازی شده و در حال استفاده می‌باشند.این الگوریتمها معمولا پیچیده هستند و اثبات درستی آنها بسیار سخت می‌باشد. یکی از دلایل اینکه این پیچیدگی وجود دارد این است که آنها در اصطلاحات مختلف بیان می‌شوند و بیان های مختلفی برای آنها وجود دارد. یکی از دلایل اینکه این پیچدگی وجود دارد این است که مساله از زیر قسمتهای مختلف تشکیل شده است و برای هر یک از این زیر قسمتها یک زیر الگوریتم ارائه می‌شود. بهترین راه برای فائق آمدن بر این پیچدگی این است که زیر مساله ها و الگوریتمهای ارائه شده برای هر یک را در ی.ک سطح از انتزاع نگاه داریم.

با بررسی الگوریتمهای مختلف می‌توان به این حقیقت رسید که این الگوریتمها همگی ترکیبی از زیر الگوریتمهای محدودی هستند. در حقیقت این زیر الگوریتمها نسخه‌های متفاوتی از دو تکنیک اصلی در کنترل همروندی توزیعی به نامهای قفل دو مرحله ای و ترتیب برچسب زمانی می‌باشند.

همانطور که گفته شد، هدف کنترل همروندی مقابله با تزاحمهایی است که در اثر استفاده چند کاربر از یک سری داده واحد برای کاربران بوجود می‌آید است. حال ما با ارائه دو مثال در خصوص این مسائل بحث خواهیم نمود. این دو مثال از محک معروف TPC_A مقتبس شده اند. در این مثالها، یک سیستم اطلاعات را از پایگاه داده ها استخراج کرده و محاسبات لازم را انجام داده و در نهایت اطلاعات را در پایگاه داده ذخیره می‌نماید.

حالت اول را می‌توان بروزآوری از دست رفته نامید. حالتی را تصور کنید که دو مشتری از دو سیستم مجزا بخواهند از یک حساب مالی برداشت نمایند. در این حالت فرض کنید در غیاب سیستم کنترل همروندی، هر دو با هم اقدام به خواندن اطلاعات و درج اطلاعات جدید در سیستم میکنند. در این حالت در غیاب سیستم کنترل همروندی تنها آخرین درج در سیستم ثبت می‌شود. این حالت در شکل 1 نشان داده شده‌ است.

ساختمان داده ها و الگوریتم ها - جعفر تنها، ناصر آیت - مهندسی کامپیوتر

کتاب ساختمان داده ها و الگوریتم ها

تالیف مهندس جعفر تنها و مهندس ناصر آیت

منبع درس ساختمان داده ها رشته مهندسی کامپیوتر دانشگاه پیام نور

شامل 351 صفحه کتاب در قالب فایل pdf

مقاله کامل در مورد الگوریتم های ژنتیک

لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه: 44

کار برد های GA

برخی از مهم تر ین کار بردهای GA در علوم مختلف عبارتند از:

زمینه

کاربرد

کنترل:

خطوط انتقال گاز – پرتاب موشک – سیستم های تعادلی – رهگیری و ...

طراحی :

طراحی هواپیما – طراحی مدارات VLSI – شبکه های ارتباطی و ...

مدیریت و برنامه ریزی :

برنامه ریزی تولید – زمان بندی – تخصیص منابع و ...

روباتیک:

مسیر حرکت روبات ...

یادگیری ماشین :

طراحی شبکه های عصبی – الگوریتم های طبقه بندی و ...

پردازش سیگنال:

طراحی فیلتر و ...

سایر موارد:

هنر و موسیقی – حل مسئله فروشنده دوره گرد – مسیر یابی در شبکه ها و ...

طراحی آنتن

سیستم های ارتباط ماهواره ای از آنتنها برای دریافت سیگنال های ارسال شده از ماهواره استفاده می کنند . هر آنتن دارای یک Main  Beam  و تعدادی Sidelobe است .قسمت Main  beam که در جهت ماهواره قرار می گیرد دارای بهره (gain)  بالایی است تا بتواند سیگنال های ضعیف را تقویت کند . اما Sidelobe ها دارای بهر ه های پایینی هستند . بر خلاف Main  beamدر جهت های مختلفی قرار می گیرند . شکل زیر یک آنتن را با Sidelobe و Main  beam آن نشان می دهد .

مشکل این جا است که امکان ورود سیگنال ها ی ناخواسته قوی به داخل Sidelobe ها و یا ورود سیگنال های اصلی ضعیف به داخل Main  beam وجود دارد . فرض کنیم که  Main  beam یک آنتن ماهواره ای در راستا و جهت ماهواره قرار گرفته باشد .  سیگنال ها ی ماهواره بسیار ضعیف هستند زیرا از فاصله بسیار دور و با قدرت کمی ارسال می شوند اگر یک تلفن بی سیم نیز با همان فرکانس ماهواره در نزدیکی آن کار کند ممکن است سیگنال ها ی تلفن  وارد Side lobe آنتن شده و باعث تداخل با سیگنال های اصلی گردد . بنا بر این مهندسان افزایش بهره Main  beam و کاهش بهره Side lobe هستند .

یک نوع از آنتن ها (Antenna   array) است . ویژگی این آنتن ها توانایی آنها را در کاهش بهرة  Side lobeها است . در حقیقت این نوع آنتن یک گروه از آنتن های تکی هستند که سیگنال های آنها را با هم جمع کرده و یک خروجی را تولید می کند .

سیگنال های دریافتی در هر آنتن دارای یک دامنه و فاز است که یک تابعی از فرکانس، موقعیت آنتن و زاویه ارسال سیگنال ها است .

خروجی این آنتن یک تابعی از سیگنال های در یافتی در هر آنتن است . بنا بر این با توجه به مقدار دامنه های سیگنال برای آنتن ها ممکن است باعث کاهش یا حذف Side lobe شود. در این مثال نشان می دهیم که چگونه می توان با استفاده از GAبه طراحی شبکه آنتن با Side lobe کم پرداخت .

مدل این آرایه خطی در راستای محور X و به صورت زیر است :

فرمول ریاضی در این خصوص برای حالتی که Main  beamبه صورت 90 درجه باشد برابر است با :

AF (  ) =  ei(n-1)                                                                                    (8-1)

که در این معادله :

N :تعداد آنتن ها

an: دامنه وزن دهی شده برای am =an+ 1-m که m = 1,2 ,… , N/2

: طول موج

d: فاصله بین آنتن ها

   : زوایه موج میدان الکترو مغناطیس

    =Kdu = Kdcos 

K= 2

هدف در این مسئله پیدا کردن an به گونه ای است که حداقل سطحSide lobe در الگوی آنتن وجود داشته باشد .

یک راه برای مسئله تولید Side lobeهایی برابر-   و پایین پیک Main  beam است به عبارت دیگر هیچگونهSide lobe ای وجود نداشته باشد .

روش حل این مسئله را شبکه دو جمله ای و وزن های دامنه سیگنال را ضرایب دو جمله ای می گویند ، بنا بر این یک آرایه 5 عضوی با وزن هایی که به عنوان ضرایب چند جمله ای در نظر گرفته شده است ، با پنج ضریب در نظر می گیریم .

ضرایب یک معادله چند جمله ای ، از مرتبه (N-1)یا وزن های دو جمله ای یک آرایه N عنصری همان ضرایب چند جمله ایN-1 (Z+1)   مفروض برای N ردیف مثلث پاسکال هستند .                        1                     

                                                        1     1 

                                                    1      2       1

                                                1       3     3       1

                                            1        4      6       4     1

                                             .

                                             .

                                             .    

در اولین تلاش اقدام به حذف Side lobe های یک آرایه 42 تایی با d=0.5 می کنیم .

هر دو روش الگوریتم ژنتیک پیوسته و باینری در پیدا کردن یک محدود کننده دامنه نوسان که حداکثر سطح Side lobeآن کمتر از 4db- و پایین پیک ، Main  beam باشد ناکار آمد هستند و این موضوع ناامید کننده است . مشکل احتمالا" به خاطر تابع هزینه است . تابع هزینه ما برابر با ماکزیمم سطح Side lobeمعادله (8-1) با پارامتر anاست . پیاده کردن این فرمول مشکل و همراه با جواب های نا خواسته ای خواهد بود که منجر به منحرف شدن GA می گردد .

 اما تابع هزینه دیگری وجود دارد که عملکرد بهتری دارد .

این روش همان تبدیل  zبرای معادله 8-1 است . بنا بر این با جایگذاری مقدار            

در معادله فوق خواهیم داشت :

AF

تابع هزینه حداکثر سطح Side lobe معادله فوق است که  به عنوان پارامتر آن در نظر گرفته می شود . شکل 50 همگرایی GAپیوسته را با تعداد 21 متغیر و تعداد 8 کروموزوم در Mating  pool  و  نشان می دهد .

و برای این روش GAباینری نیز جواب به صورت شکل 51 در می آید :

 هر الگوریتم پس از 10 بار تکرار و با تولید مقادیر به صورت تصادفی اجرا می شود . شکل زیر نتیجه میانگین هزینه را پس از 75 نسل برای این دو الگوریتم نشان می دهد :

همان طور که در شکل مشخص است ، روش باینری از این روش پیوسته جلو افتاده است. اما چرا ؟ شاید یک دلیل آن اندازه فضای جستجو باشد.

مسئله فروشنده دوره گرد TSP  

این مسئله یکی از مسائل مشهور در بهینه سازی و در بسیاری از رشته های مهندسی است که در طی چندین سال یک راه حل جامعی با استفاده از روش های کلاسیک بهینه سازی برای حل آن وجود نداشته است . هدف در این مسئله پیدا کردن کوتاه ترین مسیر برای فروشنده دوره گرد است که باید از N شهر بگذرد . این نوع مسئله در بسیاری از کاربرد های مهندسی مثل لوله کشی خطوط گاز ، طراحی آنتن ها، نحوه قرار گیری ترانزیستورها در مدارات VLSI و یا مرتب کردن اشیاء برای یک پیکره بندی خاص کاربرد دارد . اویلر در سال 1759 یک فرمی از این مسئله را ارائه کرد که در سال 1948 توسط شرکت Rand معرفی شد . مقدار تابع هزینه به فرم ساده برای این مسئله با توجه به مسافتی که فروشنده طی می کند با:

فرض موقعیت (  Xn ,yn  ) و N و ...وn=1 برابر است با :

که در این فرمول (  Xn ,yn ) مختصات و موقعیت n امین شهر است .

برای مثال ، فرض کنیم نقطه ابتدا و انتها برابر با :

 باشد از آنجایی که مسیر های محتمل بهینه بسیار زیادی با افزایش تعداد شهر ها به وجود می آید ، امکان حل این مسئله با استفاده از روش های بهینه سازی کلاسیک وجود ندارد . حتی در مقایسه با شبکه های عصبی الگوریتم ژنتیک نشان داده اند که در حل این مسئله بهتر عمل می کنند ! برای عملگر ادغام در حل این مسئله از روش جایگشتی (Permutation ) استفاده شده است و عملگر جهش ( موتاسیون ) به صورت تصادفی یک رشته را انتخاب کرده و بر روی آن عمل می کند .

برای مثال تعداد شهر ها را برابر با N =13 در نظر می گیریم که تعداد ترکیب های نقاطی که باید چک شود برابر است با :                            13!/2 = 3.1135* 109

برای شروع فرض می کنیم شهرها به صورت مستطیلی شکل و مطابق شکل زیر قرار گرفته باشند .

تعداد 200 کروموزوم و نرخ جهشی برابر با 04/0 پس از 35 نسل به صورت شکل می گردد :

حال فرم پیچیده تری را در نظر می گیریم . فرض کنیم 25 شهر به صورت تصادفی در یک مستطیلی با ابعاد 1*1 قرار گرفته اند . در این حالت برای 50 کروموزوم و با نرخ موتاسیون 04/0 پس از 130 نسل مقدار مینیمم به دست می آید . شکل زیر نحوه همگرایی الگوریتم را نشان می دهد :

و شکل نیز جواب بهینه ( بهترین مسیر) را نشان می دهد :  

یک نتیجه مهم : جمعیت های کوچک با نرخ موتاسیون بالا برابر حل مسائل جایگشتی

( Permutation )مناسب نیست .

رمز گشایی یک پیام سری :

در این مثال ، از روش GA پیوسته برای شکستن یک رمز استفاده می کنیم . یک پیام رمز شامل یکسری حروف جا به جا شده است که به صورت تصادفی و یا بر اساس یک متد خاص قرار گرفته اند . برای مثال :فرض کنیم تمام حروف dرا با حرف cو فضاهای خالی را با  qنشان دهیم . اگر پیام از همه حروف الفبا به علاوه فضای خالی استفاده کند . تعداد !27 ( فاکتوریل ) کد ممکن وجود دارد که فقط یکی از آنها درست است و اگر پیام از s سمبل استفاده کند تعداد !s - !27 کد ممکن وجود خواهد داشت .

بنابراین یک کروموزوم شامل 27 ژن با مقادیر واحدی از 1 تا 27 متناظر با حروف الفبا در نظر گرفته می شود . مثلا" 1 برای فضای خالی (space) 2 برای a و ...

مقدار تابع هزینه (Cost   function)مطابق فرمول زیر از تفاضل حدس (guess) از پیام (message) و جمع این مقادیر به دست می آید .

اگر مقدار Costصفر باشد ، یعنی پیام کشف شده است .

برای مثال فرض کنیم بخواهیم ببینیم GA برای رمز گشایی پیام :

"bonny and amy are our children"                                          

چگونه عمل می کند .

این پیام در مجموعه شامل 30 سمبل است .

 GAدر این مسئله با فرض جمعیت کروموزوم در mating  pool  برابر با 40 و نرخ جهشی برابر با 20/0پس از 68 نسل مطابق شکل زیر رمز به دست می آورد :

این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید

پروژه رمزنگاری تصویر توسط سیگنال های آشوب

پروژه رمزنگاری تصویر توسط سیگنال های آشوب پژوهش کامل در حوزه کامپیوتر و IT میباشد و در 4 فصل تنظیم شده است. شما میتوانید فهرست مطالب پروژه را در ادامه مشاهده نمایید.

پروژه بصورت فایل قابل ویرایش ورد(WORD) در 62 صفحه برای رشته کامپیوتر و IT در پایین همین صفحه قابل دانلود میباشد. شایسته یادآوری است که پروژه از ابتدا تا پایان ویرایش وتنظیم , سکشن بندی (section) ، نوشتن پاورقی (Footnote) و فهرست گذاری اتوماتیک کامل شده وآماده تحویل یا کپی برداری از مطالب مفید آن است.

چکیده

در این پروژه، یک روش رمزنگاری تصویر با استفاده از سیستم آشوب لجستیک ارائه شده است. این روش نه تنها بسیار ساده است بلکه از امنیت بالایی نیز برخوردار است که این امر ناشی از ویژگی های سیستم های آشوب و تناسب آن با داده های تصویری با حجم زیاد اطلاعات است. از دیگر مزایای این الگوریتم امکان بکارگیری آن در تصاویر خاکستری و رنگی است. مقدار بیشترین نسبت تفاوت بین تصویر رمزشده و تصویر اولیه نزدیک به عدد 11 می باشد. این عدد نشان می دهد که تصویر رمزشده به اندازه ی کافی با تصویر اولیه متفاوت است. علاوه بر این میانگین مجذور خطا بین تصویری که به درستی رمز شده با تصویر اولیه صفر است و پس از رمزگشایی با کلیدهای صحیح تصویری کاملا مساوی با تصویر اولیه حاصل می شود.

واژه های کلیدی:رمزنگاری،تصویر،سیگنل های آشوب،الگوریتم،پروتکل

فهرست مطالب

فصل اول  مقدمه

1-1 برخی اصطلاحات در رمزنگاری... 3

1-2 سرویس رمزنگاری... 3

1-2-1 محرمانگی یا امنیت محتوا3

1-2-2 سلامت محتوا:4

1-2-3 احراز هویت یا اصالت محتوا:4

1-2-4 عدم انکار:4

1-3 پنهان نگاری... 4

1-3-1 فشرده سازی jpeg. 5

1-3-2 الگوریتم پنهان نگاری jpeg-jsteg. 6

1-4 تفاوت پنهان نگاری و رمزنگاری... 7

1-5 موارد کاربرد رمزنگاری... 7

1-6 رمزنگاری و انواع ان.. 7

1-6-1 رمزنگاری متقارن.. 7

1-6-2 رمزنگاری نامتقارن.. 7

1-7 پروتکل های انتقال در رمزنگاری... 10

1-7-1 پروتکل‌ها10

1-8 پروتکل های انتقال در رمزنگاری... 11

1-8-1 SSL.. 11

1-8-2 TLS. 11

1-8-3 S/MIME.. 12

1-8-4 SSH.. 12

1-9 نتیجه گیری... 13

فصل دوم  اشنایی با توابع اشوب و معرفی سیستم

2-1 مقدمه.. 15

2-2 تعریف اشوب... 15

2-3 سایفرهای رمزنگاری تصویر. 19

2-4 سیستم های رمزنگاری اشوبگون تصویر. 21

2-4-1 سیستم لورنز. 21

2-4-2 نگاشت لجستیک.... 24

2-5 نتیجه گیری... 27

فصل سوم  تاثیر مدل های رنگ بر نحوه ی رمزنگاری در تصویر

3-1 مقدمه.. 29

3-2 مدل رنگ RGB.. 29

3-3 مدل رنگ CMY.. 31

3-4 مدل رنگ YIQ.. 32

3-5 مدل رنگ HIS. 32

3-6 نتیجه گیری... 36

فصل چهارم  تعریف پروژه

4-1 مقدمه.. 38

4-2 هیستوگرام.. 38

4-3 تسهیم هیستوگرام.. 40

4-4 هیستوگرام تصاویر رنگی... 42

4-5 معرفی ابزارهای توسعه.. 44

4-6 محیط برنامه ی پیاده سازی شده. 44

4-7 نتیجه گیری... 50

نتیجه گیری و پیشنهادات... 51

منابع.. 52

فهرست شکل ها

شکل 1-1 ماتریس کوانتیزاسیون استاندارد. 6

شکل 1-2 نمونه یک بلاک 8×8 بعد از کوانتیزاسیون.. 6

شکل2-1 تصویر جاذب سیستم در فضای فاز(x-y). 22

شکل2-2 تصویر جاذب سیستم درفضای فاز(x-z). 22

شکل 2-3 تصویر جاذب سیستم در فضای فاز(y-z). 22

شکل2-4 تصویر جاذب سیستم در فضای فاز(x-y-z). 23

شکل2-5 پاسخ زمانی متغیرهای حالت سیستم آشوبناک لورنز. 23

شکل 2-6 مسیر فضای حالت (الف: یک سیستم تصادفی (ب: یک سیستم اشوبناک.... 24

شکل2- 7 رفتار اشوبناک نگاشت لجستیک.... 25

شکل 2- 8 مسیر فضای حالت نگاشت لجستیک.... 25

جدول 2- 1 ماهیت رفتار سیستم به ازای مقادیر مختلف r26

شکل 2- 9 نگاشت لجستیک با توجه به مقادیر مختلف.... 26

شکل 3-1 مکعب رنگی RGB.. 30

شکل 3-2 مکعب رنگی 24 بیتی... 30

شکل 3-3 روابط ادراکی بین مدل های رنگ RGB و HSI. 34

شکل 3-4 مدل HSI مبتنی بر مثلث ها و دایره های رنگی را نشان می دهد.35

شکل 3-5 مدل رنگ HSI مبتنی بر صفحات مثلثی و دایره ای. مثلث ها و دایره ها بر محور عمودی شدت، عمود هستند 35

شکل 4-1 تصویر به صورت grayscale. 39

شکل 4-2 هیستوگرام تصویر1.. 39

شکل 4-3 هیستوگرام تصویر1.. 40

شکل4-4 تصویر با کنتراست پایین... 41

شکل 4-5 هیستوگرام تصویر4.. 41

شکل4-6 تسهیم هیستوگرام شکل 4.. 42

شکل4-7 هیستوگرام شکل 6.. 42

شکل 4-8تصویر رنگی نشان دهنده سه مولفه R، G و B.. 43

شکل4-9 هیستوگرام مربوط به مولفه ی R.. 43

شکل4-10 هیستوگرام مربوط به مولفه ی G.. 43

شکل4-11 هیستوگرام مربوط به مولفه ی B.. 44

شکل4-12 تصویر اصلی و هیستوگرام آن.. 45

شکل4-13 تصویر رمز شده وهیستوگرام آن.. 46

شکل 4-14 تصویر رمزگشایی شده و هیستوگرام ان.. 47

جدول 4-1 مدت زمان انجام عملیات رمزنگاری/رمزگشایی تصاویر وانتروپی انها47

شکل4-15 Cameraman. 48

شکل4-16 تصویر رمزشده ی Carea man. 48

شکل4-17 Lena. 48

شکل4-18 تصویر رمزشدهیLena. 49

شکل 4- 19 نمایی از محیط برنامهی نوشته شده در نرمافزار متلب.... 49