Difference between revisions of "BSc: AlgorithmsAndAlgorithmicLanguages"

From IU
Jump to navigation Jump to search
(Created page with "= <span style="color:red;">Название дисциплины</span> = : '''Квалификация выпускника''': <span style="color:red;">бакалавр/ма...")
 
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
  +
= Алгоритмы и программирование 1 =
−
= <span style="color:red;">Название дисциплины</span> =
  
−
: '''Квалификация выпускника''': <span style="color:red;">бакалавр/магистр</span>
 +
: '''Квалификация выпускника''': бакалавр
−
: '''Направление подготовки''': __________________
 +
: '''Направление подготовки''': 09.03.01 - “Информатика и вычислительная техника”
−
: '''Направленность (профиль) образовательной программы''': <span style="color:red;">(Указывается направленность (профиль) образовательной программы</span>
 +
: '''Направленность (профиль) образовательной программы''': Математические основы ИИ
−
: '''Программу разработал(а)''': __________________
 +
: '''Программу разработал(а)''': Станкевич А.С.
  +
   
 
== 1. Краткая характеристика дисциплины ==
  
== 1. Краткая характеристика дисциплины ==
−
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области <span style="color:red;">(указывается область изучаемой дисциплины. Например: программного обеспечения и его разработки; робототехники и т.д.)</span>, их применение для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают <span style="color:red;">(краткое описание содержания дисциплины)</span>.
 +
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области разработки и анализа алгоритмов и структур данных и их применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают основные концепции алгоритмов, структур данных и навыки программирования на языках Python и C++. Студенты изучают различные методы решения задач, включая сортировку, поиск, динамическое программирование и другие классические алгоритмы. Курс включает в себя лекции по алгоритмам и структурам данных, семинары по программированию, практические занятия с разбором теоретических ДЗ и лабораторные работы по реализации изученных алгоритмов на языках программирования Python и C++.
  +
   
 
== 2. Перечень планируемых результатов обучения ==
  
== 2. Перечень планируемых результатов обучения ==
−
: '''Целью освоения дисциплины''' ...
 +
: '''Цели освоения дисциплины'''
  +
  +
1. Понимание концепции алгоритма: студенты изучают различные алгоритмы и методы их проектирования, что помогает им понять принципы работы различных процессов.
  +
  +
2. Изучение различных структур данных: студенты учатся выбирать и применять подходящие структуры данных для эффективного решения конкретных задач.
  +
  +
3. Приобретение навыков программирования на Python и C++: изучение языков программирования позволяет студентам реализовывать изученные алгоритмы и применять их на практике.
  +
  +
4. Развитие аналитического мышления и навыков решения проблем: работа с алгоритмами и структурами данных требует анализа задачи, разработки эффективного решения и его реализации, что способствует развитию у студентов аналитических и проблемно-ориентированных навыков.
  +
: '''Задачами дисциплины''' являются:
  +
  +
1. Разработка и оптимизация алгоритмов: Студенты изучают различные алгоритмы и методы их разработки, что помогает им разрабатывать эффективные алгоритмы для решения разнообразных задач.
  +
  +
2. Применение структур данных: Осваивая различные структуры данных, студенты учатся выбирать и применять наиболее подходящие для конкретных задач, что позволяет им эффективно управлять данными и решать сложные задачи.
  +
  +
3. Разработка программного обеспечения: Изучение языков программирования Python и C++ позволяет студентам разрабатывать программное обеспечение, включая реализацию алгоритмов и работу со структурами данных.
  +
  +
4. Решение алгоритмических задач: Дисциплина позволяет студентам улучшить навыки решения алгоритмических задач, что может быть полезно при участии в соревнованиях по программированию или при подготовке к техническим собеседованиям.
  +
  +
5. Анализ сложности алгоритмов: Студенты изучают методы анализа временной и пространственной сложности алгоритмов, что помогает им оценивать эффективность их работы и выбирать наиболее подходящие решения для конкретных задач.
  +
  +
6. Развитие алгоритмического и аналитического мышления: Изучение алгоритмов и их реализация на практике способствует развитию у студентов алгоритмического мышления, а также аналитических навыков, необходимых для эффективного решения различных задач.
   
−
: '''Задачами дисциплины''' вляются ... <span style="color:red;">(перечислить задачи дисциплины, например: изучение принципов организации подсистем обработки естественного языка для различных прикладных задач и тенденций развития лингвистических ресурсов в сфере интеллектуальных информационных технологий и т.д.).</span>
  
   
 
=== Общая характеристика результата обучения по дисциплине ===
  
=== Общая характеристика результата обучения по дисциплине ===
−
: '''Знания:''' сформированы систематические знания ...
 +
: '''Знания:''' сформированы систематические знания:
  +
−
<span style="color:red;">(информация, которой обладает обучающийся в определенных областях, полученная в процессе обучения, то есть это информация для осуществления какой-либо деятельности (действия))</span>
  
  +
1. понятие алгоритма, сложности алгоритма
  +
  +
2. алгоритмы сортировки и поиска
  +
  +
3. метод динамического программирования для решения задач с оптимальностью для подзадач
  +
  +
4. методы построения и анализа жадных алгоритмов
  +
  +
5. синтаксис и стандартная библиотека языка программирования Python
  +
  +
6. информация о представлении в памяти компьютера целых и вещественных чисел, методов обработки вещественных чисел
  +
  +
7. элементы синтаксиса языка С++
  +
  +
  +
: '''Умения:''' сформированы умения
  +
  +
1. выбирать подходящую структуру данных и алгоритм для решения задачи
  +
  +
2. реализовывать, а также при необходимости модифицировать алгоритмы поиска, сортировки для поставленной задачи
  +
  +
3. формулировать и доказывать жадные алгоритмы для решения задач
  +
  +
4. формулировать и реализовывать алгоритмы динамического программирования для решния задач
  +
  +
5. анализировать сложность алгоритма, в том числе рекурсивных алгоритмов с использованием мастер-теоремы
  +
  +
  +
: '''Навыки (владения):''' сформировано владение навыками
  +
  +
1. выбирать язык программирования для реализации алгоритма, в зависимости от требований
  +
  +
2. реализовывать алгоритмы с использованием языков программирования Python и C++
  +
  +
3. пользоваться стандартной библиотекой языка Python для ввода, вывода данных в текстовой форме, реализации алгоритмов, в том числе алгоритмов сортировки и поиска
   
  +
4. использовать системы контроля версий и сборки
−
: '''Умения:''' сформированы умения ...
  
−
<span style="color:red;">(предполагает целенаправленное выполнение действий, по изученной информации)</span>
  
   
−
: '''Навыки (владения):''' сформировано владение навыками ...
  
−
<span style="color:red;">(автоматизированные устойчивые умения выполнять определенную работу, то есть действие выполняется без контроля сознания, автоматически)</span>
  
   
 
== 3. Структура и содержание дисциплины ==
  
== 3. Структура и содержание дисциплины ==
  +
−
<span style="color:red;">(Указываются: 1) порядковый номер раздела (количество разделов зависит от содержания Вашей дисциплины); 2) наименования разделов дисциплины; 3) темы указанных разделов (количество тем в каждом разделе зависит от содержания Вашей дисциплины)</span>
  
 
{| class="wikitable" style="width:70%;"
  
{| class="wikitable" style="width:70%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
  
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
Line 30: Line 84:
 
| style="width:30%" | Наименование раздела <br> дисциплины
  
| style="width:30%" | Наименование раздела <br> дисциплины
 
| style="width:60%" | Содержание дисциплины по темам
  
| style="width:60%" | Содержание дисциплины по темам
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
| style="text-align:center;" | 1. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
  
  +
| style="text-align:center;" | 1. || Сложность и анализ алгоритмов || - понятие алгоритма, сложность по времени и памяти
−
|- style="background-color:#F8F9FA; color:#202122;"
  
  +
−
| style="text-align:center;" | 2. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
  
  +
- асимптотический анализ сложности алгоритмов
−
|- style="background-color:#F8F9FA; color:#202122;"
  
  +
−
| style="text-align:center;" | 3. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
  
  +
- анализ сложности рекурсивных алгоритмов, мастер-теорема
−
|- style="background-color:#F8F9FA; color:#202122;"
  
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
| style="text-align:center;" | 4. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
  
  +
−
|- style="background-color:#F8F9FA; color:#202122;"
  
  +
| style="text-align:center;" | 2. || Программирование на языке Python || - основные конструкции языка
−
| style="text-align:center;" | 5. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
  
  +
−
|- style="background-color:#F8F9FA; color:#202122;"
  
  +
- ввод и вывод
−
| style="text-align:center;" | ... || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
  
  +
  +
- функции
  +
  +
- списки, обработка списков
  +
  +
- создание своих классов
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 3. || Линейные алгоритмы || - линейные алгоритмы обработки данных
  +
  +
- многокритериальный поиск
  +
  +
- префиксные минимумы и максимумы
  +
  +
- метод двух указателей
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 4. || Сортировка и поиск || - двоичный поиск
  +
  +
- квадратичные сортировки
  +
  +
- доказательство нижних границ на примере сортировки сравнениями
  +
  +
- сортировки за n log n, сортировка кучей
  +
  +
- сортировки за линейное время, цифровая сортировка, корзинная сортировка, сортировка сложных объектов
  +
  +
- сортировка слиянием
  +
  +
- быстрая сортировка
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 5. || Рекурсия и рекурсивные алгоритмы || - рекурсивный перебор
  +
  +
- рекурсивная генерация комбинаторных объектов
  +
  +
- реализация рекурсии в языке Python, локальные и глобальные переменные
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 6. || Жадные алгоритмы || - концепция жадного алгоритма
  +
  +
- принципы доказательств жадных алгоритмов
  +
  +
- примеры жадных алгоритмов из теории расписаний
  +
  +
- сжатие данных, алгоритм Хаффмана
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 7. || Динамическое программирование || - основные принципы динамического программирования, декомпозиция задачи, оптимальность для подзадач
  +
  +
- ДП на префиксе
  +
  +
- классические задачи ДП: наибольшая возрастающая подпоследовательность, наибольшая общая подпоследовательность
  +
  +
- задача о редакционном расстоянии
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 8. || Архитектура компьютера || - хранение целых чисел
  +
  +
- хранение вещественных чисел
  +
  +
- точность, работа с вещественными числами
  +
  +
- указатели, массивы
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 9. || Программирование на С++ || - синтаксис С++, основные конструкции языка
  +
  +
- функции
  +
  +
- ввод, вывод
  +
  +
- создание своих структур и классов
  +
  +
- шаблонные классы и функции
  +
  +
- операторы
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 10. || Системы хранения и сборки || - github, система контроля версий git
  +
  +
- системы сборки проектов
  +
 
|}
  
|}
   
