Примечания и библиографические указания

Учебное пособие Редактор А. В. Крейцер Издательство спбгэту «лэти» 1 97376, С. Петербург, ул. Проф. Попова, 5
2. Деревья поиска Идеально сбалансированные бинарные деревья
2 Случайные бинарные деревья поиска
Абракадабра!, содержащий 12 символов, включая специальный символ !
Задача кодирования сообщений. Префиксные коды и деревья Пусть задан алфавит
1 Код Фано-Шеннона
1 Метод Хаффмана
1 Реализация алгоритмов кодирования
1 Доказательство оптимальности кода Хаффмана Лемма 1
1 Энтропийная оценка средней длины кода
1 Динамическое кодирование по Хаффману
Абракадабра!, содержащий 12 символов, включая специальный символ !
Абракадабра!, содержащий 12 символов, включая специальный символ !
А. Ю. Алексеев с. А. Ивановский д. В. Куликов
При обучении программированию особую трудность вызывает работа с динамическими структурами данных
2. стеки и очереди спецификация стека и очереди
3 Определения дерева, леса, бинарного дерева. Скобочное представление
Примечания и библиографические указания
Списки
Задача о порядке перемножения матриц
С. А. Ивановский разработкакорректныхпрограм м санкт-Петербург 2003
Программирования
Разработка, доказательство корректности и анализ алгоритма
2. основы аналитической верификации программ основные правила аналитической верификации программ
3. индуктивные функции на последовательностях
4. корректность программ при работе с массивами
5. поиск в массиве линейный поиск
Разработка, доказательство корректности
Шень А. Программирование: теоремы и задачи: Учеб пособие

скачать rtf

Примечания и библиографические указания

Материал, изложенный в учебном пособии, на протяжении ряда лет был опробован при выполнении лабораторных и курсовых работ по отдельным разделам учебных дисциплин «Программирование» (линейные списки, иногда – иерархические списки) и «Алгоритмы и структуры данных» (иерархические списки, стеки, очереди, деки, деревья и леса) для специальностей 073000 – «Прикладная математика», 220400 – «Программное обеспечение вычислительной техники и автоматизированных систем» и направлений 552800 и 644600 – «Информатика и вычислительная техника» и 510200 – «Прикладная математика и информатика». Классические книги [2], [10], [16], в которых рассматриваются основные динамические структуры данных в связи с разработкой эффективных алгоритмов, в большей степени ориентированы на алгоритмический аспект проблемы. Известные книги Н. Вирта [5], [6] ориентированы на программирование эффективных алгоритмов, но в меньшей степени затрагивают технологию программирования. Используемая в пособии идеология абстрактных типов данных, основанная на выделении этапов спецификации, представления и реализации динамических структур данных, представлена в той или иной форме в [7], [8], [11] [15]. В оригинальном учебном курсе [11] фактически последовательно реализован именно такой подход, включая идею реализации одних структур данных на базе других. Более формальное изложение вопросов, связанных со спецификацией, представлением и реализацией структур данных, можно найти в [8] и в цитированной там литературе.

Материал по рекурсивной обработке списков из 1.6 и 1.7 может рассматриваться как «мостик» в функциональное программирование. На абстрактном уровне эти вопросы хорошо изложены в [18], [19], а основы реализации иерархических списков на Паскале можно найти в [1], [4].

При рассмотрении стека, очереди и дека в значительной степени использовались [3], [11], [13] и статья К. Хоора в [7].

Дополнительную информацию по программированию деревьев можно найти в [10], [13], [15], [20].

В качестве основных источников заданий для упражнений использовались [10], [13], [17]. Дополнительно можно рекомендовать [9].
Список литературы

Алагич С., Арбиб М. Проектирование корректных структурированных программ. М.: Радио и связь, 1984.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
Ахо А. В., Хопкрофт Дж., Ульман Дж. Д. Структуры данных и алгоритмы: Учеб. пособие. – М.: Издательский дом Вильямс, 2000.
Бауэр Ф. Л., Гооз Г. Информатика. Вводный курс: В 2 ч. М.: Мир, 1990.
Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.
Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. (СПб.: Невский Диалект, 2001. (2-е изд., испр.))
Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975.
Калинин А. Г., Мацкевич И. В. Универсальные языки программирования. Семантический подход. М.: Радио и связь, 1991.
Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ: Учеб. пособие для вузов. М.: Наука, 1986.
Кнут Д. Искусство программирования для ЭВМ: В 3 т. Т. 1. Основные алгоритмы. М.: Мир, 1976. (Учеб. пособие: В 3 т. Т. 1. Основные алгоритмы. 3-е изд. М.: Издательский дом Вильямс, 2000.)
Кушниренко А. Г., Лебедев Г. В. Программирование для математиков: Учеб. пособие для вузов. М.: Наука, 1988.
Лисков Б., Гатэг Дж. Использование абстракций и спецификаций при разработке программ. М.: Мир, 1989.
Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. М.: Мир, 1989.
Мейер Б., Бодуэн К. Методы программирования: В 2 т. М.: Мир, 1982.
Райли Д. Абстракция и структуры данных: Вводный курс. М.: Мир, 1993.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.
Пильщиков В. Н. Сборник упражнений по языку Паскаль: Учеб. пособие для вузов. М.: Наука, 1989.
Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, 1983.
Берж В. Методы рекурсивного программирования. М.: Машиностроение, 1983.

Учащимся

Учителям