WEBVTT

00:00:12.288 --> 00:00:17.329
Тема лекции — практикум хода лабораторных
работ по учебной дисциплине «Математика

00:00:17.449 --> 00:00:22.730
информатика». Преподаватель, кандидат
петаук, доцент Романова Татьяна

00:00:22.890 --> 00:00:28.810
Николаевна. План занятия: технические и
программные средства реализации

00:00:29.010 --> 00:00:30.450
информационных процессов.

00:00:31.188 --> 00:00:36.382
Архитектура компьютера, уровни
программного обеспечения, современные

00:00:36.582 --> 00:00:43.294
операционные системы и их разновидности и
различия: защита информации на

00:00:43.374 --> 00:00:47.410
персональном компьютере, классификация
программного обеспечения.

00:00:48.030 --> 00:00:54.237
Информационные технологии, определения и
задачи, работа со сжатыми данными,

00:00:54.477 --> 00:00:57.680
архивирование, периферийные устройства.

00:01:52.188 --> 00:01:56.471
Под чертежом в рамках лабораторной работы
называют графическое изображение

00:01:57.191 --> 00:02:02.994
модулируемого объекта, характеризующее его
форму и размеры и выполненное по

00:02:03.114 --> 00:02:08.157
определённым правилам проектирования с
применением общепринятых соглашений.

00:02:08.547 --> 00:02:14.863
по изображению и обозначению графических
элементов По чертежам изготавливать детали

00:02:15.502 --> 00:02:15.542
и

00:02:16.326 --> 00:02:21.286
Производит сборку узлов, машин и
конструкций, чертёж на производстве — это

00:02:21.446 --> 00:02:27.565
основной технический документ, в котором
указаны необходимые сведения о деталях, их

00:02:27.605 --> 00:02:31.645
материале, термической обработке и
технические условия.

00:02:31.725 --> 00:02:37.405
На изготовление по нему проверяют качество
обработки на всех стадиях технического

00:02:37.645 --> 00:02:38.205
процесса.

00:02:38.753 --> 00:02:45.109
Различают чертёж, детали, сборочный
чертёж, чертёж общего вида и другого

00:02:47.507 --> 00:02:53.743
в рамках лабораторной работы ставится
задача разработки программного комплекса

00:02:53.943 --> 00:02:58.140
для представления, редактирования
отображения на экране дисплея.

00:02:58.739 --> 00:03:04.534
конкретного типа графических данных,
чертежей, образуемых из ограниченного

00:03:04.694 --> 00:03:10.968
набора различных геометрических элементов,
точек, линий, окружностей и тому подобное

00:03:11.967 --> 00:03:14.805
Разрабатываемый комплекс должен
обеспечивать

00:03:16.637 --> 00:03:22.314
Представление чертежей в памяти AVM,
демонстрацию хранимых чертежей на экране

00:03:22.394 --> 00:03:27.632
дисплея, редактирование чертежей, вставку
и удаление линий.

00:03:29.471 --> 00:03:32.909
Запись чтения данных о чертежах в файлах.

00:03:34.170 --> 00:03:38.886
Данная лабораторная работа является одной
из завершённых работ лабораторного

00:03:39.046 --> 00:03:43.203
практикума, учебного курса по методам
программирования.

00:03:43.762 --> 00:03:49.078
Тем самым постановка лабораторной работы
должна иметь повышенную сложность тем

00:03:49.623 --> 00:03:55.783
Чтобы для выполнения работы потребовалось
участие нескольких разработчиков.

00:03:56.543 --> 00:04:01.943
Освоение принципов командной работы
является одной из ключевых учебных задач

00:04:02.103 --> 00:04:03.623
лабораторной работы.

00:04:04.743 --> 00:04:06.183
Для успешного выполнения

00:04:06.942 --> 00:04:12.383
Данной лабораторной работы, её реализация
должна поручаться группе студентов из

00:04:12.543 --> 00:04:14.344
трёх-четырех человек.

00:04:14.824 --> 00:04:19.905
Для лучшей координации выполняемых работ в
каждой группе может быть выделен

00:04:19.985 --> 00:04:23.146
ответственный за разработку главный
программист.

00:04:24.009 --> 00:04:29.852
задачу которого входило бы согласование
заданий на разработку, распределение работ

00:04:30.453 --> 00:04:36.497
между участниками разработки согласование
спецификаций и тому подобное.

00:04:36.737 --> 00:04:42.661
Отдельный разработчик-тестировщик может
отвечать за тестирование разрабатываемого

00:04:42.861 --> 00:04:43.061
кода

00:04:43.864 --> 00:04:49.386
Ещё один разработчик — технический
писатель — может быть ориентирован на

00:04:49.586 --> 00:04:54.787
подготовку документации и презентаций по
программе системы.

00:04:55.908 --> 00:05:00.909
Важной частью разработки программной
системы является реализация диалоговой

00:05:01.029 --> 00:05:04.230
программы для взаимодействия с
пользователем.

00:05:04.964 --> 00:05:11.400
Данная часть разработки также может быть
поручена отдельному участнику группы

00:05:11.720 --> 00:05:18.235
разработчиков. С другой стороны, возможный
вариант выполнения лабораторной работы

00:05:19.754 --> 00:05:25.231
может состоять в использовании уже
имеющихся ранее разработанных диалоговых

00:05:25.311 --> 00:05:25.830
программ.

00:05:26.518 --> 00:05:31.877
В этом случае группе разработчиков следует
освоить правила использования IP,

00:05:31.957 --> 00:05:38.196
переданных для использования программы
Следует отметить важность

00:05:38.516 --> 00:05:41.716
выделенных ролей участников группы
разработчиков.

00:05:42.387 --> 00:05:48.348
От тестировщика зависит безошибочность,
надёжность разработанного кода программ.

00:05:48.828 --> 00:05:53.990
От разработчика диалоговой программы
зависит удобство использования программной

00:05:54.150 --> 00:05:58.471
системы. И наконец, от технического
редактора зависит

00:05:59.082 --> 00:06:04.967
Лёгкость сопровождения и развития проекта
и возможность более широкого привлечения

00:06:05.607 --> 00:06:09.891
потенциальных потребителей разработанных
программ.

00:06:11.011 --> 00:06:16.816
Условия и ограничения рамков выполнения
данной лабораторной работы.

00:06:17.307 --> 00:06:21.387
Могут быть использованы следующие основные
допущения.

00:06:22.067 --> 00:06:27.866
В качестве чертежа будем рассматривать
плоский геометрический объект, состоящий

00:06:28.426 --> 00:06:35.105
из отрезков прямых линий и ограничен и
граничных точек

00:06:35.265 --> 00:06:35.505
этих

00:06:40.441 --> 00:06:45.318
Представление других геометрических
элементов может рассматриваться как тема

00:06:45.558 --> 00:06:47.117
дополнительных заданий.

00:06:51.473 --> 00:06:55.791
Набор линий, образующих чертёж, должен
быть связным.

00:06:55.951 --> 00:07:01.389
То есть любая линия чертежа должна иметь
общую точку, хотя бы с одной другой линией

00:07:01.468 --> 00:07:07.266
чертежа. Пример возможного чертежа
представлен на следующем рисунке.

00:07:08.578 --> 00:07:14.461
Итак, представлен пример чертежа,
состоящего из трёх линий и трёх точек.

00:07:14.741 --> 00:07:21.385
В данном случае прямоугольная система
координат, треугольник, который состоит из

00:07:21.545 --> 00:07:24.586
трёх отрезков и точек AB

00:07:28.145 --> 00:07:31.347
Метод решения структуры данных.

00:07:31.507 --> 00:07:37.831
Каждый чертёж может быть представлен в
виде множества базовых геометрических

00:07:37.952 --> 00:07:41.674
объектов: точек, линий, окружностей и так
далее.

00:07:43.509 --> 00:07:49.987
Информационное описание объектов включает
в себя параметры фигуры, координаты,

00:07:50.147 --> 00:07:56.105
размер, радиус и другие с различной
степенью детализации в зависимости от

00:07:56.265 --> 00:07:58.425
требований, предъявляемых к чертежу.

00:07:59.011 --> 00:08:00.852
Данной предметной области.

00:08:01.532 --> 00:08:06.696
В общем случае для описания фигуры
необходимо предусмотреть хранение

00:08:06.937 --> 00:08:09.979
координат некоторой опорной точки.

00:08:10.619 --> 00:08:16.904
Операция обработки геометрических объектов
состоят в задании и изменении

00:08:17.184 --> 00:08:17.905
параметров.

00:08:18.328 --> 00:08:22.806
А также визуализации на пример на экране
дисплея фигур.

00:08:25.685 --> 00:08:31.962
Для обеспечения возможности динамической
визуализации геометрических объектов в

00:08:32.082 --> 00:08:37.279
лабораторной работе вводится тип данных,
значения которых вычисляются в

00:08:37.359 --> 00:08:38.879
соответствии с задаваемым

00:08:39.800 --> 00:08:41.799
Формульным выражением.

00:08:45.318 --> 00:08:50.476
Возможная схема иерархии классов для
представления базовых геометрических

00:08:50.596 --> 00:08:52.916
элементов может состоять в следующем.

00:08:53.035 --> 00:08:55.475
В дальнейшем мы посмотрим на рисунке семь.

00:08:56.297 --> 00:09:02.092
Наиболее общие свойства геометрических
фигур и методы их разработки выделяются в

00:09:02.251 --> 00:09:04.889
абстрактных базовых классах.

00:09:05.289 --> 00:09:10.644
От него наследуются классы для
представления точки, на основе которого

00:09:10.923 --> 00:09:16.438
реализуется класс для представления линии
и классы для других геометрических

00:09:16.558 --> 00:09:17.197
элементов.

00:09:18.663 --> 00:09:22.063
Точка определяется координатами на
плоскости.

00:09:22.343 --> 00:09:27.504
Значения координат определяются при помощи
формальных объектов класса.

00:09:29.184 --> 00:09:35.384
При формировании чертежа следует обратить
внимание, что одна и та же точка в чертеже

00:09:35.705 --> 00:09:37.825
может присутствовать несколько раз.

00:09:38.322 --> 00:09:43.364
В этом случае необходимо обеспечить
однократное представление точки без

00:09:43.604 --> 00:09:49.486
дублирования, для обеспечения корректной
работы операции вставки и удаления.

00:09:50.486 --> 00:09:56.248
Для представления линии в наиболее простом
варианте необходимо хранить начальную и

00:09:56.408 --> 00:09:57.528
конечную точки.

00:09:58.245 --> 00:10:03.199
В общем случае при формировании чертежа в
объекты линии могут храниться не

00:10:03.439 --> 00:10:07.953
координаты точек, а указатели на другие
линии чертежа.

00:10:08.872 --> 00:10:13.745
Данная ситуация допускается при выполнении
следующих условий.

00:10:15.751 --> 00:10:21.066
Начальная точка текущей линии может
определяться при помощи указателя на