Line 50: Line 187:
 
| style="width:10%" | №<br>п/п
  
| style="width:10%" | №<br>п/п
 
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
  
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
−
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br><span style="color:red;">(Указываются ВСЕ задания для практических занятий по разделам дисциплины подробно в соответствии с темами)</span>
 +
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br>
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
| style="text-align:center;" | 1. || ||
  
  +
| style="text-align:center;" | 1 || Сложность и анализ алгоритмов || Сравнение асимптотического поведения различных функций
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
−
| style="text-align:center;" | 2. || ||
  
  +
Определение асимптотического поведения функции
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
−
| style="text-align:center;" | 3. || ||
  
  +
Определение сложности алгоритма
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 4. || ||
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
| style="text-align:center;" | 2 || Программирование на языке Python || Использование основных конструкций языка Python для написания программ
−
| style="text-align:center;" | 5. || ||
  
  +
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
Реализация простых алгоритмов обработки данных на языке Python
−
| style="text-align:center;" | ... || ||
  
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 3 || Линейные алгоритмы || Реализация алгоритма поиска элемента по критерию
  +
  +
Реализация метода двух указателей
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 4 || Сортировка и поиск || Решение задач с использованием встроенных алгоритмов сортировки
  +
  +
Использование нетривиальных ключей сортировки
  +
  +
