Назад

Методы программирования

Практика

Внимание! Выложенный здесь материал был подготовлен в 2004 году. С тех пор я неоднократно находил в нём различные неточности и опечатки (что, однако, не помешало многим студентам успешно использовать его для разбора теории). Сейчас я неторопливо занимаюсь вдумчивым переписыванием и дополнением этого материала, результат этого процесса можно наблюдать здесь.

Окончательный список семестровых заданий («лабораторных работ»)

Звездочками помечены дополнительные задания. Для получения оценки «4» достаточно выполнить обязательный план (задания, не помеченные звездочкой), для получения оценки «5» необходимо выполнить все обязательные задания и задания, помеченные одной звездочкой. Выполнение заданий, помеченных двумя звездочками, не является обязательным, но всячески приветствуется.

  1. Связанные списки.
    1. Сортировка чисел при помощи односвязного списка.
    2. * Реализация хэш-таблицы с разрешением коллизий при помощи списков.
  2. Вычисления на стеке.
    1. Вычисление значения арифметического выражения, заданного в инфиксной форме.
    2. * Выполнение программы вычислений.
  3. Деревья. Реализация двоичного дерева поиска, условия аналогичны заданию 1b.
    1. Реализация простых двоичных деревьев поиска.
    2. ** Реализация сбалансированных деревьев.
    3. Реализация префиксного, инфиксного и постфиксного обходов двоичного дерева.
  4. Топологическая сортировка вершин графа.
    1. Реализация на матрицах смежности.
    2. * Реализация на списках смежности.
  5. Поиск кратчайшего пути во взвешенном графе.
    1. Алгоритм Флойда.
    2. Алгоритм Дейкстры.
  6. Обходы графа.
    1. Поиск в глубину.
    2. Поиск в ширину (лабиринт).
  7. Построение остовного дерева (каркаса) графа минимальной стоимости.
    1. Алгоритм Прима.
    2. Алгоритм Краскала.
  8. * Поиск двусвязных компонент и точек сочленения.
  9. Задание на динамическое программирование.