WEBVTT

00:00:12.396 --> 00:00:17.399
Тема лекции — практикум хода лабораторных
работ по учебной дисциплине «Математика

00:00:17.560 --> 00:00:22.803
информатика». Преподаватель, кандидат
педаук, доцент Романова Татьяна

00:00:23.003 --> 00:00:28.887
Николаевна. План занятия: технические и
программные средства реализации

00:00:29.127 --> 00:00:30.568
информационных процессов.

00:00:31.239 --> 00:00:36.485
Архитектура компьютера, уровни
программного обеспечения, современные

00:00:36.685 --> 00:00:43.452
операционные системы, их разновидности и
различия: защита информации на

00:00:43.532 --> 00:00:47.616
персональном компьютере, классификация
программного обеспечения.

00:00:48.076 --> 00:00:54.314
Информационные технологии, определения и
задачи, работа со сжатыми данными,

00:00:54.553 --> 00:00:57.832
архивирование, периферийные устройства.

00:01:52.307 --> 00:01:56.584
Под чертежом в рамках лабораторной работы
называют графическое изображение

00:01:57.304 --> 00:02:03.060
модулируемого объекта, характеризующее его
форму и размеры и выполненное по

00:02:03.180 --> 00:02:08.577
определённым правилам проектирования с
применением общепринятых соглашений по

00:02:08.737 --> 00:02:12.095
изображению и обозначению графических
элементов.

00:02:12.844 --> 00:02:15.092
По чертежам изготавливать детали.

00:02:15.775 --> 00:02:21.379
И производит сборку узлов, машин и
конструкций, чертёж на производстве — это

00:02:21.539 --> 00:02:27.664
основной технический документ, в котором
указаны необходимые сведения о деталях, их

00:02:27.744 --> 00:02:31.747
материале, термической обработке и
технические условия.

00:02:31.867 --> 00:02:37.511
На изготовление по нему проверяют качество
обработки на всех стадиях технического

00:02:37.751 --> 00:02:40.793
процесса, различают чертёж, детали.

00:02:41.706 --> 00:02:45.663
Сборочный чертёж, чертёж общего вида и
другого.

00:02:47.581 --> 00:02:53.856
В рамках лабораторной работы ставится
задача разработки программного комплекса

00:02:54.016 --> 00:02:58.252
для представления, редактирования
отображения на экране дисплея.

00:02:58.840 --> 00:03:04.635
конкретного типа графических данных,
чертежей, образуемых из ограниченного

00:03:04.795 --> 00:03:11.070
набора различных геометрических элементов,
точек, линий, окружности и тому подобное

00:03:12.029 --> 00:03:14.866
Разрабатываемый комплекс должен
обеспечивать

00:03:16.772 --> 00:03:22.409
Представление чертежей в памяти AVM,
демонстрацию хранимых чертежей на экране

00:03:22.449 --> 00:03:27.687
дисплея, редактирование чертежей, вставку
и удаление линий.

00:03:29.566 --> 00:03:33.044
Запись чтения данных о чертежах в файлах.

00:03:34.295 --> 00:03:38.972
Данная лабораторная работа является одной
из завершённых работ лабораторного

00:03:39.172 --> 00:03:43.289
практикума, учебного курса по методам
программирования.

00:03:43.849 --> 00:03:49.486
Тем самым постановка лабораторной работы
должна иметь повышенную сложность с тем,

00:03:49.686 --> 00:03:52.004
чтобы для выполнения работы потребовалось

00:03:52.988 --> 00:03:59.512
участие нескольких разработчиков Освоение
принципов командной работы является

00:04:00.033 --> 00:04:03.955
одной из ключевых учебных задач
лабораторной работы.

00:04:04.876 --> 00:04:10.440
Для успешного выполнения данной
лабораторной работы её реализация должна

00:04:10.560 --> 00:04:14.162
поручаться группе студентов из
трёх-четырех человек.

00:04:14.991 --> 00:04:19.988
Для лучшей координации выполняемых работ в
каждой группе может быть выделен

00:04:20.068 --> 00:04:25.625
ответственный за разработку главный
программист, в задачу которого входило бы

00:04:25.865 --> 00:04:31.662
согласование заданий на разработку,
распределение работ между участниками

00:04:31.822 --> 00:04:36.060
разработки, согласование спецификаций и
тому подобное.

00:04:36.945 --> 00:04:42.752
Отдельный разработчик, тестировщик может
отвечать за тестирование разрабатываемого

00:04:42.992 --> 00:04:49.520
кода. Ещё один разработчик — технический
писатель, может быть ориентирован на

00:04:49.680 --> 00:04:52.563
подготовку документации и презентации.

00:04:53.209 --> 00:04:54.929
по программе системы.

00:04:56.050 --> 00:05:01.013
Важной частью разработки программной
системы является реализация диалоговой

00:05:01.133 --> 00:05:04.655
программы для взаимодействия с
пользователем.

00:05:04.975 --> 00:05:11.539
Данная часть разработки также может быть
поручена отдельному участнику группы

00:05:11.779 --> 00:05:12.459
разработчиков

00:05:13.918 --> 00:05:19.872
С другой стороны, возможный вариант
выполнения лабораторной работы может

00:05:20.231 --> 00:05:26.105
состоять в использовании уже имеющихся
ранее разработанных диалоговых программ.

00:05:26.544 --> 00:05:31.619
В этом случае группе разработчиков следует
освоить правила использования IP.

00:05:32.133 --> 00:05:34.414
Передано для использования программы.

00:05:36.216 --> 00:05:42.059
Следует отметить важность выделенных ролей
участников группы разработчиков.

00:05:42.380 --> 00:05:48.263
От тестировщика зависит безошибочность,
надёжность разработанного кода программы.

00:05:49.002 --> 00:05:54.077
От разработчика диалоговой программы
зависит удобство использования программной

00:05:54.237 --> 00:06:00.671
системы. И наконец, от технического
редактора зависит лёгкость сопровождения и

00:06:00.791 --> 00:06:04.987
развития проекта и возможность более
широкого привлечения

00:06:05.822 --> 00:06:12.778
потенциальных потребителей разработанных
программ Условия и ограничения

00:06:13.658 --> 00:06:19.455
рамках выполнения данной лабораторной
работы могут быть использованы следующие

00:06:19.615 --> 00:06:21.214
основные допущения.

00:06:22.363 --> 00:06:28.003
В качестве чертежа будем рассматривать
плоский геометрический объект, состоящий

00:06:28.523 --> 00:06:35.242
из отрезков прямых линий и ограниченных
точек

00:06:35.442 --> 00:06:38.882
этих линий.

00:06:40.707 --> 00:06:45.388
Представление других геометрических
элементов может рассматриваться как тема

00:06:45.668 --> 00:06:47.749
дополнительных заданий.

00:06:51.510 --> 00:06:57.752
Набор линий, образующих чертёж, должен
быть связным, то есть любая линия чертежа

00:06:57.952 --> 00:07:02.153
должна иметь общую точку хотя бы с одной
другой линией чертежа.

00:07:03.657 --> 00:07:07.696
Пример возможного чертежа представлен на
следующем рисунке.

00:07:08.576 --> 00:07:14.534
Итак, представлен пример чертежа,
состоящего из трёх линий и трёх точек.

00:07:14.854 --> 00:07:19.014
В данном случае прямоугольная система
координат, треугольник

00:07:20.306 --> 00:07:26.141
Э-э, который состоит из трёх отрезков и
точек A, B, Ц.

00:07:28.179 --> 00:07:31.456
Метод решения структуры данных.

00:07:31.616 --> 00:07:37.890
Каждый чертёж может быть представлен в
виде множества базовых геометрических

00:07:38.010 --> 00:07:38.569
объектов.

00:07:39.214 --> 00:07:42.411
точек, линий, окружностей и так далее.

00:07:43.450 --> 00:07:50.044
Информационное описание объектов включает
в себя параметры, фигуры, координаты,

00:07:50.203 --> 00:07:56.158
размер, радиус и другие с различной
степенью детализации в зависимости от

00:07:56.317 --> 00:07:58.316
требований, предъявляемых к чертежу

00:07:59.133 --> 00:08:01.014
Данной предметной области.

00:08:01.655 --> 00:08:06.778
В общем случае, для описания фигуры
необходимо предусмотреть хранение

00:08:07.058 --> 00:08:10.100
координат некоторой опорной точки.

00:08:10.740 --> 00:08:16.984
Операции обработки геометрических объектов
состоят в задании и изменении

00:08:17.264 --> 00:08:17.905
параметров.

00:08:18.457 --> 00:08:22.893
А также визуализации, например, на экране
дисплея фигур.

00:08:25.770 --> 00:08:32.084
Для обеспечения возможности динамической
визуализации геометрических объектов в

00:08:32.164 --> 00:08:34.841
лабораторной работе вводится тип данных.

00:08:35.362 --> 00:08:40.405
Значения которых вычисляются в
соответствии с задаваемым формульным

00:08:40.725 --> 00:08:47.370
выражением. Возможная схема иерархии

00:08:47.530 --> 00:08:52.254
классов для представления базовых
геометрических элементов может состоять в

00:08:52.294 --> 00:08:55.536
следующем. В дальнейшем мы посмотрим на
рисунке семь.

00:08:56.399 --> 00:09:02.242
Наиболее общие свойства геометрических
фигур и методы их разработки выделяются в

00:09:02.322 --> 00:09:05.044
абстрактных базовых классах.

00:09:05.404 --> 00:09:10.768
От него наследуются классы для
представления точки, на основе которых

00:09:11.088 --> 00:09:13.930
реализуется класс для представления линии.

00:09:14.307 --> 00:09:17.629
...и классы для других геометрических
элементов.

00:09:18.590 --> 00:09:22.232
Точка определяется координатами на
плоскости.

00:09:22.472 --> 00:09:27.635
Значения координат определяются при помощи
формальных объектов класса.

00:09:29.236 --> 00:09:31.197
При формировании чертежа...

00:09:31.555 --> 00:09:36.831
Следует обратить внимание, что одна и та
же точка в чертеже может присутствовать

00:09:37.070 --> 00:09:42.785
несколько раз. В этом случае необходимо
обеспечить однократное представление точки

00:09:43.425 --> 00:09:48.500
без дублирования, для обеспечения
корректной работы операции вставки и

00:09:48.620 --> 00:09:49.300
удаления.

00:09:50.696 --> 00:09:56.337
Для представления линии в наиболее простом
варианте необходимо хранить начальную и

00:09:56.497 --> 00:09:57.817
конечную точку.

00:09:58.257 --> 00:10:03.337
В общем случае при формировании чертежа в
объекты линии могут храниться не

00:10:03.497 --> 00:10:07.778
координаты точек, а указатели на другие
линии чертежа.

00:10:09.085 --> 00:10:14.009
Данная ситуация допускается при выполнении
следующих условий.

00:10:15.771 --> 00:10:21.175
Начальная точка текущей линии может
определяться при помощи указателя на