Использование нетривиальных функций сравнения для сортировки
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 5 || Рекурсия и рекурсивные алгоритмы || Определение асимптотики времени работы рекурсивного алгоритма по рекуррентному соотношению с использованием мастер-теоремы
  +
  +
Реализация алгоритма рекурсивного перебора
  +
  +
Реализация алгоритма генерации всех комбинаторных объектов для двоичных векторов, перестановок, сочетаний
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 6 || Жадные алгоритмы || Доказательство корректности работы жадного алгоритма для различных задач
  +
  +
Реализация жадных алгоритмов решения задач теории расписаний
  +
  +
Реализация алгоритма Хаффмана
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 7 || Динамическое программирование || Решение задач по теоретической постановке с использованием метода динамического программирования
  +
  +
Восстановление ответа в задачах динамического программирования
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 8 || Архитектура компьютера || Работа с представлением целых чисел
  +
  +
Работа с представлением вещественных чисел
  +
  +
Работа с вещественными числами с учетом невозможности их точного представления
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 9 || Программирование на С++ || Использование основных конструкций языка С++ для написания программ
  +
  +
Реализация простых алгоритмов обработки данных
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 10 || Системы хранения и сборки || Работа с системой контроля версий
  +
  +
Работа с системой автоматической сборки проекта
  +
 
