ИВТ. Алгоритмы и структуры данных. Базовый поток 2026: различия между версиями

Материал из Public ATP Wiki
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Строка 9: Строка 9:
{| class="wikitable"
{| class="wikitable"
|-
|-
! Неделя !! Лекция/Семинар !! Д/З !! Контроль / событие !! Дедлайн
! Неделя !! Лекция !! Семинар !! Контроль / событие !! Дедлайн
|-
|-
|1–3
|1–2
|'''Основные понятия структур данных.'''
|Интуитивное понятие алгоритма, определение алгоритма. Свойства алгоритмов. Виды алгоритмов.  
<br>Концепция типа данных. Простейшие типы данных.
Способы задания алгоритмов.
<br>Простейшие стандартные типы данных.  
Машины Тьюринга и Поста. Нормальные алгорифмы Маркова.
<br>Ограниченные типы (диапазоны). Массивы.  
Решение задач на Машины Тьюринга и Поста. Нормальные алгорифмы Маркова
<br>Записи. Записи с вариантами. Множества.  
|Решение задач на Машины Тьюринга и Поста. Нормальные алгорифмы Маркова.
<br>Представление массивов, записей и множеств.
|тесты
<br>Последовательности (элементарные операции,
|10.09.2026
<br>буферизация, стандартные ввод и вывод).
|-
|
|3–4
|Основные понятия структур данных.
|Основные понятия структур данных.
|
|
|
|
|-
|-
|4–6
|4–6
|'''Данные с динамической структурой.'''
|Данные с динамической структурой.
<br>Линейные списки: основные операции, упорядоченные списки
|Данные с динамической структурой.
<br>и перестройка списков. Стеки, очереди, деки, нелинейные
<br>структуры данных, иерархические списки, мультисписки.
<br>Реализация перечисленных структур данных. Стандартные
<br>классы в ООП, поддерживающие динамические структуры.
|
|
|
|
|
|-
|-
|7–11
|7-9
|'''Алгоритмы поиска.''' Задачи поиска и кодирования
|Алгоритмы поиска.
<br>(сжатия) данных. Кодовые деревья, оптимальные префиксные коды,
|Алгоритмы поиска.
<br>исчерпывающий поиск. Линейный поиск. Поиск делением пополам
<br>(двоичный поиск). Поиск в таблице. Прямой поиск строки. Поиск
<br>в строке (алгоритмы Кнута, Мориса и Прата). Алгоритмы Боуэра-Мура.
<br>Алгоритмы Рабина-Карпа.
|
|
|
|
|
|-
|-
|nn
|10–12
|'''Алгоритмы сортировки.''' Анализ сложности и эффективности алгоритмов
|Алгоритмы сортировки.  
<br>поиска и сортировки. Оценка временной и пространственной сложности алгоритмов
|Алгоритмы сортировки.  
<br>на основе асимптотических соотношений (О –и Ω нотации). Порядковые статистик.
<br>Сортировка массивов: прямым включением, прямым выбором и прямым обменом.
<br>Улучшенные методы сортировки: включениями с уменьшающимися расстояниями,
<br>с помощью дерева, разделением. Нахождение медианы. Сравнение методов сортировки
<br>массивов. Файлы: организация и обработка. Сортировка файлов: прямое слияние,
<br>естественное слияние, сбалансированное многопутевое слияние, многофазная сортировка,
<br>распределение начальных серий.
|
|
|
|
|
|-
|-
|12–15
|13-15
|'''Быстрый доступ к данным.''' Хеширование данных.  
|Быстрый доступ к данным.
<br>Способы вычисления хеш-функций. Разрешение коллизий. Линейное,
|Быстрый доступ к данным.
<br>квадратичное опробование. Метод цепочек, двойное хеширование.
<br>Оценка качества хеш-функций. Инвертированные индексы. Битовые карты.
|
|
|
|
|

Версия от 06:44, 21 августа 2026

О курсе

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

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

Программа курса

Неделя Лекция Семинар Контроль / событие Дедлайн
1–2 Интуитивное понятие алгоритма, определение алгоритма. Свойства алгоритмов. Виды алгоритмов.

Способы задания алгоритмов. Машины Тьюринга и Поста. Нормальные алгорифмы Маркова. Решение задач на Машины Тьюринга и Поста. Нормальные алгорифмы Маркова

Решение задач на Машины Тьюринга и Поста. Нормальные алгорифмы Маркова. тесты 10.09.2026
3–4 Основные понятия структур данных. Основные понятия структур данных.
4–6 Данные с динамической структурой. Данные с динамической структурой.
7-9 Алгоритмы поиска. Алгоритмы поиска.
10–12 Алгоритмы сортировки. Алгоритмы сортировки.
13-15 Быстрый доступ к данным. Быстрый доступ к данным.

Коммуникация

Чат курса (Telegram или другой мессенджер).

Прогресс студентов

Таблица с оценками, доступная студентам.

Критерии оценивания и формы контроля успеваемости

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

Команда курса

Руководитель и лектор курса: Дивари Ирина Николаевна

Ассистент: Карецкий Владислав Олегович

Материалы курса

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

  1. Моделирование абстрактных типов данных (АТД) для различных реализаций (табличное, списковое, комбинированное и т.д.).
  2. Поиск информации в различных структурах данных с использованием классических алгоритмов поиска в текстовой информации.
  3. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных.
  4. Реализация структур данных типа дерево и типовые алгоритмы их обработки.
  5. Реализация функций расстановки (хеширование) и различных методов разрешения коллизий.
  6. Реализовать алгоритмы поиска: КМП – алгоритм.
  7. Реализация алгоритма Боуэра-Мура.
  8. Алгоритм Рабина-Карпа.
  9. Построение графика зависимости количества операций сравнения от количества символов в массиве.
  10. Определение временной сложности алгоритма и сравнение с экспериментальными исследованиями.
Источник — https://wiki.atp-fivt.org/index.php?title=ИВТ._Алгоритмы_и_структуры_данных._Базовый_поток_2026&oldid=5081