مقاله تبدیل مبنا

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

  مقاله تبدیل مبنا دارای ۱۶ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله تبدیل مبنا  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله تبدیل مبنا،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن مقاله تبدیل مبنا :

تبدیل مبنا

درخت مبنا (radix tree) یا درخت پاتریشیا (Patricia tree) یا درخت کریت بیت (crit bit tree)، گروهی از داده ساختار های بر پایه ترای هستند که برای نگهداری مجموعه ای از رشته ها استفاده می شوند. برخلاف ترای معمولی، یال ها در درخت مبنا با مجموعه ای از کاراکترها

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

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

این داده ساختار، عملیات‌های اصلی زیر را پشتیبانی می‌کند و همه آن‌ها از هستند که حداکثر طول یک کلمه در آن گروه از رشته هاست:
• مراجعه: تعیین می‌کند که یک رشته در درخت هست یا نه. این عملیات کاملا همانند درخ

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

• حذف: حذف یک رشته از درخت. ابتدا برگ متناظر را حذف می کنیم. سپس اگر پدر آن فقط یک بچه داشت، پدر را هم حذف کرده و دو یال لازم را با هم ادغام می کنیم.
• پیدا کردن جد: بزرگ‌ترین رشته کوچکتر از یک رشته داده شده را برحسب ترتیب واژه نگاری پیدا می کند.

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

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

تاریخچه
اولین بار دونالد موریسون در ۱۹۶۸ چیزی که خودش

درخت پاتریشیا نامید را توصیف کرد. نام آن در واقع مخفف “الگوریتم عملی برای بازیابی اطلاعات کدشده به صورت الفباعددی” ( Practical Algorithm To Retrieve Information Coded In Alphanumeric) می باشد. گرنوت گوهنبرگر در همان زمان به طور مستقل این داده ساختار را طراحی و توصیف کرد.
مقایسه با دیگر داده ساختارها
برخلاف درخت‌های متوازن، درخت مبنا اجازه مراجعه، درج و حذف را در به نسبت را می دهد. زمانی که این یک برتری به نظر نمی آید اما در یک درخ

ت متوازن، هر مقایسه یک رشته در بدترین حالت زمان نیاز دارد که خیلی از آن‌ها در عمل برای اشتراکات طولانی حروف ابتدایی کند هستند. در یک درخت، همه مقایسه‌ها نیازمند زمان ثابتی

است اما درخت مبنا مقایسه برای جستجوی

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

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

باینری و دسیمال و تبدیل آنها به یکدیگر :
می خواستم در مورد IP ها توضیح بدم دیدم احتمالا تو توضیحات به مشکل باینری و دسیمال بر می خوریم

برای همین گفتم همین جا همه چیز رو در مورد این مبنا ها بگم
سعی می کنم ساده توضیح بدم که متوجه بشین، سعس کنید کامل مطالعه کنید تا دیگه با این موضوع مشکل نداشته باشید

دسیمال : یعنی مبنای ۱۰
باینری : یعنی مبنای ۲

اکتان : یعنی مبنای ۸
هگزا دسیمال : یعنی مبنای ۱۶

وقتی ما از عددی مثل ۲۲۵ صحبت می کنیم

یعنی یک مقدار عددی هست که در مبنای ۱۰ یعنی دسیمال نمایش داده میشه ، اما همین عدید رو اگر بخواهیم به صورت باینری ( مبنای ۲ ) نمایش بدیم نتیجه میشه ۱۱۱۰۰۰۰۱ به صورت اکتان میشه ۳۴۱ و به صورت هگزا دسیمال ( مبنای ۱۶ ) میشه E1 ولی همه این مدل نمایش ها در نهایت بیانگر یک عدد هستند که به صورت های مختلف نمایش داده شده اند
که تو حالت عادی ما و روزمره از اعداد در مبنای ۱۰ استفاده می کنیم
ولی در کامپیوتر از مبنای ۲ یعنی همون باینری استفاده میشه ، برای همین ما باید بتوانیم مبنای ۱۰ را به ۲ تبدیل کنیم

اما روش تبدیل :
روش تبدیل دسیمال به باینری : ( مبنای ۱۰ به مبنای ۲ )
فرض کنید می خواهم عدد ۲۵۳ که دسیمال هست را به باینری تبدیل کنم
برای اینکار باید عدد ۲۵۳ را به ۲ تقسیم کنیم
بعد با قی مانده را نگه داریم و خارج قسمت را به ۲

