مهدی قیاسوند

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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