00:10:21.335 --> 00:10:27.100
линию, конечная точка которой является
начальной точкой текущей линии.

00:10:30.572 --> 00:10:35.414
В данном случае вам показан показана
схема: абстрактный базовый

00:10:35.534 --> 00:10:41.177
класски, линия, окружность,

00:10:41.457 --> 00:10:47.620
квадрат. Прошу вас переписать данную
схему.

00:14:18.778 --> 00:14:24.018
Конечная точка текущей линии может
определяться при помощи указателя на

00:14:24.138 --> 00:14:29.498
линию. Конечная точка, которая является
конечной точкой текущей линии.

00:14:29.858 --> 00:14:34.777
Наряду с базовыми геометрическими
элементами, требующими для своего

00:14:34.897 --> 00:14:37.337
представления разработки отдельных классов

00:14:37.902 --> 00:14:43.188
В лабораторной работе предлагается
реализовать несколько различных способов

00:14:43.428 --> 00:14:50.195
формирования составных геометрических
объектов,

00:14:50.516 --> 00:14:54.720
образуемых на основе уже существующих
геометрических фигур.

00:14:55.256 --> 00:15:00.855
...как базовых, так и составных, и
рассматриваемых при выполнении операций

00:15:00.975 --> 00:15:03.175
обработки как единое целое.

00:15:04.255 --> 00:15:09.894
Возможные способы формирования составных
объектов состоят в следующем:

00:15:10.454 --> 00:15:11.454
группирование.

00:15:12.194 --> 00:15:18.360
Когда составной объект представляет набор
уже существующих, как

00:15:18.520 --> 00:15:23.805
базовых, так и базовых, так и составных
геометрических фигур.

00:15:24.285 --> 00:15:29.009
Подобной операцией является, например,
группирование в графическом редакторе

00:15:29.169 --> 00:15:30.130
системы Wort.

00:15:32.016 --> 00:15:38.016
Конструирование, когда составной объект
определяется на основе уже существующих

00:15:38.136 --> 00:15:39.896
геометрических фигур.

00:15:40.336 --> 00:15:46.657
Например, ломаная может быть определена
через набор конечных точек составляющих

00:15:46.817 --> 00:15:47.377
отрезки.

00:15:48.351 --> 00:15:54.513
Конструирование приводит к созданию новой
сложной геометрической фигуры, которая не

00:15:54.673 --> 00:15:59.435
может быть разделена на составные
геометрические элементы.

00:16:00.515 --> 00:16:06.917
Комбинирование, когда составной объект
формируется при помощи сборки существующих

00:16:07.077 --> 00:16:07.637
объектов.

00:16:08.162 --> 00:16:12.367
Так, например, чертёж может быть образован
из точек и линий.

00:16:12.847 --> 00:16:19.534
В рамках сконструированного объекта,
входящие в состав элементов, по-прежнему

00:16:20.055 --> 00:16:24.259
могут обрабатываться как отдельные
геометрические фигуры.

00:16:25.908 --> 00:16:30.829
Для представления данных, описывающих
структуру чертежа, предлагается

00:16:31.069 --> 00:16:34.030
использовать структуру хранения типа
«Плекс».

00:16:34.550 --> 00:16:39.471
Плекс — есть структура хранения,
включающая звенья различных типов,

00:16:39.671 --> 00:16:43.632
отношения между которыми задаются при
помощи сцепления.

00:16:44.916 --> 00:16:50.355
Таким образом, плекс является
разновидностью многосвязного списка и

00:16:50.515 --> 00:16:54.194
используется для хранения сетевых моделей
данных.

00:16:54.994 --> 00:17:01.552
Основу плексов для представления чертежей,
состоящих из линий и точек, составляют

00:17:01.632 --> 00:17:03.072
вершины, узлы.

00:17:03.590 --> 00:17:09.711
В каждой из которых располагается
информация о той или иной линии чертежа.

00:17:09.951 --> 00:17:14.151
Имя линия, координаты начальной и конечной
точки.

00:17:17.032 --> 00:17:20.712
Вам представлен пример разработанной
структуры хранения.

00:17:20.912 --> 00:17:23.952
На рисунке восемь приведён плекс для
чертежа.

00:17:38.213 --> 00:17:44.251
Алгоритмы. В качестве основных алгоритмов
обработки плексов в рамках лабораторной

00:17:44.371 --> 00:17:50.568
работы должны быть рассмотрены операции
обхода плексов, необходимых, например, при

00:17:50.768 --> 00:17:52.727
отрисовке чертежа.

00:17:53.287 --> 00:17:54.606
Реализация алгоритмов

00:17:56.656 --> 00:17:59.895
Платичек обхода плексов может быть
выполнена поэтапно.

00:18:00.055 --> 00:18:06.292
На первом этапе можно реализовать частный
алгоритм обхода плексов без подплексов,

00:18:06.372 --> 00:18:11.730
как, например, было предложено на рисунке
«Три» в предыдущей лабораторной работе.

00:18:12.278 --> 00:18:17.192
И только затем приступить к разработке
общего алгоритма обхода.

00:18:19.030 --> 00:18:21.388
Обход плекса без подплексов.

00:18:21.747 --> 00:18:26.302
Плексы без подплексов соответствуют
представлению чертежей, которые можно

00:18:26.622 --> 00:18:27.301
нарисовать.

00:18:27.702 --> 00:18:29.942
Без отрыва карандаша от бумаги.

00:18:30.222 --> 00:18:35.502
Пример такого объекта — треугольник
представлен на рисунке один,

00:18:35.702 --> 00:18:39.542
соответствующий плекс без подплексов
приведён на рисунке три.

00:18:39.942 --> 00:18:44.502
Для того чтобы нарисовать линию,
необходимо знать её начальную и конечную

00:18:44.702 --> 00:18:45.182
точку.

00:18:45.893 --> 00:18:52.051
Так как в подплексе допускается вместо
указателя точки хранения указатель линии,

00:18:52.171 --> 00:18:57.050
то необходимо найти первую линию, у
которой указатель начало — точка.

00:18:57.689 --> 00:19:00.569
В приведённом ранее примере на рисунке три

00:19:01.441 --> 00:19:03.039
Это линия BC.

00:19:03.398 --> 00:19:08.552
Тогда конечная точка этой линии будет
начальной точкой предыдущей линии в

00:19:08.592 --> 00:19:10.030
примере CA.

00:19:10.630 --> 00:19:15.823
То есть, на первом этапе необходимо
отыскать линию, у которой указатель

00:19:16.223 --> 00:19:17.262
начало-точки.

00:19:17.803 --> 00:19:23.997
При этом указатели на все пройденные линии
необходимо запомнить в стеке.

00:19:24.716 --> 00:19:29.591
На втором этапе из стека извлекаются
линии, для которых в качестве начальной

00:19:29.711 --> 00:19:33.867
точки выступает конечная точка
обработанной линии.

00:19:34.392 --> 00:19:40.192
Процесс заканчивается, когда в стеке
больше не содержится указателей на линию.

00:19:42.712 --> 00:19:44.912
Обход плекса с подплексами.

00:19:45.312 --> 00:19:50.192
Плекс с подплексами служит для
представления чертежей, которые нельзя

00:19:50.272 --> 00:19:52.952
нарисовать без отрыва карандаша от бумаги.

00:19:53.967 --> 00:19:57.368
Пример такого чертежа представлен на
рисунке девять.

00:19:58.208 --> 00:20:02.529
И возможная структура плекса, для которого
показана на рисунке 10.

00:20:03.969 --> 00:20:09.211
Рисунок No9 — пример чертежа, для
представления которого требуется плекс с

00:20:09.331 --> 00:20:10.131
подплексами.

00:20:11.105 --> 00:20:17.110
Верхняя горизонтальная линия состоит из
двух отрезков и

00:20:20.914 --> 00:20:27.279
Далее представлен пример чертежа, для
представления которого требуется плекс с

00:20:27.359 --> 00:20:28.160
подплексом.

00:20:29.313 --> 00:20:35.915
Верхняя горизонтальная линия состоит из
двух отрезков: D и B.

00:20:41.636 --> 00:20:47.077
Для таких плексов указатель на конечную
точку может также указывать на линию.

00:20:47.538 --> 00:20:53.183
То есть конечная точка линии верхнего узла
плекса может являться конечной точкой

00:20:53.343 --> 00:20:55.184
линии правого подплекса.

00:20:55.545 --> 00:21:01.549
Для обхода плекса с подплексами можно
предложить рекурсивный и нерекурсивный

00:21:01.669 --> 00:21:03.471
вариант. Общая схема.

00:21:04.544 --> 00:21:09.700
Рекурсивного алгоритма состоит в
следующем: вам предложен файл.

00:21:10.699 --> 00:21:15.895
То есть нужно отрисовать подплекс, на
который указывает указатель начальной

00:21:16.015 --> 00:21:19.572
точки, запомнить конечную точку подплекса.

00:21:20.738 --> 00:21:26.133
Отрисовать подплекс, на который указывает
указатель конечной точки, запомнить

00:21:26.253 --> 00:21:28.211
конечную точку подплекса.

00:21:29.330 --> 00:21:32.047
Отрисовать корневую линию.

00:21:33.166 --> 00:21:36.723
Для нерекурсивного алгоритма определим
класс.

00:21:37.910 --> 00:21:42.794
Чарт Лайн для представления линии, которая
подлежит отрисовке.

00:21:43.594 --> 00:21:50.559
Класс для методов отрисовки рисунка
представлен файл линия, начальная точка

00:21:50.839 --> 00:21:52.560
и конечная точка.

00:21:53.361 --> 00:21:54.201
Общая схема

00:21:55.973 --> 00:22:01.889
Алгоритм обхода состоит в следующем:
линии, определяемые при обходе плекса,

00:22:01.929 --> 00:22:03.368
помещаются в стек.

00:22:03.848 --> 00:22:08.805
При линии, извлекаемые из стека,
последовательно определяется начальная и

00:22:08.965 --> 00:22:10.364
конечная точка.

00:22:11.444 --> 00:22:15.721
Для определения начальной точки
используется метод джет.

00:22:16.514 --> 00:22:18.914
First Point линии.

00:22:19.794 --> 00:22:24.713
Если получаемый указатель указывает на
линию обработки текущей линии,

00:22:24.753 --> 00:22:31.192
откладывается линия помещается в стек и
начинается

00:22:31.432 --> 00:22:32.792
анализ новой линии.

00:22:33.458 --> 00:22:39.334
Данная процедура выполняется итеративно до
получения линии с известной начальной

00:22:39.774 --> 00:22:46.648
точкой. Для определения конечной точки
используется метод

00:22:46.808 --> 00:22:48.847
Get Last Point — линии.

00:22:49.557 --> 00:22:54.632
Если получаемый указатель указывает на
линию обработки текущей линии, снова

00:22:55.351 --> 00:22:59.946
откладывается текущая линия, помещается в
стек.

00:23:00.186 --> 00:23:05.580
После этого формируется описание новой
линии, которая также помещается в стек.

00:23:05.981 --> 00:23:09.260
И цикл алгоритма обхода повторяется.

00:23:10.060 --> 00:23:15.859
При получении линий с определёнными
граничными точками следует выполнить

00:23:16.019 --> 00:23:18.618
обработку линий, отрисовать.

00:23:18.978 --> 00:23:23.097
Из стека извлекается новая линия, для
которой конечная точка

00:23:23.965 --> 00:23:29.488
Обработанной линии используется в качестве
первой неизвестной граничной точки.

00:23:30.328 --> 00:23:35.531
Выполнение обхода завершается при
опустошении стека линии.

00:23:36.851 --> 00:23:39.812
Какова же разработка программного
комплекса?

00:23:39.933 --> 00:23:40.453
Структура

00:23:41.553 --> 00:23:46.718
С учётом рассмотренных выше предложений, к
реализации целесообразно представляется

00:23:46.958 --> 00:23:49.199
следующая структура программы.

00:23:49.800 --> 00:23:56.045
Это модуль с классом для формульного
транслятора, шаблонный класс для

00:23:56.245 --> 00:23:57.606
формульных значений.

00:23:58.502 --> 00:24:04.980
Шаблонный базовый абстрактный класс, класс
для точки.

00:24:05.220 --> 00:24:08.578
Класс для составного геометрического
объекта.

00:24:09.618 --> 00:24:14.616
Модуль с классами конструируемого
геометрического объекта и линии.

00:24:15.816 --> 00:24:22.532
Модуль программы тестирования, модуль
функций, реализующих визуальный диалоговый

00:24:23.012 --> 00:24:26.769
интерфейс для взаимодействия с
пользователем.

00:24:27.609 --> 00:24:31.447
Прошу запомнить и записать данные модули.

00:24:33.771 --> 00:24:35.204
Даю вам несколько минут.

00:27:01.758 --> 00:27:07.521
На рисунке далее показаны отношения между
классами стрелками с незакрашенными

00:27:07.641 --> 00:27:12.563
треугольниками показаны отношения
наследования: базовый класс — производный

00:27:12.683 --> 00:27:19.166
класс. Рамбовидными стрелками — отношения
ассоциации: класс владелец, класс

00:27:19.286 --> 00:27:19.927
компонент.

00:27:20.890 --> 00:27:27.209
Обычными стрелками показано наличие поля
типа указатель на другой класс.

00:27:29.408 --> 00:27:36.247
Класс формального транслятора, класс
формальных значений, абстрактный

00:27:36.367 --> 00:27:39.006
базовый класс для объектов значений.

00:27:40.341 --> 00:27:42.740
Далее абстрактный базовый класс.

00:27:43.300 --> 00:27:46.539
Класс для составного геометрического
объекта.

00:27:47.098 --> 00:27:48.978
Класс для точки.

00:27:56.963 --> 00:28:01.605
Класс для конструируемого геометрического
объекта.

00:28:01.725 --> 00:28:04.486
Класс для отрисовки линий.

00:28:08.648 --> 00:28:14.011
Спецификации классов с учётом предложенных
к реализации алгоритмов.

00:28:15.070 --> 00:28:18.829
Пессификации классов могут состоять в
следующем.

00:28:20.548 --> 00:28:25.667
Класс Eftran для формульного транслятора

00:28:28.186 --> 00:28:32.505
предложен вам файл Далее.

00:28:32.705 --> 00:28:35.824
Шаблонный класс для формульных значений.

00:29:06.555 --> 00:29:10.357
Следующий файл — шаблонный базовый
абстрактный класс.

00:29:29.330 --> 00:29:35.930
Далее класс Thardoint для точки, в

00:29:36.090 --> 00:29:39.489
которой необходимо указать координаты
точки.

00:29:40.609 --> 00:29:47.608
Далее произвести операции визуализацию
объекта, скрытие объекта,

00:29:48.088 --> 00:29:49.528
вычислить параметры.

00:29:50.295 --> 00:29:52.216
...и создать копию.

00:29:55.016 --> 00:30:02.016
Следующий файл, класс Thar Group для
создания геометрического объекта.

00:30:12.878 --> 00:30:16.876
...в который входит список графических
элементов группы.

00:30:18.435 --> 00:30:25.112
Необходимо будет вставить объект в группу,
где есть визуализация объекта,

00:30:25.591 --> 00:30:27.071
скрытие объекта.

00:30:28.710 --> 00:30:29.589
Необходимо...

00:30:30.532 --> 00:30:33.693
Вычислить параметры и создание копии.

00:30:37.014 --> 00:30:43.456
Класс Techart для конструируемого
геометрического объекта представлен.

00:30:52.513 --> 00:30:58.391
В данном случае класс для методовки
рисунков.

00:30:59.191 --> 00:31:03.749
Линия, начальная точка, конечная точка.

00:31:08.627 --> 00:31:11.905
Нужно получить начальную точку, конечную
точку.

00:31:12.506 --> 00:31:16.269
Вставить начальную и конечную точки.

00:31:17.870 --> 00:31:22.873
Необходима визуализация рисунка и скрытие
рисунка.

00:31:25.275 --> 00:31:27.477
Предлагаются этапы разработки.

00:31:28.305 --> 00:31:33.550
Выполнение лабораторной работы должно быть
разделено на несколько этапов.

00:31:34.471 --> 00:31:40.156
Каждый из этих этапов должен иметь
достаточно небольшую длительность.

00:31:40.316 --> 00:31:46.242
При этом должна обеспечиваться возможность
решения поставленной прикладной задачи.

00:31:46.889 --> 00:31:53.333
...той или иной ограниченной постановки на
как можно более ранних этапах выполнения

00:31:53.493 --> 00:31:59.176
работ С учётом высказанных рекомендаций,
последовательность разработки программ

00:31:59.657 --> 00:32:01.138
может быть следующей.

00:32:01.538 --> 00:32:02.458
Этап первый.

00:32:02.967 --> 00:32:07.886
Реализация программ для работы с флексами
простой структуры, например, для одной

00:32:08.006 --> 00:32:10.845
линии. Этап второй.

00:32:11.285 --> 00:32:16.284
Реализация программ для работы с основными
геометрическими объектами.

00:32:16.924 --> 00:32:18.523
Поддержка группирования.

00:32:20.027 --> 00:32:26.470
Этап третий — реализация отрисовки чертежа
на основе алгоритма обхода плексов без

00:32:26.710 --> 00:32:32.872
подплексов. Этап должен включать развитие
диалоговой формы управления.

00:32:33.872 --> 00:32:35.193
Этап четвёртый.

00:32:35.513 --> 00:32:39.955
Реализация операций чтения и записи
информации в файл.

00:32:41.347 --> 00:32:46.468
Этап пятый — реализация общего алгоритма
обхода флексов.

00:32:47.668 --> 00:32:52.830
Этап шесть — реализация дополнительных
операций обхода флексов.

00:32:53.630 --> 00:32:58.911
Результаты выполнения каждого этапа
требуют проведения самого тщательного

00:32:59.111 --> 00:32:59.912
тестирования.

00:33:00.595 --> 00:33:04.798
Поскольку возможные ошибки могут
проявляться только после некоторого

00:33:05.079 --> 00:33:07.721
длительного времени работы с плексами.

00:33:08.161 --> 00:33:14.326
Ошибочные ситуации могут возникать не при
каждом сценарии выполнения программ.

00:33:15.687 --> 00:33:17.569
Рекомендации по разработке.

00:33:18.415 --> 00:33:22.891
Набор программ для работы с плексами
представляет собой достаточно сложную

00:33:23.091 --> 00:33:24.490
программную систему.

00:33:25.010 --> 00:33:30.366
При выполнении лабораторной работы следует
уделять особое внимание техническим

00:33:30.485 --> 00:33:33.763
аспектам разработки программного
обеспечения.

00:33:34.469 --> 00:33:39.749
Этапность разработки, тщательное
тестирование, командную методику

00:33:39.909 --> 00:33:46.669
выполнения работ, обеспечение простого и
понятного интерфейса, использование

00:33:46.909 --> 00:33:50.148
инструментов поддержки процесса
разработки.

00:33:50.865 --> 00:33:56.463
Система контроля версий, система
поддержки, тестирования и другое.

00:33:59.222 --> 00:34:02.781
Вам предложены возможные темы
дополнительных заданий.

00:34:03.061 --> 00:34:08.379
Для развития навыков практического
программирования рекомендуются следующие

00:34:08.499 --> 00:34:11.698
направления расширения постановки задачи.

00:34:12.448 --> 00:34:16.527
Реализовать построение чертежа с
использованием дополнительных

00:34:16.647 --> 00:34:22.844
геометрических элементов, окружности и их
дуг, прямоугольников и другое.

00:34:23.603 --> 00:34:29.001
Разработка операций динамического
изменения, вставка и удаление линий.

00:34:29.357 --> 00:34:31.279
Для чертежа флекса.

00:34:32.000 --> 00:34:38.206
Реализовать проверку тождественности
чертежей для разных схем структур данных.

00:34:38.846 --> 00:34:44.452
Разработка представления арифметических
выражений с использованием флексов.

00:34:45.493 --> 00:34:48.255
Реализовать построение блоков схем.

00:34:50.451 --> 00:34:54.774
Критерии оценивания выполнения данной
лабораторной работы.

00:34:55.295 --> 00:35:00.098
Лабораторная работа считается выполненной
при выполнении следующего минимального

00:35:00.218 --> 00:35:01.499
набора требований.

00:35:02.260 --> 00:35:07.744
Реализованы все классы, разработанные
программы обеспечивают демонстрацию

00:35:07.904 --> 00:35:10.986
методов отрисовки плекса без подплекса.

00:35:12.074 --> 00:35:15.475
Данные для построения считаются из файла.

00:35:15.755 --> 00:35:20.876
В качестве примера может быть использован
чертёж, представленный на рисунке No6.

00:35:21.596 --> 00:35:26.837
В расширенном варианте выполнения
лабораторной работы должен быть реализован

00:35:27.077 --> 00:35:28.958
обход плекса с подплексами.

00:35:29.787 --> 00:35:35.582
Организован визуальный пользовательский
интерфейс с функциями чтения, записи

00:35:35.742 --> 00:35:41.577
данных Applexy File, обеспечена поддержка
анимации и другое.

00:35:43.536 --> 00:35:45.934
Вопросы и задания для самоконтроля.

00:35:46.870 --> 00:35:51.111
Какие возможные модели можно использовать
для представления чертежа?

00:35:51.471 --> 00:35:53.792
В чём состоит модель чертежа?

00:35:54.552 --> 00:35:58.233
Какая структура хранения используется для
чертежа?

00:35:58.793 --> 00:36:04.594
Какие преимущества и недостатки есть у
рекурсивного и нерекурсивного алгоритмов

00:36:04.794 --> 00:36:05.914
обхода плекса?