|}
  
|}
  +
 
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
  
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
   
−
<span style="color:red;">(К формам текущего контроля можно отнести собеседование, коллоквиум, тест, контрольную работу, лабораторную работу, эссе, реферат и иные творческие работы.)</span>
  
 
{| class="wikitable" style="width:70%;"
  
{| class="wikitable" style="width:70%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
  
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| style="width:5%" | №<br>п/п
  
| style="width:5%" | №<br>п/п
 
| style="width:20%" | Наименование раздела<br>дисциплины
  
| style="width:20%" | Наименование раздела<br>дисциплины
−
| style="width:25%" | Форма текущего контроля<br><br><span style="color:red;">(выберите соответствующие формы контроля)</span>
 +
| style="width:25%" | Форма текущего контроля<br>
−
| style="width:50%" | Материалы текущего контроля<br><br><span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ текущего контроля успеваемости обучающихся по разделам дисциплины подробно в соответствии с требованиями)</span>
 +
| style="width:50%" | Материалы текущего контроля<br>
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
| style="text-align:center;" | 1.
  
  +
| style="text-align:center;" | 1. || Сложность и анализ алгоритмов || Проверка выполнения домашних заданий || Устный ответ домашних заданий:
−
|
 
  +
−
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
  
  +
- сравнение асимптотического поведения различных функций
−
| Например:
  
  +
−
Устный / письменный опрос:<br>-<br>-<br>-<br>...<br>
  
  +
- определение асимптотического поведения функции
−
Тематика групповых проектов:<br>-<br>-<br>-<br>...<br>
  
  +
−
Темы докладов:<br>-<br>-<br>-<br>...<br>
  
  +
- определение сложности алгоритма
−
Тематика эссе:<br>-<br>-<br>-<br>...<br>
  
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
Задания, в том числе, для групповых проектов:<br>-<br>-<br>-<br>...<br>
  
  +
−
Тестирование (письменное или компьютерное):<br>-<br>-<br>-<br>...<br><br>
  
  +
| style="text-align:center;" | 2. || Программирование на языке Python || Решение заданий по программированию с автоматической проверкой || Задания по программированию с автоматической проверкой:
−
Проверка разработки отдельных частей кода программного продукта.
  
  +
  +
- реализация простых алгоритмов обработки данных
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 3. || Линейные алгоритмы || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
  +
  +
- разработка линейного алгоритма для решения задачи по текстовой постановке
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация алгоритма поиска элемента по критерию
  +
  +
- реализация метода двух указателей
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 4. || Сортировка и поиск || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
  +
  +
- анализ свойств алгоритмов поиска
  +
  +
- анализ свойств алгоритмов сортировки
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация алгоритма двоичного поиска
  +
  +
- реализация сортировки
  +
  +
- решение задач с использованием встроенных алгоритмов сортировки
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 5. || Рекурсия и рекурсивные алгоритмы || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
  +
  +
- определение асимптотики времени работы рекурсивного алгоритма по рекуррентному соотношению с использованием мастер-теоремы
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация алгоритма рекурсивного перебора
  +
  +
- реализация алгоритма генерации всех комбинаторных объектов для двоичных векторов, перестановок, сочетаний
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 6. || Жадные алгоритмы || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
  +
  +
- доказательство корректности работы жадного алгоритма для различных задач
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация жадного алгоритма решения задач теории расписаний
  +
  +
- реализация алгоритма Хаффмана
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 7. || Динамическое программирование || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
  +
  +
- решение задач по теоретической постановке с использованием метода динамического программирования
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация алгоритма подсчета числа путей на линейной и прямоугольной сетке
  +
  +
- реализация алгоритма поиска наибольшей общей подпоследовательности
  +
  +
- реализация алгоритма поиска наибольшей возрастающей подпоследовательности
  +
  +
- реализация алгоритма поиска редакционного расстояния
  +
  +
- решение задач с использованием динамического программирования
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 8. || Архитектура компьютера || Тесты с использованием системы автоматической проверки || Тесты с использованием системы автоматической проверки:
  +
  +
- работа с представлением целых чисел
  +
  +
- работа с представлением вещественных чисел
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 9. || Программирование на С++ || Решение заданий по программированию с автоматической проверкой || Задания по программированию с автоматической проверкой:
  +
  +
- реализация простых алгоритмов обработки данных
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 10. || Системы хранения и сборки || Проверка разработки отдельных частей кода программного продукта || Загрузка всех решений заданий курса в систему контроля версий
   
−
Другие формы текущего контроля, используемые Вами на занятиях<br>-<br>-<br>-<br>...<br>
  
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 2.
  
−
|
  
−
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
  
−
|
 
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 3.
  
−
|
  
−
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
  
−
|
 
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 4.
  
−
|
  
−
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
  
−
|
 
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 5.
  
−
|
  
−
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
  
−
|
 
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | ... || || ||
  
 
|}
  