00:10:21.226 --> 00:10:27.260
линию. Конечная точка, которая является
начальной точкой текущей линии.

00:10:30.297 --> 00:10:35.892
В данном случае вам показана схема
абстрактный базовый класс.

00:10:38.085 --> 00:10:42.482
Точка линия, окружность, квадрат.

00:10:43.921 --> 00:10:47.518
Прошу вас переписать данную схему.

00:14:18.684 --> 00:14:23.928
Конечная точка текущей линии может
определяться при помощи указателя на

00:14:24.048 --> 00:14:29.172
линию. Конечная точка, которая является
конечной точкой текущей линии.

00:14:29.808 --> 00:14:34.690
Наряду с базовыми геометрическими
элементами, требующими для своего

00:14:34.810 --> 00:14:38.891
представления разработки отдельных
классов, в лабораторной работе

00:14:39.051 --> 00:14:44.132
предлагается реализовать несколько
различных способов формирования

00:14:47.493 --> 00:14:49.894
составных геометрических объектов.

00:14:50.476 --> 00:14:56.437
Образуемых на основе уже существующих
геометрических фигур, как базовых, так и

00:14:56.557 --> 00:15:02.117
составных, и рассматриваемых при
выполнении операций обработки как единое

00:15:02.397 --> 00:15:08.918
целое. Возможные способы формирования
составных объектов состоят в

00:15:08.958 --> 00:15:09.598
следующем.

00:15:10.433 --> 00:15:16.672
Группирование, когда составной объект
представляет собой набор уже

00:15:17.032 --> 00:15:23.670
существующих, как базовых, так и базовых,
так и составных геометрических фигур.

00:15:24.150 --> 00:15:28.909
Подобной операцией является, например,
группирование в графическом редакторе

00:15:29.069 --> 00:15:30.029
системы Word.

00:15:31.932 --> 00:15:37.934
Конструирование, когда составной объект
определяется на основе уже существующих

00:15:38.054 --> 00:15:39.775
геометрических фигур.

00:15:40.295 --> 00:15:46.538
Например, ломанная может быть определена
через набор конечных точек составляющих

00:15:46.698 --> 00:15:47.258
отрезки.

00:15:48.267 --> 00:15:54.431
Конструирование приводит к созданию новой
сложной геометрической фигуры, которая не

00:15:54.591 --> 00:15:59.314
может быть разделена на составные
геометрические элементы.

00:16:00.394 --> 00:16:06.799
Комбинирование, когда составной объект
формируется при помощи сборки существующих

00:16:06.959 --> 00:16:07.519
объектов.

00:16:08.044 --> 00:16:12.245
Так, например, чертёж может быть образован
из точек и линий.

00:16:12.765 --> 00:16:19.407
В рамках сконструированного объекта,
входящие в состав элементы, по-прежнему

00:16:19.967 --> 00:16:24.208
могут обрабатываться как отдельные
геометрические фигуры.

00:16:25.807 --> 00:16:30.722
Для представления данных, описывающих
структуру чертежа, предлагается

00:16:30.921 --> 00:16:33.918
использовать структуру хранения типа
«Плекс».

00:16:34.398 --> 00:16:39.392
Плекс — есть структура хранения,
включающая звенья различных типов,

00:16:39.552 --> 00:16:43.547
отношения между которыми задаются при
помощи сцепления.

00:16:44.815 --> 00:16:50.260
Таким образом, флекс является
разновидностью многосвязного списка и

00:16:50.421 --> 00:16:54.064
используется для хранения сетевых моделей
данных.

00:16:54.905 --> 00:17:01.472
Основу флексов для представления чертежей,
состоящих из линий и точек, составляют

00:17:01.512 --> 00:17:02.993
вершины, узлы.

00:17:03.540 --> 00:17:09.623
В каждой из которых располагается
информация о той или иной линии чертежа.

00:17:09.864 --> 00:17:14.026
Имя линия, координаты начальной и конечной
точки.

00:17:16.908 --> 00:17:20.630
Вам представлен пример разработанной
структуры хранения.

00:17:20.790 --> 00:17:23.952
На рисунке восемь приведён плекс для
чертежа.

00:17:38.106 --> 00:17:44.103
Алгоритмы. В качестве основных алгоритмов
обработки плексов в рамках лабораторной

00:17:44.263 --> 00:17:50.460
работы должны быть рассмотрены операции
обхода плексов, необходимых, например, при

00:17:50.700 --> 00:17:52.619
отрисовке чертежа.

00:17:53.219 --> 00:17:54.499
Реализация алгоритмов

00:17:56.521 --> 00:17:59.840
Платичек обхода плексов может быть
выполнена поэтапно.

00:17:59.960 --> 00:18:06.197
На первом этапе можно реализовать частный
алгоритм обхода плексов без подплексов,

00:18:06.277 --> 00:18:11.635
как, например, было предложено на рисунке
«Три» в предыдущей лабораторной работе.

00:18:12.177 --> 00:18:17.099
И только затем приступить к разработке
общего алгоритма обхода.

00:18:18.939 --> 00:18:21.260
Обход плекса без подплексов.

00:18:21.661 --> 00:18:26.262
Плексы без подплексов соответствуют
представлению чертежей, которые можно

00:18:26.543 --> 00:18:27.183
нарисовать.

00:18:27.634 --> 00:18:29.836
Без отрыва карандаша от бумаги.

00:18:30.156 --> 00:18:35.440
Пример такого объекта — треугольник
представлен на рисунке один,

00:18:35.600 --> 00:18:39.483
соответствующий плекс без подплексов
приведён на рисунке три.

00:18:39.843 --> 00:18:44.447
Для того чтобы нарисовать линию,
необходимо знать её начальную и конечную

00:18:44.607 --> 00:18:45.047
точку.

00:18:45.825 --> 00:18:51.948
Так как в падфлексе допускается вместо
указателя точки хранения указатель линии,

00:18:52.068 --> 00:18:56.950
то необходимо найти первую линию, у
которой указатель начало — точка.

00:18:57.590 --> 00:19:00.471
В приведённом ранее примере на рисунке три

00:19:01.278 --> 00:19:02.917
Это линия BC.

00:19:03.317 --> 00:19:08.474
Тогда конечная точка этой линии будет
начальной точкой предыдущей линии в

00:19:08.554 --> 00:19:09.914
примере CA.

00:19:10.513 --> 00:19:15.671
То есть, на первом этапе необходимо
отыскать линию, у которой указатель

00:19:16.150 --> 00:19:17.110
начало-точки.

00:19:17.702 --> 00:19:23.948
При этом указатели на все пройденные линии
необходимо запомнить в стеке.

00:19:24.629 --> 00:19:29.513
На втором этапе из стека извлекаются
линии, для которых в качестве начальной

00:19:29.633 --> 00:19:33.837
точки выступает конечная точка
обработанной линии.

00:19:34.235 --> 00:19:40.072
Процесс заканчивается, когда в стеке
больше не содержится указателей на линию.

00:19:42.630 --> 00:19:44.789
Обход плекса с подплексами.

00:19:45.228 --> 00:19:50.065
Плекс с подплексами служит для
представления чертежей, которые нельзя

00:19:50.185 --> 00:19:52.783
нарисовать без отрыва карандаша от бумаги.

00:19:53.855 --> 00:19:57.294
Пример такого чертежа представлен на
рисунке девять.

00:19:58.094 --> 00:20:02.454
И возможная структура плекса, для которого
показано на рисунке 10.

00:20:03.854 --> 00:20:09.053
Рисунок 9 — пример чертежа, для
представления которого требуется плекс с

00:20:09.213 --> 00:20:10.013
подплексами.

00:20:11.021 --> 00:20:17.014
Верхняя горизонтальная линия состоит из
двух отрезков и

00:20:17.214 --> 00:20:23.487
B. Далее представлен пример

00:20:23.726 --> 00:20:28.042
чертежа, для представления которого
требуется плекс с подплексом.

00:20:29.212 --> 00:20:35.816
Верхняя горизонтальная линия состоит из
двух отрезков: D и B.

00:20:41.540 --> 00:20:44.461
Для таких плексов указатель на конечную
точку

00:20:45.138 --> 00:20:51.133
Может также указывать на линию, то есть
конечная точка линии верхнего узла плекса

00:20:51.333 --> 00:20:55.050
может являться конечной точкой линии
правого подплекса.

00:20:55.450 --> 00:21:01.405
Для обхода плекса с подплексами можно
предложить рекурсивный и нерекурсивный

00:21:01.485 --> 00:21:02.005
вариант.

00:21:02.603 --> 00:21:09.516
Общая схема рекурсивного алгоритма состоит
в следующем: вам предложен файл.

00:21:10.635 --> 00:21:15.790
То есть нужно отрисовать подплекс, на
который указывает указатель начальной

00:21:15.950 --> 00:21:19.386
точки, запомнить конечную точку подплекса.

00:21:20.637 --> 00:21:26.077
Отрисовать подплекс, на который указывает
указатель конечной точки, запомнить

00:21:26.157 --> 00:21:28.117
конечную точку подплекса.

00:21:29.198 --> 00:21:31.958
Отрисовать корневую линию.

00:21:33.078 --> 00:21:36.638
Для нерекурсивного алгоритма определим
класс.

00:21:37.826 --> 00:21:42.742
Чарт Лайн для представления линии, которая
подлежит отрисовке.

00:21:43.542 --> 00:21:50.457
Класс для методов отрисовки рисунка
представлен файл линия, начальная точка

00:21:50.697 --> 00:21:52.376
и конечная точка.

00:21:53.255 --> 00:21:54.094
Общая схема

00:21:55.872 --> 00:22:01.796
Алгоритм обхода состоит в следующем:
линии, определяемые при обходе плекса,

00:22:01.876 --> 00:22:03.318
помещаются в стек.

00:22:03.758 --> 00:22:08.722
При линии, извлекаемые из стека,
последовательно определяется начальная и

00:22:08.882 --> 00:22:10.283
конечная точка.

00:22:11.324 --> 00:22:15.687
Для определения начальной точки
используется метод джет.

00:22:16.362 --> 00:22:18.765
First Point линии.

00:22:19.686 --> 00:22:24.612
Если получаемый указатель указывает на
линию обработки текущей линии,

00:22:24.692 --> 00:22:31.140
откладывается линия помещается в стек и
начинается

00:22:31.340 --> 00:22:32.742
анализ новой линии.

00:22:33.351 --> 00:22:39.233
Данная процедура выполняется итеративно до
получения линии с известной начальной

00:22:39.713 --> 00:22:46.555
точкой. Для определения конечной точки
используется метод

00:22:46.675 --> 00:22:48.796
Get Last Point — линии.

00:22:49.429 --> 00:22:54.513
Если получаемый указатель указывает на
линию обработки текущей линии, снова

00:22:55.274 --> 00:22:59.838
откладывается текущая линия, помещается в
стек.

00:23:00.118 --> 00:23:05.883
После этого формируется описание новой
линии, которая также помещается в стек, и