تقسیم کنیم
دوباره باقی مانده را نگه می داریم و خارج قسمت را به ۲ تقسیم می کنیم ، این کار و ادامه میدهیم تا جایی که خارج قسمت ۰ بشه

سپس باقیمانده‌ها را یادداشت می‌کنیم به این صورت که اولین باقیمانده‌ را در سمت راست و آخرین باقیمانده‌ را در سمت چپ می‌نویسیم
که برای عدد ۲۵۳ ای که ما داشتیم جواب برابر ۱۱۱۱۱۱۰۱ می شود

حالا فرض کنید ما می خواهیم حاصل تبدیل ما از دسیمال به باینری یک عدد ۸ رقمی باشه و لی جواب ما کمتر از ۸ رقم بشه . مثلا فرش کنید شده ۱۱۱۰۱ یعنی ۵ قم ، پس ما ۳ رقم کم داریم ، برای همین به سمت چپ به تعدادی که لازم داریم ۰ اضافه می کنیم . پس میشه ۰۰۰۱۱۱۰۱

شما برای تمرین چند تا عدد رو به باینری تبدیل کنید ، برای مثال ۱۳۲ و ۸۰ رو به باینری تبدیل کنید

اما حالا تبدیل باینری به دسیمال : ( مبنای ۲ به مبنای ۱۰ )
فرض کنید حالا ما می خواهیم عدد باینری ۱۱۱۱۱۱۰۱ را به دسیمال تبدیل کنیم ( عکس عمل قبلی )
برای اینکار میایم عدد اول از سمت راست یعنی ۱ را در ۱ ضرب می کنیم
۱*۱
بعد عدد دوم از سمت راست را که میشه ۰ در ۲ ضرب می کنیم
۰*۲
بعد عدد سوم از راست که میشه ۱ را در ۴ ضرب می کنیم ، عدد بعدی در ۸ ، بعدی ۱۶ و ;
و در انتها جواب همه ضرب ها رو با هم جمع می کنیم

برای مشخص کردن تعداد چیزها آن ها را می ش

ماریم. این شمارش باید در دستگاه مشخصی و در چهارچوب خاصی انجام گیرد. به طور معمول شمارش در دستگاه دهدهی انجام می شود، یعنی دستگاهی که مبنای شمارش ر آن ۱۰ است. در این دستگاه واحد هر مرتبه ۱۰برابر واحد مرتبه ی قبلی است. مثلاً واحد مرتبه هزارگان ۱۰برابر واحد مرتبه ی صدگان است و واحد مرتبه ی ص

دگان۱۰برابر واحد مرتبه ی دهگان است و واحد مرتبه ی دهگان ۱۰برابر واحد مرتبه ی یکان می باشد.
اما آیا می توان شمارش را به گونه ای دیگر نیز انجام داد ؟
به مثال زیر توجه کنید:
مدیر یک کارخانه ی لیوان سازی به انباردار خود دستور داد آمار تمام لیوان های موجود در انبار کارخانه را به او بدهد. در واحد بسته بندی این کارخانه هر ۶ عدد لیوان را در یک بسته پلاستیکی و هر ۶ بسته را در یک کارتن و هر ۶ کارتن را در یک جعبه و بعد هر ۶ جعبه را در یک صندوق چوبی بزرگ قرار می دهند. سپس صندوق ها را بار قطار کرده و برای مشتریان خود به شهرهای دور و نزدیک می فرستند. انباردار برای شمارش تعداد لیوان ها جدولی را که در اختیار داشت به صورت زیر کامل کرد:
واحد یکی بسته کارتن جعبه صندوق
تعداد ۲ ۱ ۴ ۱ ۵
او در گزارش خود تعداد لیوان های موجود را ۵۱۴۱۲ نوشت. اما وقتی تعجب مدیر کارخانه را دید ساعتی بعد آن را اصلاح کرد و تعداد لیوان ها را ۶۸۴۸ اعلام کرد .
آیا به نظر شما او دروغ گفته بود ؟

خیر. او هر دو بار راست گفته بود ولی فراموش کرده بود که روش شمارش لیوان ها را توضیح دهد. در مرتبه ی اول او تعداد لیوان ها را بر اساس چگونگی بسته بندی آن ها حساب کرده بود. در این روش شمارش در مبنای ۶ انجام گرفته بود و او می بایست تعداد لیوان ها را ۶(۵۱۴۱۲) ثبت می کرد. در مرتبه ی دوم او با توجه به این که می دانست در هر بسته ۶ لیوان و در هر کارتن۶*۶لیوان و در هر جعبه ۶*۶*۶ لیوان و در هر صندوق ۶*۶*۶*۶ لیوان وجود دارد، جدول خود را به صورت زیر کامل کرد :
واحد یکی بسته
۶تایی کارتن
۳۶ تایی جعبه
۲۱۶ تایی صندوق
۱۲۹۶تایی