00:36:07.070 --> 00:36:13.263
Как можно модифицировать алгоритм обхода
плекса для проверки чертежа на связность?

00:36:17.259 --> 00:36:24.212
Теперь переходим к изучению лабораторной
работы номер восемь, в которой мы должны

00:36:26.037 --> 00:36:32.877
Научиться статистической обработке
результатов экзаменационной

00:36:32.997 --> 00:36:38.998
сессии, где будет постановка учебной
задачи, основные понятия и

00:36:39.118 --> 00:36:43.438
определения, требования, предложенные к
лабораторной работе.

00:36:43.891 --> 00:36:49.257
Условия и ограничения, методы решения,
структуры данных,

00:36:49.618 --> 00:36:55.985
алгоритмы, разработка программного
комплекса, структуры,

00:36:56.105 --> 00:36:59.469
спецификации классов, этапы разработки.

00:36:59.990 --> 00:37:06.155
Рекомендации по разработке, возможные темы
дополнительных заданий.

00:37:13.041 --> 00:37:16.884
Критерии оценивания выполнения данной
лабораторной работы.

00:37:17.749 --> 00:37:20.870
Вопросы и задания для самоконтроля.

00:37:24.152 --> 00:37:29.754
Статистическая обработка результатов
экзаменационной сессии.

00:37:29.834 --> 00:37:30.475
Таблицы.

00:37:32.248 --> 00:37:36.927
Представление данных во многих задачах и
из разных областей человеческой

00:37:37.087 --> 00:37:40.646
деятельности может быть организовано при
помощи таблиц.

00:37:41.365 --> 00:37:46.204
Таблицы представляют собой
последовательности строк, записей,

00:37:46.404 --> 00:37:48.683
структура строк может быть различной.

00:37:49.259 --> 00:37:55.703
Но обязательным является поле, задающее
имя ключ записи.

00:38:00.386 --> 00:38:06.711
Таблицы применяются в бухгалтерском учёте,
ведомости разработанной платы, в торговле,

00:38:06.791 --> 00:38:07.752
прайс-листы.

00:38:08.378 --> 00:38:13.620
В образовательных учреждениях
экзаменационные ведомости и является одним

00:38:13.780 --> 00:38:19.141
из наиболее распространённых структур
данных, используемых при создании

00:38:19.261 --> 00:38:23.263
системного и прикладного математического
обеспечения.

00:38:24.503 --> 00:38:26.023
Таблица широко применяется

00:38:27.480 --> 00:38:34.240
Трансляторах, таблицы идентификаторов и
операционных системах могут

00:38:34.320 --> 00:38:41.199
рассматриваться как программная реализация
ассоциативной памяти и тому подобное.

00:38:42.639 --> 00:38:46.959
Существование отношения иметь имя,
является обязательным в

00:38:47.842 --> 00:38:53.364
в большинстве разрабатываемых
программистами структур данных Доступ по

00:38:53.444 --> 00:38:58.645
имени в этих структурах служит для
получения соответствия между адресным

00:38:58.805 --> 00:39:05.247
принципом указания элементов памяти ЭВМ и
общепринятым, более удобным для человека

00:39:05.924 --> 00:39:09.487
способом указания объектов по их именам.

00:39:10.648 --> 00:39:16.613
Целью данной лабораторной работы помимо
изучения способов организации таблиц,

00:39:16.813 --> 00:39:20.536
является начальное знакомство с принципами

00:39:21.261 --> 00:39:26.976
Проектирование структур хранения,
используемых в методах решения прикладных

00:39:27.176 --> 00:39:32.571
задач. На примере таблиц изучается
возможность выбора разных вариантов

00:39:32.771 --> 00:39:39.205
структур хранения, анализ их эффективности
и определение областей приложения, в

00:39:39.285 --> 00:39:39.565
которых

00:39:40.078 --> 00:39:44.877
Выбираемые структуры хранения являются
наиболее эффективными.

00:39:46.557 --> 00:39:52.235
В качестве практической задачи, на примере
которой будет продемонстрированы возможные

00:39:52.395 --> 00:39:57.194
способы организации таблиц,
рассматривается проблема статистической

00:39:57.394 --> 00:40:01.793
обработки результатов экзаменационной
успеваемости студентов.

00:40:02.577 --> 00:40:08.063
Выполнение таких, например, вычислений,
как определение среднего балла по предмету

00:40:08.944 --> 00:40:14.870
или по программе при назначении студентов
на стипендию или при распределении

00:40:15.110 --> 00:40:18.634
студентов по кафедрам и тому подобное.

00:40:21.015 --> 00:40:23.294
Постановка учебной задачи.

00:40:23.454 --> 00:40:25.612
Основные понятия и определения.

00:40:25.812 --> 00:40:28.051
Таблица доска.

00:40:28.250 --> 00:40:33.527
Перевод с латинского — это динамическая
структура данных, базисным множеством

00:40:33.687 --> 00:40:37.804
которым является семейство линейных
структур и записей.

00:40:38.700 --> 00:40:44.867
Базисное отношение включения определяется
операциями вставки и удаления записей.

00:40:46.909 --> 00:40:52.275
Запись — кортеж, каждый элемент которого
обычно именуется полем.

00:40:53.316 --> 00:40:54.797
Имя записи — ключ.

00:40:55.261 --> 00:41:01.896
Одно из полей записи, по которому обычно
осуществляется поиск записи в таблице.

00:41:02.215 --> 00:41:05.653
Остальные поля образуют тело записи.

00:41:07.491 --> 00:41:12.887
Двоичное дерево поиска — это представление
данных в виде дерева.

00:41:13.368 --> 00:41:17.290
Для которого выполняются следующие
условия.

00:41:19.531 --> 00:41:26.294
Для любого узла вершины дерева существует
не более двух потомков — двоичное дерево.

00:41:27.054 --> 00:41:31.576
Для любого узла значение во всех узлах
левого поддерева

00:41:32.122 --> 00:41:34.162
Меньше значения в узле.

00:41:34.642 --> 00:41:41.003
Для любого узла значение во всех узлах
правого поддерева больше значения в узле.

00:41:41.763 --> 00:41:48.403
Кэш-функция — это функция, ставящая в
соответствие ключу номер записи в таблице.

00:41:48.964 --> 00:41:55.531
используется при организации таблиц с
вычислимым

00:41:55.731 --> 00:41:56.932
входом.

00:41:58.254 --> 00:42:00.617
Требования к лабораторной работе.

00:42:01.177 --> 00:42:05.782
В рамках данной лабораторной работы
ставится задача создания программных

00:42:05.902 --> 00:42:06.183
средств

00:42:07.024 --> 00:42:12.822
поддерживающих табличные динамические
структуры данных таблицы и базовые

00:42:12.942 --> 00:42:19.580
операции над ними Поиск записи Вставка
записи без дублирования

00:42:20.700 --> 00:42:21.780
удаление записи

00:42:23.207 --> 00:42:28.689
Выполнение операций над таблицами может
осуществляться с различной степенью

00:42:28.809 --> 00:42:34.611
эффективности в зависимости от способа
организации таблицы.

00:42:35.251 --> 00:42:40.213
В рамках лабораторной работы как
показатель эффективности предлагается

00:42:40.493 --> 00:42:42.774
использовать количество операций.

00:42:43.335 --> 00:42:47.972
необходимых для выполнения операции поиска
записи в таблице.

00:42:48.892 --> 00:42:54.289
Величина этого показателя должна
определяться как аналитически при

00:42:54.489 --> 00:42:59.006
использовании тех или иных упрощающих
предложений

00:42:59.590 --> 00:43:05.268
Так и экспериментально, на основе
проведения вычислительных экспериментов.

00:43:05.588 --> 00:43:11.826
В лабораторной работе предлагаются
реализовать следующие типы таблиц.

00:43:16.504 --> 00:43:18.983
Просмотровые, неупорядоченные.

00:43:19.738 --> 00:43:26.497
Упорядоченные сортированные таблицы со
структурами хранения на основе

00:43:26.657 --> 00:43:32.736
деревьев поиска-таблицы или перемешанные с
вычисляемыми

00:43:32.896 --> 00:43:39.694
адресами. Необходимо разработать интерфейс
доступа к операциям поиска,

00:43:39.774 --> 00:43:41.134
вставки и удаления.

00:43:41.648 --> 00:43:45.645
независящий от способа организации
таблицы.

00:43:45.964 --> 00:43:51.120
Демонстрацию работоспособности
разрабатываемых при выполнении

00:43:51.719 --> 00:43:57.514
лабораторной работы программ следует
проводить на примере таблиц, содержащих

00:43:57.634 --> 00:43:58.912
данные о результатах

00:43:59.412 --> 00:44:02.534
Экзаменационной успеваемости студентов.

00:44:02.974 --> 00:44:07.577
Для данного примера следует реализовать
следующие операции

00:44:09.539 --> 00:44:15.503
таблицы для таблицы с результатами
успеваемости отдельной студенческой

00:44:15.703 --> 00:44:16.183
группы.

00:44:17.255 --> 00:44:23.542
Это получение сведений об успеваемости
отдельного студента, оценка по конкретному

00:44:23.662 --> 00:44:27.546
предмету, сравнение оценки по всем
предметам.

00:44:28.307 --> 00:44:32.192
Определение средней оценки по группе по
отдельным предметам.

00:44:32.617 --> 00:44:39.575
Или по всем предметам Подсчитать
количество студентов,

00:44:39.695 --> 00:44:45.652
отличников и тому подобное для нескольких
таблиц с результатами успеваемости для

00:44:45.812 --> 00:44:47.892
всех студенческих групп курса.

00:44:49.098 --> 00:44:53.775
Получение средних оценок по всем
студенческим группам по отдельному

00:44:53.855 --> 00:44:57.053
предмету или по всем предметам.

00:44:59.092 --> 00:45:05.169
Определение студенческой группы с лучшей
успеваемостью по конкретному предмету или

00:45:05.449 --> 00:45:08.327
по всем предметам экзаменационной сессии.

00:45:09.409 --> 00:45:15.486
Подсчёт количества студентов-отличников
для всего курса и тому подобное.

00:45:16.286 --> 00:45:22.723
Задача обработки результатов успеваемости
может быть расширена возможностью хранения

00:45:22.963 --> 00:45:29.200
данных для нескольких экзаменационных
сессий, например, за весь период обучения

00:45:29.399 --> 00:45:30.079
студентов.

00:45:31.718 --> 00:45:36.553
Указанный выше набор операций обработки
результатов успеваемости является

00:45:37.112 --> 00:45:38.791
минимально необходимым.

00:45:39.590 --> 00:45:46.543
Определение полного перечня необходимых
операций должно выполняться на этапе

00:45:46.663 --> 00:45:48.861
постановки в лабораторной работе.

00:45:49.515 --> 00:45:55.680
В том числе, например, могут быть выбраны
различающиеся выборы операций для

00:45:55.881 --> 00:45:59.964
получения разных постановок лабораторной
работы.

