Difference between revisions of "BSc: BasicProgramDevelopmentConcepts"

From IU
Jump to navigation Jump to search
(Created page with "= <span style="color:red;">Название дисциплины</span> = : '''Квалификация выпускника''': <span style="color:red;">бакалавр/ма...")
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
  +
= Алгоритмы и структуры данных 2=
−
= <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++: изучение языков программирования позволяет студентам реализовывать изученные алгоритмы и применять их на практике.
  +
  +
5. Развитие аналитического мышления и навыков решения проблем: работа с алгоритмами и структурами данных требует анализа задачи, разработки эффективного решения и его реализации, что способствует развитию у студентов аналитических и проблемно-ориентированных навыков.
  +
  +
  +
: '''Задачами дисциплины''' являются:
  +
1. Разработка и оптимизация алгоритмов: Студенты изучают различные алгоритмы и методы их проектирования, что помогает им разрабатывать эффективные алгоритмы для решения разнообразных задач, таких как алгоритмы на графах, алгоритмы на строках, алгоритмы обработки конечных автоматов, алгоритмы анализа и преобразования контекстно-свободных грамматик, и другие.
  +
  +
2. Применение структур данных: Осваивая различные структуры данных, студенты учатся выбирать и применять наиболее подходящие для конкретных задач, что позволяет им эффективно управлять данными и решать сложные задачи.
  +
  +
3. Разработка программного обеспечения: Изучение языков программирования Python и C++ позволяет студентам разрабатывать программное обеспечение, включая реализацию алгоритмов и работу со структурами данных.
  +
  +
4. Решение алгоритмических задач: Дисциплина позволяет студентам улучшить навыки решения алгоритмических задач, что может быть полезно при участии в соревнованиях по программированию или при подготовке к техническим собеседованиям.
  +
  +
5. Развитие алгоритмического и аналитического мышления: Изучение алгоритмов и их реализация на практике способствует развитию у студентов алгоритмического мышления, а также аналитических навыков, необходимых для эффективного решения различных задач.
   
−
: '''Задачами дисциплины''' вляются ... <span style="color:red;">(перечислить задачи дисциплины, например: изучение принципов организации подсистем обработки естественного языка для различных прикладных задач и тенденций развития лингвистических ресурсов в сфере интеллектуальных информационных технологий и т.д.).</span>
  
   
 
=== Общая характеристика результата обучения по дисциплине ===
  
=== Общая характеристика результата обучения по дисциплине ===
−
: '''Знания:''' сформированы систематические знания ...
 +
: '''Знания:''' сформированы систематические знания:
  +
- структуры данных, лежащие в основе стандартных контейнеров библиотеки шаблонов языка программирования С++
−
<span style="color:red;">(информация, которой обладает обучающийся в определенных областях, полученная в процессе обучения, то есть это информация для осуществления какой-либо деятельности (действия))</span>
  
   
  +
- понятие графа, алгоритмы обработки графов, алгоритмы поиска кратчайшего пути в графах
−
: '''Умения:''' сформированы умения ...
  
  +
−
<span style="color:red;">(предполагает целенаправленное выполнение действий, по изученной информации)</span>
  
  +
- алгоритмы обработки строк
  +
  +
- понятие регулярного языка и регулярного выражения
  +
  +
- понятие конечного автомата, связь между регулярными языками и конечными автоматами
  +
  +
- понятие контекстно-свободной грамматики, методы их анализа и разбора
  +
информация о реализованных в стандартной библиотеке языка С++ алгоритмах и структурах данных
  +
  +
- информация о реализованных в стандартной библиотеке языка Python алгоритмах обработки различных форматов файлов, содержащих данные
  +
  +
  +
: '''Умения:'''сформированы умения<br>
  +
1. выбирать подходящую структуру данных и алгоритм для решения задачи<br>
  +
2. формулировать задачу предметной области как задачу анализа графа, в том числе задачу поиска кратчайшего пути в графе<br>
  +
3. реализовывать, а также при необходимости модифицировать алгоритмы на графах<br>
  +
4. использовать алгоритмы обработки строковых данных для решения задач<br>
  +
