Алгоритмы и программирование 1

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а): Станкевич А.С.

1. Краткая характеристика дисциплины

Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области разработки и анализа алгоритмов и структур данных и их применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают основные концепции алгоритмов, структур данных и навыки программирования на языках Python и C++. Студенты изучают различные методы решения задач, включая сортировку, поиск, динамическое программирование и другие классические алгоритмы. Курс включает в себя лекции по алгоритмам и структурам данных, семинары по программированию, практические занятия с разбором теоретических ДЗ и лабораторные работы по реализации изученных алгоритмов на языках программирования Python и C++.

2. Перечень планируемых результатов обучения

Цели освоения дисциплины

1. Понимание концепции алгоритма: студенты изучают различные алгоритмы и методы их проектирования, что помогает им понять принципы работы различных процессов.

2. Изучение различных структур данных: студенты учатся выбирать и применять подходящие структуры данных для эффективного решения конкретных задач.

3. Приобретение навыков программирования на Python и C++: изучение языков программирования позволяет студентам реализовывать изученные алгоритмы и применять их на практике.

4. Развитие аналитического мышления и навыков решения проблем: работа с алгоритмами и структурами данных требует анализа задачи, разработки эффективного решения и его реализации, что способствует развитию у студентов аналитических и проблемно-ориентированных навыков.

Задачами дисциплины являются:

1. Разработка и оптимизация алгоритмов: Студенты изучают различные алгоритмы и методы их разработки, что помогает им разрабатывать эффективные алгоритмы для решения разнообразных задач.

2. Применение структур данных: Осваивая различные структуры данных, студенты учатся выбирать и применять наиболее подходящие для конкретных задач, что позволяет им эффективно управлять данными и решать сложные задачи.

3. Разработка программного обеспечения: Изучение языков программирования Python и C++ позволяет студентам разрабатывать программное обеспечение, включая реализацию алгоритмов и работу со структурами данных.

4. Решение алгоритмических задач: Дисциплина позволяет студентам улучшить навыки решения алгоритмических задач, что может быть полезно при участии в соревнованиях по программированию или при подготовке к техническим собеседованиям.

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

6. Развитие алгоритмического и аналитического мышления: Изучение алгоритмов и их реализация на практике способствует развитию у студентов алгоритмического мышления, а также аналитических навыков, необходимых для эффективного решения различных задач.

Общая характеристика результата обучения по дисциплине

Знания: сформированы систематические знания:

1. понятие алгоритма, сложности алгоритма

2. алгоритмы сортировки и поиска

3. метод динамического программирования для решения задач с оптимальностью для подзадач

4. методы построения и анализа жадных алгоритмов

5. синтаксис и стандартная библиотека языка программирования Python

6. информация о представлении в памяти компьютера целых и вещественных чисел, методов обработки вещественных чисел

7. элементы синтаксиса языка С++

Умения: сформированы умения

1. выбирать подходящую структуру данных и алгоритм для решения задачи

2. реализовывать, а также при необходимости модифицировать алгоритмы поиска, сортировки для поставленной задачи

3. формулировать и доказывать жадные алгоритмы для решения задач

4. формулировать и реализовывать алгоритмы динамического программирования для решния задач

5. анализировать сложность алгоритма, в том числе рекурсивных алгоритмов с использованием мастер-теоремы

Навыки (владения): сформировано владение навыками

1. выбирать язык программирования для реализации алгоритма, в зависимости от требований

2. реализовывать алгоритмы с использованием языков программирования Python и C++

3. пользоваться стандартной библиотекой языка Python для ввода, вывода данных в текстовой форме, реализации алгоритмов, в том числе алгоритмов сортировки и поиска