|}
  +
 
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
  
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
 
{| class="wikitable" style="width:70%;"
  
{| class="wikitable" style="width:70%;"
Line 116: Line 362:
 
| style="width:25%" | Наименование <br> раздела дисциплины
  
| style="width:25%" | Наименование <br> раздела дисциплины
 
| style="width:65%" | Вопросы
  
| style="width:65%" | Вопросы
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
| style="text-align:center;" | 1. || ||
  
  +
| style="text-align:center;" | 1. || Сложность и анализ алгоритмов || Проанализировать сложность заданного алгоритма по времени и памяти.
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
−
| style="text-align:center;" | 2. || ||
  
  +
Проанализировать заданный рекурсивный алгоритм с использованием мастер-теоремы.
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 3. || ||
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 4. || ||
 +
| style="text-align:center;" | 2. || Программирование на языке Python || Реализовать заданный алгоритм на языке Python.
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
| style="text-align:center;" | 5. || ||
  
  +
| style="text-align:center;" | 3. || Линейные алгоритмы || Применить метод линейного поиска для решения задачи.
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
−
| style="text-align:center;" | ... || ||
  
  +
Применить метод двух указателей для решения задачи.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 4. || Сортировка и поиск || Применить метод двоичного поиска для решения задачи.
  +
  +
Применить сортировку для решения задачи.
  +
  +
Доказать, что время работы сортировки сравнениями не может быть меньше n log n.
  +
  +
Реализовать алгоритм сортировки на языке Python.
  +
  +
Воспользоваться встроенным алгоритмом сортировки на языке Python, применив нетривиальный ключ сортировки.
  +
  +
Проанализировать различные алгоритмы сортировки на устойчивость.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 5. || Рекурсия и рекурсивные алгоритмы || Реализовать рекурсивную генерацию заданных комбинаторных объектов на языке Python
  +
  +
Оптимизировать заданную функцию методом рекурсивного перебора всех вариантов.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 6. || Жадные алгоритмы || Применить жадный алгоритм для решения задачи.
  +
  +
Доказать корректность применения жадного алгоритма для некоторых задач теории расписаний.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 7. || Динамическое программирование || Сформулировать решение задачи с использованием метода динамического программирования.
  +
  +
Реализовать решение задачи с помощью метода динамического программирования на языке Python.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 8. || Архитектура компьютера || Указать битовое представление заданного целого числа.
  +
  +
Указать битовое представление заданного вещественного числа.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 9. || Программирование на С++ || Реализовать заданный алгоритм на языке С++.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 10. || Системы хранения и сборки || Разместить заданный код в системе контроля версий.
  +
  +
 
|}
  
|}
 
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
  
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
   
  +
