نسخه جدید سایت SID.ir

مشخصات مقاله

عنوان: 

الگوریتمهای مرتب سازی جدید برای اتوماتای سلولی دو بعدی

نوع ارائه: مقاله
نویسنده: شاه آبادي مهدي,ميبدي محمدرضا
 
 
 
عنوان همایش: كنفرانس ملي سالانه انجمن كامپيوتر ايران
نوع همایش:  انجمن هاي علمي
حامی:  انجمن کامپیوتر ایران، مرکز فن آوری دانشگاه صنعتی شریف
زمان:  1382دوره 9
 
چکیده: 

اگر چه الگوريتم هاي متعددي براي مرتب سازي در کامپيوترهاي ترتيبي و موازي ارائه شده است ولي هنوز کار زيادي بر روي مرتب سازي براي اتوماتاي سلولي انجام نگرفته است. دو الگوريتم يکي منصوب به گورديلو و لونا و ديگري منصوب به شاه آبادي و ميبدي براي اتوماتاي سلولي يک بعدي ارايه شده است. الگوريتم گورديلو و لونا، nعنصر را با استفاده از n سلول در 2n-3 مرحله و الگوريتم شاه آبادي و ميبدي n عنصر را با استفاده از n سلول در n-1 مرحله مرتب مي نمايد. تنها الکوريتم مرتب سازي براي اتوماتاي سلولي دو بعدي nxn توسط گلزاري و ميبدي ارايه شده است که داراي پيچيدگي زماني O(n2) ميباشد. در اين مقاله دو الگوريتم مرتب سازي موازي جديد براي اتوماتاي سلولي دو بعدي ارائه شده است. الگوريتمهاي ارائه شده داراي پيچيدگي متوسط O(Ön) مي باشند که نسبت به الگوريتم گلزاري و ميبدي داراي مرتبه بزرگي بمراتب کمتري ميباشد.

 
کلید واژه: آتوماتاي سلولي، مرتب سازي، پردازش موازي
 
مقالات نشریه ای مرتبط: 
 
مقالات همایشی مرتبط: 
 
ارتباط خیلی زیاد ارتباط زیاد مرتبط ارتباط کمتر
 
 
بازدید یکساله 85   pdf-file
 
 
 
آخرین های بلاگ
ورود به بلاگ مرکز اطلاعات علمی