| | | |
| | | | | | |
| | | | | | |
| - | {picture file=img/daneshnameh_up/Cayley.jpg} |
+ | {picture=Cayley.jpg} |
| | | | |
| | | | | | |
| | | | | | |
| | | | |
| | | | |
| | | | |
| | آرتور کایلی | | آرتور کایلی |
| | | | |
| | | | |
| | | | | |
|
| - | ساختاری که امروزه ((درخت ««گراف»»|درخت)) نام دارد نخستین بار در سال 1847 در کارهای گوستاو ((کیرشهف)) (1824 ـ 1877) درباره ((شبکه الکتریکی|شبکه های الکتریکی)) به کار رفت. در همین زمان این مفهوم در کتاب ((هندسه)) مکانها اثر کارل فون اشتاوت (1798 ـ 1867) نیز به کار برده شد. در 1857 آرتورکیلی (1841ـ 1895)، که از این تحولات قبلی بی اطلاع بود. مجدداً درختها را کشف کرد. |
+ | ساختاری که امروزه ((درخت ««گراف»»|درخت)) نام دارد نخستین بار در سال 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 از کتاب درسی آهو، جی، هایکرات و جی اولمان یافت. جی، ای، اتکینس، جی، اس، دیرکمن وکی، آبریان در مقاله خود، مرجع، مفهوم پیش ترتیب را برای یافتن مسیر بهینه بر فرو بی به کار گرفته اند. |
+ | کایلی نخستین کسی است که این ساختار را «درخت» نامید. او درختها را در کاربردهایی در ارتباط با ((ایزومر))های شیمیایی مورد استفاده قرار داد. او همچنین شمارش رده هایی از درختها را مورد تحقیق قرار داد. کیلی در نخستین اثر خود درباره درختها، درختهای ریشه دار نشانگداری نشده را شمارش کرد. پس از آن شمارش درختهای مرتب نشانگذاری نشده را به انجام رساند. ((کارل بورچاردت)) (1817 ـ 1880) و ((ماری آنموند جوردان)) (1838 ـ 1932) دو نفر از معاصران کیلی بودند که آنها نیز مطالعاتی درباره درختها انجام دادند.
فرمول {TEX()} {n^{n-2}} {TEX} که تعداد درختهای نشاندار n راسی را به دست می دهد .در سال 1860 توسط کارل بورچاردت کشف شد. کایلی بعداً، در 1889، برهان مستقلی برای این فرمول عرضه کرد. از آن زمان تا کنون فرمولهای دیگری نیز از آن اشتقاق شده است.
مقالات ((جی، پولیا)) اثری پیشاهنگ درباره شمارش درختها و ساختارهای ترکیباتی دیگر است.همچنین نظریه شمارش پولیا، در این اثر ابداع شد. />
عملاً ثابت شده است که ((کامپیوتر))های رقمی ای که سرعتهای بالا دارند محرکی دائمی برای کشف کاربردهای جدیدی از درختها هستند. نخستین کاربرد این ساختارها هنگام استفاده از فرمولهای ((جبر))ی بروز کرد. این مربوط می شود به ((کارگریس هوپر)) در سال 1951 از آن زمان تا کنون کاربردهای درختها، در کامپیوتر به طور وسیعی مورد تحقیق و تفحص قرار گرفته است. ابتدا تنها در مستندات برخی ((الگوریتم))ها نتایج خاصی ظاهر شد. نخستین بررسی کلی کاربردهای درختها در سال 1961 توسط کنت ایورسن به صورت بخشی از بررسی وسیعتری در مورد ساختارهای داده ها انجام گرفت. برای ردگیری ایده هایی چون ((جستجوی پیش ترتیب)) و ((جستجوی پس ترتیب)) باید تا اوایل دهه 1960 به عقب برگردیم. در اینه دهه شواهدی از این ایده ها را در کارهای ((دزیسلا پاولاک))، ((لیل جانسون)) و ((کنت ایورسن)) می بینیم. |