4. использовать системы контроля версий и сборки

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Сложность и анализ алгоритмов	- понятие алгоритма, сложность по времени и памяти - асимптотический анализ сложности алгоритмов - анализ сложности рекурсивных алгоритмов, мастер-теорема
2.	Программирование на языке Python	- основные конструкции языка - ввод и вывод - функции - списки, обработка списков - создание своих классов
3.	Линейные алгоритмы	- линейные алгоритмы обработки данных - многокритериальный поиск - префиксные минимумы и максимумы - метод двух указателей
4.	Сортировка и поиск	- двоичный поиск - квадратичные сортировки - доказательство нижних границ на примере сортировки сравнениями - сортировки за n log n, сортировка кучей - сортировки за линейное время, цифровая сортировка, корзинная сортировка, сортировка сложных объектов - сортировка слиянием - быстрая сортировка
5.	Рекурсия и рекурсивные алгоритмы	- рекурсивный перебор - рекурсивная генерация комбинаторных объектов - реализация рекурсии в языке Python, локальные и глобальные переменные
6.	Жадные алгоритмы	- концепция жадного алгоритма - принципы доказательств жадных алгоритмов - примеры жадных алгоритмов из теории расписаний - сжатие данных, алгоритм Хаффмана
7.	Динамическое программирование	- основные принципы динамического программирования, декомпозиция задачи, оптимальность для подзадач - ДП на префиксе - классические задачи ДП: наибольшая возрастающая подпоследовательность, наибольшая общая подпоследовательность - задача о редакционном расстоянии
8.	Архитектура компьютера	- хранение целых чисел - хранение вещественных чисел - точность, работа с вещественными числами - указатели, массивы
9.	Программирование на С++	- синтаксис С++, основные конструкции языка - функции - ввод, вывод - создание своих структур и классов - шаблонные классы и функции - операторы
10.	Системы хранения и сборки	- github, система контроля версий git - системы сборки проектов

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1	Сложность и анализ алгоритмов	Сравнение асимптотического поведения различных функций Определение асимптотического поведения функции Определение сложности алгоритма
2	Программирование на языке Python	Использование основных конструкций языка Python для написания программ Реализация простых алгоритмов обработки данных на языке Python
3	Линейные алгоритмы	Реализация алгоритма поиска элемента по критерию Реализация метода двух указателей
4	Сортировка и поиск	Решение задач с использованием встроенных алгоритмов сортировки Использование нетривиальных ключей сортировки Использование нетривиальных функций сравнения для сортировки
5	Рекурсия и рекурсивные алгоритмы	Определение асимптотики времени работы рекурсивного алгоритма по рекуррентному соотношению с использованием мастер-теоремы Реализация алгоритма рекурсивного перебора Реализация алгоритма генерации всех комбинаторных объектов для двоичных векторов, перестановок, сочетаний
6	Жадные алгоритмы	Доказательство корректности работы жадного алгоритма для различных задач Реализация жадных алгоритмов решения задач теории расписаний Реализация алгоритма Хаффмана
7	Динамическое программирование	Решение задач по теоретической постановке с использованием метода динамического программирования Восстановление ответа в задачах динамического программирования
8	Архитектура компьютера	Работа с представлением целых чисел Работа с представлением вещественных чисел Работа с вещественными числами с учетом невозможности их точного представления
9	Программирование на С++	Использование основных конструкций языка С++ для написания программ Реализация простых алгоритмов обработки данных
10	Системы хранения и сборки	Работа с системой контроля версий Работа с системой автоматической сборки проекта

Текущий контроль успеваемости обучающихся по дисциплине:

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1.	Сложность и анализ алгоритмов	Проверка выполнения домашних заданий	Устный ответ домашних заданий: - сравнение асимптотического поведения различных функций - определение асимптотического поведения функции - определение сложности алгоритма
2.	Программирование на языке Python	Решение заданий по программированию с автоматической проверкой	Задания по программированию с автоматической проверкой: - реализация простых алгоритмов обработки данных
3.	Линейные алгоритмы	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - разработка линейного алгоритма для решения задачи по текстовой постановке Задания по программированию с автоматической проверкой: - реализация алгоритма поиска элемента по критерию - реализация метода двух указателей
4.	Сортировка и поиск	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - анализ свойств алгоритмов поиска - анализ свойств алгоритмов сортировки Задания по программированию с автоматической проверкой: - реализация алгоритма двоичного поиска - реализация сортировки - решение задач с использованием встроенных алгоритмов сортировки
5.	Рекурсия и рекурсивные алгоритмы	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - определение асимптотики времени работы рекурсивного алгоритма по рекуррентному соотношению с использованием мастер-теоремы Задания по программированию с автоматической проверкой: - реализация алгоритма рекурсивного перебора - реализация алгоритма генерации всех комбинаторных объектов для двоичных векторов, перестановок, сочетаний
6.	Жадные алгоритмы	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - доказательство корректности работы жадного алгоритма для различных задач Задания по программированию с автоматической проверкой: - реализация жадного алгоритма решения задач теории расписаний - реализация алгоритма Хаффмана
7.	Динамическое программирование	Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой	Устный ответ домашних заданий: - решение задач по теоретической постановке с использованием метода динамического программирования Задания по программированию с автоматической проверкой: - реализация алгоритма подсчета числа путей на линейной и прямоугольной сетке - реализация алгоритма поиска наибольшей общей подпоследовательности - реализация алгоритма поиска наибольшей возрастающей подпоследовательности - реализация алгоритма поиска редакционного расстояния - решение задач с использованием динамического программирования
8.	Архитектура компьютера	Тесты с использованием системы автоматической проверки	Тесты с использованием системы автоматической проверки: - работа с представлением целых чисел - работа с представлением вещественных чисел
9.	Программирование на С++	Решение заданий по программированию с автоматической проверкой	Задания по программированию с автоматической проверкой: - реализация простых алгоритмов обработки данных
10.	Системы хранения и сборки	Проверка разработки отдельных частей кода программного продукта	Загрузка всех решений заданий курса в систему контроля версий

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Сложность и анализ алгоритмов	Проанализировать сложность заданного алгоритма по времени и памяти. Проанализировать заданный рекурсивный алгоритм с использованием мастер-теоремы.
2.	Программирование на языке Python	Реализовать заданный алгоритм на языке Python.
3.	Линейные алгоритмы	Применить метод линейного поиска для решения задачи. Применить метод двух указателей для решения задачи.
4.	Сортировка и поиск	Применить метод двоичного поиска для решения задачи. Применить сортировку для решения задачи. Доказать, что время работы сортировки сравнениями не может быть меньше n log n. Реализовать алгоритм сортировки на языке Python. Воспользоваться встроенным алгоритмом сортировки на языке Python, применив нетривиальный ключ сортировки. Проанализировать различные алгоритмы сортировки на устойчивость.
5.	Рекурсия и рекурсивные алгоритмы	Реализовать рекурсивную генерацию заданных комбинаторных объектов на языке Python Оптимизировать заданную функцию методом рекурсивного перебора всех вариантов.
6.	Жадные алгоритмы	Применить жадный алгоритм для решения задачи. Доказать корректность применения жадного алгоритма для некоторых задач теории расписаний.
7.	Динамическое программирование	Сформулировать решение задачи с использованием метода динамического программирования. Реализовать решение задачи с помощью метода динамического программирования на языке Python.
8.	Архитектура компьютера	Указать битовое представление заданного целого числа. Указать битовое представление заданного вещественного числа.
9.	Программирование на С++	Реализовать заданный алгоритм на языке С++.
10.	Системы хранения и сборки	Разместить заданный код в системе контроля версий.

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. Анализ сложности рекурсивных алгоритмов, мастер-теорема