تعداد ۲ ۶
۱* ۳۶
۴ * ۲۱۶
۱ * ۱۲۹۶
۵ *
۲ ۶ ۱۴۴ ۲۱۶ ۶۴۸۰
و سپس مجموع آن ها را به دست آورد : ۶۸۴۸ = ۲+ ۶ + ۱۴۴ + ۲۱۶ + ۶۴۸۰

این عدد تعداد لیوان ها را در مبنای ۱۰ نشان می دهد. پس : ۶۸۴۸ = ۶( ۵۱۴۱۲ )
سؤال : در آمارگیری ماه بعد او تعداد لیوان ها را ۶( ۱۴۰۲۰ ) به دست آورد. به نظر شما او چه عددی را باید در گزارش خود به مدیر کارخانه بنویسد؟
* * * * *
اگر بخواهیم عددی را که در مبنای غیر ۱۰ نوشته شده به مبنای ۱۰ ببریم. رقم های آن را در توان های مختلف مبنا ضرب می کنیم و سپس مجموع آن ها را به دست می آوریم.
مثال۱ـ نمایش معمولی عدد ۶( ۱۰۵۳) را بنویسید .
۲۴۹= ۳+ (۶*۵) + ( ۳۶*۰) + ( ۲۱۶*۱) = ۶

( ۱۰۵۳)
مثال۲ـ نمایش ۵۳۲ را در مبنای ۶ به دست آورید.

۶( ۲۲۴۴) = ۵۳۲
• اگر در مثال های بالا توجه کرده باشید خواهید دید اگر عددی را از یک مبنا به مبنای کوچک تری ببریم نمایش ظاهری عدد بزرگ تر خواهد ش
• در هر مبنا از رقم هایی می توان استفاده کرد که از خود مبنا کوچک تر باشند. مثلاً در مبنای ۱۰ از رقم های ۰ تا ۹ ودر مبنای ۴ فقط از رقم های ۰ ، ۱ ، ۲ و ۳ استفاده می شود.
سؤال: اگر شما ۱۴ سال سن داشته باشید، سن شما در هر یک از مبناهای ۲ تا ۹ برابر چند می شود؟ در چه مبنایی سن شما بیش تر است ؟
مثال۳- بزرگ ترین و کوچک ترین اعداد سه رقمی در مبنای ۷ چه اعدادی هستند؟
در مبنای ۷ فقط می توانیم رقم های ۰ تا ۶ را به کار ببریم. دو جواب داریم:
اگر بخواهیم از رقم های تکراری استفاده کنیم،عدد ۷(۶۶۶) بزرگ ترین و عدد۷(۱۰۰) کوچک ترین عدد سه رقمی در مبنای ۷ هستند. ولی اگر از رقم های تکراری استفاده نکنیم، عدد۷(۶۵۴) بزرگ ترین و عدد۷(۱۰۲) کوچک ترین عدد سه رقمی در مبنای ۷ هستند.

• جمع
برای جمع چند عدد که مبنای مساوی داشته باشند مانند اعداد در دستگاه دهدهی عمل می کنیم. اعداد را از سمت راست زیر هم می نو

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

اضافه می کنیم.
مثال۴- حاصل ۳(۲۱۲) + ۳(۲۱۰۱) را به دست آورید .
۱ ۱
۳(۲۱۰۱)
۳(۰۲۱۲) +
۳(۱۰۰۲۰)
• تفریق
در تفریق دو عدد که مبنای مساوی دارند باید توجه داشت اگر رقم مفروق منه (رقم بالایی) از رقم مفروق کم تر باشد، از رقم سمت چپ آن یک واحد کم می کنیم و به تعداد مبنا به آن رقم مفروق منه اضافه می کنیم.
مثال ۵ـ حاصل ۵(۱۳۴) – ۵(۳۲۴) را به دست آورید .
۷ ۲
۵(۳۲۴)
۵(۱۳۴) –
۵( ۱۴۰)
مثال۶ـ نمایش عدد۴(۱۲۳) را در مبنای۵ بن

ویسید .
۲۷ = ۳ + (۴*۲) + (۱۶*۱) =۴(۱۲۳)
۵( ۱۰۲ ) = ۲۷
۵( ۱۰۲ ) = ۴(۱۲۳)