00:46:01.846 --> 00:46:07.091
Результаты обработки успеваемости
рекомендуется дополнять построением

00:46:07.211 --> 00:46:07.812
графиков.

00:46:08.240 --> 00:46:10.677
...и диаграмм различного вида.

00:46:11.637 --> 00:46:17.351
Например, диаграммы по средним баллам для
разных студенческих групп, графики

00:46:17.511 --> 00:46:20.508
успеваемости студентов по разным
предметам.

00:46:22.387 --> 00:46:25.704
Полезным расширением постановки
лабораторной работы.

00:46:26.198 --> 00:46:32.914
Является реализация возможности передачи
данных в офисные программы семейства

00:46:35.072 --> 00:46:41.108
Например, в систему обработки электронных
таблиц Microsoft Excel.

00:46:44.506 --> 00:46:46.584
Условия и ограничения.

00:46:48.482 --> 00:46:51.521
Сделаем следующие основные допущения.

00:46:53.120 --> 00:46:58.916
В качестве ключа будем рассматривать
фамилию и инициалы студента в качестве

00:46:59.156 --> 00:47:04.393
полей данных — это экзаменационные оценки
по учебным дисциплинам.

00:47:06.235 --> 00:47:12.674
Сведения об экзаменационной успеваемости
должны быть разнесены по разным таблицам

00:47:13.114 --> 00:47:16.314
для каждой студенческой группы в
отдельности.

00:47:17.713 --> 00:47:22.233
Исходные данные, количество и наименование
дисциплин, данные

00:47:23.049 --> 00:47:29.253
О результатах сессии должны извлекаться из
текстовых файлов для каждой

00:47:29.333 --> 00:47:31.815
студенческой группы в отдельности.

00:47:33.376 --> 00:47:38.180
При изменении состояния таблиц должна
обеспечиваться возможность

00:47:38.749 --> 00:47:42.030
Сохранение данных в текстовых файлах.

00:47:43.071 --> 00:47:48.394
Для контроля правильности работы программ
должна обеспечиваться возможность

00:47:48.914 --> 00:47:51.515
пакетного выполнения операций.

00:47:52.035 --> 00:47:57.718
Наименования операций и их параметры
задаются при помощи текстового файла.

00:47:59.543 --> 00:48:05.497
После выполнения пакета операций и
сохранения данных должна быть реализована

00:48:05.657 --> 00:48:12.410
возможность сравнения полученных файлов с
заранее подготовленными проверочными

00:48:12.729 --> 00:48:17.125
файлами. Метод решения.

00:48:18.415 --> 00:48:19.735
Структуры данных.

00:48:20.815 --> 00:48:26.973
Под таблицей следует понимать динамическую
структуру данных, которая в каждый момент

00:48:27.533 --> 00:48:33.291
выполнения вычислений состоит из конечного
набора элементов записей.

00:48:34.170 --> 00:48:38.852
Записи таблицы могут подразделяться на
несколько полей.

00:48:39.692 --> 00:48:45.974
При этом количество и тип полей являются
одинаковыми для всех записей таблицы.

00:48:47.014 --> 00:48:50.655
Первое поле всех записей таблицы является
ключом.

00:48:51.849 --> 00:48:55.964
Поля записи без ключевого поля образуют
тело записи.

00:48:57.522 --> 00:49:01.318
Первое поле всех записей таблицы является
ключом.

00:49:01.678 --> 00:49:07.111
Например, задавая соответствие между
интентификаторами переменных именами

00:49:07.948 --> 00:49:13.345
...и адресами памяти AVM Мы можем получить
простейшую таблицу вида

00:49:14.824 --> 00:49:21.340
имя, в которой есть и адрес, в которой

00:49:21.500 --> 00:49:24.658
каждая строка записи состоит из двух
полей.

00:49:25.403 --> 00:49:29.324
Поле ключа, имени и поле тела, записи
адреса.

00:49:30.164 --> 00:49:36.806
Таблица, содержащая экзаменационные
оценки, имеет следующий вид: фамилия, имя,

00:49:36.886 --> 00:49:39.086
отчество студента.

00:49:39.526 --> 00:49:43.727
Дисциплина: первая, вторая, третья,
четвёртая и так далее.

00:49:45.185 --> 00:49:48.784
...и соответствующие оценки по каждой
дисциплине.

00:49:50.103 --> 00:49:56.822
Для этой таблицы каждая строка состоит из
ключа, фамилии, имя, отчество и телозаписи

00:49:57.101 --> 00:50:01.260
поля, содержащего оценки по четырём
дисциплинам.

00:50:02.663 --> 00:50:05.941
Основные операции, выполняемые над
таблицами.

00:50:06.540 --> 00:50:10.378
Поиск записи по одному или нескольким
ключам.

00:50:10.937 --> 00:50:14.615
Вставка записи с контролем возможных
повторений.

00:50:15.455 --> 00:50:17.533
Удаление записи.

00:50:20.491 --> 00:50:22.770
Операции вставки и удаления.

00:50:24.229 --> 00:50:31.075
Служит для формирования требуемого набора
записей Операция поиска записи по ключу

00:50:31.836 --> 00:50:36.921
обеспечивает доступ по имени ключ к
записям таблицы.

00:50:41.285 --> 00:50:42.165
Алгоритмы.

00:50:44.783 --> 00:50:46.745
Просматриваемые таблицы.

00:50:47.186 --> 00:50:52.992
Простейшим способом отыскания нужного
элемента является метод полного просмотра

00:50:53.433 --> 00:50:59.319
сканирования, когда искомый ключ
сравнивается по очереди со всеми ключами

00:50:59.520 --> 00:51:00.120
таблицы.

00:51:00.871 --> 00:51:07.866
Начиная с первого, вплоть до отыскания
совпадающего элемента или до исчерпывания

00:51:08.146 --> 00:51:14.781
записей. Если ключи в таблице расположены
в произвольном порядке, неупорядоченная

00:51:14.901 --> 00:51:18.818
таблица, этот способ является единственно
возможным.

00:51:20.315 --> 00:51:26.313
Операция вставки в неупорядоченную таблицу
может быть выполнена путём добавления

00:51:26.553 --> 00:51:32.711
новой записи в конец таблицы с
корректировкой номера последней занятой

00:51:32.791 --> 00:51:39.349
строки. Операция удаления строки может
быть реализована при помощи

00:51:40.521 --> 00:51:47.353
Переписывание последней записи таблицы на
место удаляемой и соответствующей

00:51:47.433 --> 00:51:50.390
корректировки номера последней строки.

00:51:51.948 --> 00:51:55.264
Среднее количество просматриваемых записей
таблицы

00:51:55.816 --> 00:52:00.816
При поиске записи по ключу при
предположении равной вероятности

00:52:01.216 --> 00:52:07.656
использования ключей определяется
следующим соотношением: Т среднее равно P

00:52:07.936 --> 00:52:10.817
умножить на N большое делённое на 2

00:52:11.425 --> 00:52:16.740
Плюс разность 1 минус p, умноженное на н.

00:52:17.979 --> 00:52:24.613
Где P вероятность того, что искомая запись
имеется в таблице большое N количество

00:52:24.813 --> 00:52:29.609
записей в таблице упорядоченные таблицы.

00:52:30.448 --> 00:52:35.727
При большом количестве записей в таблице
Nного больше единицы.

00:52:35.927 --> 00:52:41.567
Затраты на выполнение полного просмотра
становятся значительными.

00:52:41.847 --> 00:52:47.807
Эффективность процедуры поиска может
повысить при размещении записи в таблице в

00:52:47.927 --> 00:52:49.167
порядке возрастания.

00:52:50.168 --> 00:52:52.007
...или убывание ключей.

00:52:52.807 --> 00:52:56.205
Упорядоченная или сортированная таблица.

00:52:57.044 --> 00:53:01.921
Упорядоченность таблиц может быть
организована только при возможности

00:53:02.161 --> 00:53:05.479
сравнения ключей на множестве ключей.

00:53:06.027 --> 00:53:09.066
Задано отношение линейного порядка.

00:53:09.626 --> 00:53:16.026
Для поиска нужной записи в таких таблицах
может быть использован

00:53:17.586 --> 00:53:21.386
быстрый метод бинарного двоичного поиска.

00:53:21.866 --> 00:53:22.746
Вместе с тем,

00:53:23.267 --> 00:53:28.952
В упорядоченных таблицах усложняется
реализация операций вставки и удаления

00:53:29.152 --> 00:53:35.118
записей, при выполнении которых, для
сохранения упорядоченности становится

00:53:35.399 --> 00:53:38.442
необходимой перепаковка записей в таблицы.

00:53:39.861 --> 00:53:46.104
Среднее количество просматриваемых записей
таблицы при использовании бинарного поиска

00:53:46.304 --> 00:53:52.586
определяется следующим образом: среднее
равно логарифму по основанию 2

00:53:53.347 --> 00:53:59.709
числа nabliss на основе деревьев

00:53:59.869 --> 00:54:00.430
поиска.

00:54:01.663 --> 00:54:07.740
Снижение трудоёмкости операций вставки и
удаления за счёт исключения перепаковок

00:54:08.340 --> 00:54:13.377
может быть обеспечено при использовании
списковых структур хранения.

00:54:14.097 --> 00:54:20.614
При этом сохранение эффективности
двоичного поиска требует прямого доступа к

00:54:20.734 --> 00:54:21.293
звену.

00:54:21.622 --> 00:54:24.059
Со средней записью таблицы.

00:54:25.098 --> 00:54:30.491
Из этого звена должна существовать
возможность доступа к средним записям

00:54:30.611 --> 00:54:34.127
левой и правой частей таблицы и так далее.

00:54:35.286 --> 00:54:37.963
Данные требования могут быть обеспечены

00:54:38.637 --> 00:54:44.590
При использовании деревьев поиска для
представления таблиц Использование

00:54:44.790 --> 00:54:50.584
деревьев поиска обеспечивает сложность
средним логарифма по основанию двух числа

00:54:50.704 --> 00:54:56.219
Н для всех операций обработки, поиска,
вставки и удаления таблиц.

00:54:57.182 --> 00:55:01.743
Т среднее равно логарифму по основанию 2
числа n.

00:55:02.383 --> 00:55:08.664
Максимальная сложность обработки деревьев
поиска имеет порядок Bn большого в случае

00:55:09.104 --> 00:55:12.265
вырождения деревья в список.

00:55:13.145 --> 00:55:15.745
Для исключения вырожденных случаев

00:55:16.443 --> 00:55:23.083
Деревья поиска обобщаются до
сбалансированных деревьев поиска, в

00:55:23.243 --> 00:55:29.042
которых высота поддерв для любых узлов
отличается не более, чем на

00:55:29.642 --> 00:55:31.962
первое. Подобные деревья

00:55:32.531 --> 00:55:39.403
обеспечивает сложность порядка логарифма
по основанию двух числа Nых

