دانلود مقاله در مورد حل مساله بار 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 ميباشد، رشته خالي به وسيله