00:23:06.003 --> 00:23:08.966
цикл алгоритма обхода повторяется.

00:23:10.155 --> 00:23:15.796
При получении линий с определёнными
граничными точками следует выполнить

00:23:15.916 --> 00:23:18.556
обработку линии, отрисовать.

00:23:18.916 --> 00:23:24.956
Из стека извлекается новая линия, для
которой конечная точка обработанной линии

00:23:25.156 --> 00:23:29.037
используется в качестве первой неизвестной
граничной точки.

00:23:30.321 --> 00:23:35.405
Выполнение обхода завершается при
опустошении стека линии.

00:23:36.726 --> 00:23:39.769
Какова же разработка программного
комплекса?

00:23:39.889 --> 00:23:45.774
Структура. С учётом рассмотренных выше
предложений, к реализации целесообразно

00:23:46.054 --> 00:23:48.696
представляется следующая структура
программы.

00:23:49.829 --> 00:23:53.832
Это модуль с классом для формульного
транслятора.

00:23:54.592 --> 00:23:57.715
Шаблонный класс для формульных значений.

00:23:58.355 --> 00:24:01.398
Шаблонный базовый абстрактный класс.

00:24:01.998 --> 00:24:03.760
Класс для точки.

00:24:05.161 --> 00:24:08.203
Класс для составного геометрического
объекта.

00:24:09.606 --> 00:24:15.041
Модуль с классами конструируемого
геометрического объекта и линии.

00:24:15.600 --> 00:24:18.318
Модуль программы тестирования.

00:24:18.877 --> 00:24:25.471
Модуль функций, реализующих визуальный,
диалоговый интерфейс для взаимодействия с

00:24:25.591 --> 00:24:26.310
пользователем.

00:24:27.595 --> 00:24:31.665
Прошу заполнить и записать данные модули.

00:24:33.540 --> 00:24:35.136
Даю вам несколько минут.

00:27:01.691 --> 00:27:07.408
На рисунке далее показаны отношения между
классами стрелками с незакрашенными

00:27:07.528 --> 00:27:12.446
треугольниками показаны отношения
наследования: базовый класс — производный

00:27:12.566 --> 00:27:19.043
класс. Рамбовидными стрелками — отношения
ассоциации: класс владелец, класс

00:27:19.163 --> 00:27:19.842
компонент.

00:27:20.789 --> 00:27:27.116
Обычными стрелками показано наличие поля
типа указатель на другой класс.

00:27:29.318 --> 00:27:36.205
Класс формального транслятора, класс
формальных значений, абстрактный

00:27:36.285 --> 00:27:38.888
базовый класс для объектных значений.

00:27:40.240 --> 00:27:42.680
Далее абстрактный базовый класс.

00:27:43.200 --> 00:27:46.481
Класс для составного геометрического
объекта.

00:27:47.041 --> 00:27:48.921
Класс для точки.

00:27:56.845 --> 00:28:01.484
Класс для конструируемого геометрического
объекта.

00:28:01.603 --> 00:28:04.403
Класс для отрисовки линий.

00:28:08.522 --> 00:28:13.720
Спецификации классов с учётом предложенных
к реализации алгоритмов

00:28:14.850 --> 00:28:18.851
Спецификации классов могут состоять в
следующем.

00:28:20.491 --> 00:28:25.572
Класс Эфтран для формульного транслятора

00:28:28.092 --> 00:28:32.333
предложен вам файл Далее.

00:28:32.613 --> 00:28:35.773
Шаблонный класс для формульных значений.

00:29:06.488 --> 00:29:10.222
Следующий файл — шаблонный базовый
абстрактный класс.

00:29:29.263 --> 00:29:36.259
Далее класс Thardoint для точки, в которой

00:29:36.419 --> 00:29:39.337
необходимо указать координаты точки.

00:29:40.497 --> 00:29:45.214
Далее произвести операции визуализацию
объекта.

00:29:45.925 --> 00:29:47.646
Вскрытие объекта.

00:29:48.006 --> 00:29:52.088
Вычислить параметры и создать копию.

00:29:54.929 --> 00:30:01.492
Следующий файл, класс Techart group для
создания геометрического объекта.

00:30:12.777 --> 00:30:16.738
...который входит список графических
элементов группы.

00:30:18.298 --> 00:30:25.020
Необходимо будет вставить объект в группу,
где есть визуализация объекта,

00:30:25.500 --> 00:30:26.980
скрытие объекта.

00:30:28.580 --> 00:30:29.460
Необходимо...

00:30:30.458 --> 00:30:33.577
Вычислить параметры и создание копии.

00:30:36.897 --> 00:30:43.416
Класс Techart для конструируемого
геометрического объекта представлен.

00:30:52.412 --> 00:30:58.297
В данном случае класс для методовки
рисунков.

00:30:59.057 --> 00:31:03.821
Линия, начальная точка, конечная точка.

00:31:08.585 --> 00:31:11.827
Нужно получить начальную точку, конечную
точку.

00:31:12.574 --> 00:31:16.298
Ставить начальную и конечную точку.

00:31:17.779 --> 00:31:22.744
Необходима визуализация рисунка и скрытие
рисунка.

00:31:25.227 --> 00:31:27.630
Предлагаются этапы разработки.

00:31:28.150 --> 00:31:28.671
Выполнение

00:31:29.335 --> 00:31:33.453
Лабораторной работы должно быть разделено
на несколько этапов.

00:31:34.373 --> 00:31:40.010
Каждый из этих этапов должен иметь
достаточно небольшую длительность.

00:31:40.170 --> 00:31:46.208
При этом должна обеспечиваться возможность
решения поставленной прикладной задачи.

00:31:46.878 --> 00:31:53.235
...той или иной ограниченной постановки на
как можно более ранних этапах выполнения

00:31:53.435 --> 00:31:59.073
работ С учётом высказанных рекомендаций,
последовательность разработки программ

00:31:59.552 --> 00:32:00.992
может быть следующей.

00:32:01.431 --> 00:32:02.351
Этап первый.

00:32:02.865 --> 00:32:07.819
Реализация программ для работы с флексами
простой структуры, например, для одной

00:32:07.899 --> 00:32:10.735
линии. Этап второй.

00:32:11.215 --> 00:32:16.168
Реализация программ для работы с основными
геометрическими объектами.

00:32:16.807 --> 00:32:18.405
Поддержка группирования.

00:32:19.909 --> 00:32:26.431
Этап третий — реализация отрисовки чертежа
на основе алгоритма обхода плексов без

00:32:26.671 --> 00:32:32.793
подплексов. Этап должен включать развитие
диалоговой формы управления.

00:32:33.753 --> 00:32:34.953
Этап четвёртый.

00:32:35.519 --> 00:32:40.203
Реализация операций чтения и записи
информации в файл.

00:32:41.164 --> 00:32:46.369
Этап пятый — реализация общего алгоритма
обхода флексов.

00:32:47.610 --> 00:32:52.415
Этап шестой. Реализация дополнительных
операций обхода флексов.

00:32:53.592 --> 00:32:58.837
Результаты выполнения каждого этапа
требуют проведения самого тщательного

00:32:58.997 --> 00:33:04.722
тестирования, поскольку возможные ошибки
могут проявляться только после некоторого

00:33:04.963 --> 00:33:07.525
длительного времени работы с плексами.

00:33:08.005 --> 00:33:10.288
Ошибочные ситуации могут возникать

00:33:11.214 --> 00:33:14.291
Не при каждом сценарии выполнения
программ.

00:33:15.530 --> 00:33:17.848
Рекомендации по разработке.

00:33:18.207 --> 00:33:22.803
Набор программ для работы с флексами
представляет собой достаточно сложную

00:33:23.002 --> 00:33:24.641
программную систему.

00:33:24.920 --> 00:33:28.956
При выполнении лабораторной работы следует
уделять особое внимание

00:33:29.670 --> 00:33:34.832
Техническим аспектам разработки
программного обеспечения, этапность

00:33:35.152 --> 00:33:41.114
разработки, тщательное тестирование,
командную методику выполнения работ,

00:33:41.434 --> 00:33:45.075
обеспечение простого и понятного
интерфейса.

00:33:45.877 --> 00:33:51.760
Использование инструментов поддержки
процесса разработки, система контроля

00:33:52.040 --> 00:33:56.483
версий, система поддержки, тестирование и
другое.

00:33:59.124 --> 00:34:02.406
Вам предложены возможные темы
дополнительных заданий.

00:34:03.015 --> 00:34:08.253
Для развития навыков практического
программирования рекомендуются следующие

00:34:08.412 --> 00:34:12.050
направления расширения постановки задачи.

00:34:12.330 --> 00:34:16.408
Реализовать построение чертежа с
использованием дополнительных

00:34:16.568 --> 00:34:18.167
геометрических элементов.

00:34:18.783 --> 00:34:22.666
Окружности и их дуг, прямоугольников и
другое.

00:34:23.467 --> 00:34:29.272
Разработка операций динамического
изменения, вставка и удаление линий для

00:34:29.432 --> 00:34:31.073
чертежа флекса.

00:34:31.914 --> 00:34:37.759
Реализовать проверку тождественности
чертежей для разных схем структур данных.

00:34:38.763 --> 00:34:44.157
Разработка представления арифметических
выражений с использованием плексов.

00:34:45.436 --> 00:34:48.713
Реализовать построение блок схем.

00:34:50.151 --> 00:34:54.387
Критерии оценивания выполнения данной
лабораторной работы.

00:34:55.244 --> 00:34:59.966
Лабораторная работа считается выполненной
при выполнении следующего минимального

00:35:00.086 --> 00:35:01.406
набора требований.

00:35:02.167 --> 00:35:07.649
Реализованы все классы, разработанные
программы обеспечивают демонстрацию

00:35:07.809 --> 00:35:10.851
методов отрисовки плекса без подплекса.

00:35:11.973 --> 00:35:15.370
Данные для построения считаются из файла.

00:35:15.650 --> 00:35:20.766
В качестве примера может быть использован
чертёж, представленный на рисунке шесть.

00:35:21.485 --> 00:35:26.761
В расширенном варианте выполнения
лабораторной работы должен быть реализован

00:35:26.961 --> 00:35:28.840
обход плексов с подплексами.

00:35:29.635 --> 00:35:35.921
Организован визуальный пользовательский
интерфейс с функциями чтения записи данных

00:35:36.121 --> 00:35:41.486
Applexy File, обеспечена поддержка
анимации и другое.

00:35:43.447 --> 00:35:45.890
Вопросы и задания для самоконтроля.

00:35:46.814 --> 00:35:51.016
Какие возможные модели можно использовать
для представления чертежа?

00:35:51.336 --> 00:35:53.738
В чём состоит модель чертежа?

00:35:54.498 --> 00:35:58.181
Какая структура хранения используется для
чертежа?

00:35:58.701 --> 00:36:04.465
Какие преимущества и недостатки есть у
рекурсивного и нерекурсивного алгоритмов

00:36:04.705 --> 00:36:05.745
обхода плекса?

00:36:06.952 --> 00:36:13.197
Как можно модифицировать алгоритм обхода
флекса для проверки чертежа на связность?

00:36:17.201 --> 00:36:24.167
Теперь переходим к изучению лабораторной
работы номер восемь, в которой мы должны

00:36:25.879 --> 00:36:32.766
Научиться статистической обработке
результатов экзаменационной

00:36:32.926 --> 00:36:38.932
сессии, где будет постановка учебной
задачи, основные понятия и

00:36:39.012 --> 00:36:43.337
определения, требования, предложенные к
лабораторной работе.

00:36:43.817 --> 00:36:49.130
Условия и ограничения, методы решения,
структуры данных,

00:36:49.530 --> 00:36:55.842
алгоритмы, разработка программного
комплекса, структуры,

00:36:55.962 --> 00:36:59.317
спецификации классов, этапы разработки.

00:36:59.899 --> 00:37:06.098
Рекомендации по разработке возможные темы
дополнительных заданий.

00:37:12.897 --> 00:37:16.857
Критерии оценивания выполнения данной
лабораторной работы.

00:37:17.664 --> 00:37:20.780
Вопросы и задания для самоконтроля.

00:37:24.055 --> 00:37:29.567
Статистическая обработка результатов
экзаменационной сессии.

00:37:29.647 --> 00:37:30.127
Таблица.

00:37:32.147 --> 00:37:36.825
Представление данных во многих задачах и
из разных областей человеческой

00:37:37.025 --> 00:37:40.504
деятельности может быть организовано при
помощи таблиц.

00:37:41.223 --> 00:37:46.141
Таблицы представляют собой
последовательности строк, записей.

00:37:46.301 --> 00:37:51.339
Структура строк может быть различной, но
обязательным является поле

00:37:52.150 --> 00:37:54.907
Задающие имя ключ записи

00:38:00.260 --> 00:38:06.612
Таблицы применяются в бухгалтерском учёте,
ведомости разработанной платы, в торговле,

00:38:06.652 --> 00:38:07.650
прайс-листы.

00:38:08.226 --> 00:38:13.501
В образовательных учреждениях
экзаменационные ведомости и являются одним

00:38:13.701 --> 00:38:19.015
из наиболее распространённых структур
данных, используемых при создании

00:38:19.175 --> 00:38:23.131
системного и прикладного математического
обеспечения.

00:38:24.330 --> 00:38:25.889
Таблица широко применяется

00:38:27.345 --> 00:38:34.191
Трансляторах, таблицы идентификаторов и
операционных системах могут

00:38:34.271 --> 00:38:41.116
рассматриваться как программная реализация
ассоциативной памяти и тому подобное.

00:38:42.517 --> 00:38:46.881
Существование отношения иметь имя является
обязательным в

00:38:47.764 --> 00:38:52.327
в большинстве разрабатываемых
программистами структур данных.

00:38:52.687 --> 00:38:58.531
Доступ по имени в этих структурах служит
для получения соответствия между адресным

00:38:58.691 --> 00:39:05.135
принципом указания элементов памяти ЭВМ и
общепринятым, более удобным для человека

00:39:05.894 --> 00:39:09.331
способом указания объектов по их именам.

00:39:10.570 --> 00:39:16.525
Целью данной лабораторной работы помимо
изучения способов организации таблиц,

00:39:16.685 --> 00:39:23.200
является начальное знакомство с принципами
проектирования структур хранения.

00:39:24.045 --> 00:39:27.681
используемых в методах решения прикладных
задач.

00:39:27.960 --> 00:39:34.072
На примере таблиц изучается возможность
выбора разных вариантов структур хранения,

00:39:34.352 --> 00:39:39.426
анализ их эффективности и определение
областей приложения, в которых

00:39:40.083 --> 00:39:44.839
Выбираемые структуры хранения являются
наиболее эффективными.

00:39:46.477 --> 00:39:52.112
В качестве практической задачи, на примере
которой будет продемонстрированы возможные

00:39:52.272 --> 00:39:57.108
способы организации таблиц,
рассматривается проблема статистической

00:39:57.268 --> 00:39:58.547
обработки результатов.

00:39:59.145 --> 00:40:02.184
экзаменационной успеваемости студентов.

00:40:02.384 --> 00:40:07.942
Выполнение таких, например, вычислений,
как определение среднего балла по предмету

00:40:08.822 --> 00:40:14.780
или по программе при назначении студентов
на стипендию или при распределении

00:40:14.980 --> 00:40:15.380
студентов

00:40:15.909 --> 00:40:22.640
по кафедрам и тому подобное постановка
учебной задачи

00:40:23.322 --> 00:40:25.606
основные понятия и определения.

00:40:25.726 --> 00:40:26.247
Таблица

00:40:27.417 --> 00:40:32.782
Доска. Перевод с латинского — это
динамическая структура данных, базисным

00:40:32.902 --> 00:40:37.906
множеством которым является семейство
линейных структур и записей.

00:40:38.547 --> 00:40:44.392
Базисное отношение включения определяется
операциями вставки и удаления записей.

00:40:46.908 --> 00:40:52.144
Запись — кортеж, каждый элемент которого
обычно именуется полем.

00:40:53.223 --> 00:40:59.658
Имя записи — ключ — одно из полей записи,
по которому обычно осуществляется поиск

00:41:00.098 --> 00:41:01.776
записи в таблице.

00:41:02.096 --> 00:41:05.293
Остальные поля образуют тело записи.

00:41:07.523 --> 00:41:13.841
Двоичное дерево поиска — это представление
данных в виде дерева, для которого

00:41:14.121 --> 00:41:17.160
выполняются следующие условия.

00:41:19.479 --> 00:41:25.797
Для любого узла, вершины дерева существует
не более двух потомков — двоичное дерево.

00:41:26.997 --> 00:41:33.949
Для любого узла значение во всех узлах
левого под дерева меньше значения в узле.

00:41:34.509 --> 00:41:40.862
Для любого узла значение во всех узлах
правого под дерева больше значения в узле.

00:41:41.701 --> 00:41:43.659
Кэш-функция — это функция

00:41:44.428 --> 00:41:50.584
Стоящие в соответствии ключу номер записи
в таблице используется при организации

00:41:50.824 --> 00:41:56.580
таблиц с вычислимым входом.

00:41:58.179 --> 00:42:00.137
Требования к лабораторной работе.

00:42:01.196 --> 00:42:05.718
В рамках данной лабораторной работы
ставится задача создания программных

00:42:05.878 --> 00:42:12.040
средств, поддерживающих табличные
динамические структуры данных, таблицы и

00:42:12.241 --> 00:42:14.281
базовые операции над ними.

00:42:14.962 --> 00:42:16.202
Поиск записи.

00:42:17.284 --> 00:42:22.164
Ставка записи без дублирования, удаление
записи.

00:42:22.964 --> 00:42:28.564
Выполнение операций над таблицами может
осуществляться с различной степенью

00:42:28.724 --> 00:42:34.404
эффективности в зависимости от способа
организации таблицы.

00:42:35.267 --> 00:42:40.109
В рамках лабораторной работы как
показатель эффективности предлагается

00:42:40.430 --> 00:42:45.473
использовать количество операций,
необходимых для выполнения операции

00:42:45.753 --> 00:42:47.874
поиска-записи в таблице.

00:42:48.835 --> 00:42:51.996
Величина этого показателя должна
определяться

00:42:52.525 --> 00:42:59.488
Как аналитически при использовании тех или
иных упрощающих предложений, так

00:42:59.688 --> 00:43:05.010
и экспериментально, на основе проведения
вычислительных экспериментов.

00:43:05.531 --> 00:43:11.333
В лабораторной работе предлагаются
реализовать следующие типы таблиц.

00:43:16.532 --> 00:43:22.494
Просмотровые, неупорядоченные,
упорядоченные сортированные

00:43:23.454 --> 00:43:28.055
таблицы со структурами хранения на основе
деревьев поиска.

00:43:28.695 --> 00:43:33.456
Кэш-таблицы или перемешанные с
вычисляемыми адресами.

00:43:34.831 --> 00:43:41.429
Необходимо разработать интерфейс доступа к
операциям поиска, ставки и удаления,

00:43:41.549 --> 00:43:45.107
независящий от способа организации
таблицы.

00:43:45.867 --> 00:43:50.985
Демонстрацию работоспособности
разрабатываемых при выполнении

00:43:51.807 --> 00:43:57.448
Лабораторной работы программ следует
проводить на примере таблиц, содержащих

00:43:57.568 --> 00:44:02.368
данные о результатах экзаменационной
успеваемости студентов.

00:44:02.849 --> 00:44:07.689
Для данного примера следует реализовать
следующие операции.

00:44:09.712 --> 00:44:15.394
Таблицы для таблицы с результатами
успеваемости отдельной студенческой

00:44:15.594 --> 00:44:22.477
группы. Это получение сведений об
успеваемости отдельного студента, оценка

00:44:22.637 --> 00:44:27.078
по конкретному предмету, сравнение оценки
по всем предметам.

00:44:28.234 --> 00:44:33.319
Определение средней оценки по группе по
отдельным предметам или по всем

00:44:33.720 --> 00:44:36.482
предметам.

00:44:37.483 --> 00:44:41.888
Подсчитать количество студентов,
отличников и тому подобное.

00:44:42.088 --> 00:44:47.213
Для нескольких таблиц с результатами
успеваемости для всех студенческих групп

00:44:47.333 --> 00:44:47.773
курса.

00:44:48.923 --> 00:44:53.683
Получение средних оценок по всем
студенческим группам по отдельному

00:44:53.763 --> 00:44:56.963
предмету или по всем предметам.

00:44:58.963 --> 00:45:05.083
Определение студенческой группы с лучшей
успеваемостью по конкретному предмету или

00:45:05.323 --> 00:45:08.243
по всем предметам экзаменационной сессии.

00:45:09.274 --> 00:45:15.427
Подсчёт количества студентов-отличников
для всего курса и тому подобное.

00:45:16.226 --> 00:45:22.618
Задача обработки результатов успеваемости
может быть расширена возможностью хранения

00:45:22.898 --> 00:45:24.496
данных для нескольких

00:45:25.025 --> 00:45:31.985
Экзаменационных сессий, например, за весь
период обучения студентов Указанный

00:45:32.105 --> 00:45:37.425
выше набор операций обработки результатов
успеваемости является минимально

00:45:37.705 --> 00:45:41.225
необходимым определение полного перечня

00:45:41.923 --> 00:45:48.887
Необходимых операций должно выполняться на
этапе постановки лабораторной работы.

00:45:49.288 --> 00:45:55.612
В том числе, например, могут быть выбраны
различающиеся выборы операций для

00:45:55.812 --> 00:45:59.374
получения разных постановок лабораторной
работы.

00:46:01.812 --> 00:46:06.977
Результаты обработки успеваемости
рекомендуется дополнять построением

