زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۸:۴۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تمرین Hypercube (لطفا کمک کنید.)

ارسال:
۰۶ آبان ۱۳۹۵, ۰۲:۴۸ ق.ظ
تمرین Hypercube (لطفا کمک کنید.)
با سلام
دوستان لطفا اگه کسی جواب این دوسوال رو بلده کمکم کنه
در یک D ، Hypercube بعدی چند مسیر بین دو دورترین نود وجود دارد؟
آیا تعداد مسیرها بین دو گره با تغییر دو گره عوض می شود؟ چرا (اثبات)؟؟؟؟؟؟
کمکم کنیدHuh
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۰۶ آبان ۱۳۹۵, ۰۳:۱۱ ق.ظ
RE: تمرین Hypercube (لطفا کمک کنید.)
(۰۶ آبان ۱۳۹۵ ۰۲:۴۸ ق.ظ)mavin1200 نوشته شده توسط:  با سلام
دوستان لطفا اگه کسی جواب این دوسوال رو بلده کمکم کنه
در یک D ، Hypercube بعدی چند مسیر بین دو دورترین نود وجود دارد؟
آیا تعداد مسیرها بین دو گره با تغییر دو گره عوض می شود؟ چرا (اثبات)؟؟؟؟؟؟
کمکم کنیدHuh

به نظر میرسه به عنوان یک مسأله‌ی open به شما سعی کردند قالب کنند چون تا الان فرمول خاصی برای این سؤال پیدا نشده. صرفاً برای n=5، تعداد مسیرهای محاسبه شده ۱۸۶۵۱۵۵۲۸۴۰ هست. برای n=6 جوابی پیدا نشده. مگر اینکه منظورتون "کوتاه‌ترین" مسیرهای ممکن بوده باشه که فکر کنم در اون صورت [tex]n![/tex] باشه ولی مطمئن نیستم، شکل یک مستطیل رو تجسم کردم (n=3).
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Pure Liveliness
ارسال:
۰۷ آبان ۱۳۹۵, ۰۶:۱۹ ب.ظ
RE: تمرین Hypercube (لطفا کمک کنید.)
(۰۶ آبان ۱۳۹۵ ۰۳:۱۱ ق.ظ)Behnam‌ نوشته شده توسط:  
(06 آبان ۱۳۹۵ ۰۲:۴۸ ق.ظ)mavin1200 نوشته شده توسط:  با سلام
دوستان لطفا اگه کسی جواب این دوسوال رو بلده کمکم کنه
در یک D ، Hypercube بعدی چند مسیر بین دو دورترین نود وجود دارد؟
آیا تعداد مسیرها بین دو گره با تغییر دو گره عوض می شود؟ چرا (اثبات)؟؟؟؟؟؟
کمکم کنیدHuh

به نظر میرسه به عنوان یک مسأله‌ی open به شما سعی کردند قالب کنند چون تا الان فرمول خاصی برای این سؤال پیدا نشده. صرفاً برای n=5، تعداد مسیرهای محاسبه شده ۱۸۶۵۱۵۵۲۸۴۰ هست. برای n=6 جوابی پیدا نشده. مگر اینکه منظورتون "کوتاه‌ترین" مسیرهای ممکن بوده باشه که فکر کنم در اون صورت [tex]n![/tex] باشه ولی مطمئن نیستم، شکل یک مستطیل رو تجسم کردم (n=3).