00:55:39.563 --> 00:55:46.515
вариантов исходных данных но требует
расхода времени на проведение балансировки

00:55:47.560 --> 00:55:52.243
Методы балансировки деревьев поиска могут
быть рассмотрены в качестве

00:55:52.523 --> 00:55:54.604
дополнительного задания.

00:55:56.846 --> 00:55:59.767
Таблицы с вычисляемыми адресами.

00:56:00.288 --> 00:56:06.171
Иной возможный способ построения таблиц
при большом количестве записей состоит в

00:56:06.251 --> 00:56:07.011
предварительном

00:56:07.956 --> 00:56:13.280
Перед непосредственным поиском по таблице
вычисления месторасположения искомой

00:56:13.400 --> 00:56:20.245
записи. Данный метод предполагает наличие
некоторой простой

00:56:20.325 --> 00:56:22.526
функции H, которая

00:56:24.314 --> 00:56:29.112
отображает множество имён на множество
номеров строк таблицы.

00:56:29.872 --> 00:56:36.429
Эта функция называется функцией
хэширования или расстановки таблицы,

00:56:36.549 --> 00:56:39.028
получаемые при таком способе построения

00:56:40.947 --> 00:56:47.020
Называются хэш-таблицами, таблицами с
вычисляемыми адресами или

00:56:47.380 --> 00:56:50.257
перемешиваемыми таблицами.

00:56:52.974 --> 00:56:56.970
Функции расстановки могут быть построены
разными способами.

00:56:58.689 --> 00:57:04.012
Например, в качестве номера строки, в
которой хранится или будет храниться при

00:57:04.172 --> 00:57:10.976
вставке «Некоторый ключ», можно взять код
первого символа имени, либо сумму

00:57:11.136 --> 00:57:14.138
всех кодов символов ключа по модулю числа.

00:57:15.485 --> 00:57:21.367
M, где M — длина таблицы — размер массива,
отведённого для её

00:57:21.607 --> 00:57:28.369
хранения. При использовании таблиц с
вычисляемыми адресами

00:57:29.009 --> 00:57:31.890
может возникнуть ряд дополнительных
проблем.

00:57:33.833 --> 00:57:39.396
Так, например, при вставке новой записи
функция расстановки может выдавать номер

00:57:39.916 --> 00:57:41.958
занятой строки массива.

00:57:42.838 --> 00:57:49.282
Функция расстановки может определять один,
то есть для значения для нескольких

00:57:49.402 --> 00:57:50.723
различных ключей.

00:57:52.638 --> 00:57:58.155
Такая ситуация при вставке записи
называется относительным переполнением

00:57:58.275 --> 00:58:01.953
таблицы или коллизией.

00:58:05.231 --> 00:58:10.348
При возникновении коллизий возможны разные
методы их решения.

00:58:11.009 --> 00:58:12.490
Рассмотрим два из них.

00:58:13.371 --> 00:58:18.976
Метод открытого перемешивания состоит в
добавлении к вычисленному занятому номеру

00:58:19.457 --> 00:58:22.420
некоторого фиксированного смещения.

00:58:23.260 --> 00:58:29.827
Повторное перемешивание K-штрих равно K+ p
умножить на модуль

00:58:30.877 --> 00:58:35.800
Есть новый адрес К-штрих также является
занятым.

00:58:36.040 --> 00:58:41.044
Следует повторить процедуру повторного
перемешивания до тех пор, пока не

00:58:41.164 --> 00:58:46.208
обнаружится свободная строка, либо таблица
не будет исчерпана.

00:58:46.773 --> 00:58:51.851
Или значения P и N большое являются
взаимнопростыми.

00:58:52.171 --> 00:58:57.970
Открытое перемешивание обеспечивает
нахождение свободной строки массива.

00:58:59.769 --> 00:59:01.648
Следующий метод цепочки.

00:59:02.308 --> 00:59:08.904
При возникновении коллизий формирует
линейные списки-цепочки, в

00:59:09.024 --> 00:59:15.580
каждом из которых располагаются записи с
одинаковым значением функции расстановки.

00:59:16.059 --> 00:59:18.138
В этом случае в строках массива

00:59:18.795 --> 00:59:25.071
Для размещения записей следует добавить
ещё одно поле для рассылки на следующее

00:59:25.231 --> 00:59:26.630
звено списка.

00:59:28.388 --> 00:59:34.424
Среднее количество рассматриваемых записей
при поиске записи в перемешиваемых

00:59:34.584 --> 00:59:35.303
таблицах.

00:59:36.014 --> 00:59:42.217
При предположении равной вероятности
использования ключей и при использовании

00:59:42.417 --> 00:59:48.380
функции расстановки с равномерным
рассеиванием ключей по строкам массива

00:59:49.141 --> 00:59:51.902
определяется следующим соотношением.

00:59:52.754 --> 00:59:57.154
Разрешение коллизии по методу открытого
перемешивания.

00:59:58.954 --> 01:00:05.355
Среднее равно отношению числителя 1 минус
альфа, делённое на два к знаменателю 1

01:00:05.635 --> 01:00:07.075
минус альфа.

01:00:07.275 --> 01:00:08.915
Где альфа — это коэффициент

01:00:09.781 --> 01:00:14.906
Заполненности таблицы Альфа равно Н
относится к N.

01:00:15.346 --> 01:00:21.272
M большое количество строк в массиве для
хранения записей, N большое количество

01:00:21.512 --> 01:00:23.034
записей в таблице.

01:00:23.675 --> 01:00:28.840
Следует отметить, что количество сравнений
при поиске в перемешиваемых таблицах

01:00:29.440 --> 01:00:35.044
Зависит не от количества записей в
таблице, а от заполненности памяти,

01:00:35.364 --> 01:00:37.886
отведённой для размещения записей.

01:00:38.406 --> 01:00:45.170
Для примера, при заполненности массива на
75% альфа равно 0,75%

01:00:45.803 --> 01:00:50.485
Количество сравнений в среднем равно 2,5%.

01:00:51.406 --> 01:00:53.767
Разработка программного комплекса.

01:00:54.007 --> 01:00:54.728
Структура.

01:00:56.006 --> 01:01:01.891
При выполнении данной лабораторной работы
следует разработать иерархию классов,

01:01:02.051 --> 01:01:08.336
учитывая, что все таблицы имеют как общие
свойства, их описание следует поместить в

01:01:08.456 --> 01:01:14.381
определении базового класса, так и
особенности выполнения отдельных операций.

01:01:15.064 --> 01:01:20.069
Реализуется в отдельных классах для
каждого вида таблиц.

01:01:20.630 --> 01:01:24.994
При разработке классов используется ранее
разработанный класс TD

01:01:26.475 --> 01:01:32.041
Palis рекомендуемый состав классов
приведён

01:01:32.525 --> 01:01:38.606
Ниже. В данном случае это модуль с классом
объектов-значений для записей

01:01:38.726 --> 01:01:45.126
таблицы. Абстрактный базовый класс
содержит спецификации методов

01:01:45.246 --> 01:01:52.087
таблицы. Абстрактный базовый класс для
таблиц

01:01:52.287 --> 01:01:53.807
с непрерывной памятью.

01:01:57.701 --> 01:02:02.625
Модуль с классом, обеспечивающим
реализацию просматриваемых таблиц.

01:02:07.669 --> 01:02:12.032
Модуль с классом, обеспечивающим
реализацию упорядоченных таблиц.

01:02:16.793 --> 01:02:23.636
Модуль с абстрактным базовым классом
объектов-значений для деревьев.

01:02:24.037 --> 01:02:28.839
Модуль с классом, реализующим таблицы в
виде деревьев поиска.

01:02:30.960 --> 01:02:35.843
Модуль с базовым классом объектов-значений
для сбалансированных деревьев.

01:02:40.333 --> 01:02:45.172
Модуль с классом, реализующим таблицы в
виде сбалансированных деревьев поиска

01:02:48.812 --> 01:02:54.891
модуль с базовым классом, обеспечивающим
реализацию таблиц с вычислительным

01:02:55.290 --> 01:02:55.850
входом.

01:02:59.352 --> 01:03:03.707
Модуль с классом, обеспечивающим
реализацию хэш-таблиц.

01:03:04.306 --> 01:03:08.422
Разрешение коллизий на основе открытого
перемешивания.

01:03:11.459 --> 01:03:15.415
Модуль с классом, обеспечивающим
реализацию хэш-таблиц.

01:03:16.148 --> 01:03:19.585
Разрешение коллизий на основе метода
цепочек.

01:03:23.342 --> 01:03:25.780
Модуль программы тестирования.

01:03:28.377 --> 01:03:30.016
Спецификации классов.

01:03:30.136 --> 01:03:34.492
С учётом предложенных к реализации
алгоритмов можно сделать следующие

01:03:34.651 --> 01:03:35.850
объявления классов.

01:03:36.679 --> 01:03:39.879
Класс объектов-значений для записи
таблицы.

01:03:40.439 --> 01:03:47.319
Вам предложен файл,

01:03:48.039 --> 01:03:53.518
в котором есть тип ключа записи, класс
объектов-значений для записи таблицы.

01:03:54.499 --> 01:04:00.494
Поля, ключи записи, указатель на значение,
методы.

01:04:01.053 --> 01:04:07.448
Конструктор. Установить значение ключа,
получить значение ключа.

01:04:08.647 --> 01:04:11.125
Установить указатель на данные.

01:04:11.284 --> 01:04:13.043
Получить указатель на данные.

01:04:13.872 --> 01:04:20.353
Изготовить копию, присваивание, сравнение
равно

01:04:20.553 --> 01:04:22.113
больше/меньше.

01:04:22.593 --> 01:04:25.994
Дружественные классы для различных типов
таблиц.

01:04:26.954 --> 01:04:27.994
Смотрите далее.

01:04:37.250 --> 01:04:41.733
Данный тип описывает значение ключей
записи.

01:04:43.935 --> 01:04:49.260
В данном примере для типа ключей
использован класс стринг из стандартной

01:04:49.380 --> 01:04:51.902
библиотеки шаблонов STL.

01:04:52.382 --> 01:04:53.703
Абстрактный базовый

01:04:54.270 --> 01:05:00.753
Класс содержит спецификации методов
таблицы Table H, в которой у нас

01:05:00.913 --> 01:05:06.755
предлагается определять количество записей
в таблице, показатель эффективности

01:05:07.075 --> 01:05:09.076
выполнения операций.

01:05:11.517 --> 01:05:12.837
Далее, диструктор.

01:05:13.305 --> 01:05:20.218
Информационные методы, количество записей,
эффективность пуста, пуста ли

01:05:20.337 --> 01:05:22.055
запись заполнена.

01:05:22.375 --> 01:05:28.289
Доступ основные методы: найти запись,
вставить, удалить.

01:05:29.269 --> 01:05:34.668
Навигация. Установить на первую запись
Таблица завершена.

01:05:34.788 --> 01:05:36.988
Переход к следующей записи.

01:05:41.627 --> 01:05:45.147
Все методы данного класса расподелены на
четыре группы.

