Курс призначений для початківців програмістів, студентів, які вивчають комп'ютерні науки, а також для IT-інженерів, які бажають зрозуміти, як вирішувати комбінаторні завдання і оптимізувати алгоритми.
опис курсу
Курс складається з двох частин. У першій ми розглядаємо способи "універсального" вирішення комбінаторних задач методом повного перебору і способи оптимізації цих алгоритмів. У другій частині ми задіємо метод динамічного програмування з рекурсією, який дозволить створювати воістину швидкі та ефективні алгоритми пошуку.
комбінаторні алгоритми (Уроки 1-5).
Комбінаторика вивчає варіанти розміщення об'єктів. Комбінаторні алгоритми мають на увазі перебір всіх варіантів розташування об'єктів і пошук оптимального рішення, яке задовольняє заданим умовам. Комбінаторні завдання в програмуванні зустрічаються дуже часто. Завдання мінімум для будь-якого програміста-вміти їх вирішувати повним перебором і застосовувати методи оптимізації цих алгоритмів.
Динамічне програмування. (Уроки 6-10).
Алгоритми повного перебору пишуться просто, але працюють занадто довго. Застосовуючи метод динамічного програмування можна значно прискорити час пошуку рішення. Ідея полягає в тому, щоб розділити початкове завдання на кілька таких же, але з меншими початковими даними. Для створення таких алгоритмів зазвичай використовується рекурсія.
В курсі гармонійно переплітається теорія і практика, розглядаються методи оптимізації алгоритмів, є візуалізація циклічних і рекурсивних алгоритмів, розглянуті способи створення штучного інтелекту для гри в настільну гру, а також контрольна робота у вигляді сеансу "спортивного програмування" для закріплення матеріалу.
Алгоритми, які ми розглядаємо в даному курсі, можна реалізувати на будь-якій мові програмування. Ми будемо писати програми на мові С#, базових знань якого буде цілком достатньо для розуміння матеріалу.
- цикли. Графічні візерунки.
На цьому уроці ми будемо доводити навик використання циклів до досконалості. Щоб досягти інтуїтивного розуміння, краще "один раз побачити", тому ми будемо малювати химерні візерунки, використовуючи комбінації вкладених циклів і умов. - прості числа. Оптимізація алгоритмів.
На цьому уроці ми напишемо алгоритм генерації простих чисел, а потім почнемо його оптимізувати різними способами, заміряючи час роботи кожного варіанту. - прості завдання на перебір варіантів.
На цьому уроці ми вирішимо кілька комбінаторних завдань методом "грубої сили", а потім розглянемо ідеї оптимізації кожного алгоритму. - гра зі штучним інтелектом. Пошук кращого ходу перебором.
На цьому уроці ми створимо просту гру, а потім навчимо комп'ютер в неї грати: створимо штучний інтелект для пошуку хорошого ходу. - Контрольна робота на перебір варіантів.
На цьому уроці буде"спортивне програмування". У Вас буде декількох комбінаторних задачок на перебір варіантів і обмежений час. Подивимося, чому ви навчилися і скільки задачок встигнете вирішити! - рекурсія. Побудова фракталів.
На цьому уроці ми будемо доводити навик використання рекурсії до досконалості. Щоб досягти інтуїтивного розуміння, краще "один раз побачити", тому ми будемо малювати фрактали - повторювані візерунки, використовуючи алгоритми з рекурсивним викликом. - Складні функції. Оптимізація алгоритмів.
На цьому уроці ми напишемо алгоритми обчислення деяких алгебраїчних функцій. а потім почнемо їх оптимізувати різними способами, заміряючи час роботи кожного варіанту. - складні завдання на перебір варіантів.
На цьому уроці ми вирішимо кілька комбінаторних завдань методом динамічного програмування з використанням рекурсії і без неї. - гра зі штучним інтелектом. Пошук альфа-бетта відсіканням.
На цьому уроці ми продовжимо створення штучного інтелекту для нашої гри. Але цього разу ми скористаємося рекурсивним пошуком вглиб з відсіканням помилкових рішень. - Контрольна робота на динамічне програмування.
На цьому уроці буде"спортивне програмування". У Вас буде декількох комбінаторних задачок на динамічне програмування і обмежений час. Подивимося, чому ви навчилися і скільки задачок встигнете вирішити!
Тривалість: 15 год.
Кількість уроків: 10 занять
викладачі курсу: Євген Волосатов
https://privatelink.de/?https://edu.cbsystematics.com/ru/courses/algorithms-and-data-structures-practice