سمینار هندسهٔ طیفی گسسته (بهار ۹۵-۹۶)

مشخصات درس

ترم بهار سال تحصیلی ۱۳۹۵-۱۳۹۶
تعداد واحد: ۱ واحد
زمان (احتمالی) جلسه‌های کلاس: یک‌شنبه ۱۷:۰۰ تا ۱۹:۰۰
مقطع: مشترک
مدرس‌ها: امیر دانشگر، محمد هادی فروغمند اعرابی


توجه: اولین جلسهٔ این سمینار یک‌شنبه ۲۴ بهمن ساعت ۱۷:۰۰ برگزار خواهد شد و حضور شما جهت آشنایی با مفاهیم و شکل سمینار و برنامه‌ریزی برای آیندهٔ سیمنار حتما مفید خواهد بود.

توصیف درس

هدف این سمینار آشنایی با «هندسهٔ طیفی گسسته» مبتنی بر مدل گراف‌های متناهی و کاربرهای آن است. مثلا به چند مسئلهٔ به ظاهر نامرتبط زیر توجه کنید:

مسئله محاسبهٔ تبدیل خطی

تبدیل خطی x->A را در نظر بگیرید. به ازای یک ماتریس خاص A، مثلا ماتریسی که تبدیل فوریه را مشخص می‌کند، سوال این‌جاست که کم‌ترین زمان محاسبهٔ این تبدیل خطی چقدر است؟

مسئله کد تصحیح خطا

فرض کنید آلیس می‌خواهد n-بیت اطلاعات را برای باب ارسال کند و می‌داند که نسبت p از بیت‌ها ممکن است در روند ارسال تغییر کند. آلیس می‌خواهد کم‌ترین تعداد بیت را ارسال کند به صورتی که در نهایت باب بتواند n-بیت مورد نظر آلیس را بازسازی کند. کم‌ترین تعداد بیت لازم برای ارسال چقدر خواهد بود؟

کمینه‌سازی بیت‌های تصادفی

فرض کنید الگوریتمی احتمالاتی برای یک مسئلهٔ x در L داریم که اگر x در L باشد، الگوریتم حتما پاسخ درست را می‌دهد و اگر x در L نباشد، الگوریتم به احتمال حداقل ۱/۳ پاسخ صحیح را می‌دهد. کم‌ترین تعداد بیت تصادفی برای تبدیل خطای الگوریتم به خطایی کم‌تر از هر عدد مثبتی چند بیت است؟

خوشه‌بندی

داده‌هایی داریم که ماتریس شباهت بین دوبه‌دوی آن‌ها را می‌شناسیم. به دنبال الگوریتمی هستیم که داده‌ها را به $k$-قسمت خوشه‌بندی کند به صورتی که هر کدام از خوشه‌ها حجیم باشند و شباهت‌شان با یک‌دیگر زیاد باشد.

حجیم‌ترین خم

از میان همهٔ خم‌های بسته روی صفحهٔ مختصات دوبعدی با محیط ثابت، کدام بیشترین مساحت را احاطه می‌کند؟

یک روش برخورد با مسئله‌های مطرح شده، مدل‌سازی مسئله با استفاده از یک شیئ هندسی (نوعا گراف متناهی) و مطالعهٔ خواص ساختاری و هندسی آن از طریق مطالعهٔ عملگرهای خطی طبیعی وابسته به آن شیئ است. هدف اصلی این سمینار معرف روش‌های معمول چنین ابزارهایی است.

برنامهٔ کلاس

این سمینار شامل دوبخش خواهد بود. در بخش اول مدرسین درس، مبانی نظری «هندسهٔ طیفی گسسته» را طبق برنامهٔ تقریبی زیر توضیح خواهند داد. مدل اصلی که درس بر آن اساس توضیح داده می‌شود، مدل گراف متناهی خواهد بود.

  1. تصویر کلی: در مورد این‌که هندسهٔ طیفی گسسته در مورد چیست و چرا این مباحث مهم هستند.
  2. نگاه هندسی به گراف: گراف به عنوان یک شیئ هندسی توصیف می‌شود.
  3. مسئله‌های اصلی: مسئله‌های اصلی که به دنبال حل آن با روش‌های هندسهٔ طیفی گسسته هستیم چیست؟ رابطهٔ مسئله‌های مختلف در حوزه‌های مختلف با یک‌دیگر و توصیف مسئله‌های اساسی در هرکدام از حوزه‌ها نیز توضیح داده می‌شود.
  4. کاربردها: کاربردهایی در احتمال، پیچیدگی محاسبات، خوشه‌بندی، طراحی شبکه‌ها.
  5. مدل ریاضی: مباحث این سمینار چه نتایجی در چه حوزه‌هایی خواهد داشت

در نیمهٔ دوم سمینار، انتظار می‌رود دانشجوها با انتخاب موضوع‌های مورد علاقه خود که در نیمهٔ اول مطرح شده و با اساتید درس نهایی کرده‌اند، در یک جلسه ارائهٔ شخصی خود را انجام بدهند.

پیش‌نیاز

پیش‌نیازهای درس: نظریهٔ گراف و جبر خطی.

در نتیجه در صورتی که با پیش‌نیازهای سمینار آشنا هستید، برای شناخت هندسهٔ طیفی گسسته می‌توانید در این سمینار شرکت کنید.

پیوند به پروندهٔ پی‌دی‌اف شامل متن بالا.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *