منو
 کاربر Online
686 کاربر online
تاریخچه ی: تاریخچه پیدایش درخت «گراف»

نگارش: 1

عکس پیدا نشد
آرتور کایلی


ساختاری که امروزه درخت نام دارد نخستین بار در سال 1847 در کارهای گوستاو کیرشهف (1824 ـ 1877) درباره شبکه های الکتریکی به کار رفت. در همین زمان این مفهوم در کتاب هندسه مکانها اثر کارل فون اشتاوت (1798 ـ 1867) نیز به کار برده شد. در 1857 آرتورکیلی (1841ـ 1895)، که از این تحولات قبلی بی اطلاع بود. مجدداً درختها را کشف کرد.

کایلی نخستین کسی است که این ساختار را «درخت» نامید. او درختها را در کاربردهایی در ارتباط با ایزومرهای شیمیایی مورد استفاده قرار داد. او همچنین شمارش رده هایی از درختها را مورد تحقیق قرار داد. کیلی در نخستین اثر خود درباره درختها، درختهای ریشه دار نشانگداری نشده را شمارش کرد. پس از آن شمارش درختهای مرتب نشانگذاری نشده را به انجام رساند. کارل بورچاردت (1817 ـ 1880) و ماری آنموند جوردان (1838 ـ 1932) دو نفر از معاصران کیلی بودند که آنها نیز مطالعاتی درباره درختها انجام دادند.
فرمول که تعداد درختهای نشاندار راسی را به دست می دهد (تمرین 19 در پایان بند 1012) در سال 1860 توسط کارل بورچاردت کشف شد. کیلی بعداً، در 1889، برهان مستقلی برای این فرمول عرضه کرد. از آن زمان تا کنون فرمولهای دیگری نیز از آن اشتقاق شده است. این مطالب در کتاب جی، دایلیو، مون (9) مورد بررسی قرار گرفته است.
مقاله جی، پولیا (10) اثری پیشاهنگ درباره شمارش درختها و ساختارهای ترکیباتی دیگر است. نظر به شمارش پولیا، که آن را در فصل16 (جلد چهرام) خواهیم دید، در این اثر ابداع شد. برای کسب اطلاعات بیشتر درباره شمارش درختها، خواننده می تواند فصل 15 از کتاب اف، هاراری (4) را ببیند.
عملاً ثابت شده است که کامپیوترهای رقمی ای که سرعتهای بالا دارند محرکی دائمی برای کشف کاربردهای جدیدی از درختها هستند. نخستین کاربرد این ساختارها هنگام استفاده از فرمولهای جبری بروز کرد. این مربوط می شود به کارگریس هوپر در سال 1951 از آن زمان تا کنون کاربردهای درختها، در کامپیوتر به طور وسیعی مورد تحقیق و نفحص قرار گرفته است. ابتدا تنها در مستندات برخی الگوریتمها نتایج خاصی ظاهر شد. نخستین بررسی کلی کاربردهای درختها در سال 1961 توسط کنت ایورسن به صورت بخشی از بررسی وسیعتری در مورد ساختارهای داده ها انجام گرفت. برای ردگیری ایده هایی چون پیش ترتیب و پس ترتیب باید تا اوایل دهه 1960 به عقب برگردیم. در اینه دهه شواهدی از این ایده ها را در کارهای ردزیسلاپاولاک، لیل جانسون و کنت ایورسن می بینیم. در این زمان، کنت ایورسن نماد جدید را برای مقدار گردشده اضافی عدد حقیقی ابداع کرد. مطالب بیشتری درباره این ترتیبها و روشهای پیاده سازی آنها را در کامپیوتر می توان در فصل 3 از کتاب درسی آهو، جی، هایکرات و جی اولمان یافت. جی، ای، اتکینس، جی، اس، دیرکمن وکی، آبریان در مقاله خود، مرجع، مفهوم پیش ترتیب را برای یافتن مسیر بهینه بر فرو بی به کار گرفته اند.



تاریخ شماره نسخه کاربر توضیح اقدام
 سه شنبه 31 خرداد 1384 [04:51 ]   2   علی هادی      جاری 
 دوشنبه 30 خرداد 1384 [12:59 ]   1   علی هادی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..