1. Анализ сложности рекурсивных алгоритмов, мастер-теорема
−
<span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ для промежуточной аттестации.)</span>
  
  +
  +
2. Линейные алгоритмы обработки данных
  +
  +
3. Метод двух указателей
  +
  +
4. Двоичный поиск
  +
  +
5. Сортировки
  +
  +
6. Доказательство нижних границ на примере сортировки сравнениями
  +
  +
7. Рекурсивная генерация комбинаторных объектов
  +
  +
8. Жадные алгоритмы
  +
  +
9. Алгоритм Хаффмана
  +
  +
10. Основные принципы динамического программирования, декомпозиция задачи, оптимальность для подзадач
  +
  +
11. Классические задачи ДП: наибольшая возрастающая подпоследовательность, наибольшая общая подпоследовательность
  +
  +
12. Задача о редакционном расстоянии
  +
  +
13. Хранение целых чисел и вещественных чисел в компьютере
  +
   
−
1.<br>2.<br>3.<br>...<br>48.<br>49.<br>50.<br>...
  
 
=== Перечень учебно-методического обеспечения дисциплины ===
  
=== Перечень учебно-методического обеспечения дисциплины ===
−
Список основной литературы:
 +
Список основной литературы:<br>
  +
  +
1. Кормен T., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2012. — 1296 с.<br>
  +
2. Асанов М., Баранский В., Расин В. Дискретная математика: графы, матроиды, алгоритмы. — Лань, 2010. — 368 с.<br>
  +
3. Ахо А. В., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы. — М.: Вильямс, 2010. — 400 с.<br>
  +
4. Седжвик Р. Фундаментальные алгоритмы на C++. — Вильямс, 2011. — 1056 с.<br>
  +
5. Страуструп Б. Язык программирования С++. Специальное издание. — М.: Бином, 2011. — 1136 с.<br>
  +
6. Страуструп Б. Дизайн и эволюция С++. — ДМК Пресс, 2011. — 446 с.<br>
  +
7. Саттер Г. Решение сложных задач на С++. — М.: Вильямс, 2015. — 400 с.<br>
  +
8. Саттер Г. Новые сложные задачи на C++. — М.: Вильямс, 2015. — 272 с.<br>
  +
9. Саттер Г., Александреску А. Стандарты программирования на С++. — М.: Вильямс, 2015. — 224 с.<br>
  +
10. Александреску А. Современное проектирование на С++. — М.: Вильямс, 2015. — 336 с.<br>
  +
11. Саммерфилд М. Python на практике [Электронный ресурс] : учебное пособие. — Электрон. дан. — М. : ДМК Пресс, 2014. — 338 с.<br>
  +
12. Сузи, Р. А. Язык программирования Python : учебное пособие / Р. А. Сузи. — 2-е изд. — Москва : ИНТУИТ, 2016. — 350 с. — ISBN 5-9556-0058-2.<br>
  +
  +
Список дополнительной литературы:<br>
  +
1. Вики-конспекты. — http://neerc.ifmo.ru/wiki/index.php?title=Заглавная_страница<br>
  +
2. Документация к языку Python – https://docs.python.org/3/<br>
  +
3. Документация к языку программирования С++ — https://en.cppreference.com/w/<br>
  +
   
−
Список дополнительной литературы:
  
 
=== Методические указания для обучающихся по освоению дисциплины ===
  
