حل مسائل طراحی الگوریتم

آيا کتاب حل مسائل طراحي الگوريتم نپوليتان هست؟

عنوان: الگوريتم شناسايي الگو در توالي هاي بيولوژيکي
هدف: پيدا کردن الگو يا موتيف ها در مجموعه اي از توالي هاي بيولوژيکي
ورودي : مجموعهُ Sمتشکل از m توالي که هر کدام به طول n باشد و دو عدد صحيح lو dبه گونه اي که d<l<n
ورودي: مجموعه S متشکل از m توالي که طول هر کدام n مي باشد و دو عدد صحيح l و n به گونه اي که n < l< باشد.
خروجي: يک الگوي M به گونه اي که هر توالي در مجموعه S شامل يک زير رشته ( به هم چسبيده-پيوسته) به طول l است که مي توان آن را پس از حداکثر d جايگزيني به M تبديل کرد.
چنين الگويي به صورت يک موتيف ( l,d ) از توالي هاي مجموعه S سناخته مي شود.
مثال ورودي مجموعه S شامل 4 توالي زير است.

1. TAGTACTAGGTCGGACTCGCGTCTTGCCGG
2. CAAGGTCCGGCTCTCATATTCAACGGTTGG
3. TACGCCCAAAGGCGGGGCTCGCATCCGGC
4. ACTCTGTGACGTGTCAGGTCGGGCTCTCAA

يک الگوM يا موتيف ( 15/2 ) براي توالي هاي بالا عبارت است از ( AGGTCGGGCTGGCAT )
الفباي تشکيل دهنده هر توالي { T,A,G,C } مي باشد.
ارزيابي با توجه به دقت و صحت جواب، سرعت بدست آوردن جواب ( پيچيدگي زماني ) و فضاي مورد استفاده در الگوريتم ( پيچيدگي فضايي ) انجام خواهد گرفت.

نميخواستم پروژه رو بنويسم تا کسي نگه تو گوگل سرچ کن ولي خداييش مثل اين که يا اين سخته يا من از طراحي الگوريتم هيچي بلد نيستم!
از ظاهرش اينجوري بر مياد که دايناميک بهترين راهش باشه...
اگه به کسي بر نميخوره يکي يه راهنمايي به من بکنه...اگه يکي مثل شما به يکي مثل من راهنمايي نکنه که چيزي تو گوگل پيدا نميشه Brick wall

مشکل از همون چند تاييه که عيبي نداره با هم فرق داشته باشن Brick wall

ميدونم از نظر خيلياتون اين خيلي آسونه ولي خب براي من سخته d'oh!

در ضمن من صورت سوال رو همونطور که بود کپي و پيست کردم...بعضي جاهاش عجيبه!

عجب آدمي هستي ها!!! Shame on you

خب توي گوگل سرچ ميکردي! Brick wall

.
.
.
.
.
.
.
.
.
.
Mr. Green

___
انصافا اگه بلد بودم جواب ميدادم. ولي حيف که جوابش رو بلد نيستم! Sad

انصافا اگه بلد بودم جواب ميدادم. ولي حيف که جوابش رو بلد نيستم!(اين جمله احسان نبود ها!!! اينو ميخوام موقع تحويل پروژه به تحويل گيرنده بگم!!!)
خداييش سخته که وقت داشته باشي...وقت بذاري ولي از وقت گذاشتنت هيچ سودي نبري...يعني هيچ کاري نتوني بکني d'oh!

دستت درد نکنه احسان که لااقل زيرش يه متلک بهم پروندي!!! دلگرم کننده ست! Wink

نکته جالبش اين بود ياد زنجيره مکمل دي ان اي افتادم ..آدنين,گوانين،تيمين،سيتوزين... يادش بخير! Confused

يه نکته ديگه اش اينکه خيلي شبيه مسائل لم تزريق نظريه زبانهاست!
منطق استدلالش شبيه اونه. d'oh!

مسئله اش خيلي آشناست!! يا سوال امتحانيم بوده يا تمرينم! در هر حال مطمئنم با همه ي اينا حلش نکردم! Mr. Green

pantea نوشته بود:

نکته جالبش اين بود ياد زنجيره مکمل دي ان اي افتادم ..آدنين,گوانين،تيمين،سيتوزين... يادش بخير! Confused

يه نکته ديگه اش اينکه خيلي شبيه مسائل لم تزريق نظريه زبانهاست!
منطق استدلالش شبيه اونه. d'oh!

مسئله اش خيلي آشناست!! يا سوال امتحانيم بوده يا تمرينم! در هر حال مطمئنم با همه ي اينا حلش نکردم! Mr. Green

اين اسم سختا رو ديگه قاطيش نکنين خواهشا d'oh!

ممنون که صورتش رو خوندين و در موردش فکر کردين...لطف کردين Applause

همين حالا به اين نتيجه رسيدم که از دايناميک يا حل نميشه يا خيلي خفن ميشه!!! شايد راه حلش Greedy (اميدوارم درست نوشته باشم) باشه Think

يعني قسمتهاي کوچيک مسئله رو با بهترين راه حل براي همون قسمت و بدون توجه به ساير قسمتها حل کنيم...
سايد بايد به قسمت هايي با سايز راديکال n تقسيم کنيم و به دنبال قسمت هاي مشابه هر دنباله با دنباله هاي ديگه بگرديم و نتايج رو يه جورايي يه کاري تو مايه هاي merg انجام بديم
يه تئوريه و در گام اول عملي به نظر ميرسه ولي در گام دوم پيچيده ميشه خدا به داد گام سوم برسه Brick wall

هنوز هم عاجزانه تقاضاي کمک دارم d'oh!

با سلام
لطفاً بگيد حل اين مسئله چه مشکلي رو حل مي کنه؟يعني کجا استفاده مي شه؟

نميخواستم پروژه رو بنويسم تا کسي نگه تو گوگل سرچ کن ولي خداييش مثل اين که يا اين سخته يا من از طراحي الگوريتم هيچي بلد نيستم!
از ظاهرش اينجوري بر مياد که دايناميک بهترين راهش باشه...
اگه به کسي بر نميخوره يکي يه راهنمايي به من بکنه...اگه يکي مثل شما به يکي مثل من راهنمايي نکنه که چيزي تو گوگل پيدا نميشه Brick wall

مشکل از همون چند تاييه که عيبي نداره با هم فرق داشته باشن Brick wall

ميدونم از نظر خيلياتون اين خيلي آسونه ولي خب براي من سخته d'oh!

در ضمن من صورت سوال رو همونطور که بود کپي و پيست کردم...بعضي جاهاش عجيبه![/quote]

------------------------------
اصلا هم سخت نيست بجز دايناميک هم راه حل خوب داره.