برنامه‌سازی پیشرفته

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

• مفاهیم اولیه (۱ جلسه)
  • تاریخچه‌ی C/C++
  • مراحل ایجاد، کامپایل و اجرای برنامه
  • مقایسه زمان اجرای برنامه‌ها در سی و پایتون
• مهاجرت از پایتون به سی (۱ جلسه)
  • متغیرها، انواع داده
  • ورودی و خروجی با استفاده از جویبار‌ها
  • دستورهای انتخاب (if, if/else, switch)
  • دستورهای تکرار (while, for, do/while)
  • تبدیل داده‌ها و عملگرها
• فرمت‌بندی ورودی/خروجی (۱ جلسه)
  • قالب‌بندی خروجی با printf
  • کنترل دقت نمایش اعداد در خروجی
  • چاپ اعداد صحیح، اعداد ممیزدار، رشته‌ها، و کاراکترها
  • خواندن قالب‌بندی شده از ورودی با scanf
• توابع (۲ جلسه)
  • الگوی توابع (prototype)
  • پرونده‌های header
  • انواع فراخوانی توابع (با مقدار و با ارجاع)
  • توابع درون‌خط (inline)
  • تعریف مقدار پیش فرض در توابع
  • سربارگذاری توابع
  • توابع ریاضی و تصادفی
  • توابع بازگشتی
• آرایه‌ها و اشاره‌گرها (۲ جلسه)
  • تعریف و به‌کارگیری آرایه‌ها
  • عملگرهای اشاره‌گری
  • فراخوانی با ارجاع توسط اشاره‌گرها
  • استفاده از const در اشاره‌گرها
  • محاسبات آدرس بر روی اشاره‌گرها (جمع، تفریق)
  • ارتباط بین اشاره‌گرها و آرایه‌ها
  • آرایه‌ای از اشاره‌گرها
• رشته‌ها (۱ جلسه)
  • توابع رشته‌ای
  • دست‌کاری رشته‌ها
  • تبدیل کاراکترها
• رده‌ها (۱ جلسه)
  • اعضای داده‌ای و توابع عضو
  • حوزه‌های public و private
  • سازنده‌ها
  • مقداردهی اشیاء
  • ارسال/دریافت اشیاء به/از توابع
• پرونده‌ها (۱ جلسه)
  • خواندن و نوشتن در پرونده‌های ترتیبی
  • جویبار‌های ورودی و خروجی
• قالب‌ها (۱ جلسه)
  • مفهوم Template در توابع
  • بارگذاری قالب‌ها در توابع
  • قالب در کلاس‌ها
• کتابخانه استاندارد STL (‍۱ جلسه)
  • آشنایی با STL
  • کانتینرهای ترتیبی: vector, deque, list
  • کانتینرهای انجمنی: set, multiset, map, multimap
  • آداپتورها: stack, queue, priority_queue
• برنامه‌سازی حرفه‌ای (۱ جلسه)
  • تعیین مرتبه زمان اجرا بر اساس محدودیت‌های ورودی
  • تکنیک‌های Debugging
• داده‌ساختارهای پیشرفته (۲ جلسه)
  • استک و استفاده حرفه‌ای از آن
  • هرم کمینه
  • Fenwick Tree
• روش توان‌های ۲ (۱ جلسه)
  • پیش پردازش $n\log n$
  • پیدا کردن کمینه بازه در زمان ثابت
  • LCA
• الگوریتم‌های گراف (۲ جلسه)
  • DFS و خواص جالب آن
  • پیدا کردن تور اویلری
  • مرتب‌سازی توپولوژیکی
  • حل 2-SAT در زمان خطی
• کار با بیت‌ها (۱ جلسه)
  • به عنوان یک مجموعه
• الگوریتم‌های ریاضی (۱ جلسه)
  • جبر خطی: n معادله و m مجهول
  • تقارن گروه‌ها: لم برنساید
• نظریه اعداد (۱ جلسه)
  • ب.م.م و معادله $ax+by=c$
  • باقی‌مانده چینی
  • ریشه اولیه و میدان
  • عدد اویلر
• جایگشت‌ها (۱ جلسه)
  • گراف جایگشت
• الگوریتم‌های پویا (۲ جلسه)
  • الگوریتم‌های پویای نمایی
  • الگوریتم‌های پویا روی درخت (همراه با dfs)
• الگوریتم‌های هندسی (۱ جلسه)
  • اعداد مختلط و کار با آن‌ها
  • تقاطع‌ها
  • ضرب داخلی
  • ضرب خارجی
  • مساحت چندضلعی
  • جمع زوایا (برای چک پادساعتگرد بودن)

• تمرین‌های عملی: ۸ نمره
• آزمون‌‌های میان و پایان‌دوره: ۱۲ نمره
• فعالیت اضافی (مانند شرکت در مسابقه‌ی برنامه‌سازی): ۱ نمره‌ی اضافی