Mehdi Ghiyasvand

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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