5. применять алгоритмы обработки конечных автоматов, использовать конечные автоматы для решения задач<br>
  +
6. применять алгоритмы обработки контекстно-свободных грамматик, использовать контекстно-свободные грамматики для решения задач<br>
  +
  +
  +
: '''Навыки (владения):''' сформировано владение навыками<br>
  +
1. реализовывать хранение графа в программе<br>
  +
2. реализовывать алгоритмы обработки графов<br>
  +
3. реализовывать алгоритмы обработки строк<br>
  +
4. пользоваться стандартной библиотекой языка Python для работы с регулярными выражениями, обработки данных в стандартных форматах JSON и XML<br>
  +
5. пользоваться стандартной библиотекой шаблонов языка С++, встроенными алгоритмами и структурами данных<br>
  +
6. реализовывать метод рекурсивного спуска для разбора выражений и вычисления значений<br>
   
−
: '''Навыки (владения):''' сформировано владение навыками ...
  
−
<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 75:
 
| 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>
  
  +
- std::vector, std::set, std::map, std::unordered_set, std::unordered_map
−
|- 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>
  
  +
- модуль algorithm в С++
−
|- 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;" | 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;" | 2. || Алгоритмы на графах || - хранение графов
  +
  +
- обход графа в глубину и его применения
  +
  +
- минимальное остовное дерево, алгоритм Прима, алгоритм Краскала
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 3. || Кратчайшие пути в графах || - обход графа в ширину
  +
  +
- алгоритм Дейкстры
  +
  +
- алгоритм Флойда
  +
  +
- алгоритм Беллмана-Форда
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 4. || Обработка строк || - представление строк
  +
  +
- задача о поиске подстроки в строке
  +
  +
- префикс-функция
  +
  +
- Z-функция
  +
  +
- хранение коллекции строк, бор
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 5. || Автоматы и регулярные языки || - регулярные языки
  +
  +
- регулярные выражения
  +
  +
- детерминированные конечные автоматы
  +
  +
- недетерминированные конечные автоматы
  +
  +
- детерминизация автомата
  +
  +
- связь конечных автоматов и регулярных выражений, теорема Клини
  +
  +
- минимизация ДКА
  +
  +
- работа с регулярными выражениями в языке Python
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 6. || Контекстно-свободные грамматики || - контекстно-свободные грамматики и языки
  +
  +
- обработка КС-языков
  +
  +
- алгоритм Кока-Янгера-Касами
  +
  +
- нисходящий разбор
  +
  +
- рекурсивный спуск, ручная реализация на языке Python
  +
  +
- вычисление значений выражений
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 7. || Стандартные средства работы с файлами || - разбор JSON-файлов в языке Python
  +
  +
- разбор XML-файлов в языке Python
  +
  +
 
|}
  
|}
   
Line 50: Line 162:
 
| 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;" | 5. || ||
 +
| style="text-align:center;" | 2. || Алгоритмы на графах || Реализация алгоритма поиска компонент связности
  +
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
Реализация алгоритма поиска цикла
−
| 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. || Обработка строк || Реализация наивного алгоритма поиска подстроки в строке
  +
  +
Реализация алгоритма Кнута-Морриса-Пратта построения префикс-функции
  +
  +
Реализация алгоритма Манакера построения Z-функции
  +
|- 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. || Стандартные средства работы с файлами || Реализация чтения данных из JSON-файла с использованием стандартных библиотек
  +
  +
Реализация чтения данных из XML-файла с использованием стандартных библиотек
  +
  +
 
|}
  
|}
  +
 
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
  
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
   
−
<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>
  
  +
|- style="background-color:#F8F9FA; color:#202122;"
−
Темы докладов:<br>-<br>-<br>-<br>...<br>
  
  +
−
Тематика эссе:<br>-<br>-<br>-<br>...<br>
  
  +
| style="text-align:center;" | 2. || Алгоритмы на графах || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
−
Задания, в том числе, для групповых проектов:<br>-<br>-<br>-<br>...<br>
  
  +
−
Тестирование (письменное или компьютерное):<br>-<br>-<br>-<br>...<br><br>
  
  +
- сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов на графах
−
Проверка разработки отдельных частей кода программного продукта.
  
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация алгоритма поиска компонент связности
  +
  +
