منو
 کاربر Online
593 کاربر online
تاریخچه ی: رابرت تارژان

||V{maketoc}||
^@#16:
!رابرت تارژان
__من درختها، گرافها و ساختار داده‌ها را در ذهنم مجسم می‌کنم. آنها راحتتر از بسیاری چیزهای دیگر به ذهن من می‌آیند.__
سه چیزی نشانه یک ایده خوب در علوم رایانه است. یکی این که کاربرد زیاد داشته باشد. دیگر این که در همان سالهای اولیه به دانشمندان جوان رایانه آموخته شده باشد و بالاخره این که راهی برای پژوهشهای بعدی پیش رو بگذارد. اگر این سه معیار را بپذیریم آنگاه می‌توانیم با اطمینان بگوییم که رابرت تارژان خالق بسیاری ایده‌های خوب بوده است.
کارهایی که او در دوره دکتریش در دانشگاه استنفورد به همراه جان هاپکرافت در زمینه آزمون مسطح بودن و سایر الگوریتمهای گرافها انجام داد کاربردهای وسیعی، از طرح‌بندی کارآمدتر تراشه‌ها گرفته تا جانمایی بهتر نقشه‌ها، پیدا کرد. این الگوریتمها تاکیدی بر قدرت یک تکنیک برنامه‌سازی به نام جستجوی ژرفایی میلیونها بار هر روز در بازیهای رایانه‌ای، برنامه‌های نگاره‌ای (گرافیکی) و کاربرگها به کار برده می‌شود. کارهای بعدی تارژان در زمینه جریان شبکه‌ای کارآمد،‌ به همراه دن اسلیتور و اندرو گلدبرگ، به طراحان شبکه‌ها در تعیین ظرفیت هر پیوند به منظور بهبود جریان در شبکه، خواه شبکه انتقال نفت باشد خواه شبکه تلفن، کمک شایانی کرد. کارهای دیگر او بر روی یک جفت ساختار داده ساده به نام up – tree و splay – tree‌ (در ادامه مقاله درباره این دو نوع درخت توضیح داده شده است)، روشهای جدیدی را برای تعیین کارآیی الگوریتمها به وجود آورد.
از دیگر کارهای تارژان به ابداع یک ساختار داده برای نگهداری اطلاعات حال و گذشته به طور توأم و به شکلی بسیار کارآمد اشاره کرد. او این کار را به همراه نیل سارناک، ذن اسلیتور و جیمز دریسکول انجام داد. چنین ساختار داده «ماندگاری» امروزه در روباتیک و سامانه های پایگاه داده‌ها، بسیار به کار گرفته می‌شود.
علاوه بر اینها، تارژان یک تغییر فرهنگی در یادگیری و مطالعه علوم رایانه به وجود آورده است: اول یک «ایده بزرگ» به دست آورید و سپس ساختار داده‌های لازم را برای پشتیبانی از آن ایجاد کنید. این شیوه، راهنمای او و دیگران در استفاده بهتر از الگوریتم «کوتاهترین مسیر» دایکسترا و الگوریتمهای بنیادی دیگر شد.
وجه مشخصه کارهای تارژان، خلاصه‌نویسی، زیبایی، دقت و عمومیت‌پذیری است. او می‌گوید:
«یک ایده خوب را همیشه می‌توان ساده‌تر کرد و از آن برای حل مسائلی غیر از آنچه که از اول مورد نظر بوده است، استفاده کرد.»
رابرت اندر تارژان در سال 1948 در شهر پومونا در کالیفرنیا به دنیا آمد. او از همان دوران کودکی به علم علاقه داشت.
«از کلاس هفتم با خواندن مقالات مارتین گاردنر در مجله ساینتیفیک آمریکن درباره بازیها و حل معماها به ریاضیات علاقه‌مند شدم. قبل از آن به ستاره‌شناسی و نجوم علاقه پیدا کرده بودم و می‌خواستم نخستین انسانی باشم که پا به مریخ می‌گذارد.
پدر رابرت، روانپزشک کودکان و مدیر یک بیمارستان دولتی بود. رابرت هنگامی که در دبیرستان بود، به طور پاره‌وقت در آن بیمارستان کار می‌کرد و همانجا بود که او برای نخستین بار با دستگاه جمع‌آوری کارتهای منگنه آی‌بی‌ام آشنا شد و با آن کار کرد. تارژان این دستگاه را «پیش‌رایانه» می‌نامد. او در یک برنامه علمی تابستانی که در سال 1964 و بلافاصله پس از دوره دبیرستانش برگزار شد، برای نخستین بار با رایانه‌های واقعی کار کرد. او در این باره می‌گوید:
«ما باید مشاهداتی از یک سیاره به عمل می‌آوردیم و مدارش را محاسبه می‌کردیم. این امکان به ما داده شده بود که از رایانه‌ای در دانشگاه کالیفرنیا (UCLA) استفاده کنیم. برای این منظور، من زبان فرترن را فرا گرفتم.
در آن زمان، بیمارستان پدرم نیز یک رایانه ضعیف خریداری کرده بود. من هرگاه فرصت می‌یافتم با آن نیز کار می‌کردم و برنامه‌هایی برای استخراج آمارهای بیماران می‌نوشتم.
تارژان پس از دوره دبیرستان، به تحصیل ریاضیات در دانشگاه کالیفرنیا (CalTech) پرداخت ولی تمام واحدهای علوم رایانه را نیز برداشت.
::||{picture=img/daneshnameh_up/0/03/5.jpg}{picture=img/daneshnameh_up/1/18/6.jpg}::
::شکل1:یک گراف مسطح.گراف A را می توان طوری دوباره ترسیم کرد که لبه هایش همپوشانی نداشته باشند.(گراف B)||::
«به نظر من، علوم رایانه، نوع کاربردیتر ریاضیات بود و علاقه‌ام به آن نیز به همین خاطر بود. در ابتدا به هوش مصنوعی علاقه‌مند شدم و این بیشتر از دید منطق و اثبات قضایا بود. ولی هنگامی که در دوره فوق‌لیسانس خود در دانشگاه استنفورد درس هوش مصنوعی را گرفتم، برخلاف تصور اولیه، موضوعات درس را خیلی نادقیق یافتم.
در آن زمان، دانشگاه استنفورد از داشتن برخی از پیشتازان علوم رایانه، نظیر دونالد کنوث و جان مک‌کارتی به خود می‌بالید.
«نخستین الهام‌بخش من کنوث بود. الهام‌بخشی از این جهت که تمرکز کاری‌اش بر روی تحلیلهای بسیار دقیق بود. او همیشه به دقت و موشکافی ریاضیات و به دست آوردن نتایج دقیق علاقه‌مند بوده است.»
الهام‌بخش بعدی تارژان، چان هاپکرافت بود که در آن زمان برای گذراندن فرصت مطالعاتی از دانشگاه کورنل به استنفورد آمده بود. او در تابستان قبل از شروع سال دوم تحصیل تارژان به استنفورد آمد و تصادفاً اتفاق کار مشترکی در اختیار آنها قرار داده شد. همکاری علمی آن دو خیلی زود شروع شد و سرانجام به دریافت جایزه تورینگ در سال 1986 انجامید.
«من درس پردازش نمادی جان مک‌کارتی را گرفتم که عمدتاً به معرفی زبان لیسپ اختصاص داشت. یکی از تمرینهایی که به ما داد این بود که برنامه‌ای برای تعیین مسطح بودن یک گراف بنویسیم.
من در آن‌هنگام، هیچ تصور خاصی از این مساله نداشتم. فقط دانشجویی بودم که به دنبال حل مسائل جالب می‌گشتم.»
!تسطیح گراف
گراف، مجموعه‌ای از گره‌ها و لبه‌های بین آنهاست. (در گراف شکل 1، گره‌ها با دایره‌های کوچک نشان داده شده‌اند. لبه‌ها، خطوط متصل‌کننده آنها هستند.) از گرافها برای نمایش بسیاری از پدیده‌های مختلف دنیای واقعی استفاده می‌شود. برای نمونه، گره‌ها می‌توانند نمایشگر مولکولها و لبه‌ها نشانگر پیوندهای مولکولی باشند. یا آن که گره‌ها ممکن است نشانگر مردم و لبه‌ها بیانگر ارتباط آشنایی بین آنها باشند.
برای برخی کاربردهای خاص، این که لبه‌ها همپوشانی نداشته باشند اهمیت دارد. برای نمونه، در طرح مدار، همپوشانی لبه‌ها (سیمها) ممکن است باعث اتصال کوتاه شود. بنابراین، سوالی که طبیعی به نظر می‌رسد این است که آیا می‌توان یک گراف را طوری ترسیم کرد که تمام لبه‌هایش محفوظ بمانند ولی همپوشانی نداشته باشند؟ چنین گرافی را مسطح (یا مستوی) می‌نامند. در شکل 1، لبه‌ها در گراف A همپوشانی دارند ولی ترسیم دوباره گراف به نحوی که لبه‌ها همپوشانی نداشته باشند امکانپذیر بوده است، که این امر با گراف B نشان داده شده است.
آزمون تعیین این که یک گراف، مسطح است یا نه به اویلر، ریاضیدان معروف قرن هجدهم باز می‌گردد. این ریاضیدان سوئیسی نشان داد که اگر تعداد گره‌ها N باشد، آنگاه هیچ گرافی با 6 – N3 یا بیشتر لبه وجود ندارد که مسطح باشد (N بزرگتر یا مساوی 3).
در سال 1930، کوراتوسکی ریاضیدان لهستانی نشان داد که هر گراف غیرمسطح باید شامل گرافی با اتصالات نشان داده شده در یکی از گرافهای شکل 2 باشد. مک‌کارتی به دانشجویان توصیه کرده بود که از شرط کوراتوسکی در برنامه‌هایشان استفاده کنند. تارژان خیلی زود متوجه شد که الگوریتم حاصله بسیار ناکارآمد خواهد شد. آزمون کوراتوسکی قابل تبدیل به الگوریتم هست ولی زمان اجرای این الگوریتم، متناسب با تعداد گره‌های گراف به توان 6 خواهد بود. بنابراین، برای گرافی با 100 گرم مستلزم هزار میلیارد مرحله خواهد بود.
#@
@#16:
«آزمون مسطح بودن گراف، سخت فکر مرا به خود مشغول کرده بود. هنگامی که هاپکرافت رسید، من موضوع را با او مطرح کردم و با هم درباره الگوریتمها و کارآیی آنها صحبت کردیم.
::||{picture=img/daneshnameh_up/2/2a/Backup_of_MAT4401-4437.jpg}::
::شکل2: هر گراف غیر مسطح باید دارای زیر گرافی مشابه یکی از این دو گراف باشد||::
هاپکرافت الگوریتمی برای یافتن مولفه‌های به شدت متصل به دست آورد که طرح دقیقی برای شروع نبود. اما چیزی که واقعاً نقطه آغاز خوبی برای ما بود، جستجوی ژرفایی بود. من در مورد آن فکر کردم و سعی کردم اصول و پایه‌های الگوریتم او را با دقت بیشتر درک کنم.»
!مساله Union – Find
تارژان کوته‌زمانی پس از ورود به دانشگاه کورنل، کار بر روی مساله ظاهراً ساده union – find را آغاز کرد. یافتن راه حل سریعی برای این مساله، باعث سرعت بخشیدن به راه حل تعداد زیادی مسائل دیگر می‌شد. در بسیاری از الگوریتمهای گراف، گره‌ها باید به مجموعه‌های مختلفی به نام افراز تقسیم شوند. در خلال مراحل مختلف یک الگوریتم، ممکن است افرازهای مختلف برای تشکیل یک افراز بزرگتر با هم ادغام شوند. برای نمونه، فرض کنید در مساله‌ای لازم باشد که تمام گره‌های یک افراز متصل باشند. یعنی از هر گره به گره‌های دیگر مسیری وجود داشته باشد.
فرض کنید در مرحله‌ای از الگوریتم، مشخص شود که برخی از گره‌های در افراز A توسط یک لبه به برخی گره ها در افراز B متصلند. در این صورت، این دو افراز باید با همدیگر ادغام شده و افرازی را به وجود آورند. که اعضایش برابر با اجتماع اعضای افراز A و اعضای افراز B‌ است.
شکل 3 مثالی از این مورد را نشان می‌دهد. در ابتدا، هر عنصر به عنوان یک مجموعه در نظر گرفته می‌شود (شکل 3، بخش الف). در این مثال، افراز A برابر است با مجموعه {4, 2, 1} و افراز B برابر است با مجموعه‌ی {6,3} و افراز حاصله دارای عناصر {6, 3, 4, 2,1} می‌باشد.
هر بار که دو مجموعه با هم ادغام می‌شوند، یک پیکان از گره کانونیک یکی از آنها به گره کانونیک دیگری (معمولاً از مجموعه کوچکتر به مجموعه بزرگتر) رسم می‌شود (لبه خط‌چین از گره 6 به گره 2 در شکل 3 بخش ب). گره کانونیک یک مجموعه، گرهی است که لبه خروجی نداشته باشد. این بخش union (اجتماع) از الگوریتم Union – Find را تشکیل می‌دهد.
چون عضویت در افرازها در طول زمان تغییر می‌کند، یک ساختار داده‌های خوب باید این امکان را برای الگوریتم فراهم آورد که به سادگی بتوان فهمید دو گره در یک زمان خاص متعلق به یک افراز هستند یا نه. ساختار به کار رفته در بخش (ب) شکل 3، مثالی از یک up – tree (بالادرخت) است. این نام در سال 1964 توسط گالر و فیشر برای ساختاری که در آن، شناسه افراز، گرهی است که لبه خروجی ندارد پیشنهاد شد. برای تشخیص این که دو گره به یک افراز تعلق دارند یا نه می‌توان لبه‌های جهت‌دار را تا شناسه افراز تعقیب کرد. به عبارت دیگر، برای تعیین این که دو گره به یک مجموعه تعلق داشته باشند، می‌توان به سادگی بررسی کرد که آیا آنها گره کانونیک یکسانی دارند یا نه. این، بخش find از الگوریتم Union – Find‌ است.
بنابر آنچه گفته شد 2 = (3)find و 2 = (1)find و در نتیجه آنها در یک مجموعه قرار دارند. در حالی که 5=(5)find (چون هیچ لبه خروجی ندارد). و بنابراین 5 در مجموعه متفاوتی از 6 و 3 قرار دارد.
هر عمل find، مسیری که به شناسه افراز وجود دارد را تا حد ممکن کوتاه می‌کند. این کار اضافی که فشرده‌سازی مسیر نامیده می‌شود بدین خاطر انجام می‌شود که عملیات union و find بعدی را تسریع کند. بخش (ب) شکل 3 نشان می‌دهد که چگونه الگوریتم هاپکرافت – اولمان از فشرده‌سازی مسیر برای کوتاه‌ کردن مسیر از 3 به 2 استفاده می‌کند. بدین ترتیب، عملیات find بعدی از 3، تنها به یک مرحله نیاز خواهد داشت.
::||{picture=img/daneshnameh_up/f/fe/7.jpg}::
::{picture=img/daneshnameh_up/1/15/2.jpg}::
::{picture=img/daneshnameh_up/7/79/3.jpg}::
::شکل 3: مساله Union-Find||::
#@
@#16:
نقش union – find در بسیاری از الگوریتمها شبیه نقش آسانبر (آسانسور) در یک آسمانخراش است. اگر یک آسمانخراش، آسانبر سریع نداشته باشد برای ساکنان آن بسیار ناراحت‌کننده است. بدین دلیل، یافتن سریعترین الگوریتم ممکن برای union – find نیز اهمیت بسزایی دارد. این کار، نیازمند تحلیل زمانی بسیار دقیقی است که توسط تارژان صورت گرفت.
پیش از آن، هاپکرافت و اولمان ظاهراً ثابت کرده بودند که این مساله دارای یک حد بالای زمانی خطی است. حد بالای زمانی خطی در اینجا نیز مانند مساله مسطح بودن گراف به این معنی است که با دو برابر کردن اندازه مساله، زمان محاسبات هم دو برابر خواهد شد. در سال 1973، مایک فیشر از دانشگاه ییل، اشکاری را در اثبات هاپکرافت – اولمان نشان داد. تارژان به این مساله علاقه‌مند شد و کار بر روی آن را آغاز کرد. او ابتدا ثابت کرد که وارون تابع اَکِرمن، حد پایینی مساله است. به عبارت دیگر، ثابت کرد که هیچ الگوریتمی خطی برای این مساله وجود ندارد. سپس ثابت کرد که این حد پایینی، حد بالایی مساله نیز هست. او این مورد را با نشان دادن یک الگوریتم که این مقدار زمان می‌گرفت نشان داد. تارژان در این‌باره می‌گوید:
«این جالبترین چیز در مورد این مساله بود. هیچ راهی وجود نداشت که بتوان چنین نتیجه‌ای را پیش‌بینی کرد. اغلب مردم عقیده داشتند که زمان اجرای این الگوریتم خطی است.»
البته این عقیده مردم تا حدی هم به واقعیت نزدیک بود. تابع اکرمن که در یک شاخه پیشرفته ریاضیات به نام نظریه بازگشت‌پذیری مطرح شده است، به نحو فوق‌العاده سریعی رشد می‌کند. بنابراین وارون تابع اکرمن، فوق‌العاده کند رشد می‌کند و نزدیک رشد خطی است.
اما در اینجا نیز همانند مساله مسطح بودن گراف، نتیجه اعلام شده توسط تارژان، بسیار تعجب‌انگیز بود. زیرا تا آن زمان، هیچکس گمان نمی‌کرد که تابع اکرمن، کاربردی در زندگی واقعی داشته باشد. این باعث شد تا پژوهشگران نگاه جدیتری به روش ابداعی تارژان برای تحلیل الگوریتمها بیندازند.
تحلیل الگوریتم union- find بسیار مشکل است زیرا عمل find‌ چنانچه مسیر فشرده شده باشد (بخش پ شکل 3)، تنها یک پیمایش نیاز دارد ولی اگر مسیر فشرده نشده باشد ممکن است نیازمند پیمایشی طولانی باشد.
در روشهای تحلیلی که تا آن زمان به کار می‌رفت (از جمله روشی که توسط خود تارژان و هاپکرافت برای مساله مسطح بودن استفاده شد)، پژوهشگران پیچیدگی یک الگوریتم را با ضرب کردن تعداد عملیات در زمان بدترین حالت هرکدام، اندازه‌گیری می‌کردند. این روش محافظه‌کارانه، معمولاً درست کار می‌کرد. تارژان مشاهده کرد که این روش استاندارد تحلیل الگوریتمها، به زمان بزرگ و گمراه‌کننده‌ای برای این مساله می‌انجامد.
استدلال او این بود که در حالی که یک عمل find‌ ممکن است زمانی طولانی بگیرد، ولی می‌تواند زمان عملیات find بعدی را با فشرده‌سازی مسیر، کاهش دهد.
«نکته این است که یک دنباله طولانی از عملیات روی یک ساختار داده وجود دارد. ما به یک عمل منفرد علاقه‌مند نیستیم بلکه به زمان میانگین هر عمل در کل دنباله فکر می‌کنیم. کار اضافی یک عمل find، در عملیات بعدی find که از آن بهره‌مند می‌شوند، مستهلک می‌شود.»
همان‌طور که جستجوی ژرفایی به صورت یک روش الگوریتمی استاندارد درآمده است، استهلاک نیز به عنوان یک روش تحلیل استاندارد پذیرفته شده است و در بسیاری از الگوریتمها که در آن، یک عمل بر روی عملیات بعدی تاثیر می‌گذارد کاربرد دارد.
!رقابت‌پذیری
مسطح بودن گراف، جریان شبکه‌ای، و سایر مسائلی که تارژان تا اوایل دهه 1980 روی آن کار کرده بود، دارای پاسخهای صریح و معینی بودند. یک گراف یا مسطح است یا نیست، جریان در شبکه یا بیشینه است یا نیست. ولی در نقطه مقابل، برخی مسائل به جواب معین درست یا نادرست منجر نمی‌شوند و باید مزیت نسبی پاسخها را در مقایسه با هم در نظر گرفت.
تشبیه زیر می‌تواند به درک بهتر مطلب کمک کند. نویسنده ستون سرمایه‌گذاری یک روزنامه را در نظر بگیرید. از نظر ما، کار او هنگامی خوب است که پیشنهادهای خوبی برای خرید سهام بدهد. یکی از معیارهایی که می‌توانیم باری بررسی کیفیت کار این نویسنده به کار بگیریم، در نظر گرفتن موفقیت سرمایه‌گذاری از طریق انجام دادن توصیه‌های او در مقایسه با گوش دادن به توصیه‌های غیبگویی است که اطلاعاتش از آینده صحیح و کامل است. هر چند چنین غیبگویی وجود خارجی ندارد ولی استاندارد خوبی برای مقایسه در اختیار می‌گذارد. تارژان و اسلیتور نیز دقیقاً‌ چنین استاندارد مقایسه‌ای برای مساله مهم مدیریت میانگیر ارائه کردند.
هر رایانه دارای حافظه سریعی به نام RAM (حافظه با دستیابی تصادفی) و یک حافظه از نوع دیگر به نام دیسک است که 1000 بار کندتر از قبلی است. چون RAM نمی‌تواند تمامی داده‌های مورد نیاز کاربر را در خود جای دهد، هدف مدیریت میانگیر، نگهداری آن داده‌هایی در میانگیر RAM است که به احتمال زیاد در آینده نزدیک مورد استفاده خواهند بود. از آنجا که هیچ الگوریتمی اطلاع از آینده نزدیک مورد استفاده خواهند بود. از آنجا که هیچ الگوریتمی اطلاع از آینده ندارد، الگوریتمهای واقعی سعی می‌کنند برای رسیدن به این هدف، حدسیاتی بر پایه تاریخچه مراجعات قبلی بزنند. متداولترین و محبوبترین این الگوریتمها، LRU (با کمترین استفاده در گذشته) نام دارد. در این روش، زمانهای مراجعه به هر صفحه حافظه ثبت می‌شود و برای جایگزینی، صفحه‌ای انتخاب می‌شود که دارای قدیمیترین زمان مراجعه باشد. فرضیه‌ای که در پشت روش LRU وجود دارد این است که صفحاتی از حافظه که اخیراً توسط برنامه شما مورد مراجعه قرار گرفته‌اند، به احتمال زیاد بزودی نیز دوباره مورد مراجعه قرار خواهند گرفت. گذشته آینه آینده است.
#@
@#16:
«فرض کنید شما از آینده اطلاع دارید و تمامی دنباله مراجعات بعدی به صفحات را می‌دانید. در این صورت،‌ بهترین راهبرد صفحه‌بندی چه خواهد بود؟ این کار توسط بلادی در شرکت آی‌بی‌ام در دهه 1960 انجام شد. الگوریتم بلادی، صفحه‌ای را جایگزین می‌کرد که استفاده بعدی از آ‌ن در دورترین زمان در آینده بود. اما این راهبرد برون‌خط (غیبگویانه)، قابل پیاده‌سازی نیست زیرا اطلاع از آینده وجود ندارد. سوالی که در اینجا مطرح می‌شود این است که چگونه می‌توان با یک راهبرد ساده و بر خط به نتیجه قابل قبولی در مقایسه با بهترین راهبرد برون خط دست یافت؟
اسلیتور، واژه رقابتی را برای این مورد پیشنهاد کرد. یک الگوریتم بر خط، رقابتی است. چنانچه کارآیی‌اش در محدوده ضریب ثابتی از بهترین الگوریتم برون‌خط قرار داشته باشد.»
تارژان و اسلیتور نشان دادند که عملکرد الگوریتم LRU با در نظر گرفتن این معیار، قابل قبول و خوب است. الگوریتم LRU با میانگیری به اندازه S، حداکثر دو برابر الگوریتم غیبگو (با میانگیری به اندازه 2/S ) جایگزینی صفحه خواهد داشت. این کار تارژان و اسلیتور، معیار خوبی برای الگوریتمهای بر خط زمانبندی، توزیع منابع و مسائل مشابه، به دست داد.
!ساختار داده های ماندگار
در اوایل دهه 80، تارژان همزمان با ادامه پژوهشهایش در آزمایشگاههای بل، در دانشگاه نیویورک نیز به عنوان استاد میهمان، تدریس می‌کرد. او با همکاری نیل سارناک، دانشجوی دکتری دانشگاه نیویورک اسلیتور و جیمز دریسکول، دانشجوی دانشگاه کارنگی ملون، کار بر روی ساختار داده‌هایی با دوره عمر طولانی را آغاز کرد. او در این‌باره می‌گوید:
«مساله،‌ ساختن ساختار داده‌هایی بود که بتوان سابقه قبلی داده‌ها را نیز در آن نگاهداری کرد و البته با کارآیی بالا و بدون کپی کردن کل ساختار داده ها.»
::||{picture=img/daneshnameh_up/d/d0/4.jpg}::
::شکل4:ساختار داده های ماندگار تارژان-سارناک||::
ساختار داده‌ها، ساختاری است که در حافظه رایانه ذخیره می‌شود تا دستیابی به داده ها را سرعت بخشد. یک نمونه از ساختار داده‌ها، درختها هستند که با سرعت زیادی داده ها را در اختیار می‌گذارند. برای مثال، متداولترین ساختار داده‌ها در سامانه‌های پایگاه داده‌ها B-Tree‌ است که توسط رایانه‌دان آلمانی رودلف بایر و مک‌کرایت آمریکایی ابداع شده و در اوایل دهه 70 در شرکت بوئینگ توانست یک درخواست را در میان 100 میلیارد درخواست دیگر، در کمتر از 01/0 ثانیه پیدا کند. یعنی حدوداً 10000 بار سریعتر از آن‌که می‌خواستیم درخواستها را یکی‌یکی (دنباله‌ای) در نظر بگیریم. تارژان و همکارانش، ساختار داده‌های خود را ساختار داده‌های ماندگار نامیدند. ساختار داده‌های ماندگار،‌تقریباً به سرعت ساختار داده‌های معمولی برای داده‌های فعلی است، به اضافه این‌که برنامه‌ها (در نتیجه کاربران) را قادر می‌سازد که به وضعیت داده‌ها در گذشته نیز، با کمی هزینه اضافی، دسترسی داشته باشند.
در شکل 4، مثالی از یک ساختار داده‌های ماندگار، ارائه شده توسط تارژان و سارناک نشان داده شده است. چنانچه بخواهیم داده‌های نشان داده شده توسط گره X را تغییر دهیم، کارآمدترین روش انجام این کار، جایگزین ساختن X با مقدار جدید X' است. مشکل این روش این است که دیگر نمی‌توان به وضعیت پایگاه داده‌ها قبل از جایگزینی (لحظه 1) دسترسی داشت. اما با استفاده از روش تارژان – سارناک، برنامه می‌تواند به وضعیت لحظه 1 با شروع از ریشه در لحظه 1 و به وضعیت لحظه 2 با شروع از ریشه در لحظه 2 دسترسی داشته باشد. چون بسیاری از داده‌ها بین لحظه 1 و 2 بدون تغییر باقی مانده‌اند، ساختار داده ها برای لحظه 2 فقط اختلافها را نگهداری می‌کند. به جای جایگزین ساختن X با X' و از دست دادن سابقه، برنامه یک گره جدید برای نگهداری X' و سپس گره‌های جدیدی برای تمام پیشینیان X'‌ بنا می‌کند. برای اغلب ساختارها، این‌کار، سربار خیلی زیادتری نسبت به مکانیابی X و جایگزین ساختن آن با X'‌ ایجاد نمی‌کند.
این ایده کاربردهای زیادی در هندسه محاسباتی و پردازش موازی دارد اما کاربرد اصلی‌اش در پایگاه داده‌های زمانی است. این پایگاه داده‌ها برای باز تولید تصویری از گذشته، با سرعت و کارایی مناسب، طراحی شده‌اند.
!الگوی کار
تارژان در بسیاری از مسائلی که بر روی آنها کار کرده است، الگوی مشترکی یافته است:
«بیش از نیمی از کار، انتخاب مسائل است نه پیدا کردن راه حل برای آنها، اگر مسائل درستی را انتخاب کنید و سوالات درستی بپرسید، بیشتر کار را انجام داده‌اید.
مسائلی را انتخاب کنید که از کاربردها برخاسته باشند. خطری که همواره وجود دارد افتادن در شاخه باریکی از علوم نظری است که از خود تغذیه می‌کند و حاصل ملموسی برای دنیای واقعی ندارد. من همیشه سعی کرده‌ام بر روی مسائلی کار کنم که اهمیت عملی و تجربی داشته باشند.
از سوی دیگر، شما هیچگاه نمی‌توانید بگویید چه موقع ایده‌ای که در یک محدوده ایزوله به وجود آمده است با یک چیز دیگر ارتباط پیدا می‌کند. معجزه ریاضیات و علوم نظری رایانه در کشف ارتباطات پیش‌بینی نشده است. ش

تاریخ شماره نسخه کاربر توضیح اقدام
 شنبه 01 مهر 1385 [13:35 ]   5   زینب معزی      جاری 
 شنبه 01 مهر 1385 [13:24 ]   4   زینب معزی      v  c  d  s 
 یکشنبه 01 مرداد 1385 [08:55 ]   3   سعید صدری      v  c  d  s 
 یکشنبه 01 مرداد 1385 [08:54 ]   2   سعید صدری      v  c  d  s 
 یکشنبه 01 مرداد 1385 [08:52 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..