Цели и задачи дисциплины
Сформировать у студентов систематическое понимание принципов разработки, анализа и оптимизации алгоритмов, позволяющее обоснованно выбирать и создавать эффективные алгоритмические решения для инженерных задач, в том числе для ресурсоемких задач в сфере искусственного интеллекта, оценивая их вычислительную трудоемкость и потребление ресурсов.
Задачи:
- Освоить фундаментальный аппарат анализа сложности алгоритмов.
- Сформировать навык применения основных методов разработки алгоритмов.
- Научить проводить сравнительный анализ и выбирать ресурсно-эффективные алгоритмы для решения прикладных задач.
Краткое содержание дисциплины
Понятие и свойства алгоритмов. Представления алгоритмов (псевдокод, язык блок-схем).
Структурное и функциональное тестирование. Модульное и интеграционное тестирование.
Основы анализа алгоритмов. Порядок роста сложности алгоритма.
Асимптотический анализ алгоритмов. Худший, средний и лучший случаи алгоритмов.
Временная и пространственная сложность алгоритмов. Примеры анализа сложности алгоритмов.
Анализ циклических алгоритмов.
Анализ рекурсивных функций.
Оптимизация временной и пространственной сложности алгоритмов.
Методы разработки алгоритмов: метод пошаговой детализации (декомпозиции задачи), метод рекуррентных соотношений, метод динамического программирования.
Разработка и выбор эффективных алгоритмов на основе ресурсного анализа (обмен содержимого ячеек, поиск максимума из трех чисел, сортировка трех чисел по месту, возведение числа в целую степень, извлечение квадратного корня)
Ресурсно-эффективные алгоритмы с переменной длиной входа: поиск минимума и максимума в массиве, организация счетчика в массиве, бинарный поиск в отсортированном массиве
Разработка и анализ эффективности алгоритмов для задач: нахождение НОД двух чисел, вычисление факториала, возведение в степень, дискретный логарифм.
Выбор алгоритма умножения длинных целых чисел на основе анализа временной эффективности
Ресурсно-эффективные комбинированные алгоритмические решения
Задача одномерной упаковки для реализации в машинном обучении
Разбор решения задач в области машинного обучения.