- реализация алгоритма поиска цикла
  +
  +
- реализация алгоритма топологической сортировки
  +
  +
- реализация алгоритма поиска компонент сильной связности
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 3. || Кратчайшие пути в графах || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
  +
  +
- сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов поиска кратчайшего пути в графе
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация алгоритма обхода в ширину
  +
  +
- реализация алгоритма Дейкстры
  +
  +
- реализация алгоритма Флойда
  +
  +
- реализация алгоритма Беллмана-Форда
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 4. || Обработка строк || Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой || Устный ответ домашних заданий:
  +
  +
- сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов на строках
  +
  +
Задания по программированию с автоматической проверкой:
  +
  +
- реализация наивного алгоритма поиска подстроки в строке
  +
  +
- реализация алгоритма Кнута-Морриса-Пратта построения префикс-функции
  +
  +
- реализация алгоритма Манакера построения Z-функции
  +
|- 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. || Стандартные средства работы с файлами || Решение заданий по программированию с автоматической проверкой || Задания по программированию с автоматической проверкой:
  +
  +
- реализация чтения данных из JSON-файла с использованием стандартных библиотек
  +
  +
- реализация чтения данных из XML-файла с использованием стандартных библиотек
  +
   
−
Другие формы текущего контроля, используемые Вами на занятиях<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 321:
 
| 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 || Коллекции и их реализация || Как устроена коллекция (std::vector, std::set, std::map, std::unordered_set, std::unordered_map) в C++?
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
−
| style="text-align:center;" | 2. || ||
  
  +
Проведите амортизационный анализ std::vector
−
|- 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;" | 5. || ||
 +
| style="text-align:center;" | 2 || Алгоритмы на графах || Хранение графа.
  +
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  
  +
Двухцветный и трехцветный обход в глубину.
−
| 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 || Обработка строк || Задача о поиске подстроки в строке
  +
  +
Префикс-функция
  +
  +
Z-функция
  +
  +
Хранение коллекции строк, бор
  +
|- 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 || Стандартные средства работы с файлами || Написание программы обработки JSON-файлов.
  +
  +
Написание программы обработки XML-файлов.
  +
  +
 
|}
  
|}
 
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
  
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
   
  +
1. Коллекции C++. std::vector, std::set, std::map, std::unordered_set, std::unordered_map<br>
−
<span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ для промежуточной аттестации.)</span>
  
  +
2. Амортизационный анализ. Саморасширяющийся массив<br>
  +
3. Деревья поиска<br>
  +
4. Хеширование, хеш-функции<br>
  +
5. Обход графа в глубину и его применения для поиска компонент связности и цикла.<br>
  +
6. Обход графа в глубину и его применения для топологической сортировки и поиска компонент сильной связности<br>
  +
7. Минимальное остовное дерево, алгоритм Прима, алгоритм Краскала<br>
  +
8. Обход графа в ширину<br>
  +
9. Алгоритм Дейкстры<br>
  +
10. Алгоритм Флойда<br>
  +
11. Алгоритм Беллмана-Форда<br>
  +
12. Задача о поиске подстроки в строке. Префикс-функция.<br>
  +
13. Задача о поиске подстроки в строке. Z-функция<br>
  +
14. Хранение коллекции строк, бор<br>
  +
15. Регулярные языки<br>
  +
16. Детерминированные конечные автоматы<br>
  +
17. Недетерминированные конечные автоматы, детерминизация автомата<br>
  +
18. Связь конечных автоматов и регулярных выражений, теорема Клини<br>
  +
19. Минимизация ДКА<br>
  +
20. Контекстно-свободные грамматики и языки<br>
  +
21. Алгоритм Кока-Янгера-Касами<br>
  +
22. Нисходящий разбор. Рекурсивный спуск.<br>
  +
   
−
1.<br>2.<br>3.<br>...<br>48.<br>49.<br>50.<br>...
  
 
=== Перечень учебно-методического обеспечения дисциплины ===
  
=== Перечень учебно-методического обеспечения дисциплины ===
−
Список основной литературы:
 +
Список основной литературы:<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>
  +
