ترکیبیات

تکنیک های تصادفی در الگوریتم های ترکیبی

Randomized techniques in combinatorial algorithms

دانلود کتاب Randomized techniques in combinatorial algorithms (به فارسی: تکنیک های تصادفی در الگوریتم های ترکیبی) نوشته شده توسط «Zito M.A.A.»

اطلاعات کتاب تکنیک های تصادفی در الگوریتم های ترکیبی

موضوع اصلی: ریاضیات – ترکیبیات

نوع: کتاب الکترونیکی

نویسنده: Zito M.A.A.

زبان: english

فرمت کتاب: DJVU (قابل تبدیل به سایر فرمت ها)

سال انتشار: 1999

تعداد صفحه: 150

حجم فایل: 963 کیلوبایت

نوبت چاپ: PhD Thesis

توضیحات کتاب تکنیک های تصادفی در الگوریتم های ترکیبی

تکنیک های احتمالی روز به روز در علوم کامپیوتر اهمیت بیشتری پیدا می کنند. برخی از آنها برای تجزیه و تحلیل الگوریتم ها مفید هستند. هدف این پایان نامه توصیف و توسعه کاربردهای این تکنیک ها می باشد. ما ابتدا به مشکل تولید یک نمودار به طور تصادفی از مجموعه همه نمودارهای بدون برچسب با n راس، با استفاده از الگوریتم‌های موازی کارآمد نگاه می‌کنیم. مدل ما از محاسبات موازی، ماشین دسترسی تصادفی موازی معروف (PRAM) است. الگوریتم های ارائه شده در اینجا جزو اولین الگوریتم های موازی برای تولید تصادفی ساختارهای ترکیبی هستند. ما دو الگوریتم موازی مختلف را برای تولید یکنواخت نمودارهای بدون برچسب ارائه می کنیم. الگوریتم‌ها در زمان O(log2 n) با احتمال زیاد روی کالسکه EREW با استفاده از پردازنده‌های O(n2) اجرا می‌شوند. در نهایت به دو مسئله تطبیق نظری نمودار نگاه می کنیم. ما ابتدا پیچیدگی محاسباتی این مسائل و تقریب الگوریتمی راه‌حل‌های بهینه، در کلاس‌های خاص نمودارها را مطالعه می‌کنیم. ما همچنین الگوریتمی را استخراج می کنیم که یکی از آنها را در زمان خطی به طور بهینه حل می کند، زمانی که نمودار ورودی یک درخت است و همچنین تعدادی از نتایج غیرقابل تقریب است. سپس چند فرض در مورد توزیع ورودی می‌سازیم، ساختار مورد انتظار این تطابق‌ها را مطالعه می‌کنیم و نتایج تقریب بهبود یافته‌ای را در چندین مدل از نمودارهای تصادفی به دست می‌آوریم.

Probabilistic techniques are becoming more and more important in Computer Science. Some of them are useful for the analysis of algorithms. The aim of this thesis is to describe and develop applications of these techniques. We first look at the problem of generating a graph uniformly at random from the set of all unlabelled graphs with n vertices, by means of efficient parallel algorithms. Our model of parallel computation is the well-known parallel random access machine (PRAM). The algorithms presented here are among the first parallel algorithms for random generation of combinatorial structures. We present two different parallel algorithms for the uniform generation of unlabelled graphs. The algorithms run in O(log2 n) time with high probability on an EREW PRAM using O(n2) processors. Finally we look at two graph theoretic matching problems. We first study the computational complexity of these problems and the algorithmic approximability of the optimal solutions, in particular classes of graphs. We also derive an algorithm that solves one of them optimally in linear time when the input graph is a tree as well as a number of non-approximability results. Then we make some assumptions about the input distribution, we study the expected structure of these matchings and we derive improved approximation results on several models of random graphs.

دانلود کتاب «تکنیک های تصادفی در الگوریتم های ترکیبی»

مبلغی که بابت خرید کتاب می‌پردازیم به مراتب پایین‌تر از هزینه‌هایی است که در آینده بابت نخواندن آن خواهیم پرداخت.

📖 خرید این کتاب

برای دریافت فایل و اطلاع از قیمت، روی یکی از دکمه‌های زیر کلیک کنید تا پیام آماده برای شما ارسال شود:

پس از ارسال پیام، قیمت و لینک دریافت فایل در اسرع وقت برای شما ارسال خواهد شد.

برچسب ها

دیدگاهتان را بنویسید

مبلغی که بابت خرید کتاب می‌پردازیم به مراتب پایین‌تر از هزینه‌هایی است که در آینده بابت نخواندن آن خواهیم پرداخت.
کتابخانه دیجیتال بَلیان