00:46:07.137 --> 00:46:10.900
графиков и диаграмм различного вида.

00:46:11.540 --> 00:46:17.265
Например, диаграммы по средним баллам для
разных студенческих групп, графики

00:46:17.505 --> 00:46:20.147
успеваемости студентов по разным
предметам.

00:46:22.488 --> 00:46:28.331
Полезным расширением постановки
лабораторной работы является реализация

00:46:28.651 --> 00:46:34.613
возможности передачи данных в офисные
программы семейства Microsoft Office.

00:46:34.973 --> 00:46:38.254
Например, в систему обработки электронных
таблиц.

00:46:44.427 --> 00:46:46.906
Условия и ограничения.

00:46:48.265 --> 00:46:51.424
Сделаем следующие основные допущения.

00:46:53.023 --> 00:46:57.700
В качестве ключа будем рассматривать
фамилию и инициалы студента.

00:46:58.540 --> 00:47:03.465
В качестве полей данных это
экзаменационные оценки по учебным

00:47:03.625 --> 00:47:10.193
дисциплинам. Сведения об экзаменационной
успеваемости должны быть

00:47:10.393 --> 00:47:15.919
разнесены по разным таблицам для каждой
студенческой группы в отдельности.

00:47:17.703 --> 00:47:24.501
Исходные данные, количество и наименований
дисциплин, данные о результатах сессии

00:47:25.021 --> 00:47:31.658
должны извлекаться из текстовых файлов для
каждой студенческой группы в отдельности.

00:47:33.257 --> 00:47:38.095
При изменении состояния таблиц должна
обеспечиваться возможность

00:47:38.580 --> 00:47:41.942
Сохранение данных в текстовых файлах.

00:47:42.983 --> 00:47:48.307
Для контроля правильности работы программ
должна обеспечиваться возможность

00:47:48.787 --> 00:47:51.429
пакетного выполнения операций.

00:47:51.950 --> 00:47:57.634
Наименования операций и их параметры
задаются при помощи текстового файла.

00:47:59.509 --> 00:48:05.391
После выполнения пакета операций и
сохранения данных должна быть реализована

00:48:05.551 --> 00:48:12.313
возможность сравнения полученных файлов с
заранее подготовленными проверочными

00:48:12.673 --> 00:48:17.074
файлами. Метод решения.

00:48:18.297 --> 00:48:19.656
Структуры данных.

00:48:20.694 --> 00:48:26.887
Под таблицей следует понимать динамическую
структуру данных, которая в каждый момент

00:48:27.407 --> 00:48:33.240
выполнения вычислений состоит из конечного
набора элементов записей.

00:48:34.103 --> 00:48:38.821
Записи таблицы могут подразделяться на
несколько полей.

00:48:39.541 --> 00:48:45.899
При этом количество и тип полей являются
одинаковыми для всех записей таблицы.

00:48:46.938 --> 00:48:50.537
Первое поле всех записей таблицы является
ключом.

00:48:51.714 --> 00:48:55.869
Поля записи без ключевого поля образуют
тело записи.

00:48:57.427 --> 00:49:01.223
Первое поле всех записей таблицы является
ключом.

00:49:01.543 --> 00:49:06.976
Например, задавая соответствие между
индентификаторами переменных именами

00:49:07.830 --> 00:49:10.311
...и адресами памяти AVM.

00:49:10.391 --> 00:49:17.154
Мы можем получить простейшую таблицу вида
имя, в которой есть и

00:49:17.354 --> 00:49:24.077
адрес, в которой каждая строка записи
состоит из двух

00:49:24.157 --> 00:49:24.557
полей.

00:49:25.318 --> 00:49:29.236
Поле ключа, имени и поле тела, записи
адреса.

00:49:30.075 --> 00:49:36.711
Таблица, содержащая экзаменационные
оценки, имеет следующий видия, имя,

00:49:36.791 --> 00:49:38.949
отчество студента.

00:49:39.429 --> 00:49:43.626
Дисциплина: первая, вторая, третья,
четвёртая и так далее.

00:49:45.067 --> 00:49:48.747
...и соответствующие оценки по каждой
дисциплине.

00:49:49.987 --> 00:49:56.227
Для этой таблицы каждая строка состоит из
ключа, фамилии, имя, отчество и тело

00:49:56.387 --> 00:50:01.227
записи поля, содержащего оценки по четырём
дисциплинам.

00:50:02.578 --> 00:50:05.857
Основные операции, выполняемые над
таблицами.

00:50:06.456 --> 00:50:10.294
Поиск записи по одному или нескольким
ключам.

00:50:10.814 --> 00:50:14.492
Вставка записи с контролем возможных
повторений.

00:50:15.371 --> 00:50:17.370
Удаление записи.

00:50:20.408 --> 00:50:22.607
Операции вставки и удаления.

00:50:24.162 --> 00:50:28.321
Служит для формирования требуемого набора
записей.

00:50:28.481 --> 00:50:34.601
Операция поиска записи по ключу
обеспечивает доступ по имени ключ к

00:50:34.721 --> 00:50:36.881
записям таблицы.

00:50:41.161 --> 00:50:42.081
Алгоритмы.

00:50:44.715 --> 00:50:46.633
Просматриваемые таблицы.

00:50:47.073 --> 00:50:52.866
Простейшим способом отыскания нужного
элемента является метод полного просмотра

00:50:53.345 --> 00:50:59.178
сканирования, когда искомый ключ
сравнивается по очереди со всеми ключами

00:50:59.378 --> 00:51:00.137
таблицы.

00:51:00.702 --> 00:51:06.856
Начиная с первого, вплоть до отыскания
совпадающего элемента или до

00:51:07.015 --> 00:51:08.933
исчерпывания записей.

00:51:09.533 --> 00:51:14.647
Если ключи в таблице расположены в
произвольном порядке, неупорядоченная

00:51:14.767 --> 00:51:18.683
таблица, этот способ является единственно
возможным.

00:51:20.248 --> 00:51:26.206
Операция вставки в неупорядоченную таблицу
может быть выполнена путём добавления

00:51:26.486 --> 00:51:32.604
новой записи в конец таблицы с
корректировкой номера последней занятой

00:51:32.684 --> 00:51:39.282
строки. Операция удаления строки может
быть реализована при помощи

00:51:40.487 --> 00:51:47.255
Переписывание последней записи таблицы на
место удаляемой и соответствующей

00:51:47.335 --> 00:51:50.298
корректировки номера последней строки.

00:51:51.900 --> 00:51:55.224
Среднее количество просматриваемых записей
таблицы

00:51:55.789 --> 00:52:00.711
При поиске записи по ключу при
предположении равной вероятности

00:52:01.151 --> 00:52:07.554
использования ключей определяется
следующим соотношением: Т среднее равно П

00:52:07.834 --> 00:52:10.715
умножить на N большое делённое на 2

00:52:11.352 --> 00:52:16.675
Плюс разность 1 минус p, умноженное на н.

00:52:17.876 --> 00:52:24.521
Где P вероятность того, что искомая запись
имеется в таблице большое N количество

00:52:24.761 --> 00:52:29.564
записей в таблице упорядоченные таблицы.

00:52:30.363 --> 00:52:35.518
При большом количестве записей в таблице N
намного больше единицы.

00:52:35.798 --> 00:52:41.473
Затраты на выполнение полного просмотра
становятся значительными.

00:52:41.792 --> 00:52:47.707
Эффективность процедуры поиска может
повысить при размещении записи в таблице в

00:52:47.787 --> 00:52:49.065
порядке возрастания.

00:52:50.067 --> 00:52:51.949
...или убывание ключей.

00:52:52.670 --> 00:52:56.034
Упорядоченная или сортированная таблица.

00:52:56.955 --> 00:53:01.841
Упорядоченность таблиц может быть
организована только при возможности

00:53:02.081 --> 00:53:03.723
сравнения ключей.

00:53:04.123 --> 00:53:05.445
На множестве ключей...

00:53:05.860 --> 00:53:08.903
Задано отношение линейного порядка.

00:53:09.504 --> 00:53:15.911
Для поиска нужной записи в таких таблицах
может быть использован

00:53:17.513 --> 00:53:20.797
быстрый метод бинарного двоичного поиска.

00:53:21.917 --> 00:53:28.237
Вместе с тем, в упорядоченных таблицах
усложняется реализация операций вставки и

00:53:28.317 --> 00:53:34.957
удаления записей, при выполнении которых,
для сохранения упорядоченности, становится

00:53:35.277 --> 00:53:38.357
необходимой перепаковка записей в таблицы.

00:53:39.760 --> 00:53:46.044
Среднее количество просматриваемых записей
таблицы при использовании бинарного поиска

00:53:46.204 --> 00:53:52.489
определяется следующим образом: среднее
равно логарифму по основанию 2

00:53:53.290 --> 00:53:59.614
числа nabliss на основе деревьев

00:53:59.814 --> 00:54:00.295
поиска.

00:54:01.545 --> 00:54:07.664
Снижение трудоёмкости операций вставки и
удаления за счёт исключения перепаковок

00:54:08.223 --> 00:54:13.262
может быть обеспечено при использовании
списковых структур хранения.

00:54:13.982 --> 00:54:14.462
При этом

00:54:15.214 --> 00:54:22.178
Сохранение эффективности двоичного поиска
требует прямого доступа к звену со средней

00:54:22.258 --> 00:54:23.899
записью таблицы.

00:54:25.100 --> 00:54:30.423
Из этого звена должна существовать
возможность доступа к средним записям

00:54:30.543 --> 00:54:33.785
левой и правой частей таблицы и так далее.

00:54:35.342 --> 00:54:40.818
Данные требования могут быть обеспечены
при использовании деревьев поиска для

00:54:40.978 --> 00:54:42.697
представления таблиц.

00:54:43.777 --> 00:54:49.853
Использование деревьев поиска обеспечивает
сложность средним логарифм по основанию

00:54:49.973 --> 00:54:56.090
двух числа N для всех операций обработки,
поиска, вставки и удаления таблиц.

00:54:57.132 --> 00:55:01.653
Т среднее равно логарифму по основанию 2
числа n.

00:55:02.294 --> 00:55:08.576
Максимальная сложность обработки деревьев
поиска имеет порядок Н большого в случае

00:55:09.016 --> 00:55:15.699
вырождения деревья в список для исключения
вырожденных случаев

00:55:16.358 --> 00:55:22.997
Деревья поиска обобщаются до
сбалансированных деревьев поиска, в

00:55:23.117 --> 00:55:28.995
которых высота поддерев для любых узлов
отличается не более, чем на

00:55:29.555 --> 00:55:35.793
первое. Подобные деревья обеспечивают
сложность порядка логарифма по основанию

00:55:35.993 --> 00:55:37.073
двух числа N.

00:55:38.880 --> 00:55:45.076
Для любых вариантов исходных данных нот
расхода времени на проведение

00:55:45.555 --> 00:55:52.150
балансировки Методы балансировки деревьев
поиска могут быть рассмотрены в качестве

