الگوریتم وارشا

[nsh]

کسی میدونه الگوریتم وارشا چیه و چجوریه ( سوال استاد ساختمان گسسته مون بوده )
یک سر نخ کوچیک هم اگه کسی داشته باشه بقیه شو خودم میگیرم :blush:

 

[nsh]

یعنی هیچ کس چیزی نمیدونه ؟

 

[seymour]

اسمش دقیقا همینه ؟ ... انگلیسی اش رو نمی دونی ؟

 

[bloody]

کسی میدونه الگوریتم وارشا چیه و چجوریه ( سوال استاد ساختمان گسسته مون بوده )
یک سر نخ کوچیک هم اگه کسی داشته باشه بقیه شو خودم میگیرم :blush:

سلام NSH جان ...
خب ببين الگوريتم وارشال براي بدست آوردن بستار متعدي و روابط هم ارزي به كار ميره(تا اونجا كه اطلاع دارم)
اگه شما كتاب ساختمان گسسته دكتر بهروز قلي زاده رو بخوني ميتوني در صفحات 86 به بعد به بررسي الگوريتم وارشال بپردازي...البته من اونجوري كه خودم فهميدم واست توضيح ميدم كتاب يكم گنگ توضيح داده...
بستار ::اگر R رو يك رابطه روي مجموعه A در نظر بگيريم ممكنه است داراي بعضي از خصوصيات بازتابي ،تقارني و يا تعدي(تراگذري) نباشه ،بستارها حداقل زوج هايي هستن كه اين خصوصيات را ايجاد ميكنن...براي اينكه بيشتر متوجه بشي يه مثال ميزنم:

A:{1,2,3}
R:{(1,2) (1,1) (2,3)}
I​

همونطور كه ميبيني مجموعه R هيچ كدوم از خواص بازتابي ،تقارني،تراگذري رو نداره ...بنابر اين در زير بستار هاي اين روابط رو مينويسيم كه يه جورايي مكمل مجموعه A براي برقرار شدن روابطه مورد نظر هستن.

بستار بازتابي
S:{(2,2) (3,3)}
I
بستار تقارني
S:{(2,1) (3,2)}
I
بستار تراگذري
S:{(1,3)}
I
​

در اين مثال به اين دليل كه اعضاي مجموعه كم تعداد بودن به راحتي ميتونيم بستار متعدي مجموعه رو تشكيل بديم ولي در نظر بگير با يه مجموعه كه تعداد زيادي عضو داره رو برو هستيم اونجا هست كه براي بدست آوردن بستار متعدي مجموعه به مشكل برميخوريم

تنها كاري كه بايد بكنيم اينه كه ماتريس رابطه رو رسم كنيم و R بينهايت رو بدست بياريم..
اگه R يك رابطه در A باشه ....بستار متعدي R رابطهR به توان بينهايت هست
البته كاري كه شما بايد انجام بدي و زمان امتحان به كارت مياد اينه كه الگوريتم وارشال بستار متعدي مجموعه داده شده رو پيدا كني(يعني همونR بينهايت)..كه خيلي كار راحتي

 

[nsh]

سلام NSH جان ...
خب ببين الگوريتم وارشال براي بدست آوردن بستار متعدي و روابط هم ارزي به كار ميره(تا اونجا كه اطلاع دارم)
اگه شما كتاب ساختمان گسسته دكتر بهروز قلي زاده رو بخوني ميتوني در صفحات 86 به بعد به بررسي الگوريتم وارشال بپردازي...البته من اونجوري كه خودم فهميدم واست توضيح ميدم كتاب يكم گنگ توضيح داده...
بستار ::اگر R رو يك رابطه روي مجموعه A در نظر بگيريم ممكنه است داراي بعضي از خصوصيات بازتابي ،تقارني و يا تعدي(تراگذري) نباشه ،بستارها حداقل زوج هايي هستن كه اين خصوصيات را ايجاد ميكنن...براي اينكه بيشتر متوجه بشي يه مثال ميزنم:

A:{1,2,3}
R:{(1,2) (1,1) (2,3)}
I
همونطور كه ميبيني مجموعه R هيچ كدوم از خواص بازتابي ،تقارني،تراگذري رو نداره ...بنابر اين در زير بستار هاي اين روابط رو مينويسيم كه يه جورايي مكمل مجموعه A براي برقرار شدن روابطه مورد نظر هستن.

بستار بازتابي
S:{(2,2) (3,3)}
I
بستار تقارني
S:{(2,1) (3,2)}
I
بستار تراگذري
S:{(1,3)}
I
در اين مثال به اين دليل كه اعضاي مجموعه كم تعداد بودن به راحتي ميتونيم بستار متعدي مجموعه رو تشكيل بديم ولي در نظر بگير با يه مجموعه كه تعداد زيادي عضو داره رو برو هستيم اونجا هست كه براي بدست آوردن بستار متعدي مجموعه به مشكل برميخوريم تنها كاري كه بايد بكنيم اينه كه ماتريس رابطه رو رسم كنيم و R بينهايت رو بدست بياريم..
اگه R يك رابطه در A باشه ....بستار متعدي R رابطهR به توان بينهايت هست
البته كاري كه شما بايد انجام بدي و زمان امتحان به كارت مياد اينه كه الگوريتم وارشال بستار متعدي مجموعه داده شده رو پيدا كني(يعني همونR بينهايت)..كه خيلي كار راحتي ...با يك مثال برات توضيح ميدم:
خب متاسفانه الان ساعت 4 وكلاسم ساعت 4.30 شروع ميشه و مجبورم برم البته امشب رو قول نميدم ولي فردا بعد از ظهر ادامه مثال رو ميگم....
__________________

ااااه دستت درد نکنه
پس من اشتباه کرده بودم وارشاله نه وارشا
خوشحال میدم ادامه بدی