Методы программирования, 2 семестр 2006-2007 уч. года

На этой страничке выкладывается различная полезная информация для студентов группы 603а Высшего колледжа информатики при НГУ, изучающих предмет «методы программирования» под моим руководством. Возможно, что-нибудь отсюда пригодится и другим людям, изучающим программирование. Если у вас есть вопросы по поводу содержания данного сайта или курса методов, не стесняйтесь обращаться ко мне; контактная информация приведена внизу страницы.

Текущая ситуация

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

Выложены экзаменационные вопросы. Напоминаю, что экзамен сдаётся по темам обоих семестров.

Практические задания

  1. Частота встречаемости. Подсчитать, сколько раз каждая из латинских букв встречается в файле input.txt.
  2. Телефонный справочник. Используя указатели и динамическое выделение памяти (malloc/realloc/free), реализовать «телефонный справочник» с функциями добавления и удаления записей и поиска записи по имени человека. Не использовать массивы; предусмотреть возможность расширения выделенной памяти в случае, если выделенного объёма не хватает для вставки новой записи.
  3. Вставка в упорядоченный список. Файл input.txt содержит последовательность целых чисел. Читая числа по одному, вставлять их в односвязный список (изначально пустой) так, чтобы список постоянно был упорядоченным по возрастанию. Вывести отсортированную последовательность в файл output.txt, освободить использованную память.
    Теория: списки.
  4. Хэш-таблицы. Реализация телефонного справочника через хэш-таблицы с разрешением коллизий при помощи списков.
  5. Вычисление значения выражения. Файл input.txt содержит арифметическое выражение, состоящее из целых неотрицательных чисел, знаков операций (+, –, *, /) и круглых скобок. Вывести значение этого выражения.
    Теория: стеки, обратная польская нотация.
  6. Деревья. Сортировка последовательности вставкой в дерево двоичного поиска.
  7. Топологическая сортировка. Особый способ упорядочения вершин графа.
  8. Алгоритм Флойда. Поиск кратчайших путей в графе алгоритмом Флойда.
  9. Алгоритм Дейкстры. Поиск кратчайших путей в графе алгоритмом Дейкстры.
  10. Обход графа в глубину.
  11. Обход графа в ширину.
  12. Каркасы. Построение каркаса минимальной стоимости для связного неориентированного взвешенного графа алгоритмом Прима.
  13. Двусвязные компоненты. Поиск двусвязных компонент и точек сочленения в неориентированном графе. (задание обязательно для выполнения, только если студент хочет получить оценку «отлично»)
  14. Динамическое программирование. Алгоритм Ахо поиска максимальной общей части двух последовательностей.

Архив

Слабо структурированный набор страничек прошлых лет, содержащих различную (возможно, полезную) информацию. Пока ничего не выложено про группу 503а: кое-что есть на домашнем компьютере, но не обработано и к выкладыванию не пригодно.

Контакты

Александр Геннадьевич Фенстер
fenster@fenster.name
+7 913 9053295
http://fenster.name