PDA

View Full Version : برج هانوی به صورت موازی



maryamghani
جمعه 15 اردیبهشت 1385, 23:52 عصر
دوستان من میخام الگوریتم برج هانوی را با paskal به صورت موازی بنویسم یعنی با همروند

raha_hakhamanesh
چهارشنبه 27 اردیبهشت 1385, 11:54 صبح
با سلام
اگه بشه این الگوریتم رو بصورت موازی حل کرد خوب خیلی خوبه و ما هم همینو می خواهیم
میخواهیم ببینیم می شه یه راه حل مطرح کرد که موازی بنویسیم . (مرتبه زمانی خیلی مهمه)
اگر بگیم نمی شه که خیلی بده به هر حال فکر چند نفر بهتر از یک نفره . تلاشمون رو می کنیم
همراه ما باشید

اَرژنگ
چهارشنبه 27 اردیبهشت 1385, 12:23 عصر
با سلام
اگه بشه این الگوریتم رو بصورت موازی حل کرد خوب خیلی خوبه و ما هم همینو می خواهیم
میخواهیم ببینیم می شه یه راه حل مطرح کرد که موازی بنویسیم . (مرتبه زمانی خیلی مهمه)
اگر بگیم نمی شه که خیلی بده به هر حال فکر چند نفر بهتر از یک نفره . تلاشمون رو می کنیم
همراه ما باشید
۱- الگریتم یعنی طرزه کار، الگریتم حل کردن نداره، الگریتم جواب سواله
۲- سوال برجهایه هانوی، اینه که عوض کردن حلقه‌ها یکی یکی انجام بشه،
یعنی اینکه خود سوال موازی نیست.
۳- اصلاً منظور از پیدا کردن روش موازی به چیزی که باید یکی یکی انجام بشه معنی ندارد، سوال در این حالتش فقط به طریقه غیره موازی معنی داره.
۴-سوال را به نهوه‌ای که بتونه بیشتر از یک عملیات را بشه انجام داد بیان کنید بعدش میشه اینکه به اینکه به صورته موازی جواب داره و یا نه دنبالش گشت.

raha_hakhamanesh
چهارشنبه 27 اردیبهشت 1385, 12:41 عصر
سلام آرژنگ
ببینید صحبت شما صحیح اما اونچه در ذهن شما هست روش متداولی هست که تا به حال مطرح شده چرا علاقه مند به برپایی یک الگوریتم نو و تازه برای حل این مسئله نیستید .
ضمن اینکه نمی خواهیم همین حالا یک جواب برای این مسئله پیدا کنیم اگه اجازه بدین یه کم فکر کنیم . موافقید ؟

اَرژنگ
چهارشنبه 27 اردیبهشت 1385, 13:05 عصر
سلام آرژنگ
ببینید صحبت شما صحیح اما اونچه در ذهن شما هست روش متداولی هست که تا به حال مطرح شده چرا علاقه مند به برپایی یک الگوریتم نو و تازه برای حل این مسئله نیستید .
ضمن اینکه نمی خواهیم همین حالا یک جواب برای این مسئله پیدا کنیم اگه اجازه بدین یه کم فکر کنیم . موافقید ؟
سلام رها جان
راستش را بخواهید، من اینکه سوال را چطوره میشه قسمت بندی کرد را نمیبینم، قبل از اینکه بخواهیم دنباله جواب بگردیم اوّل باید سوال مشخص باشه، یکی از شرایط این مسعله اینه که قبل از هر حرکت جدید، حرکت قبلی تمام شده باشه، این شرط، سوال را تبدیل کرده به خطی بودن، اصlان ذاته سوال جواب خطی درخواست میکنه.
ولی یک سوال مثل جمع کردن ۱۰ تا عدد، اینکه قبل از هر جمع عملیاته قبلی تمام شده باشند مهم نیست، برایه همین میشه دنباله الگریتم موازی برایه این یکی سوال گشت.
من با جواب دادن به سوال مخالف نیستم، ولی سوالی را که شرایطش بیان نشده را نمیشه جواب داد، اگر هم فرض کنیم که الگریتمه موازیه برایه این کار وجود داره، هر قسمت از الگیتم به حرکته قبلیش احتیاج داره، یعنی اینکه تا تمامه حرکات قبلیش تمام نشده باشند نمیشه حرکت بعدی را حساب کرد.
قبل از اینکه دنبال الگریتم گشت اوّل باید حداقل به وجود داشتن و یا نداشتن الگریتم جواب داد، چونکه سوالاتی هستند که الگریتم ندارند مثال Halting Problem.

