دانلود مقاله در مورد حل مساله بار 1 0 چند بعدي توسط سيستم‌هاي P به همراه ورودي و غشاء فعال 24 ص

لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل :  word (..doc) ( قابل ويرايش و آماده پرينت )
تعداد صفحه : 28 صفحه

 قسمتی از متن word (..doc) : 
 

‏1
‏حل مساله بار 1-0 چند بعدي توسط سيستم‏‌‏هاي P‏ به همراه ورودي و غشاء فعال:
‏خلاصه:
‏سيستم‏‌‏هاي غشايي از نظر زيستي مدل‏‌‏هاي تئوري محاسبه همسو و توزيع شده را فعال مي‏‌‏كند. در اين مقاله الگوريتم غشايي را نشان مي‏‌‏دهيم تا به كمك آن مساله بار 1-0 چند بعدي را در زماني خطي توسط سيستم‏‌‏هاي شناسنده P‏ به همراه ورودي غشاهاي فعال كه از دو قسمت استفاده مي‏‌‏كند، حل كند. اين الگوريتم را مي‏‌‏توان اصلاح كرد و از آن براي حل مساله برنامه‏‌‏نويسي عدد صحيح 1-0 عمومي استفاده كرد.
‏مقدمه:
‏سيستم‏‌‏هاي P‏،‏ طبقه‏‌‏اي از ابزار محاسله همسوي توزيع شده يك نوع بيوشيمي ‏هستند كه در [4] معرفي شد و مي‏‌‏توان آن را به عنوان معماري‏ محاسبه كلي دانست كه انواع مختلف اشياء در آن قسمت توسط عملكردهاي مختلف پردازش مي‏‌‏شوند. از اين ديدگاه مطرح مي‏‌‏شود كه پردازش‏‌‏هاي‏ خاصي كه در ساختار پيچيده موجودات زنده صورت مي‏‌‏گيرد، به صورت محاسباتي درنظر گرفته مي‏‌‏شوند.
‏از زماني كه Gh, Paun‏ ‏آن را مطرح كرد، دانشمندان كامپيوتر و بيولوژيست‏‌‏ها اين زمينه را با نقطه نظرهاي مختلف خود غني‏‌‏سازي كرده‏‌‏اند. براي انگيزه و جزئيات توضيحات مربوط به مدل‏‌‏هاي متفاوت سيستم P‏ لطفاً به [6/4] توجه كنيد. تقسيم‏‌‏بندي غشايي (الهام شده از تقسيمات سلولي گفته شده در ‏بيولوژي)، تنها راهي است كه براي بدست آوردن فضاي كاري —- در زمان خطي بيشتر و بر اساس حل مسائل مشكل (عموماً مسائل تكميل شده VP‏) در زمان چند جمله‏‌‏اي (اغلب به صورت خطي) بررسي‏ شده است. جزئيات را مي‏‌‏توان در [4.6.8] ببينيد.
‏3
‏اخيراً مسائل كامل PSPACE‏ به اين روش مطرح شدند. در گفتگويي غيررسمي، ‏در سيستم‏‌‏هاي P‏ به همراه غشاء فعال مي‏‌‏توانيم از 6 نوع قانون استفاده كنيم:
‏قوانين بازگشت چندگانه؛
‏قوانين مربوط به حل معرفي اشياء در غشاءها؛
‏قوانين مربوط به ارسال اشياء به بيرون از غشاء؛
‏قوانين مربطو به حل غشاء؛
‏قوانين مربوط به تقسيم غشاء اوليه؛
‏قوانين مربوط به تقسيم غشاء ثانويه.
‏در [10] Perez-Jimenez‏، مساله قابل راضي كننده‏‌‏اي را در زمان خطي با توجه به تعداد متغيرها و شروط فرمول‏‌‏گزاره‏‌‏اي توسط سيستم تشخيص دهنده P‏ به همراه ورودي و به همراه غشاء فعال 2 قسمتي حل مي‏‌‏كند. مساله قابل راضي شدن hard NP‏ نيست، چون الگوريتم‏‌‏هاي تقريبي چند جمله‏‌‏اي وجود دارد ‏كه آن را حل مي‏‌‏كند و اين نمونه‏‌‏اي براي مساله بار 1-0 چند جمله‏‌‏اي به حساب نمي‏‌‏آيد. در اين مقاله به حل مساله بار 1-0 چند بعدي توسط سيستم P‏ توجه كرديم.
‏مساله اصلي تكميل NP‏ مي‏‌‏باشد و همچنين مساله بار 1-0 چندبعدي به درجه مساله تكميل NP‏ بستگي دارد.‏ بنابراين اين مساله در زمان چندجمله‏‌‏اي توسط سيستم‏‌‏هاي P‏ با ورودي و با غشاء فعال كه از تقسيم 2 استفاده مي‏‌‏كند، حل خواهد شد. مي‏‌‏توانيم اين نوع محلول را با كمك كاهش مساله بار 1-0 چندبعدي براي مساله ‏راضي شدن بدست آوريم تا آن سيستم P‏ را كه به حل مساله راضي شدن در زمان خطي مي‏‌‏پردازيم، بكار بريم. همچنان اين مساله قابل بحث است كه چگونه مي‏‌‏توان مساله NP‏ را به مساله تكميل شده NP‏ ديگر بوسيله سيستم P‏ ساده كرد.
‏در اين مقاله مستقيماً الگوريتم غشايي را براي حل مساله بار 1-0 چندبعدي در زمان خطي توسط سيستم تشخيص دهنده P‏ به همراه ورودي به همراه غشاء فعال كه از تقسيم 2 استفاده مي‏‌‏كند، ارائه مي‏‌‏دهيم.در اينجا به طرحي از يك محدوده سيستم
‏3
P‏ توجه مي‏‌‏كنيم كه مساله بار 1-0 چندبعدي را حل مي‏‌‏كند (نه به شكل بررس‏ي‏ رسمي‏ الگورينتم غشايي)‏‌‏. همانطور كه در بخش 4 گفته شد، استفاده از اين الگوريتم اصلاح شده براي حل مساله برنامه‏‌‏نويسي عدد صحيح 1-0 كلي، كار آساني است.
‏سيستم‏‌‏هاي P‏ در الگوريتم در [5] تقريباً به طور يكسان به شكلي ساخته مي‏‌‏شوند كه براي هر نمونه از مساله قابل راضي شدن، يك سيستم P‏ شكل مي‏‌‏گيرد. در الگوريتم ما مربوط به مساله 0-1 چندبعدي، سيستم‏‌‏هاي P‏ به طور يكسان شكل مي‏‌‏گيرند. براي همه نمونه‏‌‏هايي كه يك اندازه هستند، ‏يك سيستم P‏ طراحي مي‏‌‏شود.
‏الگوريتم مربوط به مساله قابل راضي شدن در [5] از سيستم P‏ با قوانين نوع (a‏)، (f‏)-(c‏) استفاده مي‏‌‏كند و الگوريتم براي مساله راضي شدن در ‏‍‏]6] از سيستم‏‌‏هاي P‏ با قوانين نوع (c‏)-(a‏) و (e‏) استفاده مي‏‌‏كند. ‏در اينجا براي حل مساله ‏بار 1-0 چندبعدي از سيستم‏‌‏هاي P‏ محدوتر استفاده مي‏‌‏كنيم، يعني سيستم P‏ به همراه قوانين نوع‏ (a‏)، ‏(c‏) و (e‏).
‏مساله كلاسيك بار مورد خاصي از مساله بار 1-0 چندبعدي با يك بعد مي‏‌‏باشد. تقريباٌ مي‏‌‏توان الگوريتم غشايي را براي حل مساله بار كلاسيك [7]درنظر بگيريم. الگوريتم جديد ما نسبت به الگوريتم در [7] مراحل محاسبه كمتري دارد، بويژه در الگوريتم در [7]. 2n+1‏ مرحله براي مطرح كردن همه assignment‏ متغيرها استفاده مي‏‌‏شود، حال آنكه در الگوريتم جديد ما، n+1‏ مرحله براي توليد كردن همه assignment‏ متغيرها استفاده مي‏‌‏شود. در اينجا n‏ تعداد متغيرهاست. در اين مفهوم، الگوريتم ما، اصلاح الگوريتم [7] مي‏‌‏باشد.
‏اين مقاله به صورت زير طبقه‏‌‏بندي شده است:
‏در بخش 2‏،‏ مفهوم سيستم P‏ سازمان دهنده معرفي مي‏‌‏شود كه مدل محاسبه‏‌‏اي براي حل مساله بار 1-0 چندبعدي بوده و آن را در محاسبه با غشاءها ‏درجه پيچيدگي چندجمله‏‌‏اي مي‏‌‏نامند.
‏5
‏در بخش 3، براي حل مساله بار 1-0 چندبعدي به كمك سيستم‏‌‏هاي P‏ سازمان دهنده با غشاءهاي فعال 2 قسمتي، الگوريتم غشايي ارائه مي‏‌‏دهد.
‏در بخش 4، بحث ارائه شده است.
‏2. سيستم P‏:
‏با توجه به [5] با معرفي سيستم P‏ با غشاءهاي فعال شروع مي‏‌‏كنيم كه در اين قسمت جزئيات بيشتري وجود دارد.
‏ساختار يك غشاء به صورت نمودار Venn‏ مطرح شد و با كمك رشته‏‌‏اي از پرانتزهاي انتخابي دقيق (با يك جفت پرانتز خارجي) معرفي مي‏‌‏شود. اين جفت پرانتزهاي خارجي با غشاء خارجي كه ‏«‏موپست‏»‏ ناميده ميشود، تطبيق دارد. هر غشايي بدون داشتن غشايي دروني، غشاء اوليه ناميده مي‏‌‏شود. به عنوان مثال، ساختار درون همه غشاءها شماره‏‌‏گذاري شده است.در اينجا ما از عدد 1 تا 8 استفاده كرده‏‌‏ايم. عدد غشاءها، درجه ساختار غشاء را نشان مي‏‌‏دهد، در حالي كه‏ بلندترين درخت مربوط به روش معمول با ساختار، عمق آن مي‏‌‏باشد. در نمونه بالا ساختار‏ غشايي با درجه 8 و عمق 4 داريم.
‏با توجه به چيزي كه به دنبال دارد، غشاء مي‏‌‏توان + يا ‏–‏ علامتگذاري كرد (و‏ آن را به عنوان ‏«‏تغيير الكتريكي‏»‏ ‏مي‏‌‏نامند) يا با صفر (كه آن را ‏«‏تغيير خنثي‏»‏ مي‏‌‏نامند). در اين مثال به ترتيب آن را به صورت ‏ ‏مي‏‌‏نويسند. غشاءهايي كه فضاي محدودي ‏ن‏دارند،‏‌‏ دقيقاً بوسيله غشاءها معرفي مي‏‌‏شون (فضاي يا جايگاه يك غشاء بوسيله غشاء و همه غشاءهايي كه بلافاصله درون آن قرار دارند، de limited‏ مي‏‌‏شود [البته اگر غشايي وجود داشته باشد]).
‏در اين مقاله اشياء را قرار مي‏‌‏دهيم كه توسط سمبل‏‌‏هاي يك الفبا نشان داده شده است. ‏چندين كپي از اشياء يكسان در اين فضا قرار دارد. بنابراين با چندين مجموعه اشياء سروكار داريم. مجموعه‏‌‏اي كه در بالاي حدف V‏ قرار دارد، ‏توسط رشته‏‌‏اي در بالاي V‏ نشان داده شده‏‌‏اند: تعداد رخدادهاي ‏يك سمبل ‏ در رشته‏‌‏اي ‏ (V‏ مجموعه‏‌‏اي از همه رشته‏‌‏ها بر V‏ مي‏‌‏باشد، رشته خالي به وسيله