مهدی قیاسوند

شبکه ای با مجموعه ای از گره های منبع و مقصد داده شده است. فرض کنیم ارسال اطلاعات از گره های منبع به گره های مقصد ممکن است با خطا انجام گیرد. در این پایان نامه، در مبحت نظریه اطلاعات به موضوع حذف یال معکوس قوی و چگونگی تغییر ظرفیت شبکه (در صورتی که فقط یک یال شبکه حذف شود) پرداخته شده است.

در این پایان نامه یک مشخصه نظری گراف از شدنی بودن کدگذاری شبکه ای با دو دوره یک پخشی ساده مورد بحث قرار گرفته است و برای این هدف، مساله کد گذاری روی شبکه های چند پخشی و شبکه هایی با دو دوره یک پخشی شرح داده شده است.

در این پایان نامه، راهبرد تجزیه/ترکیب برای بررسی مساله دو زوجی تک نرخی مورد بررسی قرار گرفته است. بدین ترتیب که حل پذیری مساله دو زوجی تک نرخی توسط چهار زیر مجموعه خاص از شبکه اصلی تعیین شده است. همچنین الگوریتمی با مرتبه چند جمله ای برای تشخیص حل پذیری مساله مورد تحلیل قرار گرفته است.

شبکه جهت دار فاقد دور با چند مبدا و چند مقصد که هر مقصد متقاضی رمزگشایی از مجموع منابع تولید شده در گره های منبع می باشد داده شده است. در این پایانه روشی را توصیف شده است که بتوسط آن می توان یک گراف ساده بدون جهت را جهت استفاده برای ساختن چنین شبکه جمعی استفاده کرد و کران بالایی را در میزان محاسبه آن قرار داد. همچنین، شرایط کافی برای ساختن یک کد شبکه خطی که به این کران بالا می رسد، مورد بررسی قرار گرفته است که توسط آن می توان شبکه های مجموعی ساخت که نرخ محاسبه دلخواه p/q دارند (p و q اعداد صحیح مثبت می باشند).

بحث کدهای قابل بازیابی محلی طی دهه ی اخیر مورد توجه بسیاری از محققان قرار گرفته است. کد قابل بازیابی محلی (کد LRC) یک کد بر روی الفبای محدود است که در آن هر مولفه کدواژه های آن تابعی از تعدادی از مولفه های دیگر است، مجموعه بازیابی را تشکیل می دهند. در این پایان نامه به اثباتو تحلیل کران های پارامترهای نرخ و حداقل فاصله از یک کد LRC پرداخته شده است.

در این پایان نامه، بازی مسیر یابی مورد بررسی قرار گرفته است که در آن هر بازیگر ممکن است مسیری را با هدف کاستن بیشترین تراکم در یال های مسیر خود انتخاب کند. هزینه هر بازیکن، بیشترین تراکم در یال های مسیر و همچنین، هزینه سراسری شبکه بیشترین تراکم در همه یال های شبکه می باشد. دست یابی هر بازیگر به ترافیک کمتر، زمانی به دست می آید که تمام بازیگران به بهترین نتایج خود برسند. این موضوع با برقراری تعادل نش در انتخاب های بازیگران میسر خواهد شد. در تعادل نش، هزینه پایداری برابر یک و هزینه بی قانونی بر اساس مشخصات مکانی شبکه معین می شود.

در این پایان نامه به بازی کیفیت مسیریابی همراه با تعادل نش پرداخته می شود. تعادل نش به به حالت پایداری در یک بازی اطلاق می گردد که با فرض ثابت بودن راهبرد سایر بازیکنان، یک بازیکن با تفییر بازی خود نتواند به شرایط بهتری دست یابد. در این بازی ها، مسیر ها به کلاس های مختلفی تقسیم می شوند که اشتراکی با یکدیگر ندارند. به عبارت دیگر، هر مسیر یه یک کلاس تعلق دارد و نمی تواند هم بازی متعلق به کلاس دیگری باشد. از آنجا که عمل محاسبه تراکم یال ها تنها در کلاس ها انجام می شود، تراکم هر یال تنها توسط مسیرهایی محاسبه می گردد که در یک کلاس یکسان قرار دارند. خروجی بازی توسط معیار هزینه آشوب ارزیابی می شود.

در این پایان نامه، کدهای تعمیر پذیر محلی و کران بالا برای مینیمم فاصله کدهای خطی و غیر خطی مورد بحث قرار می گیرد. تحت شرایط مناسب، مینیمم فاصله کد به کران بالای فاصله خواهد رسید. ثابت می شود که بین کدهای تعمیرپذیر محلی و شبکه جریان، ارتباط وجود دارد. با ارایه مثال، برخی کدهای تعمیرپذیر محلی برای مجموعه ای از پارامتر های کدگذاری بازسازی شده و محلی بودن کدها، مورد بررسی قرار می گیرد.

