Основы разработки и анализа алгоритмов

Цели и задачи дисциплины

Сформировать у студентов систематическое понимание принципов разработки, анализа и оптимизации алгоритмов, позволяющее обоснованно выбирать и создавать эффективные алгоритмические решения для инженерных задач, в том числе для ресурсоемких задач в сфере искусственного интеллекта, оценивая их вычислительную трудоемкость и потребление ресурсов. Задачи: - Освоить фундаментальный аппарат анализа сложности алгоритмов. - Сформировать навык применения основных методов разработки алгоритмов. - Научить проводить сравнительный анализ и выбирать ресурсно-эффективные алгоритмы для решения прикладных задач.

Краткое содержание дисциплины

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

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать: