تبليغاتX
ریاضی کاربردی ریاضی کاربردی      ریاضیات کاربردی و علوم کامپیوتر

                 

 

 

صفحه نخست
پست الکترونيک
آرشيو وبلاگ

 

درباره وبلاگ

آيا کساني که مي دانند با کساني که نمي دانند يکسانند. قرآن کريم
ریاضی کابردی شاخه ای از ریاضیات نیست بلکه جهت حرکت در آن است.
نویسندگان :
شهریار میرزاده روزبه ابرازی
دانشجویان ریاضی کاربردی
دانشگاه خواجه نصیر الدین طوسی
E-Mail:R.Ebrazi@gmail.com

 

نویسندگان وبلاگ

روزبه ابرازی
شهریار میرزاده


 آرشيو موضوعي

  عمومی
تئوری بازی ها
تئوری اعداد
سیستم های خبره
بهینه سازی
ریاضیدانان
توپولوژی
رمزنگاری

 

نوشته هاي پيشين

شهریور 1386
اردیبهشت 1386
فروردین 1386
اسفند 1385
بهمن 1385
مهر 1385
شهریور 1385
مرداد 1385
تیر 1385
اردیبهشت 1385
فروردین 1385
اسفند 1384
بهمن 1384
دی 1384
آذر 1384
مهر 1384
شهریور 1384
مرداد 1384

 

جستجو و آمار

Google

در اين سايت

در كل اينترنت
 



 

 

9:5یکشنبه یازدهم دی 1384

بخش پذیری بر«7»

روزبه ابرازی

بخش پذیری بر«7»

 

گفتن اینکه یک عدد صحیح داده شده بر 2 بخش پذیر است یا نه کار آسانی است . این کار فقط با بررسی زوج بودن آخرین رقم میسر است . روش های ساده ی دیگری هم برای تعیین بخش پذیری یک عدد بر 3و4و5و6و8و9 یا 10 وجود دارد . تنها استثنا عدد 7 است.

 

روش های شناخته شده برای امتحان بخش پذیری بر عدد 7 به طور شکفت انگیزی مشکل است.

 

این روش هم  یکی از آنها است.برای اینکه بفهمیم یک عدد مضربی از 7 است یا نه ، رقم آخر را 2 برابر کنید ، سپس عدد به دست آمده را از ارقام باقی مانده کم کنید . اگر به عددی رسیدید که بر 7 بخش پذیر است ، می توان نتیجه گرفت که عدد اصلی بر 7 بخش پذیر است .  حال اگر ندانیم که عدد به دست آمده بر 7 بخش پذیر است یا نه می توانیم همین کار را دوباره انجام دهیم .

 

مثلا عدد 616 را در نظر بگیرید برای اینکه بخش پذیری آن را بر 7 امتحان کنیم رقم آخر آن را 2 برابر کنید(12=6*2)،سپس جواب را از ارقام باقیمانده کم کنید (49=12 61). چون 49 بر 7 بخش پذیر است 616 هم بر 7 بخش پذیر می شود.

 

این روش برای اعداد کوچک خیلی خوب کار می کند اما برای اعداد بزرگتر ،  به اندازه کافی پیچیده می شود ، به طوری که تقریبا به اندازه ی خود عملیات تقسیم بر 7 وقت گیر است.

 

در طول سالها افراد مختلف یک دو جین از این دست الگوریتم ها را ابداع کرده اند. آخرین روش بدست آمده متعلق به   Gustavo Gerald Toja Frachi از دانشگاه سائو پائولو برزیل است.

 

روش ابتکاری Toja به این صورت عمل می کند:

 

·             عدد زیر که مضربی از 7 است را در نظر بگیرید
6،049،344

·            از سمت راست عدد را به جفت هایی از ارقام تقسیم کنید.
44_93_04_6

·            حال تفاوت بین هر جفت از اعداد با نزدیکترین مضرب 7 بالایی یا پایینی آن ، را  حساب کنید. با جفت اول شروع کنید . برای اولین جفت  مضرب 7 پایینی را به کار ببرید، برای عدد دوم از مضرب 7 بالایی و برای سومی از مضرب 7 پایینی استفاده کنید  و به همین طریق ادامه دهید تا جفت ها تمام شود. 
44 – 42 = 2  ;   98 – 93 = 5 ;   04 – 0 = 4  ;   7 – 6 = 1  

·            ارقام به دست آمده را به ترتیبی که محاسبه کردیم (یعنی از جفت های راست به چپ) روی کاغذ بنویسید .
2541

·            برای  ارقام 2541هم  این  رویه را تکرار کنید .
25 41