در این پابان نامه، روش ساخت کدهای محلی بهینه مورد بررسی قرار می گیرد. یک کد خطی C با طول کد n، بعد k و کمترین فاصله d داده شده است. هر کد واژه Cj در کد C می تواندتوسط سمبل های دیگر بازسازی شود که یکی از روش های بهینه و به صرفه در سیستم های ذخیره سازی داده ها محسوب می شود. کران بالایی از مینیمم فاصله ارایه شده و همچنین، توسط چند مثال، روش به صورت عملی مورد بحث قرار گرفته است

در این پایان نامه برای شبکه برای دو-تک پخشی با درجه (2و1) توسط تجزیه ناحیه ای روشی برای تشخیص شدنی بودن ارایه شده است. فرض کنیم یک گراف جهت دار فاقد دور داده شده است که در آن دو گره منبع s1 و s2 و همچنین دو گره مقصد t1 و t2 مشخص می باشند. در گره منبع s1 پیغام x1 ودر گره منبع s2 پیغام x2 تولید می شود. هدف مساله ارسال پیغام x1 به گره مقصد t1 و ارسال دو پیغام x1و x2 به گره مقصد t2 است. در این پایان نامه، ملاک های بر آورده کردن خواسته های گره مقصد مورد بحث قرار می گیرد که آنها را ملاک های شدنی بودن خواسته های مساله نیز می نامند. برای این هدف از ایده های مربوط به روش تجزیه ناحیه ای و روش کد گذاری شبکه استفاده می شود.

در این پایان نامه توسط تجزیه ناحیه ای شبکه به تشخیص شدنی بودن مساله مجموع منابع پرداخته شده است. فرض کنیم که یک گراف جهت دار فاقد دور داده شده است که در آن سه گره منبع و سه گره مقصد به طور خاص مشخص می باشند. در هر گره منیه سیکنال خاصی تولید می گردد. هر گره مقصد، متقاضی دریافت مجموع سیگنال های تولیدی در گره های مبدا می باشد. به این نوع شبکه، شبکه سه منبع-سه مقصد گویند. در این پاین نامه با استفاده از مفهوم ناحیه بندی در شبکه(در بحث ناحیه بندی، مجموعه ای از یال ها و گره در داخل یک ناحیه خاص قرار می گیرند)، شرایط لازم و کافی برای حل پذیری این مساله ارایه می گردد که توسط آنها الگوریتمی با زمان اجرای چندجمله ای براس تشخیص حل پذیری مساله به دست می آید.

در این پایان نامه، کد های اصلاح پذیر محلی با هدف احیای متوالی چندین خرابی مورد بررسی قرار می گیرد. احیای متوالی به این معنی است که تمام کد واژه های خراب می توانند یک به یک احیا شوند و کد واژه احیا شده در احیای کد واژهای خراب دیگر مورد استفاده قرار گیرند. این روش احیا در مقاسیه با روش احیای موازی، بیانگر این است که کد خراب شده برای حداقل سه خرابی دلخواه ایجاد می شود و کران بالای آن به مقدار کارایی کد بستگی دارد. در این پایان نامه، ابتدا یک کران بالا برای نرخ ارسال اطلاعات به دست آمده و سپس دو خانواده باینری تشکیا شده است که برای حداکثر هفت خرابی کارا می باشد.

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

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

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

در این پایان نامه برای سیستم های مخزن توزیع شده عمل رمز نگاری صورت گرفته است.

در این پایان نامه برای مساله مینیمم-ماکسیمم سریع ترین مسیر چند الگوریتم مورد تحلیل قرار گرفته است

در این پایان نامه سریع ترین الگوریتم فعلی برای جریان های ماکزیمم مورد بحث قرار گرفته است

در این پایان نامه برای مساله سریع ترین مسیر و مساله سریع ترین مسیر قابل اطمینان چند الگوریتم مورد تحلیل قرار گرفته است.

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

در این پایان نامه برای ساختار های خاصی از مساله جریان با مینیمم هزینه الگوریتم هایی مورد تحلیل قرار گرفته است

در این پایان نامه حالت چند مسیری بودن مساله جریان ماکسیمم مورد بحث قرار گرفته است.

در صورت مسدود شدن یک یال درختی یک یال جدید به درخت کوتاه ترین مسیر اضافه می شود.

مسیر ضد-ریسک بین گره در گراف های بدون جهت محاسبه می شود

با حذف یک کمان از درخت، کمان مناسب جایگزین آن می شود