13. Хопкрофт Д. , Мотвани Р., Ульман Д., Введение в теорию автоматов, языков и вычислений. — Вильямс, 2016. — 528 с.<br>
  +
  +
<br>
  +
Список дополнительной литературы:<br>
  +
1. Вики-конспекты. — http://neerc.ifmo.ru/wiki/index.php?title=Заглавная_страница <br>
  +
2. Документация к языку Python – https://docs.python.org/3/ <br>
  +
Документация к языку программирования С++ — https://en.cppreference.com/w/<br><br>
   
−
Список дополнительной литературы:
  
 
=== Методические указания для обучающихся по освоению дисциплины ===
  
=== Методические указания для обучающихся по освоению дисциплины ===
−
<span style="color:red;">(Указываются рекомендации для обучающихся, которые раскрывают суть их работы при различных видах деятельности в рамках освоения дисциплины. Данные рекомендации должны охватывать работу с лекционным материалом, подготовку и работу во время проведения семинарских занятий, самостоятельную работу, подготовку к текущему контролю и промежуточной аттестации)</span>
  
   
  +
Самостоятельная работа учащихся состоит: <br>
−
<span style="color:red;">(Выберите соответствующие виды учебных занятий, которые используются при изучении Вашей дисциплины)</span>
  
  +
• в изучении лекционного материала, доступных видео и конспектов лекций учебно-методической литературы<br>
  +
• подготовки к практическим заданиям текущего контроля и промежуточной аттестации:<br>
  +
• решение теоретических задач по разработке и модификации алгоритмов и структур данных<br>
  +
• решение алгоритмических задач на языках Python и С++ с автоматической проверкой.<br>
  +
  +
 
