Архив‎ > ‎

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

Общая информация

Информационные технологии
 Объем курса
 1/2 года (1 сем, 1 лекция в неделю)
 Отчётность теоретический экзамен
 Направление  010400, информационные технологии
 Семестр  IV (2 курс, весна) 
 Код дисциплины
 CS103
 Трудоёмкость 3 зачётных единицы

Вопросы по курсу (2013 год)

Часть I

  1. Буква, символ, алфавит; кодирование и кодировки до Unicode.
  2. Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.
  3. Абсолютная и относительная погрешности; позиционные системы счисления; дополнительный код.
  4. Симметричные системы; троичные арифметика и логика.
  5. Числа с плавающей запятой; нормализация; распределение.
  6. Комплексные числа, распределение разных представлений.
  7. Назначение линейных контейнеров; преимущества и недостатки массивов.
  8. Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: шитые и иерархические списки.
  9. Назначение, преимущества и недостатки деревьев.
  10. AVL - деревья.
  11. B - деревья.
  12. R - деревья.
  13. Красно-черные деревья.
  14. Декартовы деревья.
  15. Представления графов.
  16. Хеш-таблицы: назначение, подходы к расширению, преимущества и недостатки перед деревьями.
  17. Хеш-функции: требуемые свойства, примеры.
  18. Распределенные хеш-таблицы.

Часть II

  1. Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).
  2. Назначение кучи; куча для элементов одинакового размера.
  3. Тривиальная организация кучи; дефрагментация.
  4. Оптимизация дефрагментации методом граничных маркеров.
  5. Метод двоичных близнецов.
  6. Массивы; представление многомерных массивов при помощи векторов Айлифа.
  7. Представление контекста вложенных процедур при помощи цепочек фреймов и мониторов.
  8. Передача процедур "вниз" по цепочке вызовов; поддержание статической цепочки.
  9. Произвольная передача замыканий (процедур с контекстом) с копированием или динамическим выделением контекста.
  10. Генетические алгоритмы.
  11. Вдумчивые и конструктивные замечания по программе курса.
  12. Таблица виртуальных методов при одиночном наследовании.
  13. Таблица виртуальных методов и смещений для невиртуального множественного наследования.
  14. Таблица виртуальных методов и смещений для виртуального множественного наследования.
  15. Виртуальные таблицы для одиночного наследования и множественной реализации интерфейсов.
  16. Виртуальные таблицы для динамических языков.
  17. Распараллеливание алгоритмов на примере сортировок с и без использования дополнительной памяти; ускорение и эффективность, распараллеливание и оптимизация умножения квадратных матриц.
  18. Жадные и динамические алгоритмы (только 2 курс, экзамен).

    Источники информации

    • Конспект.
    • Дж. Д. Ульман А. В. Ахо, Дж. Э. Хопкрофт. Структуры данных и алгоритмы. Издательский дом «Вильямс», 2000.
    • Дональд Э. Кнут. Искусство Программирования. Издательский дом «Вильямс», 2000.
    • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
    • Кубенский А. А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++. СПб.: БХВ-Петербург, 2004.
    • Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.
    • Материалы лектора: приложение к данной странице; кому-то может показаться, что это лучше, чем ничего.
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    06.trees.pdf
    (1110k)
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Ċ
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    ċ
    crc_demo.py
    (1k)
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    ċ
    fp.c
    (2k)
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    ċ
    val2posn.scm
    (0k)
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    ċ
    val2symn.scm
    (1k)
    Dmitry Luciv,
    18 мая 2014 г., 21:30
    Comments