При обучении программированию особую трудность вызывает работа с динамическими структурами данных

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

скачать rtf

-3-

Введение

При обучении программированию особую трудность вызывает работа с динамическими структурами данных. Как правило, такие структуры данных являются «самодельными», и программист сам должен управлять их размещением в памяти машины: порождать, модифицировать и уничтожать их в процессе выполнения программы. Все эти операции в конечном итоге реализуются на встроенных в вычислительную машину (ВМ) структурах данных (на базе модели памяти данной ВМ). При этом встроенные структуры данных отражают специфику организации ВМ (как совокупности программно-аппаратных средств), в то время как «самодельные» структуры данных отражают специфику решаемой задачи. Разрешение этого естественного противоречия может основываться на абстрагировании от деталей реализации динамических структур данных, на определении указанных структур через базовые операции над ними с описанием их характерных свойств.

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

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

Учащимся

Учителям