41
– 35 = 6; 28 – 25 = 3
63

·            آخرین جفت ،63، مضربی از 7 است .

 

Toja در http://www.divisibilitybyseven.mat.br/  روش خود را توصیف می کند و راجع به اینکه این روش چگونه کار می کند توضیح می دهد.او ادعا می کند که روشش بطور قابل ملاحظه ای سریع است و به اندازه کافی برای تعیین بخش پذیری بر7 اعداد بزرگ کار آمد است.

 

Alexander Bogolmolny به تازگی الگوریتم Toja را برای بخش پذیری بر 11 و بر 13 گسترش داده (اینجا را ببینید http://www.cut-the-knot.org/blue/div7-11-13.shtml ) ، و Toja هم روشی برای تعیین باقیمانده هنگامی که عدد بر 7 بخش پذیر نیست اضافه کرده.

 

 جالب اینکه الگوریتم Toja با الگو ریتمی که توسط L. Vosburgh Lyons ، یک روان پزشک عصبی (neuropsychiatrist  ) از نیویورک ، ارئه شده با روشی کاملا  مشابه آغاز می شوند.

 

این مثالی است که Martin Gardner برای نشان دادن روش Lyons به کار می برد.

 

·        ارقام را از چپ به راست دو تا دو تا جفت کنید.( م. عدد اصلی 2359406178839 بوده)
39_88_17_06_94_35_2

·        اضافی  هر جفت را از مضرب 7 ما قبل آن .
06 – 0 = ;   17 – 14 = 3 ;   88 – 87 = 4  ;   39 – 35 = 4

2 – 0 = 2  ;   35 – 35 = ;   94 – 91 = 3
2036344

·        ارقام عدد به دست آمده را از سمت راست به صورت گروه های 3 تایی در آورید در زیر هم بنویسید سپس ارقام هر ستون را با هم جمع بزنید .
344
036
2
ستون اول:    
3
=0+3
ستون دوم:    7
=3+4
ستون سوم: 12
=2+6+4

·        سه رقم به دست آمده را با کاهش مضرب هفت پایینی آنها ، کوچک کنید.
3
=03  ;  0=77  ;  5=712

 
305

·        اضافی اولین رقم و دومین رقم باهم را  از مضرب هفت پایینی  حساب کنید درسمت چپ یادداشت کنید و اضافی رقم دوم و سوم را  از مضرب هفت پایینی  حساب کنید و درسمت راست  یادداشت کنید.
 
305 ،5_30 ،05_3
2
= 2830   ;  5=0 05

25

·        رقم سمت چپ را از رقم سمت راست کم کنید . ( اگر رقم سمت راست کوچکتر از رقم سمت چپ بود 7  تا به آن قبل از تفریق اضافه کنید.) عدد انتهایی باقیمانده تقسیم  عدد اصلی بر 7 است. بنابراین عدد اصلی زمانی بر 7 بخش پذیر است که رقم بدست آمده - 0- صفر باشد.
3


 

هنوز به نظر می آید که انجام این مراحل کار زیادی باشد ! همیشه چیزی راجع به 7 وجود دارد که منجر به هر گونه پیچیدگی می شود.

 

در زمانی که ماشین حساب ها و کامپیوتر ها همه جا را  گرفته اند . روشن نیست که این الگوریتم های  بخش پذیری به چه کار می آیند. اگر چه باز ی با اعداد همیشه جاذبه های پایدار خودش را دارد بخصوص زمانی که از رمز راز عدد هفت ، بدست آمده باشد.

 

نویسنده : Ivars Peterson  

پیوند به متن اصلی :

http://www.maa.org/mathland/mathtrek_05_23_05.html

 

منابع:

Gardner, M. 1969. Tests of divisibility. In The Unexpected Hanging and Other Mathematical Diversions. New York: Simon and Schuster. See Martin Gardner's Mathematical Games.

Peterson, I. 2002. Testing for divisibility. MAA Online (Aug. 19).

برای  اطلاعات بیشتر راجع به قوانین بخش پذیری به پیوندهای زیر مراجع کنید:

بخش پذیری بر 7

http://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml

بخش پذیری بر سایر اعداد

http://mathforum.org/k12/mathtips/division.tips.html,
http://www.cut-the-knot.org/blue/FurtherDivisibility.shtm  http://argyll.epsb.ca/jreed/math7/strand1/1104.htm.

 


12:55شنبه سوم دی 1384

مسیر های هنرمندانه

روزبه ابرازی

مسیر های هنرمندانه

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

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

مسیر بهینه برای 10 شهر

                                           

.

بعنوان مثال ،برای پیدا کردن کوتاه ترین مسیر ممکن برای 10 شهر یک کامپیوتر مجبور به ارزیابی 362،880(!9) امکان است.همین طور که شمار شهر ها افزایش می یابد ، شمار مسیر ها با سرعت موشک رشد می کند!

                    

                این نقشه ی یک مسیر بهینه شده از میان 13،509 شهر در آمریکا  است.
                      طراح :
Courtesy of William Cook, Georgia Tech

با این وجود ، محققان روش هایی را برای محاسبه مسیری بهینه برای شمار قابل توجهی از شهرها یافته اند.رکورد کنونی که در سال 2004 محاسبه شده ، گشتی است که  از هر 24،978 شهر ، شهرک و روستای سوئد  عبور می کند.(اینجا را ببینیدhttp://www.tsp.gatech.edu/sweden/index.html).این مسیر 72،500 کیلومتر  طول دارد و هیچ مسیر کوتاهتری وجود ندارد.

این رکورد توسط David Applegate از آزمایشگاه تحقیقاتی شرکت تلگراف و تلفن آمریکا AT&T ،Robert Bixby از دانشگاه Rice ، Vašek Chvátal از دانشگاه Rutgers ،William Cook ازGeorgia Tech و Keld Helsgaun از دانشگاه Roskilde.

Robert Bosch ریاضیدان و Adrianne Herman دانشجوی کالج Oberlin در اوهایو در حال حاضر برنامه کامپیوتری ای را ساخته اند که مسئله فروشنده دوره گرد را به دنیای هنر می آورد. آنها از مسیرهایی استفاده می کنند که حاصل پاسخگویی به مسئله طراحی با خط ممتد(بدون برداشتن قلم از کاغذ) است.

اساتید هنر خیلی تمایل دارند از دانشجویان تازه کار بخواهند از این قبیل طراحی ها انجام دهند . ایده این کار این است که به یک شکل نگاه کنید ،نوک مداد را روی کاغذ بگذارید ،سپس بدون اینکه نوک قلم از کاغذ جدا شود طرحی از شیئ بکشید تا زمانی که طراحی به پایان برسد.این کار خیلی شبیه پیدا کردن یک مسیر بهینه است که شمار زیادی از شهرها  را به هم وصل می کند.

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

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

برای یافتن راه حلی متناظر با مسئله فروشنده دوره گرد ، Bosch وHerman شیوه ای مشابه  با روشی را به کار بردند که گروه مشابه آنها در پیدا کردن رکورد گشت در سوئد به کار برده بودند.نتیجه این گشت یک طراحی با خطوط پیوسته از تصویر مورد نظر است.

                   

  را ه حل تقریبی مسئله فروشنده گرد برای مجموعه ای از 27،486  شهر با دقت جایگذاری شد   ه تصویری مشابه و گیرا  از مونالیزا را تولید می کند.
طراح :اهدا شده ی
Robert Bosch  

                                                

                منظره ای بزرگ شده از مسیر لازم برای ایجاد نقاشی ای با خطوط پیوسته از مونالیزا
                                            طراح :اهدا شده ی
Robert Bosch

Bosch از همین تکنیک برای ایجاد شماری از نقاشی ها با خطوط پیوسته استفاده کرد این مسیرهای هنرمندانه در پاره ای از اوقات شامل 100،000 شهر می شود.

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

نویسنده: Ivars Peterson

لینک اصلی مقاله :

http://www.maa.org/mathland/mathtrek_01_03_05.html

  منابع:

Becker, T.J. 2004. No accidental tourist. Research Horizons (Fall). Available at http://gtresearchnews.gatech.edu/reshor/rh-f04/tsp.html.

Bosch, R., and A. Herman. 2004. Continuous line drawings via the traveling salesman problem. Operations Research Letters 32(July):302-303. Preprint available at http://www.oberlin.edu/math/faculty/bosch/tspart.pdf.

Fowler, Y.G. 2004. One continuous line. Oberlin Alumni Magazine (Spring). Available at http://www.oberlin.edu/alummag/spring2004/ats.html.

Peterson, I. 2003. Constructing domino portraits. MAA Online (April 14).

______. 2000. Calculating swarms. Science News 158(Nov. 11):314-316. Available at http://www.sciencenews.org/articles/20001111/bob10.asp.

______. 1997. The traveling monkey. MAA Online (July 7).

Robert Bosch has a Web page at http://www.oberlin.edu/math/faculty/bosch.html. His domino artwork is featured at http://www.dominoartwork.com/.

Information about the traveling salesman problem is available at http://www.tsp.gatech.edu