=== Методические указания для обучающихся по освоению дисциплины ===
−
<span style="color:red;">(Указываются рекомендации для обучающихся, которые раскрывают суть их работы при различных видах деятельности в рамках освоения дисциплины. Данные рекомендации должны охватывать работу с лекционным материалом, подготовку и работу во время проведения семинарских занятий, самостоятельную работу, подготовку к текущему контролю и промежуточной аттестации)</span>
  
   
  +
Самостоятельная работа учащихся состоит:
−
<span style="color:red;">(Выберите соответствующие виды учебных занятий, которые используются при изучении Вашей дисциплины)</span>
  
  +
- в изучении лекционного материала, доступных видео и конспектов лекций учебно-методической литературы
  +
  +
- подготовки к практическим заданиям текущего контроля и промежуточной аттестации:
  +
  +
- решение теоретических задач по разработке и модификации алгоритмов и структур данных
  +
  +
- решение алгоритмических задач на языках Python и С++ с автоматической проверкой.
  +
  +
 
{| class="wikitable" style="width:80%;"
  
{| class="wikitable" style="width:80%;"
−
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#FF0000; font-weight:bold;"
 +
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; font-weight:bold;"
 
| style="width:20%" | Вид учебных<br>занятий/деятельности
  
| style="width:20%" | Вид учебных<br>занятий/деятельности
 
| style="width:80%" | Деятельность обучающегося
  
| style="width:80%" | Деятельность обучающегося
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
|-
 
  +
−
| style="vertical-align:middle; text-align:center; color:red;" | Лекция
  
−
| style="vertical-align:middle; text-align:left; color:red;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
 +
| style="text-align:center;" | Лекция || Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
|-
  
  +
−
| style="vertical-align:middle; text-align:center; color:red;" | Практическое (семинарское) занятие
  
−
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.<br>Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
 +
| style="text-align:center;" | Практическое (семинарское) занятие || При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.
  +
−
|-
  
  +
Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
−
| style="vertical-align:middle; text-align:center; color:red;" | Устный/письменный опрос
  
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
| style="vertical-align:middle; text-align:left; color:red;" | Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
 
  +
−
|-
  
  +
| style="text-align:center;" | Подготовка к промежуточной аттестации || При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.
−
| style="vertical-align:middle; text-align:center; color:red;" | Реферат
  
  +
−
| style="vertical-align:middle; text-align:left; color:red;" | Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты.<br>Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата.
  
  +
Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
−
|-
  
−
| style="vertical-align:middle; text-align:center; color:red;" | Эссе
 +
|- style="background-color:#F8F9FA; color:#202122;"
  +
−
| style="vertical-align:middle; text-align:left; color:red;" | Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др.
 
  +
| style="text-align:center;" | Практические (лабораторные) занятия || Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
−
|-
  
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
| style="vertical-align:middle; text-align:center; color:red;" | Подготовка к промежуточной аттестации
  
  +
−
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.<br>Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
  
  +
| style="text-align:center;" | Самостоятельная работа || Самостоятельная работа состоит из следующих частей:
−
|-
  
  +
−
| style="vertical-align:middle; text-align:center; color:red;" | Практические (лабораторные) занятия
  
  +
1) чтение учебной, справочной, научной литературы;
−
| style="vertical-align:middle; text-align:left; color:red;" | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
 
  +
−
|-
  
  +
2) повторение материала лекций;
−
| style="vertical-align:middle; text-align:center; color:red;" | Самостоятельная работа
  
  +
−
| style="vertical-align:middle; text-align:left; color:red;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
  +
3) составление планов устных выступлений;
−
|-
  
  +
−
| style="vertical-align:middle; text-align:center; color:red;" | Видеопрезентация
  
  +
4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
−
| style="vertical-align:middle; text-align:left; color:red;" | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
  
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
|-
  
  +
−
| style="vertical-align:middle; text-align:center; color:red;" | Доклад
  
  +
| style="text-align:center;" | Разработка отдельных частей кода || Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
−
| style="vertical-align:middle; text-align:left; color:red;" | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
  
  +
−
|-
  
  +
−
| style="vertical-align:middle; text-align:center; color:red;" | Дискуссия
  
−
| style="vertical-align:middle; text-align:left; color:red;" | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
  
−
|-
  
