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

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

اسلاید 1: بسم الله الرحمن الرحیم

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

اسلاید 3: تاریخچه درخت: کایلیساختاری که امروزه درخت نام دارد نخستین بار در سال 1847 در کارهای گوستاوشهف  (1824 ـ 1877) درباره شبکه های الکتریکی به کار رفت. در همین زمان این مفهوم در کتاب هندسه مکانها اثر کارل فون اشتاوت (1798 ـ 1867) نیز به کار برده شد. در 1857 آرتور کایلی (1841ـ 1895)، که از این تحولات قبلی بی اطلاع بود. مجدداً درختها را کشف کرد.  کایلی نخستین کسی است که این ساختار را «درخت» نامید. او درختها را در کاربردهایی در ارتباط با ایزومرهای شیمیایی مورد استفاده قرار داد. او همچنین شمارش رده هایی از درختها را مورد تحقیق قرار داد. کیلی در نخستین اثر خود درباره درختها، درختهای ریشه دار نشانگداری نشده را شمارش کرد. پس از آن شمارش درختهای مرتب نشانگذاری نشده را به انجام رساند. کارل بورچاردت (1817 ـ 1880) و ماری آنموند جوردان (1838 ـ 1932) دو نفر از معاصران کیلی بودند که آنها نیز مطالعاتی درباره درختها انجام دادند. 

اسلاید 4: عملاً ثابت شده است که کامپیوترهای رقمی ای که سرعتهای بالا دارند محرکی دائمی برای کشف کاربردهای جدیدی از درختها هستند. نخستین کاربرد این ساختارها هنگام استفاده از فرمولهای جبری بروز کرد. این مربوط می شود به کارگریس هوپر در سال 1951 از آن زمان تا کنون کاربردهای درختها، در کامپیوتر به طور وسیعی مورد تحقیق و تفحص قرار گرفته است. ابتدا تنها در مستندات برخی الگوریتمها نتایج خاصی ظاهر شد. نخستین بررسی کلی کاربردهای درختها در سال 1961 توسط کنت ایورسن به صورت بخشی از بررسی وسیعتری در مورد ساختارهای داده ها انجام گرفت. برای ردگیری ایده هایی چون جستجوی پیش ترتیب و جستجوی پس ترتیب باید تا اوایل دهه 1960 به عقب برگردیم. در اینه دهه شواهدی از این ایده ها را در کارهای زدزیسلا پاولاک، لیل جانسون و کنت ایورسنمی بینیم. 

اسلاید 5: درخت (نظریه گراف)در نظریهٔ گراف، درخت گرافی همبند و بدون دور است. درخت‌ها به‌طور گسترده در علوم رایانه و ساختار داده‌ها کاربرد دارند. مثل درخت‌های جستجوی دودویی، پشته‌ها،  درخت‌های هافمن برای فشرده‌سازی اطلاعات و غیره.

اسلاید 6: تعاریفدرخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:1-متصل است و دور ندارد.2-هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود می‌آید.3-متصل است و اگر یک یال آن حذف شود دیگر متصل نیست.4-هر دو رأس با یک مسیر سادهٔ یکتا به هم وصل می‌شوند.5-اگر تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند با: یال دارد.n-1*متصل است و یال دارد. n-1*مدار ساده ندارد و

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