درخت ها و کاربرد آن در علوم کامپیوتر

صفحه 1:


صفحه 2:
موضوع پاورپوینت درخت هاوکاربردان درعلوم کامپیونتر 

صفحه 3:
68 تاریخچه درخت: ساختاری که آمروزه درخت نام دارد متس بار در سل 1847 بر ازهای گوستاوشمت ۶ درباره شبکه هاعاکتریکیوبه کار رفت‌در همینزمان‌لین‌مفهوم در کتاب( 1877 1824( ۰ مکلنها اثر > ارلف ورلشتاوت(1798 - 1867) نیز به کار برده شد در 1857 آیته = کابلی(1841- 1895). که از لین حولاتقبلى واطلاع بود. مجدداً درختها را کشفکرد. ‎LS‏ خستیر کسراسکم لیرساختار زا «درخه نامید. او درعتها زا در کاییردهایودر ارتباط هایشیمیایی‌مورد استفاده قرار داد. او همچنینش مارشرده هایراز درختها را موردایزومربا تحقیق‌قرار داد. کیلودر ن خستیناثر خود دربایه درختهاء درختهاريشه دار ن شانگداارین شده را شعار شک رد. پساز آرشمارش‌درختهاوم رت شانگذا رین شده را به انجام رساند. کارا ورچاردیت(1817 - 1880) و مارنموند جوردلن(1838 - 1932) دو نفر از معاصران‌کیلی .بودند که آنها نیز مطاماتیدرباره درختها لنجام دادند ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 4:
عملاً ثابت شده است که کامپیوترهای رقمی ای که سرعتهای ۰ 0 برای کشف کاربردهای جدیدی از رب 2 ی ‎elas aa‏ مربوط مى شود به كارك تن فرمولهای هوير در سال 1951 از آن زمان تا کنون کاربردهای درختها. در کامپیوتر به طور وسیعی مورد تحفیق و تفحص قرار گرفته ها نتایج خاصی است ایند ‎Ua‏ در مستدات برقل ظاهر شد. نخستین بررسی کلی کاربردهای درختها در سال 1 توسط كنت ارورسن به صورت بعشی از بررسی وسیعتری در مورد ساختارهای داده ها انجام گرفت. برای ردگیری ایده هایی چون حستحوى ‎Api te‏ و حستحوى بس ترتیب باید تا اوایل دهه به عقب بیم. در اینه دهه الشدى از اين ‎a‏ ها 7 ‎Sar RIGS‏ ا 

صفحه 5:
درخت [نطريه كراق) = 0 » در است. درخت‌ها به‌طور ترده در کار دارند. مثل ساختار داده‌ها , درخت‌های , درخت‌های حستجوی دودوبی . و غیره‌اطلاعات هافمن برای 

صفحه 6:
تعاریف :درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند .متصلاستو دور ن دارد-1 !اد مدارکندارد و اگر یکی البه آن‌لضافه شود ی کمدار ساده در آنب وجود ملد .متصلاستو اگر ی کی | لآ نحذفشود ديكر متصلن_يسحة :هر دو رامن‌ب ای کمسیر سادة یکتا به هم وصل‌موش وند4 :لگر تعداد متناههرأس‌داشته باشد (حکام بالابا شروط زیر نیز معادل‌اند ب 58 متصل است و*۱-1.یال دارد مدار ساده ندارد و*0-1 .یال دارد 

صفحه 7:
هرگره حداکتردوفرزندداردکه فرزندان راست وچپ نامیده می شوددردرخت دودوبی درجه هرگره اکثر می توانددوباشد درخت ‎Sl‏ دودویی برای پیاده سازی درخت جستجوی دودویی وانبوه دودویی وبرای جستجوی کارامد ومرتب سازی استفاده می شود 

صفحه 8:


صفحه 9:
درخت ریشه دار درخت ریشه‌دار (1۲26 800060) درختیست که یک راس آن به عنوان ريشه انتخاب شده که نسل صقر هم نامیده می‌شود. راس‌هایی که به آن متصلند را فرتدان ریشه و تصل یک می‌نامیم و همین ترتیب را ادمه می‌دهیم. بای مثال در شکل روبرو راس " را ریشه گرفتیم. در نتیجه 0 و و 8 فرزتد " مىشوند. ل فرزند © مىشود. 16 و 11 فرزند ل می‌شوند. 9 فرزند 2 می‌شود. ‏ قرزند 2 می‌شود. نسل صقر: ”7 نسل یک: ظولو6 نسل دو: 411211 نسل سه: 1 یک درخت ریشه‌دار با ریشه‌اش و خود درخت يكتا تعيين می‌شود درختی که ريشه دار نباشد. درخت آزاد نام دارد. اگرراسی که ‎SUL‏ است(نسل زودتری دارد) به راس پایین تر مسیری رو به پایین داشته باشد(مسیری که در آن نسل افزایش پیدا می‌کند): جد راس یایین خواهد بود. برای تمونه 7 جد بقیه رئوس است و جد ک1 و 11 و 1 است ولى جد 4 نیست. 

صفحه 10:


صفحه 11:
درخت ساده نشدنی درخت ساده نشدنی (۲68] ۲8000[016]) درختی است که رأسی با درجهُ 2 ندارد. درخت (-تایی درخت 77-تایی درختی است که هر راس داخلی آن حداکثر ‎M‏ فرزند دارد. 

صفحه 12:
کاربرد درخت در علوم ‎abl,‏ درخت‌ها کاربرد فراوانی در علوم کامپیوتر و مهندسی نرم افزار دارند. * در ساختمان داده و طراحي الگوریتم تا سیستم‌های عامل و سیستم‌های توزیع شده, همه به نوعی و در قسمت‌های مختلف از درخت‌های تصمیم استفاده کرده‌اند. در داده کاوی و طبقه بندی نیز اين درخت‌ها جایگاه ویژه‌ای دارند و بسیاری از الگوریتم‌های طبقه بندی بر پایه‌ی این درخت‌ها ساخته شده‌اند. به آن‌ها درخت‌های تصمیم میگویند زیرا می‌توانند یک تصمیم خاص(مثلا اینکه به یک شخص وام بدهیم یا نه) وا بر اساس اطلاعاتِ گذشته اتخاذ کنند. اجازه بدهید با یک مثال .بحت را آغاز کنیم 

صفحه 13:
بسازید تابند فرض کنید شما مدیر یک دانشکده هستید و میخواهید یک با کمک این طبقه‌بند مشخص کنید کدام یک از دانشجوهای این دانشکده می‌توانند در آزمون دکتری, قبول شوند(در می‌خواهید یک پیش‌بینی انجام دهید). ان پیش‌بیتی می‌تواند باعت این شود که شما دانشجویان با پتانسیل بالا را از این به بعد پیدا کرده و روی آن‌ها سرمایه‌گذاری کنید. مثلا به آن ها وام‌هایی دهید تا بتوانند مقالات بهتری در نشریات معتبرتر صادر = کنند. در واقع می‌خواهید یک مدل طبقه‌بندی ایجاد کنید تا بتواند از روی داده‌های گذشته, یک مدل بسازد و از اين به بعد, هر بار كه یک دانشجوی جدید را به مدل یادگرفته شده دادیم, این مدل بتواند بفهمد که اين دانشجو با جه احتمالی می‌تواند در آزمون دکتری قبول شود. همان طور که از دروس گذشته به اد دارید, باید یک مجموعه داده از دانشجویان گذشته که در آزمونِ دکتری قبول شدند یا نشدند ایجاد کنیم تا بتوانیم آن را به الگوریتم داده کاوی بدهیم و اين ‎a)‏ ياد بكيرد. دلت تاه را به اين ‎Se‏ — 

صفحه 14:
خرن كن 17/5 16/5 15 و طر42 4575 19 71 #2 eS را 

صفحه 15:
همان طور که میبیند در این‌جا دانشجویان قبلي ما که * مورد بررسی قرار گرفته اند, ۷دانشجو می باشند که هر کدام ۴ ویژگی دارند. ۱. معدل کل(عدد) ۲. تعداد ۰مقالات (عدد) ۳ ک ۱8۱۲5 زبا ‎Foc‏ سنوات تحصیلی(عدد). و همچنین یک ستون .۴ برچسب که اگر دانشجو در در مقطع دکتری قبول شده بود, بلی و اگر قبول نشده بود» خیر. در واقع اين داده‌ها مربوط به داده‌های مختلف دانشجوهای قبلی هستند که قبلاً در آزمون دکتری شرکت کرده آند. اين عى باشد.كة الكوريتم :فى توائة مجموعه از زوق آن ياد بكيرد. مثلا مورد شمازمق #1 را نكاه كنيذ. اين دانشجو معدل 19/0 دارد, تعداد ‎allie‏ ارائه كرده است و مدرك زبان أيلتس داردء همجنين سنوات تحصيلى او ۴ سال بوده است. این دانشجو در مقطع دکتری قبول .شده | 0 ات3 ۶/۳۶ 8 00 إن if 1 8 1 8 1 1 

صفحه 16:
a a SAS Sp ‏درخت های تصمیم با توجه به داده‌ها‎ 0 ‏مبادرت به ايجاد يك ساختار درخث مانند‎ ‎ELSE,‏ . می‌کنند که مانند ‏لون ه12 تي 0 0 1 ‏عمل كرده و در نهايت به برچسب‌های ‏دلخواه ما که از داده‌های آموزشی ‎Nea‏ = یادگرفته شدند. میرسند. فرض کنیدمی‌خواهیم داده‌های بالا را به صورت ۲ ‎Sy‏ ‏یک درخت بسازیم. شکل زیر در واقع یک ! ‏نمونه درخت تصمیم از روی داده های بالا :است ‎ ‎ ‎ 

صفحه 17:
تفسیر شکل بالا بسیار ساده است. این شکل می‌تواند در یک زبان * برنامه نویسی دستورات (ایف و الس) پیاده سازی شود. ريشه این درخت (سطح اول): اين است که آیا شخص مدرک زبان دارد یا خیر؟ اگر مدرک زبان داشته باتنشد به زیر درخت سمت چپ می‌رویم و اگر مدرک زبان نداشته باشد به زیر درختِ سمت راست می‌رویم. فرض كنيد به زیر درخت سمت چپ رفته ایم. حال باید بررسی کنیم که آیا شخض تعداد مقالاتی که ارائه کرده است بیشتر یا مساوی ۲تا بوده یا خیر؟ اگر بیشتر یا مساوی ۲تا بوده, اين شخص احتمالاً میتواند در آزمون دکتری قبول شود. در واقع درخت تصميم به اين نتيجه رسيده است که اگر یک شخص, مدرک زبان داشته باشد و تعداد مقالات یا مساوی ۲ ارائه کرده باشد. این شخص می‌تواند در آزمون .دکتری قبول شود 

صفحه 18:
حال فرض كنيد اين درخت توسط يكى از * است. در واقع ‎Glee‏ بادگیری در درحتِ ‎ek,‏ ات ی بررسی کنید که با توجه به داده‌های موجود و درختِ یادگرفته شده, می‌تواند دکتری قبول شود یا خیر. این کار را به مدل درخت تصمیم که از ‎ ‎ ‎ ‎ ‎ 

صفحه 19:
این دانشجو جدید معدل ۱۵.۵ * دارد, تعداد ۵ مقاله ارائه کرده اسب ولی مدرک زبان ندارد. تحصیلی دارد. می‌خواهیم بدانیم آيا اين شخص در آزمون دکتری قبول می شود یا خیر؟ اگر بفواهيم باتوجه به درخت > ‎Glib su sess eels‏ ‎su Wes ely Seca‏ شکل زیر مسیر را ادامه میدهیم تا به یکی از برگ‌ها برسیم(مسیر :حاشور خورده قرمز) 

صفحه 20:
درخت تصمیم ساخته شده به ما میگوید که این دانشجو احتمالا نمیتواند در آزمون دکتری قبول شود.(از روی درختی ‎oS‏ >59 از روی داده‌های گذشته ۰..ساخته شده بود) ( و تعداد نمونه‌ها - در اینجا تعداد دنیای واقعی, دانشجويان در مجموعه داده‌ی آموزشی - معمولاً خیلی بیشتر از اين‌ها ‎al‏ و کار ساختِ درختِ تصميم بر عهددى الكوريتم و كامييوتر مى ‎ ‎ ‎ 

صفحه 21:
۳ .«_ ۰ به پایان آمد این دفتر ** *حکایت همچنان باقیست