00:55:52.430 --> 00:55:54.229
дополнительного задания.

00:55:57.004 --> 00:55:59.641
Таблицы с вычисляемыми адресами.

00:56:00.161 --> 00:56:06.075
Иной возможный способ построения таблиц
при большом количестве записей состоит в

00:56:06.195 --> 00:56:10.950
предварительном перед непосредственным
поиском по таблице вычисления

00:56:11.309 --> 00:56:13.827
месторасположения искомой записи.

00:56:16.849 --> 00:56:22.492
Данный метод предполагает наличие
некоторой простой функции H, которая

00:56:24.093 --> 00:56:29.136
отображает множество имён на множество
номеров строк таблицы.

00:56:29.737 --> 00:56:31.898
Эта функция называется функцией

00:56:32.942 --> 00:56:39.893
Хэширование или расстановки таблицы,
получаемые при таком способе построения.

00:56:40.772 --> 00:56:46.925
Называются хэш-таблицами, таблицами с
вычисляемыми адресами или

00:56:47.284 --> 00:56:49.602
перемешиваемыми таблицами.

00:56:53.090 --> 00:56:57.173
Функции расстановки могут быть построены
разными способами.

00:56:58.453 --> 00:57:03.896
Например, в качестве номера строки, в
которой хранится или будет храниться при

00:57:04.056 --> 00:57:09.419
вставке некоторый ключ, можно взять код
первого символа имени.

00:57:10.242 --> 00:57:17.039
либо сумму всех кодов символов, ключая по
модулю числа M, где M —

00:57:17.119 --> 00:57:22.396
длина таблицы, размер массива, отведённого
для её хранения.

00:57:24.395 --> 00:57:25.875
При использовании таблиц

00:57:26.587 --> 00:57:32.144
С вычисляемыми адресами может возникнуть
ряд дополнительных проблем.

00:57:33.543 --> 00:57:39.299
Так, например, при вставке новой записи,
функция расстановки может выдавать номер

00:57:39.779 --> 00:57:41.897
занятой строки массива.

00:57:42.737 --> 00:57:47.254
Функция расстановки может определять один,
то есть для значения

00:57:48.419 --> 00:57:51.337
для нескольких различных ключей.

00:57:52.377 --> 00:57:58.053
Такая ситуация при вставке записи
называется относительным переполнением

00:57:58.173 --> 00:58:05.128
таблицы или коллизией при

00:58:05.448 --> 00:58:06.927
возникновении коллизий

00:58:07.650 --> 00:58:10.452
Возможны разные методы их решения.

00:58:10.893 --> 00:58:12.374
Рассмотрим два из них.

00:58:13.254 --> 00:58:18.898
Метод открытого перемешивания состоит в
добавлении к вычисленному занятому номеру

00:58:19.338 --> 00:58:22.340
некоторого фиксированного смещения.

00:58:23.141 --> 00:58:23.821
Повторное

00:58:25.470 --> 00:58:30.386
Перемешивание Krex равно K+ P умножить на
модуль N.

00:58:30.666 --> 00:58:35.582
Есть новый адрес Krix также является
занятым.

00:58:35.942 --> 00:58:40.898
Следует повторить процедуру повторного
перемешивания до тех пор, пока не

00:58:41.018 --> 00:58:43.097
обнаружится свободная строка.

00:58:43.870 --> 00:58:49.747
Либо таблица не будет исчерпана или
значения P и N большое являются

00:58:50.347 --> 00:58:51.746
взаимнопростыми.

00:58:52.106 --> 00:58:57.743
Открытое перемешивание обеспечивает
нахождение свободной строки массива.

00:58:59.702 --> 00:59:01.581
Следующий метод цепочек.

00:59:02.224 --> 00:59:09.222
При возникновении коллизий формирует
линейные списки-цепочки, в каждом

00:59:09.342 --> 00:59:15.500
из которых располагаются записи с
одинаковым значением функции расстановки.

00:59:15.980 --> 00:59:18.020
В этом случае в строках массива

00:59:18.734 --> 00:59:24.974
Для размещения записей следует добавить
ещё одно поле для рассылки на следующее

00:59:25.134 --> 00:59:26.573
звено списка.

00:59:28.293 --> 00:59:34.333
Среднее количество рассматриваемых записей
при поиске записи в перемешиваемых

00:59:34.493 --> 00:59:35.253
таблицах.

00:59:35.873 --> 00:59:42.116
При предположении равной вероятности
использования ключей и при использовании

00:59:42.276 --> 00:59:48.319
функции расстановки с равномерным
рассеиванием ключей по строкам массива

00:59:49.040 --> 00:59:51.801
определяется следующим соотношением.

00:59:52.619 --> 00:59:57.056
Разрешение коллизий по методу открытого
перемешивания.

00:59:58.815 --> 01:00:05.210
Среднее равно отношению числителя 1 минус
альфа, делённое на два к знаменателю 1

01:00:05.530 --> 01:00:06.849
минус альфа.

01:00:07.169 --> 01:00:08.847
Где альфа — это коэффициент

01:00:09.680 --> 01:00:11.122
Заполненности таблицы.

01:00:11.242 --> 01:00:14.766
Альфа равно Н относится к N.

01:00:15.206 --> 01:00:21.213
M большое количество строк в массиве для
хранения записей, N большое количество

01:00:21.413 --> 01:00:22.615
записей в таблице.

01:00:23.724 --> 01:00:28.841
Следует отметить, что количество сравнений
при поиске в перемешиваемых таблицах

01:00:29.241 --> 01:00:34.997
зависит не от количества записей в
таблице, а от заполненности памяти,

01:00:35.277 --> 01:00:37.835
отведённой для размещения записей.

01:00:38.275 --> 01:00:41.992
Для примера, при заполненности массива на
75%

01:00:42.979 --> 01:00:45.503
Альфа равно 0,75.

01:00:45.663 --> 01:00:50.470
Количество сравнений в среднем равно 2,5%.

01:00:51.272 --> 01:00:53.716
Разработка программного комплекса.

01:00:53.916 --> 01:00:54.677
Структура.

01:00:55.922 --> 01:01:01.796
При выполнении данной лабораторной работы
следует разработать иерархию классов,

01:01:01.955 --> 01:01:08.269
учитывая, что все таблицы имеют как общие
свойства, их описание следует поместить в

01:01:08.349 --> 01:01:10.627
определении базового класса.

01:01:10.946 --> 01:01:14.303
Так и особенности выполнения отдельных
операций.

01:01:14.997 --> 01:01:21.959
Реализуется в отдельных классах для
каждого вида таблиц при разработке классов

01:01:22.119 --> 01:01:24.880
используется ранее разработанный класс TD

01:01:26.361 --> 01:01:31.963
Palis рекомендуемый состав классов
приведён

01:01:32.430 --> 01:01:38.512
Ниже в данном случае это модуль с классом
объектов-значений для записей

01:01:38.632 --> 01:01:44.994
таблицы. Абстрактный базовый класс
содержит спецификации методов

01:01:45.114 --> 01:01:51.996
таблицы. Абстрактный базовый класс для
таблиц

01:01:52.196 --> 01:01:53.757
с непрерывной памятью.

01:01:57.600 --> 01:02:02.526
Модуль с классом, обеспечивающим
реализацию просматриваемых таблиц.

01:02:07.572 --> 01:02:11.897
Модуль с классом, обеспечивающим
реализацию упорядоченных таблиц.

01:02:16.692 --> 01:02:23.455
Модуль с абстрактным базовым классом
объектов-значений для деревьев.

01:02:23.975 --> 01:02:28.738
Модуль с классом, реализующим таблицы в
виде деревьев поиска.

01:02:30.819 --> 01:02:35.742
Модуль с базовым классом объектов-значений
для сбалансированных деревьев.

01:02:40.260 --> 01:02:45.054
Модуль с классом, реализующим таблицы в
виде сбалансированных деревьев поиска

01:02:48.689 --> 01:02:54.761
модуль с базовым классом, обеспечивающим
реализацию таблиц с вычислительным

01:02:55.161 --> 01:02:55.800
входом.

01:02:59.233 --> 01:03:03.593
Модуль с классом, обеспечивающим
реализацию хэш-таблиц.

01:03:04.193 --> 01:03:08.393
Разрешение коллизий на основе открытого
перемешивания.

01:03:11.353 --> 01:03:15.353
Модуль с классом, обеспечивающим
реализацию хэш-таблиц.

01:03:16.098 --> 01:03:19.499
Разрешение коллизий на основе метода
цепочек.

01:03:23.260 --> 01:03:25.740
Модуль программы тестирования.

01:03:28.261 --> 01:03:29.941
Спецификации классов.

01:03:30.101 --> 01:03:34.422
С учётом предложенных к реализации
алгоритмов можно сделать следующие

01:03:34.583 --> 01:03:35.783
объявления классов.

01:03:36.612 --> 01:03:39.811
Класс объектов-значений для записи
таблицы.

01:03:40.331 --> 01:03:47.211
Вам предложен файл,

01:03:47.931 --> 01:03:53.451
в котором есть тип ключа записи, класс
объектов-значений для записи таблицы.

01:03:54.449 --> 01:03:56.930
Поля, ключи записи.

01:03:57.411 --> 01:04:00.413
Указатель на значение, методы.

01:04:00.973 --> 01:04:07.258
Конструктор. Установить значение ключа,
получить значение ключа.

01:04:08.578 --> 01:04:11.020
Установить указатель на данные.

01:04:11.260 --> 01:04:12.942
Получить указатель на данный.

01:04:13.787 --> 01:04:20.263
Изготовить копию, присваивание, сравнение
равно

01:04:20.423 --> 01:04:21.901
больше/меньше.

01:04:22.501 --> 01:04:25.899
Дружественные классы для различных типов
таблиц.

01:04:26.858 --> 01:04:27.977
Смотрите далее.

01:04:37.148 --> 01:04:41.704
Данный тип описывает значение ключей
записи.

01:04:43.782 --> 01:04:49.137
В данном примере для типа ключей
использован класс стринг из стандартной

01:04:49.297 --> 01:04:51.734
библиотеки шаблонов STL.

01:04:52.254 --> 01:04:54.891
Абстрактный базовый класс содержит

01:04:55.492 --> 01:05:01.377
Спецификации методов таблицы Table H, в
которой у нас предлагается

01:05:01.977 --> 01:05:07.542
определять количество записей в таблице,
показатель эффективности выполнения

01:05:07.782 --> 01:05:12.747
операции. Далее, деструктор.

01:05:13.187 --> 01:05:15.066
Информационные методы.

01:05:15.226 --> 01:05:21.944
Количество записей, эффективность пуста,
пустая запись заполнена.

01:05:22.263 --> 01:05:28.221
Доступ основные методы: найти запись,
вставить, удалить.

01:05:29.218 --> 01:05:32.619
Навигация. Установить на первую запись.

01:05:32.779 --> 01:05:34.340
Таблица завершена.