{| 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;" | Самостоятельная работа || Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
−
|-
  
  +
|- 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="vertical-align:middle; text-align:center; color:red;" | Самостоятельная работа
  
−
| style="vertical-align:middle; text-align:left; color:red;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
−
|-
  
−
| style="vertical-align:middle; text-align:center; color:red;" | Видеопрезентация
  
−
| style="vertical-align:middle; text-align:left; color:red;" | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
  
−
|-
  
−
| 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;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
  
−
|-
  
−
| 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 01:06, 2 April 2024

Алгоритмы и структуры данных 2

Квалификация выпускника: бакалавр
Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”
Направленность (профиль) образовательной программы: Математические основы ИИ
Программу разработал(а): Станкевич А.С.

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

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


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

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

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

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

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

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


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

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

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

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

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

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


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

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

- структуры данных, лежащие в основе стандартных контейнеров библиотеки шаблонов языка программирования С++

- понятие графа, алгоритмы обработки графов, алгоритмы поиска кратчайшего пути в графах

- алгоритмы обработки строк

- понятие регулярного языка и регулярного выражения

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

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

- информация о реализованных в стандартной библиотеке языка Python алгоритмах обработки различных форматов файлов, содержащих данные


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

1. выбирать подходящую структуру данных и алгоритм для решения задачи
2. формулировать задачу предметной области как задачу анализа графа, в том числе задачу поиска кратчайшего пути в графе
3. реализовывать, а также при необходимости модифицировать алгоритмы на графах
4. использовать алгоритмы обработки строковых данных для решения задач
5. применять алгоритмы обработки конечных автоматов, использовать конечные автоматы для решения задач
6. применять алгоритмы обработки контекстно-свободных грамматик, использовать контекстно-свободные грамматики для решения задач


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

1. реализовывать хранение графа в программе
2. реализовывать алгоритмы обработки графов
3. реализовывать алгоритмы обработки строк
4. пользоваться стандартной библиотекой языка Python для работы с регулярными выражениями, обработки данных в стандартных форматах JSON и XML
5. пользоваться стандартной библиотекой шаблонов языка С++, встроенными алгоритмами и структурами данных
6. реализовывать метод рекурсивного спуска для разбора выражений и вычисления значений


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

№
п/п 		Наименование раздела
дисциплины 		Содержание дисциплины по темам
1. Коллекции и их реализация - коллекции в языке программирования С++

- std::vector, std::set, std::map, std::unordered_set, std::unordered_map

- модуль algorithm в С++

- реализация коллекций: соответствующие структуры данных

- саморасширяющийся массив

- деревья поиска

- хеширование, хеш-функции

2. Алгоритмы на графах - хранение графов

- обход графа в глубину и его применения

- минимальное остовное дерево, алгоритм Прима, алгоритм Краскала

3. Кратчайшие пути в графах - обход графа в ширину

- алгоритм Дейкстры

- алгоритм Флойда

- алгоритм Беллмана-Форда

4. Обработка строк - представление строк

- задача о поиске подстроки в строке

- префикс-функция

- Z-функция

- хранение коллекции строк, бор

5. Автоматы и регулярные языки - регулярные языки

- регулярные выражения

- детерминированные конечные автоматы

- недетерминированные конечные автоматы

- детерминизация автомата

- связь конечных автоматов и регулярных выражений, теорема Клини

- минимизация ДКА

- работа с регулярными выражениями в языке Python

6. Контекстно-свободные грамматики - контекстно-свободные грамматики и языки

- обработка КС-языков

- алгоритм Кока-Янгера-Касами

- нисходящий разбор

- рекурсивный спуск, ручная реализация на языке Python

- вычисление значений выражений

7. Стандартные средства работы с файлами - разбор JSON-файлов в языке Python

- разбор XML-файлов в языке Python


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

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

№
п/п 		Наименование раздела
дисциплины (модуля) 		Перечень рассматриваемых тем (вопросов)
1. Коллекции и их реализация Решение задач с текстовой постановкой с использованием стандартных коллекций

Использование нестандартных ключей и методов сравнения для стандартных коллекций

Реализация структур данных, используемых в стандартных коллекциях, вручную

2. Алгоритмы на графах Реализация алгоритма поиска компонент связности

Реализация алгоритма поиска цикла

Реализация алгоритма топологической сортировки

Реализация алгоритма поиска компонент сильной связности

3. Кратчайшие пути в графах Реализация алгоритма обхода в ширину

Реализация алгоритма Дейкстры

Реализация алгоритма Флойда

Реализация алгоритма Беллмана-Форда

4. Обработка строк Реализация наивного алгоритма поиска подстроки в строке

Реализация алгоритма Кнута-Морриса-Пратта построения префикс-функции

Реализация алгоритма Манакера построения Z-функции

5. Автоматы и регулярные языки Решение теоретических заданий на анализ свойств регулярных языков

Реализация алгоритмов анализа и преобразования конечных автоматов

Решение задач на соответствие регулярному выражению с использованием стандартной библиотеки языка программирования Python

6. Контекстно-свободные грамматики Решение теоретических заданий на анализ свойств контекстно-свободных языков

Реализация алгоритма Кока-Янгера-Касами

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

7. Стандартные средства работы с файлами Реализация чтения данных из JSON-файла с использованием стандартных библиотек

Реализация чтения данных из XML-файла с использованием стандартных библиотек


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

№
п/п 		Наименование раздела
дисциплины 		Форма текущего контроля
 Материалы текущего контроля
1. Коллекции и их реализация Решение заданий по программированию с автоматической проверкой Задания по программированию с автоматической проверкой:

- решение заданий с использованием стандартных коллекций

- реализация структур данных, используемых в стандартных коллекциях, вручную

2. Алгоритмы на графах Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой Устный ответ домашних заданий:

- сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов на графах

Задания по программированию с автоматической проверкой:

- реализация алгоритма поиска компонент связности

- реализация алгоритма поиска цикла

- реализация алгоритма топологической сортировки

- реализация алгоритма поиска компонент сильной связности

3. Кратчайшие пути в графах Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой Устный ответ домашних заданий:

- сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов поиска кратчайшего пути в графе

Задания по программированию с автоматической проверкой:

- реализация алгоритма обхода в ширину

- реализация алгоритма Дейкстры

- реализация алгоритма Флойда

- реализация алгоритма Беллмана-Форда

4. Обработка строк Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой Устный ответ домашних заданий:

- сведение задач в текстовой постановке к решению с использованием соответствующих алгоритмов на строках

Задания по программированию с автоматической проверкой:

- реализация наивного алгоритма поиска подстроки в строке

- реализация алгоритма Кнута-Морриса-Пратта построения префикс-функции

- реализация алгоритма Манакера построения Z-функции

5. Автоматы и регулярные языки Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой Устный ответ домашних заданий:

- анализ свойств регулярных языков

Задания по программированию с автоматической проверкой:

- реализация алгоритма проверки допуска строки детерминированным автоматом

- реализация алгоритма проверки допуска строки недетерминированным автоматом

- реализация алгоритма детерминизации автомата

- реализация алгоритма минимизации автомата

- решение задач на соответствие регулярному выражению с использованием стандартной библиотеки языка программирования Python

6. Контекстно-свободные грамматики Проверка выполнения домашних заданий. Решение заданий по программированию с автоматической проверкой Устный ответ домашних заданий:

- анализ свойств контекстно-свободных языков

Задания по программированию с автоматической проверкой:

- реализация алгоритма Кока-Янгера-Касами

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

7. Стандартные средства работы с файлами Решение заданий по программированию с автоматической проверкой Задания по программированию с автоматической проверкой:

- реализация чтения данных из JSON-файла с использованием стандартных библиотек

- реализация чтения данных из XML-файла с использованием стандартных библиотек


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

№
п/п 		Наименование
раздела дисциплины 		Вопросы
1 Коллекции и их реализация Как устроена коллекция (std::vector, std::set, std::map, std::unordered_set, std::unordered_map) в C++?

Проведите амортизационный анализ std::vector

Какие хеш-функции удачно применить для хеширования строк?

2 Алгоритмы на графах Хранение графа.

Двухцветный и трехцветный обход в глубину.

Применение обхода в глубину для выделения компонент связности графа.

Применение обхода в глубину для поиска цикла в ориентированном и неориентированном графе.

Топологическая сортировка ориентированных графов.

3 Кратчайшие пути в графах Обход графа в ширину.

Алгоритм Дейкстры.

Алгоритм Флойда.

Алгоритм Беллмана-Форда.

Поиск отрицательного цикла в графе.

4 Обработка строк Задача о поиске подстроки в строке

Префикс-функция

Z-функция

Хранение коллекции строк, бор

5 Автоматы и регулярные языки Построение регулярного выражения по текстовому описанию языка.

Построение конечного автомата по текстовому описанию языка.

Построение детерминированного автомата по недетерминированному.

Теорема Клини

6 Контекстно-свободные грамматики Контекстно-свободные грамматики и языки

Построение КС-грамматики по текстовому описанию языка.

Алгоритм Кока-Янгера-Касами

7 Стандартные средства работы с файлами Написание программы обработки JSON-файлов.

Написание программы обработки XML-файлов.


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

1. Коллекции C++. std::vector, std::set, std::map, std::unordered_set, std::unordered_map
2. Амортизационный анализ. Саморасширяющийся массив
3. Деревья поиска
4. Хеширование, хеш-функции
5. Обход графа в глубину и его применения для поиска компонент связности и цикла.
6. Обход графа в глубину и его применения для топологической сортировки и поиска компонент сильной связности
7. Минимальное остовное дерево, алгоритм Прима, алгоритм Краскала
8. Обход графа в ширину
9. Алгоритм Дейкстры
10. Алгоритм Флойда
11. Алгоритм Беллмана-Форда
12. Задача о поиске подстроки в строке. Префикс-функция.
13. Задача о поиске подстроки в строке. Z-функция
14. Хранение коллекции строк, бор
15. Регулярные языки
16. Детерминированные конечные автоматы
17. Недетерминированные конечные автоматы, детерминизация автомата
18. Связь конечных автоматов и регулярных выражений, теорема Клини
19. Минимизация ДКА
20. Контекстно-свободные грамматики и языки
21. Алгоритм Кока-Янгера-Касами
22. Нисходящий разбор. Рекурсивный спуск.


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

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


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.
13. Хопкрофт Д. , Мотвани Р., Ульман Д., Введение в теорию автоматов, языков и вычислений. — Вильямс, 2016. — 528 с.


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

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

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


Вид учебных
занятий/деятельности 		Деятельность обучающегося
Лекция Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.

Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.

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

Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.

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

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

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