برنامهسازی پیشرفته
Advanced Programming
شماره درس: ۲۰۱۲ | تعداد واحد: ۳ |
نوع درس: نظری | پیشنیاز: برنامهسازی پایتون |
اهداف درس
هدف از این درس، آشنایی دانشجویان با زبانهای برنامهسازی سی و سی++ و نحوهی ایجاد برنامههای سریع و کارآ در این زبانها است. دانشجویان در این درس با برخی تکنیکهای ویژه که در برنامهنویسی حرفهای و مسابقات برنامهسازی مورد استفاده قرار میگیرد نیز آشنا میشوند. این درس بیشتر جنبه عملی دارد و آزمون پایان دوره آن نیز عملی خواهد بود.
ریز مواد
- مفاهیم اولیه (۱ جلسه)
- تاریخچهی 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)
- الگوریتمهای هندسی (۱ جلسه)
- اعداد مختلط و کار با آنها
- تقاطعها
- ضرب داخلی
- ضرب خارجی
- مساحت چندضلعی
- جمع زوایا (برای چک پادساعتگرد بودن)
ارزیابی
- تمرینهای عملی: ۸ نمره
- آزمونهای میان و پایاندوره: ۱۲ نمره
- فعالیت اضافی (مانند شرکت در مسابقهی برنامهسازی): ۱ نمرهی اضافی
مراجع
- P. Deitel, H. Deitel. C++: How to Program. 10th edition, Prentice Hall, 2016.
- B. W. Kernighan and D. M. Ritchie. The C Programming Language. 2nd edition, Prentice Hall, 1988.
- S. Halim, F. Halim. Competitive Programming. 4th edition, 2020.
- A. Engel. Problem-Solving Strategies. Springer, 1998.