01:05:34.660 --> 01:05:36.580
Переход к следующей записи.

01:05:41.541 --> 01:05:45.062
Все методы данного класса расподелены на
четыре группы.

01:05:45.672 --> 01:05:47.554
Информационные методы.

01:05:47.834 --> 01:05:54.363
Это получить количество записей, получить
эффективность последней операции.

01:05:55.044 --> 01:05:57.807
Проверить, не является ли таблица пустой.

01:05:58.648 --> 01:06:00.891
Проверить, не является ли таблица полной.

01:06:02.928 --> 01:06:05.568
Второй метод доступа к записям.

01:06:05.968 --> 01:06:09.608
Получить значение ключа текущей записи.

01:06:09.808 --> 01:06:13.248
Получить указатель на значение текущей
записи.

01:06:14.408 --> 01:06:18.447
Третий метод — методы навигации по таблице
итератор.

01:06:20.232 --> 01:06:23.749
Установить текущую позицию на первую
запись.

01:06:24.548 --> 01:06:30.424
Проверка завершения таблицы под ситуацией
завершения таблицы понимается состояние

01:06:30.704 --> 01:06:35.701
после применения метода Go Next для
текущей позиции установления

01:06:37.140 --> 01:06:43.904
Установленный на последней записи таблицы
переместить текущую позицию на следующую

01:06:44.104 --> 01:06:49.426
запись. Четвёртый методы обработки
таблицы.

01:06:49.987 --> 01:06:52.748
Поиск записи по значению ключа.

01:06:53.553 --> 01:06:56.910
Вставка записи в таблицу, удаление записи.

01:06:57.989 --> 01:07:02.983
Абстрактный класс для таблиц с непрерывной
памятью служит для управления структурой

01:07:03.543 --> 01:07:10.375
хранения. Предложен к вашему рассмотрению
файл, в котором включён «память для

01:07:10.495 --> 01:07:11.574
записи таблицы».

01:07:12.612 --> 01:07:16.013
Максимальное возможное количество записей
из таблицы.

01:07:16.733 --> 01:07:18.214
Номер текущей записи.

01:07:18.294 --> 01:07:20.374
Нумерация начинается с нуля.

01:07:21.695 --> 01:07:26.937
Конструктор, диструктор информационные
методы.

01:07:27.457 --> 01:07:31.098
Затем определяется вопрос: заполнена ли
таблица?

01:07:32.642 --> 01:07:34.283
Каково количество записей?

01:07:34.563 --> 01:07:36.764
Доступ.

01:07:36.964 --> 01:07:42.006
Основные методы: найти запись, вставить,
удалить запись.

01:07:42.526 --> 01:07:45.928
Навигация. Установить на первую запись.

01:07:46.248 --> 01:07:47.608
Таблица завершена.

01:07:48.606 --> 01:07:50.447
Переход к следующей записи.

01:07:51.888 --> 01:07:55.251
После применения для последней записи
таблицы.

01:07:55.531 --> 01:08:00.694
Установить текущую запись получить номер
текущей записи.

01:08:03.776 --> 01:08:06.778
Данный класс обеспечивает управление
памятью.

01:08:07.114 --> 01:08:09.757
Выделение и освобождение памяти.

01:08:10.237 --> 01:08:15.283
Методы доступа применимы к первой, текущей
и последней записям таблицы.

01:08:15.603 --> 01:08:20.609
Желаемый вариант доступа задаётся через
параметр метода доступа.

01:08:21.410 --> 01:08:22.411
Методы set.

01:08:24.375 --> 01:08:31.137
Corenposs установить текущую позицию на
запись с заданным номером и получить номер

01:08:31.537 --> 01:08:37.419
текущей записи вводят операции прямого
доступа к записям таблицы в классе

01:08:37.499 --> 01:08:39.820
«Реализованные методы навигации».

01:08:41.205 --> 01:08:47.765
Следующий файл — класс, обеспечивающий
реализацию просматриваемой таблицы Test

01:08:53.484 --> 01:08:57.403
В данном классе реализованы методы
обработки таблицы.

01:08:59.211 --> 01:09:04.964
Далее файл упорядочение таблицы Tsort
Table.

01:09:06.882 --> 01:09:10.078
Метод сортировки, сортировка данных.

01:09:10.437 --> 01:09:13.833
Метод вставок, слияние.

01:09:14.433 --> 01:09:15.831
Быстрая сортировка.

01:09:17.402 --> 01:09:21.402
Конструктор из просматриваемой таблицы.

01:09:21.802 --> 01:09:25.682
Присваивание. Получить метод сортировки.

01:09:26.002 --> 01:09:28.641
Установить метод сортировки.

01:09:28.961 --> 01:09:30.321
Основные методы.

01:09:30.761 --> 01:09:32.801
Найти запись, вставить.

01:09:33.472 --> 01:09:34.871
...или удалить запись.

01:09:35.591 --> 01:09:39.511
В данном классе приводится три метода
сортировки.

01:09:39.711 --> 01:09:43.510
Другие методы сортировки могут
рассматриваться как задания для

01:09:43.630 --> 01:09:45.350
самостоятельного выполнения.

01:09:46.230 --> 01:09:49.429
Метод поиска записи основан на
алгоритме...

01:09:49.954 --> 01:09:56.270
бинарного поиска В методах вставки и

01:09:56.430 --> 01:10:03.345
удаления происходит обращение к методу
поиска и производится перепаковка

01:10:03.465 --> 01:10:04.144
таблицы.

01:10:08.274 --> 01:10:13.434
Файл абстрактного базового класса объектов
значений для деревьев.

01:10:21.474 --> 01:10:26.233
Также предложен файл таблицы со структурой
хранения в виде деревьев поиска.

01:10:27.377 --> 01:10:32.901
в котором выполняются функции указатель на
корень дерева, адрес указателя на вершину

01:10:33.101 --> 01:10:40.067
результата указатель на текущую вершину
номер текущей вершины стэк для

01:10:40.147 --> 01:10:43.950
итератора удаление диструктор

01:10:45.517 --> 01:10:47.279
Информационные методы.

01:10:47.399 --> 01:10:50.243
Запись заполнена ли таблица.

01:10:50.443 --> 01:10:55.849
Основные методы: найти, вставить либо
удалить запись.

01:10:57.171 --> 01:11:01.536
Навигация. Установить на первую запись.

01:11:02.742 --> 01:11:04.223
Завершение таблицы.

01:11:04.623 --> 01:11:06.625
Переход к следующей записи.

01:11:10.187 --> 01:11:14.429
Для обхода дерева используется стек из
библиотеки СТЛ.

01:11:14.549 --> 01:11:18.232
В нём запоминаются указатели на пройденные
узлы дерева.

01:11:19.864 --> 01:11:24.390
Базовый класс значений для
сбалансированных деревьев будет иметь

01:11:24.470 --> 01:11:30.718
следующий вид. Далее, класс для
сбалансированных

01:11:32.120 --> 01:11:32.721
деревьев.

01:11:41.582 --> 01:11:47.736
Дерево является сбалансированным, если для
каждого из узла высота левого и правого

01:11:47.896 --> 01:11:51.333
поддеревья различается не более чем на
единицу.

01:11:52.412 --> 01:11:58.446
Так как операции вставки и удаления могут
нарушать сбалансированность дерева, то

01:11:58.686 --> 01:12:02.482
необходимо в таких случаях проводить
процедуру балансировки.

01:12:03.728 --> 01:12:09.769
Базовый класс для таблицы с вычислимым
входом Thash Table.

01:12:10.569 --> 01:12:16.970
В классе содержится хэш-функция,
вычисляющая по ключу записи номер строки в

01:12:17.050 --> 01:12:18.290
структуре хранения.

01:12:20.260 --> 01:12:25.777
Класс для таблицы с вычислимым входом,
использующим для решения коллизий открытое

01:12:25.977 --> 01:12:26.416
перемещение

01:12:33.932 --> 01:12:38.730
Предложен вам файл, в котором включены
функции «память для записи таблицы»,

01:12:38.810 --> 01:12:41.368
максимально возможное количество записей.

01:12:42.214 --> 01:12:44.572
Функция «шаг вторичного перемещения».

01:12:45.252 --> 01:12:48.929
Первая свободная строка обнаружения при
поиске.

01:12:49.209 --> 01:12:55.845
Строка памяти при завершении поиска,
маркер для индикации строк с удалёнными

01:12:56.084 --> 01:13:02.800
записями. Конструктор информационные

01:13:03.039 --> 01:13:03.559
методы.

01:13:04.287 --> 01:13:10.961
Затем определяется функция заполнения
таблицы, доступы, основные методы,

01:13:11.041 --> 01:13:17.237
навигация. При открытом перемешивании
добавление новых записей возможно при

01:13:17.436 --> 01:13:19.675
наличии свободных строк в таблице.

01:13:20.335 --> 01:13:26.016
Разрешение коллизий происходит путём
вычисления нового адреса для записи, пока

01:13:26.136 --> 01:13:28.577
не будет найдена свободная строка.

01:13:28.937 --> 01:13:34.419
Поэтому при удалении строка таблицы
помещается как удалённая, без фактического

01:13:34.739 --> 01:13:35.419
удаления.

01:13:35.915 --> 01:13:42.394
...и освобождение памяти, но сохраняется
возможность записи в неё нового значения

01:13:42.674 --> 01:13:44.313
при необходимости.

01:13:49.273 --> 01:13:51.752
Класс таблиц вычисле...

01:13:53.741 --> 01:13:59.178
С вычислимым входом, использующим для
разрешения коллизий метода цепочек.

01:13:59.938 --> 01:14:05.055
Включены следующие функции: память для
массива указателей на списке записей,

01:14:05.255 --> 01:14:09.732
размер массива указателей, список, которым
выполняется поиск.

01:14:10.791 --> 01:14:17.674
Конструктор. Информационные методы,
заполнена ли таблица Доступ основные

01:14:17.914 --> 01:14:21.035
методы. Найти запись, вставить, удалить
запись

01:14:25.677 --> 01:14:28.238
навигация, установить на первую запись.

01:14:28.645 --> 01:14:31.887
Таблица завершена, переход к следующей
записи.

01:14:32.607 --> 01:14:38.291
В методе цепочек добавления новых записей
в случае возникновения коллизий происходят

01:14:38.451 --> 01:14:41.053
путём добавления значений в список.

01:14:41.613 --> 01:14:46.537
В связи с тем необходимо использовать
ранее разработанный класс для списков TD.

01:14:50.190 --> 01:14:51.750
Этапы разработки.

01:14:52.271 --> 01:14:58.434
Как и ранее выполнение лабораторной работы
должно быть разделено на несколько этапов.

01:14:58.554 --> 01:15:03.197
Каждый из этапов должен иметь достаточно
небольшую длительность.

01:15:03.645 --> 01:15:09.523
При этом должны обеспечиваться возможность
решения поставленной прикладной задачи в