01:05:45.699 --> 01:05:47.620
Информационные методы.

01:05:47.940 --> 01:05:54.423
Это получить количество записей, получить
эффективность последней операции.

01:05:55.183 --> 01:05:57.905
Проверить, не является ли таблица пустой.

01:05:58.705 --> 01:06:01.026
Проверить, не является ли таблица полной.

01:06:03.047 --> 01:06:05.686
Второй метод доступа к записям.

01:06:06.086 --> 01:06:09.366
Получить значение ключа текущей записи.

01:06:09.926 --> 01:06:13.366
Получить указатель на значение текущей
записи.

01:06:14.526 --> 01:06:18.565
Третий метод — методы навигации по таблице
итератор.

01:06:20.265 --> 01:06:23.701
Установить текущую позицию на первую
запись.

01:06:24.660 --> 01:06:27.018
Проверка завершения таблицы.

01:06:27.138 --> 01:06:31.573
Под ситуацией завершения таблицы
понимается состояние после применения

01:06:31.733 --> 01:06:35.768
метода Go Next для текущей позиции
установления

01:06:37.282 --> 01:06:44.005
Установленный на последней записи таблицы
переместить текущую позицию на следующую

01:06:44.205 --> 01:06:49.527
запись. Четвёртые методы обработки
таблицы.

01:06:50.088 --> 01:06:52.849
Поиск записи по значению ключа.

01:06:53.621 --> 01:06:57.017
Вставка записи в таблицу, удаление записи.

01:06:58.096 --> 01:07:03.091
Абстрактный класс для таблиц с непрерывной
памятью служит для управления структурой

01:07:03.610 --> 01:07:10.443
хранения. Предложен к вашему рассмотрению
файл, в котором включён «память для

01:07:10.603 --> 01:07:11.642
записи таблицы».

01:07:12.662 --> 01:07:16.141
Максимальное возможное количество записей
из таблицы.

01:07:16.861 --> 01:07:18.301
Номер текущей записи.

01:07:18.380 --> 01:07:20.740
Нумерация начинается с нуля.

01:07:21.819 --> 01:07:27.018
Конструктор, деструктор, информационные
методы.

01:07:27.578 --> 01:07:31.177
Затем определяется вопрос: заполнена ли
таблица?

01:07:32.760 --> 01:07:34.361
Каково количество записей?

01:07:34.641 --> 01:07:36.802
Доступ.

01:07:37.082 --> 01:07:42.084
Основные методы: найти запись, вставить,
удалить запись.

01:07:42.644 --> 01:07:46.006
Навигация. Установить на первую запись.

01:07:46.366 --> 01:07:47.727
Таблица завершена.

01:07:48.673 --> 01:07:50.593
Переход к следующей записи.

01:07:51.953 --> 01:07:58.431
После применения для последней записи
таблицы установить текущую запись получить

01:07:58.591 --> 01:08:01.230
номер текущей записи.

01:08:03.830 --> 01:08:06.829
Данный класс обеспечивает управление
памятью.

01:08:07.287 --> 01:08:09.888
Выделение и освобождение памяти.

01:08:10.368 --> 01:08:15.331
Методы доступа применимы к первой, текущей
и последней записям таблицы.

01:08:15.731 --> 01:08:20.694
Желаемый вариант доступа задаётся через
параметр метода доступа.

01:08:21.455 --> 01:08:22.495
Методы set.

01:08:24.459 --> 01:08:31.251
Corenpos установить текущую позицию на
запись с заданным номером и получить номер

01:08:31.611 --> 01:08:37.524
текущей записи вводят операции прямого
доступа к записям таблицы в классе

01:08:37.604 --> 01:08:39.881
«Реализованные методы навигации».

01:08:41.324 --> 01:08:47.888
Следующий файл — класс, обеспечивающий
реализацию просматриваемой таблицы Test

01:08:53.612 --> 01:08:57.454
В данном классе реализованы методы
обработки таблицы.

01:08:59.312 --> 01:09:05.073
Далее файл упорядочение таблицы Tsort
Table.

01:09:07.034 --> 01:09:10.234
Метод сортировки, сортировка данных.

01:09:10.554 --> 01:09:13.995
Метод вставок, слияние.

01:09:14.595 --> 01:09:15.915
Быстрая сортировка.

01:09:17.537 --> 01:09:21.497
Конструктор из просматриваемой таблицы.

01:09:21.897 --> 01:09:25.817
Присваивание. Получить метод сортировки.

01:09:26.097 --> 01:09:28.816
Установить метод сортировки.

01:09:29.056 --> 01:09:30.416
Основные методы.

01:09:30.856 --> 01:09:32.936
Найти запись, вставить.

01:09:33.653 --> 01:09:35.012
Или удалить запись.

01:09:35.691 --> 01:09:39.608
В данном классе приводится три метода
сортировки.

01:09:39.768 --> 01:09:43.605
Другие методы сортировки могут
рассматриваться как задания для

01:09:43.685 --> 01:09:45.444
самостоятельного выполнения.

01:09:46.323 --> 01:09:51.279
Метод поиска записи основан на алгоритме
бинарного поиска.

01:09:53.245 --> 01:10:00.089
В методах вставки и удаления происходит
обращение к

01:10:00.169 --> 01:10:04.652
методу поиска и производится перепаковка
таблицы.

01:10:08.254 --> 01:10:12.537
Файл абстрактного базового класса объектов
значений для деревьев.

01:10:21.696 --> 01:10:27.728
Также предложен файл таблицы со структурой
хранения в виде деревьев поиска, в котором

01:10:27.848 --> 01:10:33.002
выполняются функции указатель на корень
дерева, адрес указателя на вершину

01:10:33.162 --> 01:10:36.797
результата, указатель на текущую вершину.

01:10:37.261 --> 01:10:39.181
Номер текущей вершины.

01:10:39.621 --> 01:10:43.342
Стек для итератора, удаление.

01:10:43.502 --> 01:10:47.343
Деструктор. Информационные методы.

01:10:47.503 --> 01:10:50.383
Запись, заполнена ли таблица.

01:10:50.543 --> 01:10:52.423
Основные методы — найти.

01:10:53.343 --> 01:10:56.145
Вставить либо удалить запись.

01:10:57.225 --> 01:11:03.269
Навигация. Установить на первую запись
завершение

01:11:03.470 --> 01:11:06.712
таблицы. Переход к следующей записи.

01:11:10.274 --> 01:11:14.317
Для обхода дерева используется стек из
библиотеки СТЛ.

01:11:14.728 --> 01:11:18.604
В нём запоминаются указатели на пройденные
узлы дерева.

01:11:19.882 --> 01:11:24.438
Базовый класс значений для
сбалансированных деревьев будет иметь

01:11:24.518 --> 01:11:25.916
следующий вид.

01:11:28.194 --> 01:11:30.671
Далее — класс для сбалансированных

01:11:32.370 --> 01:11:32.810
деревьев

01:11:42.085 --> 01:11:47.803
является сбалансированным, если для
каждого из узла высота левого и правого

01:11:48.003 --> 01:11:51.041
поддеревья различается не более чем на
единицу.

01:11:52.720 --> 01:11:58.555
Так как операция вставки и удаления могут
нарушать сбалансированность дерева, то

01:11:58.795 --> 01:12:02.831
необходимо в таких случаях проводить
процедуру балансировки.

01:12:03.751 --> 01:12:09.346
Базовый класс для таблицы с вычислимым
входом THASTABL.

01:12:10.848 --> 01:12:17.049
В классе содержится хэш-функция,
вычисляющая по ключу записи номер строки в

01:12:17.129 --> 01:12:18.969
структуре хранения.

01:12:20.209 --> 01:12:25.850
Класс для таблицы с вычислимым входом,
использующим для решения коллизий открытое

01:12:26.050 --> 01:12:26.890
перемещение.

01:12:33.955 --> 01:12:38.838
Предложен вам файл, в который включены
функции «память для записи таблицы»,

01:12:38.918 --> 01:12:44.562
максимально возможное количество записей,
функция «шаг вторичного перемещения».

01:12:45.437 --> 01:12:49.077
Первая свободная строка обнаружения при
поиске.

01:12:49.357 --> 01:12:55.957
Строка памяти при завершении поиска,
маркер для индикации строк с удалёнными

01:12:56.197 --> 01:13:01.517
записями. Конструктор.

01:13:01.975 --> 01:13:03.856
Информационные методы.

01:13:04.256 --> 01:13:11.061
Затем определяется функция заполнения
таблицы, доступы, основные методы,

01:13:11.181 --> 01:13:16.425
навигация. При открытом перемешивании,
добавление новых записей возможно

01:13:17.472 --> 01:13:22.634
При наличии свободных строк в таблице
Разрешение коллизии происходит путём

01:13:22.754 --> 01:13:28.676
вычисления нового адреса для записи, пока
не будет найдена свободная строка.

01:13:29.036 --> 01:13:32.998
Поэтому при удалении строка таблицы
помещается как удалённая

01:13:33.700 --> 01:13:40.420
Без фактического удаления и освобождения
памяти, но сохраняется возможность записи

01:13:40.900 --> 01:13:44.060
в неё нового значения при необходимости

01:13:49.420 --> 01:13:51.180
класс таблиц вычисления

01:13:53.808 --> 01:13:59.245
С вычислимым входом, использующим для
разрешения коллизий метода цепочек.

01:14:00.005 --> 01:14:05.122
Включены следующие функции: память для
массива указателей на списке записей,

01:14:05.322 --> 01:14:09.800
размер массива указателей, список, котором
выполняется поиск.

01:14:10.892 --> 01:14:16.176
Конструктор. Информационные методы,
заполнена ли таблица.

01:14:16.296 --> 01:14:18.578
Доступ основные методы.

01:14:18.658 --> 01:14:21.140
Найти запись, вставить, удалить запись

01:14:25.743 --> 01:14:28.305
навигация, установить на первую запись.

01:14:28.769 --> 01:14:32.011
Таблица завершена, переход к следующей
записи.

01:14:32.772 --> 01:14:38.295
В методе цепочек добавления новых записей
в случае возникновения коллизий происходит

01:14:38.536 --> 01:14:41.217
путём добавления значения в список.

01:14:41.738 --> 01:14:46.621
В связи с тем необходимо использовать
ранее разработанный класс для списков TD.

01:14:50.291 --> 01:14:51.852
Этапы разработки.

01:14:52.292 --> 01:14:58.535
Как и ранее выполнение лабораторной работы
должно быть разделено на несколько этапов.

01:14:58.655 --> 01:15:03.298
Каждый из этапов должен иметь достаточно
небольшую длительность.

01:15:03.791 --> 01:15:09.629
При этом должны обеспечиваться возможность
решения поставленной прикладной задачи в

01:15:09.749 --> 01:15:16.227
той или иной ограниченной постановке на
как можно более ранних этапах выполнения