−
| style="vertical-align:middle; text-align:center; color:red;" | Контрольная работа
  
−
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
  
−
|-
  
−
| style="vertical-align:middle; text-align:center; color:red;" | Тестирование (устное/письменное)
  
−
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
  
−
|-
  
−
| style="vertical-align:middle; text-align:center; color:red;" | Индивидуальная работа
  
−
| style="vertical-align:middle; text-align:left; color:red;" | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
  
−
|-
  
−
| style="vertical-align:middle; text-align:center; color:red;" | Разработка отдельных частей кода
  
−
| style="vertical-align:middle; text-align:left; color:red;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
  
−
|-
  
−
| style="vertical-align:middle; text-align:center; color:red;" | Выполнение домашних заданий и групповых проектов
  
−
| style="vertical-align:middle; text-align:left; color:red;" | Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
  
 
|}
  
|}
 
=== Методы и технологии обучения, способствующие формированию компетенции ===
  
=== Методы и технологии обучения, способствующие формированию компетенции ===
−
<span style="color:red;">(Указываются все используемые преподавателем методы и технологии обучения)</span>
  
 
{| class="wikitable"
  
{| class="wikitable"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
  
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| Методы и технологии обучения, способствующие формированию компетенции
  
| Методы и технологии обучения, способствующие формированию компетенции
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
−
| &nbsp;
  
−
|}
  
−
<span style="color:red;">Например:</span>
  
−
{| class="wikitable" style="width:80%;"
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center; width:5%;" | 1.
  
−
| style="width:20%;" | Информационно – коммуникационная технология
  
−
| style="width:75%;" | &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 2.
  
−
| Технология развития критического мышления
  
−
| Основные методические приемы развития критического мышления
  
−
# Прием «Кластер»
  
−
# Таблица
  
−
#Учебно-мозговой штурм
  
−
#Интеллектуальная разминка
  
−
#Зигзаг, зигзаг -2
  
−
#Прием «Инсерт»
  
−
#Эссе
  
−
#Приём «Корзина идей»
  
−
#Приём «Составление синквейнов»
  
−
#Метод контрольных вопросов
  
−
#Приём «Знаю../Хочу узнать…/Узнал…»
  
−
#Круги по воде
  
−
#Ролевой проект
  
−
#Да – нет
  
−
#Приём «Чтение с остановками»
  
−
#Приём «Взаимоопрос»
  
−
#Приём «Перепутанные логические цепочки»
  
−
#Приём «Перекрёстная дискуссия»
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 3.
  
−
| Проектная технология
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 4.
  
−
| Технология проблемного обучения
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 5.
  
−
| Кейс – технология
  
−
| К методам кейс-технологий, активизирующим учебный процесс, относятся:
  
−
*метод ситуационного анализа (Метод анализа конкретных ситуаций, ситуационные задачи и упражнения; кейс-стадии)
  
−
*метод инцидента;
  
−
*метод ситуационно-ролевых игр;
  
−
*метод разбора деловой корреспонденции;
  
−
*игровое проектирование;
  
−
*метод дискуссии.
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 6.
  
−
| Технология интегрированного обучения
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 7.
  
−
| Педагогика сотрудничества
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 8.
  
−
| Технологии уровневой дифференциации
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 9.
  
−
| Групповая технология
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 10.
  
−
| Традиционные технологии (классно-урочная система)
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 11.
  
−
| Здоровьесберегающие технологии
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 12.
  
−
| Игровая технология
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 13.
  
−
| Модульная технология
  
−
|
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| style="text-align:center;" | 14.
  
−
| Технология мастерских
  
−
| &nbsp;
  
−
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
  
−
| &nbsp;
  
−
| и др.
  
 
| &nbsp;
  
| &nbsp;
 
|}
  
|}

Latest revision as of 00:34, 2 April 2024

Алгоритмы и программирование 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) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.

Разработка отдельных частей кода Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.


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

Методы и технологии обучения, способствующие формированию компетенции
 
Retrieved from "https://eduwiki.innopolis.university/index.php?title=BSc:_AlgorithmsAndAlgorithmicLanguages&oldid=9161"