سلام
نمیدونم اینو تو درس پردازش موازی بعنوان تمرین دادن و اصرار داشتن قسمت دومش حتما إثبات بشه
لطفا اگه کسی بلده کمک کنه یا منبع بگید برم بگردم دنبال جواب
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۰۷ آبان ۱۳۹۵, ۰۶:۵۳ ب.ظ
RE: تمرین Hypercube (لطفا کمک کنید.)
(۰۷ آبان ۱۳۹۵ ۰۶:۱۹ ب.ظ)mavin1200 نوشته شده توسط:  سلام
نمیدونم اینو تو درس پردازش موازی بعنوان تمرین دادن و اصرار داشتن قسمت دومش حتما إثبات بشه
لطفا اگه کسی بلده کمک کنه یا منبع بگید برم بگردم دنبال جواب
ببینید من هم درس شبکه‌های میان ارتباطی رو پاس کردم که همه‌ش از این‌ها خوندیم. جوابی برای تعداد کل مسیرها بین دو گره در یک Hypercube وجود نداره. اگه خود استاد این رو طرح کرده، بهش بگید اگه جوابی داره مقاله‌ش کنه، اگه دانشجوش هم داده که به استاد بگید تمرین بدون جواب داده. اینجا هم می‌تونید ببینید که برای دو دورترین نقطه‌ی خاص (از ۰۰///۰ به ۱۱///۱) فقط تا n=5 جواب داره:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

یعنی برای دو دورترین نقطه هم جوابی نیست (چه برسه به تمامی حالات. اگه برای تمامی حالات جواب بود، برای دو دورترین نقطه هم جواب پیدا می‌شد).
اما یک حالت خاص می‌تونه این باشه که این مسیرها با هم گره مشترک نداشته باشند، در اون صورت قابل حل هست، ولی شما این قید رو نگفتید.

قسمت دوم یعنی با تغییر دو گره آیا تعداد مسیرها عوض می‌شه، منظور از تغییر دو گره رو متوجه نشدم که به قسمت اول ربط داره یا نه.
توو قسمت اول گفته شده که "دورترین گره‌ها" از هم، که میشن گره‌هایی که تمامی بیت‌های آدرسشون با هم فرق داره. حالا اگه منظور تغییر دو گره، انتخاب "دو دورترین گره" دیگه هست خب باز فرق نمی‌کنه چون Hypercube متقارن هست و تعداد مسیرهای رفتن از ۰۰۰ به ۱۱۱، مساوی هست با رفتن از مثلاً ۰۱۰ به ۱۰۱/ این وسط فقط قواعد نام‌گذاری عوض می‌شه.




مثلا یک راه برای رفتن از ۰۰۰ به ۱۱۱ اینطوری هست:
۰۰۰ [tex]\longleftarrow[/tex] 010 [tex]\longleftarrow[/tex] 110 [tex]\longleftarrow[/tex] 111
بیت‌هایی که هر بار تغییر کردند رو قرمز کردم که عبارتست از به ترتیب بیت دوم، بیت اول (از چپ) و بیت سوم.

حالا من میگم اگه بخوایم دو گره دیگه، مثل تعداد مسیرهای بین ۰۱۰ و ۱۰۱ رو حساب کنیم، هر مسیر، تناظر یک به یک داره با یک مسیری از ۰۰۰ به ۱۱۱/ پس با حالت بالا، یعنی به ترتیب تغییر بیت دوم، بیت اول و بیت سوم، یک مسیری هم باید از ۰۱۰۱ به ۱۰۱ پیدا بشه، که میشه ۰۱۰، سپس ۰۰۰ (بیت دوم تغییر کرد)، سپس ۱۰۰ (بیت اول از چپ) و سپس ۱۰۱ (بیت سوم).

حالا شما هر مسیر دیگه‌ای از ۰۰۰ به ۱۱۱ پیدا کنید و الگوی تغییر دادن بیت‌ها رو پیدا کنید و همون الگو رو به ۰۱۰ اعمال کنید، آخرش تبدیل میشه به ۱۰۱/ چون قبلاً (یعنی تبدیل ۰۰۰ به ۱۱۱) هر بار یک بیت تغییر می‌کرد، توو مسیر جدید (۰۱۰ به ۱۰۱) هم هر بار یک بیت تغییر خواهد کرد و نگران انتخاب غلط نیستیم، فقط حالت اولیه فرق می‌کنه. شما فوقش شاید لازم باشه اثبات کنید که هر تغییر سکانسی از ۰۰۰ به ۱۱۱، روی یک مسیر دیگه هم valid هست و پیش نمیاد که دو بیت رو تغییر بده و هر بار فقط یک بیت تغییر خواهد کرد. از آنجایی که در ۰۰۰ به ۱۱۱ تمامی بیت‌ها تغییر می‌کنه، برای مسیر دیگه هم اینطور خواهد بود.

خلاصه، هر مسیر بین دو دورترین نقطه‌ی خاص، یک سکانس (الگوی تغییر) داره که اگه همون الگوی تغییر رو روی یک مبداً دیگه اعمال کنید، به دورترین نقطه‌ی متناظر با خودش خواهد رسید و سکانس ایجاد شده هم معتبر خواهد بود (بین هر دو گره فقط یک بیت تغییر می‌کنه).
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Pure Liveliness , delete4all
ارسال:
۰۹ آبان ۱۳۹۵, ۰۴:۵۰ ب.ظ
RE: تمرین Hypercube (لطفا کمک کنید.)
(۰۷ آبان ۱۳۹۵ ۰۶:۵۳ ب.ظ)Behnam‌ نوشته شده توسط:  
(07 آبان ۱۳۹۵ ۰۶:۱۹ ب.ظ)mavin1200 نوشته شده توسط:  سلام
نمیدونم اینو تو درس پردازش موازی بعنوان تمرین دادن و اصرار داشتن قسمت دومش حتما إثبات بشه
لطفا اگه کسی بلده کمک کنه یا منبع بگید برم بگردم دنبال جواب
ببینید من هم درس شبکه‌های میان ارتباطی رو پاس کردم که همه‌ش از این‌ها خوندیم. جوابی برای تعداد کل مسیرها بین دو گره در یک Hypercube وجود نداره. اگه خود استاد این رو طرح کرده، بهش بگید اگه جوابی داره مقاله‌ش کنه، اگه دانشجوش هم داده که به استاد بگید تمرین بدون جواب داده. اینجا هم می‌تونید ببینید که برای دو دورترین نقطه‌ی خاص (از ۰۰///۰ به ۱۱///۱) فقط تا n=5 جواب داره:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

یعنی برای دو دورترین نقطه هم جوابی نیست (چه برسه به تمامی حالات. اگه برای تمامی حالات جواب بود، برای دو دورترین نقطه هم جواب پیدا می‌شد).
اما یک حالت خاص می‌تونه این باشه که این مسیرها با هم گره مشترک نداشته باشند، در اون صورت قابل حل هست، ولی شما این قید رو نگفتید.

قسمت دوم یعنی با تغییر دو گره آیا تعداد مسیرها عوض می‌شه، منظور از تغییر دو گره رو متوجه نشدم که به قسمت اول ربط داره یا نه.
توو قسمت اول گفته شده که "دورترین گره‌ها" از هم، که میشن گره‌هایی که تمامی بیت‌های آدرسشون با هم فرق داره. حالا اگه منظور تغییر دو گره، انتخاب "دو دورترین گره" دیگه هست خب باز فرق نمی‌کنه چون Hypercube متقارن هست و تعداد مسیرهای رفتن از ۰۰۰ به ۱۱۱، مساوی هست با رفتن از مثلاً ۰۱۰ به ۱۰۱/ این وسط فقط قواعد نام‌گذاری عوض می‌شه.



مثلا یک راه برای رفتن از ۰۰۰ به ۱۱۱ اینطوری هست:
۰۰۰ [tex]\longleftarrow[/tex] 010 [tex]\longleftarrow[/tex] 110 [tex]\longleftarrow[/tex] 111
بیت‌هایی که هر بار تغییر کردند رو قرمز کردم که عبارتست از به ترتیب بیت دوم، بیت اول (از چپ) و بیت سوم.

حالا من میگم اگه بخوایم دو گره دیگه، مثل تعداد مسیرهای بین ۰۱۰ و ۱۰۱ رو حساب کنیم، هر مسیر، تناظر یک به یک داره با یک مسیری از ۰۰۰ به ۱۱۱/ پس با حالت بالا، یعنی به ترتیب تغییر بیت دوم، بیت اول و بیت سوم، یک مسیری هم باید از ۰۱۰۱ به ۱۰۱ پیدا بشه، که میشه ۰۱۰، سپس ۰۰۰ (بیت دوم تغییر کرد)، سپس ۱۰۰ (بیت اول از چپ) و سپس ۱۰۱ (بیت سوم).

حالا شما هر مسیر دیگه‌ای از ۰۰۰ به ۱۱۱ پیدا کنید و الگوی تغییر دادن بیت‌ها رو پیدا کنید و همون الگو رو به ۰۱۰ اعمال کنید، آخرش تبدیل میشه به ۱۰۱/ چون قبلاً (یعنی تبدیل ۰۰۰ به ۱۱۱) هر بار یک بیت تغییر می‌کرد، توو مسیر جدید (۰۱۰ به ۱۰۱) هم هر بار یک بیت تغییر خواهد کرد و نگران انتخاب غلط نیستیم، فقط حالت اولیه فرق می‌کنه. شما فوقش شاید لازم باشه اثبات کنید که هر تغییر سکانسی از ۰۰۰ به ۱۱۱، روی یک مسیر دیگه هم valid هست و پیش نمیاد که دو بیت رو تغییر بده و هر بار فقط یک بیت تغییر خواهد کرد. از آنجایی که در ۰۰۰ به ۱۱۱ تمامی بیت‌ها تغییر می‌کنه، برای مسیر دیگه هم اینطور خواهد بود.

خلاصه، هر مسیر بین دو دورترین نقطه‌ی خاص، یک سکانس (الگوی تغییر) داره که اگه همون الگوی تغییر رو روی یک مبداً دیگه اعمال کنید، به دورترین نقطه‌ی متناظر با خودش خواهد رسید و سکانس ایجاد شده هم معتبر خواهد بود (بین هر دو گره فقط یک بیت تغییر می‌کنه).

سلام
بابت حوصله ای که در حل سوال به خرج دادید واقعا ممنونم
فقط میشه برای سوال اول اون حالت خاص رو حل کنید یعنی مسیرها گره ی مشترک نداشته باشن
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۱ آبان ۱۳۹۵, ۰۶:۱۳ ب.ظ
RE: تمرین Hypercube (لطفا کمک کنید.)
(۰۷ آبان ۱۳۹۵ ۰۶:۵۳ ب.ظ)Behnam‌ نوشته شده توسط:  
(07 آبان ۱۳۹۵ ۰۶:۱۹ ب.ظ)mavin1200 نوشته شده توسط:  سلام
نمیدونم اینو تو درس پردازش موازی بعنوان تمرین دادن و اصرار داشتن قسمت دومش حتما إثبات بشه
لطفا اگه کسی بلده کمک کنه یا منبع بگید برم بگردم دنبال جواب
ببینید من هم درس شبکه‌های میان ارتباطی رو پاس کردم که همه‌ش از این‌ها خوندیم. جوابی برای تعداد کل مسیرها بین دو گره در یک Hypercube وجود نداره. اگه خود استاد این رو طرح کرده، بهش بگید اگه جوابی داره مقاله‌ش کنه، اگه دانشجوش هم داده که به استاد بگید تمرین بدون جواب داده. اینجا هم می‌تونید ببینید که برای دو دورترین نقطه‌ی خاص (از ۰۰///۰ به ۱۱///۱) فقط تا n=5 جواب داره:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

یعنی برای دو دورترین نقطه هم جوابی نیست (چه برسه به تمامی حالات. اگه برای تمامی حالات جواب بود، برای دو دورترین نقطه هم جواب پیدا می‌شد).
اما یک حالت خاص می‌تونه این باشه که این مسیرها با هم گره مشترک نداشته باشند، در اون صورت قابل حل هست، ولی شما این قید رو نگفتید.

قسمت دوم یعنی با تغییر دو گره آیا تعداد مسیرها عوض می‌شه، منظور از تغییر دو گره رو متوجه نشدم که به قسمت اول ربط داره یا نه.
توو قسمت اول گفته شده که "دورترین گره‌ها" از هم، که میشن گره‌هایی که تمامی بیت‌های آدرسشون با هم فرق داره. حالا اگه منظور تغییر دو گره، انتخاب "دو دورترین گره" دیگه هست خب باز فرق نمی‌کنه چون Hypercube متقارن هست و تعداد مسیرهای رفتن از ۰۰۰ به ۱۱۱، مساوی هست با رفتن از مثلاً ۰۱۰ به ۱۰۱/ این وسط فقط قواعد نام‌گذاری عوض می‌شه.



مثلا یک راه برای رفتن از ۰۰۰ به ۱۱۱ اینطوری هست:
۰۰۰ [tex]\longleftarrow[/tex] 010 [tex]\longleftarrow[/tex] 110 [tex]\longleftarrow[/tex] 111
بیت‌هایی که هر بار تغییر کردند رو قرمز کردم که عبارتست از به ترتیب بیت دوم، بیت اول (از چپ) و بیت سوم.

حالا من میگم اگه بخوایم دو گره دیگه، مثل تعداد مسیرهای بین ۰۱۰ و ۱۰۱ رو حساب کنیم، هر مسیر، تناظر یک به یک داره با یک مسیری از ۰۰۰ به ۱۱۱/ پس با حالت بالا، یعنی به ترتیب تغییر بیت دوم، بیت اول و بیت سوم، یک مسیری هم باید از ۰۱۰۱ به ۱۰۱ پیدا بشه، که میشه ۰۱۰، سپس ۰۰۰ (بیت دوم تغییر کرد)، سپس ۱۰۰ (بیت اول از چپ) و سپس ۱۰۱ (بیت سوم).

حالا شما هر مسیر دیگه‌ای از ۰۰۰ به ۱۱۱ پیدا کنید و الگوی تغییر دادن بیت‌ها رو پیدا کنید و همون الگو رو به ۰۱۰ اعمال کنید، آخرش تبدیل میشه به ۱۰۱/ چون قبلاً (یعنی تبدیل ۰۰۰ به ۱۱۱) هر بار یک بیت تغییر می‌کرد، توو مسیر جدید (۰۱۰ به ۱۰۱) هم هر بار یک بیت تغییر خواهد کرد و نگران انتخاب غلط نیستیم، فقط حالت اولیه فرق می‌کنه. شما فوقش شاید لازم باشه اثبات کنید که هر تغییر سکانسی از ۰۰۰ به ۱۱۱، روی یک مسیر دیگه هم valid هست و پیش نمیاد که دو بیت رو تغییر بده و هر بار فقط یک بیت تغییر خواهد کرد. از آنجایی که در ۰۰۰ به ۱۱۱ تمامی بیت‌ها تغییر می‌کنه، برای مسیر دیگه هم اینطور خواهد بود.

خلاصه، هر مسیر بین دو دورترین نقطه‌ی خاص، یک سکانس (الگوی تغییر) داره که اگه همون الگوی تغییر رو روی یک مبداً دیگه اعمال کنید، به دورترین نقطه‌ی متناظر با خودش خواهد رسید و سکانس ایجاد شده هم معتبر خواهد بود (بین هر دو گره فقط یک بیت تغییر می‌کنه).

سلام
واقعا ممنونم هر دو جوابتون درست بود ممنونم
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۱ آبان ۱۳۹۵, ۰۸:۴۲ ب.ظ
تمرین Hypercube (لطفا کمک کنید.)
(۱۱ آبان ۱۳۹۵ ۰۶:۱۳ ب.ظ)mavin1200 نوشته شده توسط:  واقعا ممنونم هر دو جوابتون درست بود ممنونم
جواب تمرین رو گفتند بهتون؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Pure Liveliness
ارسال:
۱۲ آبان ۱۳۹۵, ۰۲:۳۷ ق.ظ
RE: تمرین Hypercube (لطفا کمک کنید.)
(۱۱ آبان ۱۳۹۵ ۰۸:۴۲ ب.ظ)Behnam‌ نوشته شده توسط:  
(11 آبان ۱۳۹۵ ۰۶:۱۳ ب.ظ)mavin1200 نوشته شده توسط:  واقعا ممنونم هر دو جوابتون درست بود ممنونم
جواب تمرین رو گفتند بهتون؟
سلام
بله گفتن سوال اول یک کران بالا دارد و نمی توان برای تمام ابعاد یک عدد بدست آورد و یک فرمول خاص ندارد تنها یک کران بالا دارد.
برای قسمت دوم منظورشون این بود که اگر تعداد مسیرها بین دو گره n تا باشد با تغییر این دوگره به دو گره دیگر تعداد مسیرها بازهم n می ماند یا خیر؟
منظورشون دو دورترین گره یا گره مشخص نبوده
بنظر شما بازهم جواب اثبات شما برای این مورد هم درسته؟؟؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل تمرین کتاب سیستم های فازی و کنترل فازی neo.st ۲۶ ۳۹,۰۶۳ ۲۸ بهمن ۱۴۰۱ ۰۹:۰۶ ق.ظ
آخرین ارسال: sahar1344
  حل تمرین شدن و مصاحبه دکتری siiib70 ۱ ۳,۲۱۰ ۱۷ بهمن ۱۳۹۹ ۱۱:۳۲ ب.ظ
آخرین ارسال: hmaryam567
  کمک برای حل تمرین پایگاه داده zhila1994 ۰ ۱,۹۴۳ ۲۲ آذر ۱۳۹۹ ۰۱:۲۵ ب.ظ
آخرین ارسال: zhila1994
  کمکم لطفا پایان نامه ارشد mahtab1928 ۰ ۱,۸۳۵ ۰۹ آبان ۱۳۹۹ ۰۶:۳۹ ب.ظ
آخرین ارسال: mahtab1928
  سن واقعی بدن خود را حساب کنید fahimehazimi ۷۱ ۳۵,۱۱۴ ۲۰ مرداد ۱۳۹۹ ۰۴:۱۰ ب.ظ
آخرین ارسال: gerdoo_456
  [دانلود] کتاب clrs همراه با حل تمرین و پیوست فارسی mehrdad66 ۳۸ ۸۲,۴۳۲ ۲۴ خرداد ۱۳۹۹ ۰۴:۲۲ ب.ظ
آخرین ارسال: Nargeshassani
  ۱۲ کد شگفت‌انگیز موبایل خود را کشف کنید elecomco ۰ ۲,۳۸۵ ۰۴ خرداد ۱۳۹۹ ۰۸:۳۵ ب.ظ
آخرین ارسال: elecomco
  ریاضی گسسته روزن ویرایش ۷ همراه با کتاب حل تمرین ها livestrong ۱۲ ۱۹,۴۹۴ ۱۷ اردیبهشت ۱۳۹۹ ۰۴:۳۷ ب.ظ
آخرین ارسال: raziyeh.karbasi
Rainbow خودتونو معرفی کنید! marvelous ۹ ۱۰۵ ۲۳ اسفند ۱۳۹۸ ۰۳:۴۲ ب.ظ
آخرین ارسال: marvelous
Question یک اشکال ریز، کمک لطفا! marvelous ۶ ۵,۲۲۳ ۳۰ دى ۱۳۹۸ ۰۲:۱۶ ب.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close