01:15:16.387 --> 01:15:21.745
работ. С учётом высказанных рекомендаций,
последовательность разработки программ

01:15:22.265 --> 01:15:23.824
может быть следующей.

01:15:24.518 --> 01:15:30.832
Этап первый. Реализация программ для
работы с просматриваемыми таблицами.

01:15:31.551 --> 01:15:37.505
Выполнение этапа может быть разделено на
несколько итераций: реализация некоторой

01:15:37.625 --> 01:15:41.661
упрощённой схемы начального заполнения
таблицы.

01:15:42.524 --> 01:15:44.765
Реализация операции поиска.

01:15:45.566 --> 01:15:47.848
Реализация операции вставки.

01:15:48.408 --> 01:15:50.810
Реализация операции удаления.

01:15:51.610 --> 01:15:56.774
Результаты каждой итерации должны быть
протестированы, переход к следующей

01:15:56.854 --> 01:15:58.215
итерации разработки.

01:15:58.888 --> 01:16:04.162
Должен осуществляться только после
успешного выполнения всех запланированных

01:16:04.322 --> 01:16:10.876
тестов. На данном этапе должен быть
разработан начальный вариант диалоговой

01:16:11.036 --> 01:16:14.432
формы управления табличными операциями.

01:16:15.919 --> 01:16:22.163
Этап второй. Реализация первой очереди
операций прикладной задачи из постановки

01:16:22.404 --> 01:16:24.045
лабораторной работы.

01:16:24.285 --> 01:16:28.848
Статистическая обработка результатов
экзаменационной сессии.

01:16:29.328 --> 01:16:34.052
В числе реализуемых операций может быть,
например, ввод исходных данных.

01:16:34.667 --> 01:16:40.185
Из текстовых файлов получение данных об
успеваемости отдельных студентов

01:16:40.704 --> 01:16:47.621
вычисление средних оценок по отдельным
предметам и другое Этап

01:16:47.741 --> 01:16:51.100
должен включать развитие диалоговой формы
управления

01:16:51.869 --> 01:16:56.946
Третий этап — реализация программ для
работы с упорядоченными таблицами.

01:16:57.386 --> 01:17:02.503
Для проверки правильности работы программ
результаты выполнения должны сравниваться

01:17:02.663 --> 01:17:06.861
с результатами, получаемыми при помощи
просматриваемых

01:17:07.468 --> 01:17:13.673
таблиц. На этом же этапе может быть
расширен список реализованных операций

01:17:14.114 --> 01:17:19.599
прикладной задачи и продолжено развитие
диалоговой формы управления.

01:17:20.199 --> 01:17:25.003
На данном этапе должны быть начаты работы
по получению графических форм.

01:17:25.484 --> 01:17:28.841
результатов обработки экзаменационных
данных.

01:17:29.321 --> 01:17:34.957
Например, построение диаграмм по средним
баллам для различных студенческих групп,

01:17:35.157 --> 01:17:39.513
графики успеваемости студентов по разным
предметам и другое.

01:17:40.472 --> 01:17:41.552
Этап четвёртый.

01:17:42.606 --> 01:17:47.327
Реализация программ для работы с таблицами
на основе деревьев поиска.

01:17:48.208 --> 01:17:55.170
Дальнейшее расширение списка реализованных
операций прикладной задачи, диалоговой

01:17:55.290 --> 01:17:57.690
формы управления, графических форм.

01:17:58.262 --> 01:18:00.942
вывода результатов тестирования.

01:18:01.782 --> 01:18:07.702
Этап пятый. Реализация программ для работы
с таблицами с вычислимым

01:18:07.902 --> 01:18:13.823
входом. Дальнейшее расширение списка
реализованных операций прикладной задачи,

01:18:13.863 --> 01:18:17.063
диалоговой формы управления графических
форм.

01:18:17.708 --> 01:18:20.468
вывода результатов тестирования.

01:18:20.908 --> 01:18:22.228
Этап шестой.

01:18:22.389 --> 01:18:27.949
Выполнение вычислительных экспериментов
для оценки эффективности различных

01:18:28.109 --> 01:18:34.270
способов организации таблиц разработка
различных генераторов последовательности

01:18:34.510 --> 01:18:36.030
выполняемых операций.

01:18:37.095 --> 01:18:43.170
Генерация только операций поиска,
генерация потока операций всех типов,

01:18:43.530 --> 01:18:49.364
генерация потоков операций с равномерным
использованием ключей и тому подобное.

01:18:50.763 --> 01:18:52.602
Рекомендации по разработке.

01:18:53.565 --> 01:18:59.005
Следует уделить большое внимание
определению состава реализуемых операций

01:18:59.445 --> 01:19:04.685
прикладной задачи по статистической
обработке результатов экзаменационной

01:19:04.805 --> 01:19:05.325
сессии.

01:19:06.283 --> 01:19:11.168
Набор операций может быть достаточно
ограничен, но должен обеспечивать

01:19:11.368 --> 01:19:16.493
поддержку основных процедур анализа
успеваемости, обычно выполняемых

01:19:16.653 --> 01:19:18.414
работниками деканата.

01:19:19.455 --> 01:19:23.059
Ориентированность на практическое
использование предъявляет

01:19:23.947 --> 01:19:29.865
Особые требования к проектированию
диалоговой формы управления таблицами.

01:19:30.345 --> 01:19:37.183
Обычное требование для интерфейса с
пользователем состоит в обеспечении

01:19:37.423 --> 01:19:38.783
наглядности, понятности

01:19:39.689 --> 01:19:41.969
...дружественности и тому подобное.

01:19:42.528 --> 01:19:47.807
При практическом использовании программ
особое значение имеет наличие графических

01:19:47.927 --> 01:19:50.807
форм представления результатов обработки.

01:19:51.766 --> 01:19:56.005
Как и прежде, должно быть обеспечено
надёжное функционирование.

01:19:56.517 --> 01:19:58.119
Разработанных программ.

01:19:58.759 --> 01:20:04.683
С этой целью может быть разработан тот или
иной генератор текстовых данных для

01:20:04.883 --> 01:20:07.925
многократной проверки правильности
программ.

01:20:08.846 --> 01:20:13.129
В числе тестов должны быть и таблицы
достаточно большого объёма.

01:20:15.156 --> 01:20:20.273
При выполнении лабораторной работы может
быть рекомендована командная форма

01:20:20.473 --> 01:20:21.872
разработки программ.

01:20:22.352 --> 01:20:27.708
В составе команды один разработчик может
отвечать за реализацию программ для

01:20:27.868 --> 01:20:34.664
таблиц. Другой разработчик может отвечать
за разработку диалоговых форм управления

01:20:34.824 --> 01:20:35.623
таблицами.

01:20:36.509 --> 01:20:41.985
Ещё один может заниматься разработкой
графических форм, выводом результатов

01:20:42.305 --> 01:20:48.100
разработки и, наконец, отдельный
разработчик может проводить тестирование.

01:20:48.740 --> 01:20:54.175
Обязанности разработчиков могут изменяться
в ходе выполнения лабораторной работы.

01:20:54.937 --> 01:20:57.456
Возможные темы дополнительных заданий.

01:20:57.896 --> 01:21:02.616
Для развития навыков практического
программирования рекомендуется следующие

01:21:02.736 --> 01:21:08.495
направления расширения постановки задачи:
реализовать дополнительные операции над

01:21:08.535 --> 01:21:09.255
таблицами.

01:21:10.010 --> 01:21:15.413
Реализовать методы балансировки деревьев,
поиска и выполнить вычислительные

01:21:15.613 --> 01:21:22.175
эксперименты по оценке эффективности
операций с таблицей при балансировке,

01:21:22.456 --> 01:21:27.818
сравнить работу с таблицей при наличии и в
отсутствии методов балансировки.

01:21:28.984 --> 01:21:35.420
Реализовать дополнительный набор операций
для обработки результатов успеваемости.

01:21:35.780 --> 01:21:40.297
Реализовать дополнительный набор
графических форм вывода результатов

01:21:40.576 --> 01:21:45.013
обработки. Реализовать расширенное
представление таблиц.

01:21:48.042 --> 01:21:53.724
Выполнить замену разработанных программ
для реализации таблиц на средства работы с

01:21:53.804 --> 01:21:56.045
таблицами библиотеки СТЛ.

01:21:56.365 --> 01:22:00.407
Оценить трудоёмкость выполнения такой
замены.

01:22:00.927 --> 01:22:05.128
Выполнить лабораторную работу на примере
другой прикладной задачи.

01:22:06.554 --> 01:22:09.834
Критерии оценивания данной лабораторной
работы.

01:22:10.194 --> 01:22:16.435
Лабораторная работа считается с данной при
выполнении минимального набора требований.

01:22:17.275 --> 01:22:23.235
Реализованы просматриваемая упорядоченная
хэш-таблица.

01:22:23.811 --> 01:22:26.410
Таблицы на основе деревьев поиска.

01:22:26.770 --> 01:22:31.087
Эффективность поиска в лучшем, худшем и
среднем случаях соответствует

01:22:31.407 --> 01:22:33.206
теоретическим оценкам.

01:22:34.046 --> 01:22:39.244
Для рассматриваемой прикладной задачи
реализовано четыре-пять операций.

01:22:39.635 --> 01:22:45.757
для обработки результатов экзаменационной
сессии и две-три графические формы вывода

01:22:47.078 --> 01:22:51.679
в более полном варианте выполнения
лабораторной работы реализованы два

01:22:51.959 --> 01:22:55.440
варианта разрешения коллизий в
хэш-таблице.

01:22:55.600 --> 01:22:59.962
Реализован класс таблиц на основе
сбалансированного дерева.

01:23:01.668 --> 01:23:04.107
Вопросы и задания для самоконтроля.

01:23:04.466 --> 01:23:09.544
Приведите примеры прикладных задач, при
решении которых могут быть использованы

01:23:09.664 --> 01:23:14.941
таблицы. Какие дополнительные операции
могут быть полезны при обработке

01:23:15.061 --> 01:23:17.820
результатов экзаменационной сессии?

01:23:19.729 --> 01:23:24.613
Для разных способов организации таблиц
приведите примеры задач, в которых эти

01:23:24.853 --> 01:23:27.616
способы являются наиболее эффективными.

01:23:28.337 --> 01:23:34.102
Какова трудоёмкость алгоритма сортировки
вставками, алгоритма сортировки слиянием

01:23:34.422 --> 01:23:36.304
методом быстрой сортировки?

01:23:37.329 --> 01:23:41.969
В чём различие сбалансированных и идеально
сбалансированных деревьев поиска?

01:23:42.769 --> 01:23:47.089
Почему при реализации таблиц не
используются идеально сбалансированные

01:23:47.249 --> 01:23:53.128
деревья поиска? Какие рекомендации следует
учитывать при выборе хэш-функций?

01:23:54.155 --> 01:23:57.389
Какие существуют методы разрешения
коллизий?

01:23:57.509 --> 01:24:00.064
Укажите их сильные и слабые стороны.