01:15:09.643 --> 01:15:16.120
той или иной ограниченной постановке на
как можно более ранних этапах выполнения

01:15:16.280 --> 01:15:21.638
работ. С учётом высказанных рекомендаций,
последовательность разработки программ

01:15:22.197 --> 01:15:23.717
может быть следующей.

01:15:24.450 --> 01:15:30.724
Этап первый. Реализация программ для
работы с просматриваемыми таблицами.

01:15:31.443 --> 01:15:35.759
Выполнение этапа может быть разделено на
несколько итераций.

01:15:36.239 --> 01:15:41.594
Реализация некоторой упрощённой схемы
начального заполнения таблицы.

01:15:42.456 --> 01:15:44.618
Реализация операции поиска.

01:15:45.458 --> 01:15:47.740
Реализация операции вставки.

01:15:48.300 --> 01:15:50.742
Реализация операции удаления.

01:15:51.503 --> 01:15:56.707
Результаты каждой итерации должны быть
протестированы, переход к следующей

01:15:56.747 --> 01:15:58.148
итерации разработки.

01:15:58.736 --> 01:16:04.057
Должен осуществляться только после
успешного выполнения всех запланированных

01:16:04.257 --> 01:16:10.818
тестов. На данном этапе должен быть
разработан начальный вариант диалоговой

01:16:10.938 --> 01:16:14.219
формы управления табличными операциями.

01:16:15.835 --> 01:16:22.071
Этап второй. Реализация первой очереди
операций прикладной задачи из постановки

01:16:22.311 --> 01:16:23.910
лабораторной работы.

01:16:24.150 --> 01:16:28.747
Статистическая обработка результатов
экзаменационной сессии.

01:16:29.187 --> 01:16:33.944
В числе реализуемых операций может быть,
например, ввод исходных данных.

01:16:34.515 --> 01:16:40.071
Из текстовых файлов получение данных об
успеваемости отдельных студентов

01:16:40.550 --> 01:16:47.545
вычисление средних оценок по отдельным
предметам и другое Этап

01:16:47.664 --> 01:16:50.982
должен включать развитие диалоговой формы
управления

01:16:51.785 --> 01:16:56.866
Третий этап — реализация программ для
работы с упорядоченными таблицами.

01:16:57.226 --> 01:17:02.386
Для проверки правильности работы программ
результаты выполнения должны сравниваться

01:17:02.587 --> 01:17:06.827
с результатами, получаемыми при помощи
просматриваемых

01:17:07.322 --> 01:17:13.599
Таблиц. На этом же этапе может быть
расширен список реализованных операций

01:17:13.959 --> 01:17:19.436
прикладной задачи и продолжено развитие
диалоговой формы управления.

01:17:20.035 --> 01:17:25.912
На данном этапе должны быть начаты работы
по получению графических форм, результатов

01:17:26.192 --> 01:17:28.311
обработки экзаменационных данных.

01:17:29.298 --> 01:17:34.897
Например, построение диаграмм по средним
баллам для различных студенческих групп,

01:17:35.057 --> 01:17:39.336
графики успеваемости студентов по разным
предметам и другое.

01:17:40.376 --> 01:17:41.696
Этап четвёртый.

01:17:42.456 --> 01:17:46.975
Реализация программ для работы с таблицами
на основе деревьев поиска.

01:17:48.215 --> 01:17:55.020
Дальнейшее расширение списка реализованных
операций прикладной задачи, диалоговой

01:17:55.260 --> 01:18:00.784
формы управления, графических форм вывода
результатов тестирования.

01:18:01.704 --> 01:18:08.389
Этап пятый. Реализация программ для работы
с таблицами с вычислимым входом.

01:18:09.319 --> 01:18:14.360
Дальнейшее расширение списка реализованных
операций прикладной задачи, диалоговой

01:18:14.520 --> 01:18:20.122
формы управления графических форм вывода
результатов тести.

01:18:20.842 --> 01:18:25.163
Этап шестой. Выполнение вычислительных
экспериментов.

01:18:25.593 --> 01:18:30.437
Для оценки эффективности различных
способов организации таблиц.

01:18:30.677 --> 01:18:36.242
Разработка различных генераторов
последовательности выполняемых операций.

01:18:36.883 --> 01:18:42.848
Генерация только операций поиска генерация
потока операций всех типов.

01:18:43.582 --> 01:18:49.339
Генерация потоков операций с равномерным
использованием ключей и тому подобное.

01:18:50.659 --> 01:18:52.818
Рекомендации по разработке.

01:18:53.298 --> 01:18:58.896
Следует уделить большое внимание
определению состава реализуемых операций

01:18:59.336 --> 01:19:04.574
прикладной задачи по статистической
обработке результатов экзаменационной

01:19:04.694 --> 01:19:05.173
сессии.

01:19:06.148 --> 01:19:11.066
Набор операций может быть достаточно
ограничен, но должен обеспечивать

01:19:11.266 --> 01:19:16.384
поддержку основных процедур анализа
успеваемости, обычно выполняемых

01:19:16.544 --> 01:19:18.303
работниками деканата.

01:19:19.342 --> 01:19:22.901
Ориентированность на практическое
использование предъявляет

01:19:23.805 --> 01:19:29.759
Особые требования к проектированию
диалоговой формы управления таблицами.

01:19:30.238 --> 01:19:37.071
Обычное требование для интерфейса с
пользователем состоит в обеспечении

01:19:37.271 --> 01:19:38.670
наглядности, понятности

01:19:39.537 --> 01:19:41.898
...дружественности и тому подобное.

01:19:42.418 --> 01:19:47.741
При практическом использовании программ
особое значение имеет наличие графических

01:19:47.861 --> 01:19:50.702
форм представления результатов обработки.

01:19:51.702 --> 01:19:55.904
Как и прежде, должно быть обеспечено
надёжное функционирование.

01:19:56.422 --> 01:19:58.021
Разработанных программ.

01:19:58.621 --> 01:20:04.577
С этой целью может быть разработан тот или
иной генератор текстовых данных для

01:20:04.776 --> 01:20:07.774
многократной проверки правильности
программ.

01:20:08.734 --> 01:20:13.011
В числе тестов должны быть и таблицы
достаточно большого объёма.

01:20:15.072 --> 01:20:20.148
При выполнении лабораторной работы может
быть рекомендована командная форма

01:20:20.348 --> 01:20:21.787
разработки программ.

01:20:22.267 --> 01:20:27.664
В составе команды один разработчик может
отвечать за реализацию программ для

01:20:27.784 --> 01:20:34.540
таблиц. Другой разработчик может отвечать
за разработку диалоговых форм управления

01:20:34.740 --> 01:20:35.539
таблицами.

01:20:36.425 --> 01:20:41.865
Ещё один может заниматься разработкой
графических форм, выводом результатов

01:20:42.185 --> 01:20:48.025
разработки и, наконец, отдельный
разработчик может проводить тестирование.

01:20:48.625 --> 01:20:53.905
Обязанности разработчиков могут изменяться
в ходе выполнения лабораторной работ.

01:20:54.835 --> 01:20:57.353
Возможные темы дополнительных заданий.

01:20:57.833 --> 01:21:02.509
Для развития навыков практического
программирования рекомендуются следующие

01:21:02.629 --> 01:21:08.384
направления расширения постановки задачи:
реализовать дополнительные операции над

01:21:08.424 --> 01:21:09.104
таблицами.

01:21:09.915 --> 01:21:15.314
Реализовать методы балансировки деревьев,
поиска и выполнить вычислительные

01:21:15.554 --> 01:21:22.032
эксперименты по оценке эффективности
операций с таблицей при балансировке,

01:21:22.352 --> 01:21:27.710
сравнить работу с таблицей при наличии и в
отсутствии методов балансировки.

01:21:28.883 --> 01:21:35.319
Реализовать дополнительный набор операций
для обработки результатов успеваемости.

01:21:35.679 --> 01:21:40.197
Реализовать дополнительный набор
графических форм вывода результатов

01:21:40.476 --> 01:21:44.834
обработки. Реализовать расширенное
представление таблиц.

01:21:47.958 --> 01:21:53.602
Выполнить замену разработанных программ
для реализации таблиц на средства работы с

01:21:53.682 --> 01:21:55.924
таблицами библиотеки СТЛ.

01:21:56.284 --> 01:22:00.287
Оценить трудоёмкость выполнения такой
замены.

01:22:00.807 --> 01:22:05.010
Выполнить лабораторную работу на примере
другой прикладной задачи.

01:22:06.666 --> 01:22:09.782
Критерии оценивания данной лабораторной
работы.

01:22:10.062 --> 01:22:16.375
Лабораторная работа считается сданной при
выполнении минимального набора требований.

01:22:17.134 --> 01:22:23.168
Реализованы просматриваемая упорядоченная
хэш-таблица.

01:22:23.676 --> 01:22:26.315
Таблицы на основе деревьев поиска.

01:22:26.634 --> 01:22:30.992
Эффективность поиска в лучшем, худшем и
среднем случаях соответствует

01:22:31.312 --> 01:22:32.871
теоретическим оценкам.

01:22:34.082 --> 01:22:39.602
Для рассматриваемой прикладной задачи
реализовано четыре-пять операций для

01:22:39.842 --> 01:22:45.963
обработки результатов экзаменационной
сессии и две-три графические формы вывода.

01:22:47.025 --> 01:22:51.582
В более полном варианте выполнения
лабораторной работы реализованы два

01:22:51.822 --> 01:22:55.260
варианта разрешения коллизий в
хеш-таблице.

01:22:55.500 --> 01:23:00.137
Реализован класс таблиц на основе
сбалансированного дерева.

01:23:01.457 --> 01:23:03.775
Вопросы и задания для самоконтроля.

01:23:04.457 --> 01:23:09.457
Приведите примеры прикладных задач, при
решении которых могут быть использованы

01:23:09.577 --> 01:23:14.817
таблицы. Какие дополнительные операции
могут быть полезны при обработке

01:23:14.977 --> 01:23:17.617
результатов экзаменационной сессии?

01:23:19.627 --> 01:23:24.548
Для разных способов организации таблиц
приведите примеры задач, в которых эти

01:23:24.748 --> 01:23:27.509
способы являются наиболее эффективными.

01:23:28.229 --> 01:23:33.950
Какова трудоёмкость алгоритма сортировки
вставками, алгоритма сортировки слиянием

01:23:34.310 --> 01:23:36.230
методом быстрой сортировки?

01:23:37.262 --> 01:23:41.896
В чём различие сбалансированных и идеально
сбалансированных деревьев поиска?

01:23:42.656 --> 01:23:46.971
Почему при реализации таблиц не
используются идеально сбалансированные

01:23:47.131 --> 01:23:53.044
деревья поиска? Какие рекомендации следует
учитывать при выборе хэш-функций?

01:23:54.014 --> 01:23:57.288
Какие существуют методы разрешения
коллизий?

01:23:57.408 --> 01:24:00.043
Укажите их сильные и слабые стороны.