2. Линейные алгоритмы обработки данных

3. Метод двух указателей

4. Двоичный поиск

5. Сортировки

6. Доказательство нижних границ на примере сортировки сравнениями

7. Рекурсивная генерация комбинаторных объектов

8. Жадные алгоритмы

9. Алгоритм Хаффмана

10. Основные принципы динамического программирования, декомпозиция задачи, оптимальность для подзадач

11. Классические задачи ДП: наибольшая возрастающая подпоследовательность, наибольшая общая подпоследовательность

12. Задача о редакционном расстоянии

13. Хранение целых чисел и вещественных чисел в компьютере

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

1. Кормен T., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2012. — 1296 с.
2. Асанов М., Баранский В., Расин В. Дискретная математика: графы, матроиды, алгоритмы. — Лань, 2010. — 368 с.
3. Ахо А. В., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы. — М.: Вильямс, 2010. — 400 с.
4. Седжвик Р. Фундаментальные алгоритмы на C++. — Вильямс, 2011. — 1056 с.
5. Страуструп Б. Язык программирования С++. Специальное издание. — М.: Бином, 2011. — 1136 с.
6. Страуструп Б. Дизайн и эволюция С++. — ДМК Пресс, 2011. — 446 с.
7. Саттер Г. Решение сложных задач на С++. — М.: Вильямс, 2015. — 400 с.
8. Саттер Г. Новые сложные задачи на C++. — М.: Вильямс, 2015. — 272 с.
9. Саттер Г., Александреску А. Стандарты программирования на С++. — М.: Вильямс, 2015. — 224 с.
10. Александреску А. Современное проектирование на С++. — М.: Вильямс, 2015. — 336 с.
11. Саммерфилд М. Python на практике [Электронный ресурс] : учебное пособие. — Электрон. дан. — М. : ДМК Пресс, 2014. — 338 с.
12. Сузи, Р. А. Язык программирования Python : учебное пособие / Р. А. Сузи. — 2-е изд. — Москва : ИНТУИТ, 2016. — 350 с. — ISBN 5-9556-0058-2.

Список дополнительной литературы:
1. Вики-конспекты. — http://neerc.ifmo.ru/wiki/index.php?title=Заглавная_страница
2. Документация к языку Python – https://docs.python.org/3/
3. Документация к языку программирования С++ — https://en.cppreference.com/w/

Методические указания для обучающихся по освоению дисциплины

Самостоятельная работа учащихся состоит: - в изучении лекционного материала, доступных видео и конспектов лекций учебно-методической литературы

- подготовки к практическим заданиям текущего контроля и промежуточной аттестации:

- решение теоретических задач по разработке и модификации алгоритмов и структур данных

- решение алгоритмических задач на языках Python и С++ с автоматической проверкой.

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Подготовка к промежуточной аттестации	При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей. Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
Практические (лабораторные) занятия	Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа	Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Разработка отдельных частей кода	Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.

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

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

BSc: AlgorithmsAndAlgorithmicLanguages

Contents