raha_hakhamanesh
پنج شنبه 28 اردیبهشت 1385, 12:29 عصر
با سلام
من با آقای کرمن نویسنده کتاب introduction to algorithm در ارتباط هستم و طی سوالی که از ایشان در این رابطه پرسیدم به من جواب دادن که چنین الگوریتمی رو یکبار شندیده اند که توسط دو کامپیوتر و به صورت موازی پیاده سازی شده و از مرتبه زمانی خوبی برخوردار بوده است.
خوب تا اینجا یک قدم
اما در مورد چگونه گی : اولین پیشنهادم اینه که بیاییم این الگوریتم رو از حالت بازگشتی خارج کنیم و بصورت غیر بازگشتی بنویسیم پس ببینیم چی می شه (-:
به امید موفقیت

mohandese_hiclass
پنج شنبه 28 اردیبهشت 1385, 12:50 عصر
رها خانم مسئله بر جهای هانوی ماهیت غیر موازی داره حالا شما بر چه اسنادی می گید موازی منم نمی دونم اینم که گفتید با دو تا کامپیوتر حل کردن باید دید چطوری حل کردن اگه یه رفرنس یا لینک معرفی کنید خوب میشه

raha_hakhamanesh
پنج شنبه 28 اردیبهشت 1385, 12:56 عصر
سلام
اولا" رها اسم پسره
در ثانی من به استناد صحبت آقای کرمن نویسنده کتاب مشهور و معروف introduction to algorithm و مدرس دانشگاه MIT امریکا این مطلب رو اطلاع رسانی کردم
حالا هم بحثی نداریم اگر دلتون خواست بسم الله اگر نه ما که یقه شما رو نمی گیریم بابا به خدا قصدمون اینه که کمی اطلاعات مون رو اضافه کنیم هر کی می تونه بسم الله
موفق باشید

mohandese_hiclass
پنج شنبه 28 اردیبهشت 1385, 13:34 عصر
سلام
اولا" رها اسم پسره
در ثانی من به استناد صحبت آقای کرمن نویسنده کتاب مشهور و معروف introduction to algorithm و مدرس دانشگاه MIT امریکا این مطلب رو اطلاع رسانی کردم
حالا هم بحثی نداریم اگر دلتون خواست بسم الله اگر نه ما که یقه شما رو نمی گیریم بابا به خدا قصدمون اینه که کمی اطلاعات مون رو اضافه کنیم هر کی می تونه بسم الله
موفق باشید
من عذر می خوام آخه اگه ماهیت مسئله مشخص نشه واسه چی ادم انرژی شو هدر بده

raha_hakhamanesh
شنبه 30 اردیبهشت 1385, 20:06 عصر
با سلام
من در کتاب Algorithmics Theory and practice در صفحه 64یه چیزایی راجع به غیر بازگشتی کردن این الگوریتم دیدم شما هم به تحقیقات خودتون ادامه بدین اگه چیز به درد بخوری دیدین خبر بدین و یک چیز دیگه اینکه باید این الگوریتم رو ببریم تو مود هیبرید ولی چجوری هنوز نمی دونم
به امید موفقیت

abdollahashjaa
سه شنبه 02 خرداد 1385, 00:06 صبح
سلام
ببینید همون طور که دوستان گفتند مساله اصلی اینه که شما در اصل مساله نمیتونی تغییر ایجاد کنی یعنی شرایط مساله قابل تغییر نیست یعنی شما هر بار باید فقط و فقط یک حرکت انجام بدید و ضمنا شرط اصلی اینکه که مهره بزرگتر روی کمتر قرار نگیره دلیل حل شدن این مساله به صورت بازگشتی اینکه اگر بخواهیم به صورت معمولی اون رو بنویسیم باید از تعداد زیادی حلقه در برنامه استفاده کنیم و همچنین حد اکثر تعداد مهره ها به دلیل محدود بودن تعداد حلقه ها به یک عدد خاص از قبل مشخص محدود میشه در مورد برنامه هایی که با الگوریتم های پردازش موازی نوشته میشن باید گفت اونها برنامه هایی هستند که دستوراتی در برنامه استفاده شده که بیهوده یک قسمت برنامه باید منتظر پردازش قسمت دیگری باشه و در پردازش موازی هر دو به صورت موازی پردازش میشوند که البته این کار در واقعیت فقط با کامپیوتر های مجهز به دو پردازنده یا پردازنده های دو هسته ای به بالا عملی است که این کار دقیقا کاری است که در یک سوپر کامپیوتر اجرا میشه یعنی پردازش موازی برنامه بوسیله چندین پردازنده
موفق باشید

اَرژنگ
سه شنبه 02 خرداد 1385, 00:18 صبح
اما در مورد چگونه گی : اولین پیشنهادم اینه که بیاییم این الگوریتم رو از حالت بازگشتی خارج کنیم و بصورت غیر بازگشتی بنویسیم پس ببینیم چی می شه (-:
به امید موفقیت
من با این پیشنهادتان کاملاً موافم.

raha_hakhamanesh
پنج شنبه 04 خرداد 1385, 09:56 صبح
سلام
ببینید همون طور که دوستان گفتند مساله اصلی اینه که شما در اصل مساله نمیتونی تغییر ایجاد کنی یعنی شرایط مساله قابل تغییر نیست یعنی شما هر بار باید فقط و فقط یک حرکت اوفق باشید

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

آقای آرژنگ ممنون از اینکه در این باره وقت می زاری من مطمئن هستم بالاخره یه روزی یک لینک برای حل این مسئله پیدا می کنی . من وبقیه دوستان همچنان به این مسئله فکر می کنیم.

abdollahashjaa
پنج شنبه 11 خرداد 1385, 00:04 صبح
سلام
من متوجه منظورتون نشدم وقتی که مساله میگه شما هر بار و در هر دور فقط اجازه یک حرکت دارید چطور شما میخواهید اون رو به صورت موازی انجام بدید مثال میزنم
مثلا شما میخواهید یک خونه رو رنگ کنید میتونید اون رو با یک کارگر رنگ کنید یا با دو تا یا بیشتر هر چقدر تعداد کارگر ها بیشتر باشه کار سریعتر انجام میشه و در واقع اونها بصورت موازی با هم کار میکنند ولی فرض کنید میخواهید چند کتاب رو روی هم بچینید و هر بار حق دارید فقط یک کتاب رو روی دیگری بگذارید ( شرط مساله ) چطور وقتی هنوز کتاب دوم رو روی اولی نگذاشته اید میخواهید کتاب چهارم را روی سوم بگذارید اگر این کار رو کنید مجموعه کتاب سوم و چهارم میشود دو کتاب و شما طبق فرض مساله نمیتونید همزمان دو کتاب رو با هم جابجا کنید ( مثلا فرض میکنیم زورتون نمیرسه ) پس مجبورید باز هم کتاب چهارم رو از روی سوم بردارید بعد به ترتیب سوم را روی دوم و چهارم را روی سوم بگذارید یعنی عملا بدلیل شرایط مساله ( فرض ) که غیر قابل تغییر است شما قابلیت حل اون رو بصورت موازی ندارید ایشان هم که گفته اند دیده اند این کار انجام شده یک سند و مدرک یا استدلال عقلی بیاورند وگرنه که به خودی خود قابل اثبات نیست و وحی منزل نمیباشد
موفق باشید

raha_hakhamanesh
پنج شنبه 11 خرداد 1385, 08:49 صبح
با سلام

باشه آقا ! دست شما درد نکنه زحمت کشیدین ! ما هم استفاده کردیم ، زحمات جنابعالی بی حد است و ناتوان از سپاسگزاری . . .
ان شا الله در هفتمین کنفرانس علمی کامپیوتر حضرتعالی رو دعوت می کنم تا دفاع از این موضوع رو مشاهده کنید ولی تا اون موقع به خودتون بگین نمی شه و ما توانایی اینگونه کارها رو نداریم 4 تا مثل شما یه گروه علمی رو به عهده بگیرن چی می شه ؟ ! ! ! مثل اوضاع فعلی بعضی جوامع ...
و به همین دلیل جزئیات پاسخ مر بوطه رو توی تالار نمی زارم . ظاهرا حیفه هر چیزی رو در اختیار بعضی از برادران منتظر بزاری .
مراکز علمی ما سرشار از انسانهایی که می گویند نمی شود حتی اگر به چشمان خود ببینند که می شود - شاید هم آیه ای مبارک از جانب حق تعالی انزال گردیده باشد . والسلام

اَرژنگ
پنج شنبه 11 خرداد 1385, 16:16 عصر
با سلام

باشه آقا ! دست شما درد نکنه زحمت کشیدین ! ما هم استفاده کردیم ، زحمات جنابعالی بی حد است و ناتوان از سپاسگزاری . . .
ان شا الله در هفتمین کنفرانس علمی کامپیوتر حضرتعالی رو دعوت می کنم تا دفاع از این موضوع رو مشاهده کنید ولی تا اون موقع به خودتون بگین نمی شه و ما توانایی اینگونه کارها رو نداریم 4 تا مثل شما یه گروه علمی رو به عهده بگیرن چی می شه ؟ ! ! ! مثل اوضاع فعلی بعضی جوامع ...
و به همین دلیل جزئیات پاسخ مر بوطه رو توی تالار نمی زارم . ظاهرا حیفه هر چیزی رو در اختیار بعضی از برادران منتظر بزاری .
مراکز علمی ما سرشار از انسانهایی که می گویند نمی شود حتی اگر به چشمان خود ببینند که می شود - شاید هم آیه ای مبارک از جانب حق تعالی انزال گردیده باشد . والسلام

رها جان،
ما نمیگیم که این کار را نکن، من یکی هنوز نمیفهمم چطوری میشه این سوال را به طریقی که بشه موازی حل کرد طرح کرد.
در پست قبلیتان اشاره کردید که در یک کتاب حل این سوال را به طریقه غیره بازگشتی نوشته، یک لینک و یا اشاره به اینکه کجا موازی جواب دادن این سوال را میشه پیدا کرد هم بدید ما یک نگاه کنیم.
یک لینک به این کنفرانس هم بدید (?ISAAC 2006)،

abdollahashjaa
پنج شنبه 11 خرداد 1385, 17:12 عصر
سلام


باشه آقا ! دست شما درد نکنه زحمت کشیدین ! ما هم استفاده کردیم ، زحمات جنابعالی بی حد است و ناتوان از سپاسگزاری . . .
ان شا الله در هفتمین کنفرانس علمی کامپیوتر حضرتعالی رو دعوت می کنم تا دفاع از این موضوع رو مشاهده کنید ولی تا اون موقع به خودتون بگین نمی شه و ما توانایی اینگونه کارها رو نداریم 4 تا مثل شما یه گروه علمی رو به عهده بگیرن چی می شه ؟ ! ! ! مثل اوضاع فعلی بعضی جوامع ...
و به همین دلیل جزئیات پاسخ مر بوطه رو توی تالار نمی زارم . ظاهرا حیفه هر چیزی رو در اختیار بعضی از برادران منتظر بزاری .
مراکز علمی ما سرشار از انسانهایی که می گویند نمی شود حتی اگر به چشمان خود ببینند که می شود - شاید هم آیه ای مبارک از جانب حق تعالی انزال گردیده باشد . والسلام

استاد شما که تحمل حرف حساب رو ندارید بهتره دیگه تو این فروم مطلب ننویسی من هم که میبینی به سوالت جواب دادم همین الان دارم توی یک شرکت کار میکنم که یکی از پیشرفته ترین تکنولوژی های روز در زمیه صدا و تصویر رو در ایران تولید کرده ، به اندازه تارهای موی سر مبارک جنابعالی ایران رو دوست دارم معتقدم هر کاری که غربی ها انجام دادن رو ما بهترش رو میتونیم انجام بدیم ولی این که کی انجام بده و با چه هزینه ای اهمیت داره اگر کسی مثل شما که تحمل حرف حساب رو ندارید مدیر یک پروژه بشه وضعیت اون پروژه مشخصه احتمالا همه باید ساکت باشند تا شما نطق بفرمایید و هرچی شما بفرمایید باید وحی منزل محسوب بشه تحمل هیچ انتقادی هم ندارید تا وقتی که مملکت ما افراد مستبدی مثل شما رو داره که اعتقادات عامه مردم رو مسخره میکنن و تحمل انتقاد رو ندارن به هیچ جا نمی رسیم یک کم انصاف ، تحمل حرف حساب و حتی نا حساب ( اگر میخواهیم با هم گروهی کار کنیم نه تکی ) ، احترام به عقائد و تفکر دیگران ، سعی در متقاعد کردن فردی که اشتباه کرده با آرامش ، و ... تنها چیزی هست که توی مملکت ما نیاز داره درضمن من یک منتظر هست گرچه که بعضی وقتها یادم میره و سوتی هم میدم ولی از اعماق قلبم معتقد هستم و منتظر ایشون حالا اگر شما خوشت نمیاد عیسی به دین خود ، موسی به دین خود
موفق باشید

Omid Rekabsaz
پنج شنبه 11 خرداد 1385, 21:48 عصر
ببخشید ... آگر اجازه بدید من هم وارد ماجرا بشم ...
به نظر من حرف آقای آرژنگ منطقی است... این topic خیلی جالبیه... سعی کنیم بدور از حاشیه ادامه بدیم...
الان مسئله به نظر من طرح سواله... دوستان می گن پاسخ سوال خلاف فرضه... اگه می شه این قضیه رو روشن کنید؟!

salimipour
جمعه 09 شهریور 1386, 18:35 عصر
در کتاب آشنایی با سبک برنامه نویسی موازی اتشارات ناقوس برنامه های جالبی را با استفاده از multipascal نوشته است همچنین در کتاب طراحی الگوریتم ترجمه جعفر نژاد نیز یک فصل در مورد الگوریتم های موازی می باشد.

atilla snowman
دوشنبه 12 شهریور 1386, 01:26 صبح
پیشنهادم شاید ساده و ابلهانه باشه. ولی یه تازه کارم.
به نظر من میشه یه جورایی کلک زد و این مساله ی ذاتا خطی رو موازی کرد.
مثلا میشه مساله رو به این صورت تقسیم کرد که فرض کنیم یه ماشین یک چهارم مساله رو حل کرده. حالا به ماشین بعدی دستور می دیم که ادامه کار رو با این فرض انجام بده و همینطور به بقیه ی ماشینها ادامه ی کارو میدیم. با توجه به ذات مساله میتوان با یه سری محاسبات ساده حدس زد که وقتی یک چهارم از مساله حل بشه حلقه ها در چه وضعیتی هستند. جوابها که احتمالا یه سری از حرکت ها هستند وقتی پشت سر هم بیان میشه جواب مساله.
امیدوارم روشم عملی باشه.

amin750
چهارشنبه 10 آذر 1389, 10:56 صبح
سلام
دوستان اگلوریتم برج هانوی رو کسی با یک for ویه prtintf نوشته؟
ممنون میشم اگه کسی داره به ما هم بده.

amin750
یک شنبه 14 آذر 1389, 09:52 صبح
کسی نیست جواب ما رو بده؟
اصلا چنین چیزی امکان داره؟