WEBVTT

00:00:08.532 --> 00:00:11.892
Год по учебной дисциплине «Математика и
информатика».

00:00:12.532 --> 00:00:17.212
Преподаватель, кандидат петаук, доцент
Романова Татьяна Николаевна.

00:00:17.852 --> 00:00:23.172
План занятия: технические и программные
средства реализации информационных

00:00:23.292 --> 00:00:23.852
процессов.

00:00:24.580 --> 00:00:29.777
Архитектура компьютера, уровни
программного обеспечения, современные

00:00:29.976 --> 00:00:36.732
операционные системы, их разновидности и
различия: защита информации на

00:00:36.812 --> 00:00:40.890
персональном компьютере, классификация
программного обеспечения.

00:00:41.455 --> 00:00:47.618
Информационные технологии, определения и
задачи, работа со сжатыми данными,

00:00:47.898 --> 00:00:51.099
архивирование, периферийные устройства.

00:01:45.590 --> 00:01:49.868
Под чертежом в рамках лабораторной работы
называют графическое изображение

00:01:50.628 --> 00:01:56.385
модулируемого объекта, характеризующее его
форму и размеры и выполненное по

00:01:56.505 --> 00:02:01.902
определённым правилам проектирования с
применением общепринятых соглашений по

00:02:02.022 --> 00:02:05.260
изображению и обозначению графических
элементов.

00:02:06.161 --> 00:02:11.842
По чертежам изготавливает детали и
производит сборку узлов машин и

00:02:11.962 --> 00:02:17.203
конструкций, чертёж на производстве — это
основной технический документ, в котором

00:02:17.323 --> 00:02:21.644
указаны необходимые сведения о деталях, их
материале.

00:02:22.031 --> 00:02:24.989
Термической обработки и технические
условия.

00:02:25.149 --> 00:02:30.783
На изготовление по нему проверяют качество
обработки на всех стадиях технического

00:02:31.023 --> 00:02:37.937
процесса, различают чертёж детали,
сборочный чертёж, чертёж общего вида и

00:02:38.096 --> 00:02:38.616
другого.

00:02:52.098 --> 00:02:57.936
конкретного типа графических данных,
чертежей, образуемых из ограниченного

00:02:58.096 --> 00:03:04.374
набора различных геометрических элементов,
точек, линий, окружностей и тому подобное

00:03:05.374 --> 00:03:08.253
Разрабатываемый комплекс должен
обеспечиваться

00:03:10.073 --> 00:03:15.723
Представление чертежей в памяти AVM,
демонстрацию хранимых чертежей на экране

00:03:15.763 --> 00:03:20.050
дисплея, редактирование чертежей, вставку
и удаление.

00:03:30.614 --> 00:03:35.377
... завершённых работ лабораторного
практикума, учебного курса по методам

00:03:35.457 --> 00:03:40.901
программирования. Тем самым постановка
лабораторной работы должна иметь

00:03:41.021 --> 00:03:45.705
повышенную сложность с тем, чтобы для
выполнения работы потребовалось...

00:03:46.272 --> 00:03:52.836
участие нескольких разработчиков Освоение
принципов командной работы является

00:03:53.357 --> 00:03:57.159
одной из ключевых учебных задач
лабораторной работы.

00:03:58.200 --> 00:04:01.202
Для успешного выполнения данной
лаборатор...

00:04:01.556 --> 00:04:07.716
Работы, её реализация должна поручаться
группе студентов из трёх-четырех человек.

00:04:08.236 --> 00:04:13.276
Для лучшей координации выполняемых работ в
каждой группе может быть выделен

00:04:13.396 --> 00:04:16.677
ответственный за разработку главный
программист.

00:04:17.450 --> 00:04:23.254
задачу которого входило бы согласование
задания на разработку, распределение работ

00:04:23.855 --> 00:04:29.858
между участниками разработки согласование
спецификаций и тому подобное.

00:04:30.139 --> 00:04:36.022
Отдельный разработчик-тестировщик может
отвечать за тестирование разрабатываемого

00:04:36.263 --> 00:04:36.463
кода

00:04:37.255 --> 00:04:42.820
Ещё один разработчик — технический
писатель, может быть ориентирован на

00:04:42.980 --> 00:04:48.224
подготовку документации и презентации по
программе системы.

00:04:49.385 --> 00:04:54.309
Важной частью разработки программной
системы является реализация диалоговой

00:04:54.429 --> 00:04:54.909
программы.

00:04:55.497 --> 00:05:02.289
для взаимодействия с пользователем Данная
часть разработки также может быть поручена

00:05:02.489 --> 00:05:09.440
отдельному участнику группы разработчиков
С другой стороны возможный вариант

00:05:09.520 --> 00:05:11.598
выполнения лабораторной работы

00:05:13.300 --> 00:05:18.662
Может состоять в использовании уже
имеющихся ранее разработанных диалоговых

00:05:18.742 --> 00:05:23.423
программ. В этом случае группе
разработчиков следует освоить правила

00:05:23.583 --> 00:05:27.824
использования IP, переданных для
использования программы.

00:05:29.544 --> 00:05:31.505
Следует отметить важность

00:05:37.537 --> 00:05:41.782
Безошибочность, надёжность разработанного
кода программ.

00:05:42.222 --> 00:05:47.387
От разработчика диалоговой программы
зависит удобство использования программной

00:05:47.547 --> 00:05:53.994
системы. И наконец, от технического
редактора зависит лёгкость сопровождения и

00:05:54.114 --> 00:05:55.315
развития проекта.

00:05:55.752 --> 00:06:00.752
...и возможность более широкого
привлечения потенциальных потребителей

00:06:01.072 --> 00:06:03.113
разработанных программ.

00:06:04.433 --> 00:06:09.593
Условия и ограничения рамков выполнения
данной лабораторной...

00:06:15.558 --> 00:06:21.315
В качестве чертежа будем рассматривать
плоский геометрический объект, состоящий

00:06:21.795 --> 00:06:28.511
из отрезков прямых линий и ограничим
граничных точек

00:06:28.751 --> 00:06:32.149
этих линий.

00:06:34.007 --> 00:06:38.689
Представление других геометрических
элементов может рассматриваться как тема

00:06:38.969 --> 00:06:41.090
дополнительных заданий.

00:06:44.772 --> 00:06:48.973
Набор линий, образующих чертёж, должен
быть связным.

00:06:49.448 --> 00:06:54.771
То есть любая линия чертежа должна иметь
общую точку хотя бы с одной другой линией

00:06:54.851 --> 00:07:01.134
чертежа. Пример возможного чертежа
представлен на следующем рисунке.

00:07:01.814 --> 00:07:02.535
Итак, представ

00:07:16.705 --> 00:07:19.386
...и точек A, Б, Ц.

00:07:21.507 --> 00:07:24.748
Метод решения структуры данных.

00:07:24.948 --> 00:07:31.230
Каждый чертёж может быть представлен в
виде множества базовых геометрических

00:07:31.350 --> 00:07:31.870
объектов.

00:07:32.515 --> 00:07:35.714
точек, линий, окружностей и так далее.

00:07:36.754 --> 00:07:43.394
Информационное описание объектов включает
в себе параметры, фигуры, координаты,

00:07:43.514 --> 00:07:49.473
размер, радиус и другие с различной
степенью детализации в зависимости от

00:07:49.633 --> 00:07:51.633
требований, предъявляемых к чертежу

00:07:52.433 --> 00:07:54.312
Данной предметной области.

00:07:54.952 --> 00:08:00.069
В общем случае, для описания фигуры
необходимо предусмотреть хранение

00:08:00.349 --> 00:08:03.387
координат некоторой опорной точки.

00:08:04.026 --> 00:08:10.263
Операции обработки геометрических объектов
состоят в задании и изменении

00:08:10.543 --> 00:08:11.222
параметров.

00:08:11.792 --> 00:08:16.236
А также визуализации, например, на экране
дисплея фигур.

00:08:19.119 --> 00:08:25.406
Для обеспечения возможности динамической
визуализации геометрических объектов в

00:08:25.486 --> 00:08:28.209
лабораторной работе вводится тип данных.

00:08:28.624 --> 00:08:33.709
Значения которых вычисляются в
соответствии с задаваемым формульным

00:08:34.029 --> 00:08:40.675
выражением. Возможная схема иерархии

00:08:40.835 --> 00:08:45.560
классов для представления базовых
геометрических элементов может состоять в

00:08:45.600 --> 00:08:48.843
следующем. В дальнейшем мы посмотрим на
рисунке семь.

00:08:49.716 --> 00:08:55.510
Наиболее общие свойства геометрических
фигур и методы их разработки выделяются в

00:08:55.630 --> 00:08:58.267
абстрактных базовых классах.

00:08:58.667 --> 00:09:04.061
От него наследуются классы для
представления точки, на основе которого

00:09:04.341 --> 00:09:07.258
реализуется класс для представления линии.

00:09:07.608 --> 00:09:10.930
...и классы для других геометрических
элементов.

00:09:11.891 --> 00:09:15.534
Точка определяется координатами на
плоскости.

00:09:15.774 --> 00:09:20.979
Значения координат определяются при помощи
формальных объектов класса.

00:09:22.540 --> 00:09:24.061
При формировании чертеж...

00:09:24.816 --> 00:09:30.139
Следует обратить внимание, что одна и та
же точка в чертеже может присутствовать

00:09:30.379 --> 00:09:36.142
несколько раз. В этом случае необходимо
обеспечить однократное представление точки

00:09:36.742 --> 00:09:41.825
без дублирования, для обеспечения
корректной работы операции вставки и

00:09:41.945 --> 00:09:42.505
удаления.

00:09:44.030 --> 00:09:49.627
Для представления линии в наиболее простом
варианте необходимо хранить начальную и

00:09:49.787 --> 00:09:51.107
конечную точку.

00:09:51.546 --> 00:09:56.624
В общем случае при формировании чертежа в
объекты линии могут храниться не

00:09:56.784 --> 00:10:01.062
координаты точек, а указатели на другие
линии чертежа.

00:10:02.386 --> 00:10:07.302
Данная ситуация допускается при выполнении
следующих условий.

00:10:09.061 --> 00:10:14.457
Начальная точка текущей линии может
определяться при помощи указателя на

00:10:14.617 --> 00:10:20.333
линию, конечная точка которой является
начальной точкой текущей линии.

00:10:27.848 --> 00:10:34.611
Квадратный базовый класска линия,
окружность,

00:10:34.771 --> 00:10:36.411
квадрат.

00:10:37.332 --> 00:10:40.853
Прошу вас переписать данную схему.

00:14:11.960 --> 00:14:17.319
Конечная точка текущей линии может
определяться при помощи указателя на

00:14:17.439 --> 00:14:22.478
линию. Конечная точка, которая является
конечной точкой текущей линии.

00:14:23.278 --> 00:14:28.072
Наряду с базовыми геометрическими
элементами, требующими для своего

00:14:28.192 --> 00:14:32.866
представления о разработке отдельных
классов, в лабораторной работе предлагает

00:14:54.102 --> 00:14:56.421
...обработки как единое целое.

00:14:57.581 --> 00:15:03.259
Возможные способы формирования составных
объектов состоят в следующем:

00:15:03.779 --> 00:15:09.537
группирование, когда составной объект
представляет собой набор собой набо...

00:15:09.707 --> 00:15:16.346
Сбор уже существующих, как базовых, так и
базовых, так и составных геометрических

00:15:16.466 --> 00:15:21.665
фигур. Подобной операцией является,
например, группирование в графическом

00:15:21.785 --> 00:15:25.625
редакторе системе Word...

00:15:31.577 --> 00:15:33.179
Геометрических фигур.

00:15:33.659 --> 00:15:40.024
Например, ломаная может быть определена
через набор конечных точек составляющих

00:15:40.145 --> 00:15:46.190
отрезков. Конструирование приводит к
созданию новой, сложной геометрической

00:15:46.310 --> 00:15:46.790
фигуры.

00:15:47.302 --> 00:15:52.657
которая не может быть разделена на
составные геометрические элементы.

00:15:53.776 --> 00:16:00.250
Комбинирование, когда составной объект
формируется при помощи сборки существующих

00:16:00.370 --> 00:16:05.365
объектов. Так, например, чертёж может быть
образован из точек и линий.

00:16:07.340 --> 00:16:13.739
Конструированного объекта, входящие в
состав состав элемента, по-прежнему могут

00:16:14.059 --> 00:16:17.898
обрабатываться как отдельные
геометрические фигуры.

00:16:19.098 --> 00:16:23.017
Для представления данных, описывающих
структуру чертежа

00:16:23.548 --> 00:16:27.425
Предлагается использовать структуру
хранения типа Плекс.

00:16:27.824 --> 00:16:33.899
Плекс есть структура хранения, включающая
звенья различных типов, отношения между

00:16:34.259 --> 00:16:37.296
которыми задаются при помощи сцепления.

00:16:38.056 --> 00:16:39.215
Таким образом, плекс

00:16:39.809 --> 00:16:45.846
Является разновидностью многосвязного
списка и используется для хранения сетевых

00:16:46.086 --> 00:16:47.486
моделей данных.

00:16:48.285 --> 00:16:54.842
Основу плексов для представления чертежей,
состоящих из линий и точек, составляют

00:16:54.922 --> 00:16:56.322
вершины, узлы.

00:16:56.908 --> 00:17:03.028
В каждой из которых располагается
информация о той или иной линии чертежа.

00:17:03.268 --> 00:17:07.509
Имя линии, координаты начальной и конечной
точки.

00:17:10.349 --> 00:17:14.029
Вам представлен пример разработанной
структуры хранения.

00:17:14.229 --> 00:17:17.270
На рисунке восемь приведён плекс для
чертежа.

00:17:31.491 --> 00:17:37.537
Алгоритмы. В качестве основных алгоритмов
обработки плексов в рамках лабораторной

00:17:37.657 --> 00:17:43.903
работы должны быть рассмотрены операции
обхода плексов, необходимых, например, при

00:17:44.103 --> 00:17:46.065
отрисовке чертежа.

00:17:46.625 --> 00:17:47.906
Реализация алгоритмов

00:17:49.973 --> 00:17:53.213
Платичек обхода плексов может быть
выполнена поэтапно.

00:17:53.372 --> 00:17:59.611
На первом этапе можно реализовать частный
алгоритм обхода плексов без подплексов,

00:17:59.691 --> 00:18:04.969
как, например, было предложено на рисунке
три в предыдущей лабораторной работе.

00:18:05.545 --> 00:18:10.549
И только затем приступить к разработке
общего алгоритма обхода.

00:18:12.310 --> 00:18:14.712
Обход плекса без подплексов.

00:18:15.072 --> 00:18:19.675
Плексы без подплексов соответствуют
представлению чертежей, которые можно

00:18:19.956 --> 00:18:22.958
нарисовать без отрыва карандаша от бумаги.

00:18:23.641 --> 00:18:28.762
Пример такого объекта — треугольник
представлен на рисунке один.

00:18:29.002 --> 00:18:32.883
Соответствующий плекс без подплексов
приведён на рисунке три.

00:18:33.244 --> 00:18:37.805
Для того чтобы нарисовать линию,
необходимо знать её начальную и конечную

00:18:38.045 --> 00:18:39.125
точку. Так

00:18:39.991 --> 00:18:45.516
Если в плексе допускается вместо указателя
точки хранения указатель лини, то

00:18:45.756 --> 00:18:50.360
необходимо найти первую линию, у которой
указатель начала — точка.

00:18:51.001 --> 00:18:56.005
В приведённом ранее примере на рисунке
три, это линия BC.

00:18:56.783 --> 00:19:01.819
Тогда конечная точка этой линии будет
начальной точкой предыдущей линии в

00:19:01.898 --> 00:19:03.337
примере ЦА.

00:19:03.936 --> 00:19:09.092
То есть, на первом этапе необходимо
отыскать линию, у которой указатель

00:19:09.531 --> 00:19:16.165
начало-точка. При этом указатели на все
пройденные линии необходимо запомнить.

00:19:16.662 --> 00:19:22.257
Стеки. На втором этапе из стека
извлекаются линии, для которых в качестве

00:19:22.497 --> 00:19:27.373
начальной точки выступает конечная точка
обработанной линии.

00:19:27.652 --> 00:19:32.168
Процесс заканчивается, когда в стеке
больше не содержится указателей.

00:19:32.542 --> 00:19:38.221
На линии. Обход плекса с подплексами.

00:19:38.621 --> 00:19:43.500
Плекс с подплексами служит для
представления чертежей, которые нельзя

00:19:43.580 --> 00:19:46.540
нарисовать без отрыва карандаша от бумаги.

00:19:47.139 --> 00:19:49.499
Пример такого чертежа представлен на
рисунке.

00:19:57.968 --> 00:20:03.810
Девять — пример чертежа, для представления
которого требуется плекс с подплексами.

00:20:04.330 --> 00:20:10.412
Верхняя горизонтальная линия состоит из
двух отрезков: D и

00:20:15.573 --> 00:20:20.576
Представлен пример чертежа, для
представления которого требуется плекс с

00:20:20.656 --> 00:20:27.581
подплексом. Верхняя горизонтальная линия
состоит из двух отрезков: DB и

00:20:35.023 --> 00:20:40.619
Для таких плексов указатель на конечную
точку может также указывать на линию.

00:20:40.779 --> 00:20:46.495
То есть конечная точка линии верхнего узла
плекса может являться конечной точкой

00:20:46.655 --> 00:20:48.454
линии правого подплекса.

00:20:48.853 --> 00:20:52.091
Для обхода плекса с подплексами можно
предложить

00:20:52.508 --> 00:20:55.627
Рекурсивный и нерекурсивный вариант.

00:20:55.947 --> 00:21:02.825
Общая схема рекурсивного алгоритма состоит
в следующем: вам предложен файл.

00:21:04.025 --> 00:21:05.344
То есть нужно отрисовать

00:21:15.952 --> 00:21:18.750
...который указывает указатель конечной
точки.

00:21:18.910 --> 00:21:21.749
Запомнить конечную точку подплекса.

00:21:22.629 --> 00:21:25.308
Отрисовать корневую линию.

00:21:26.467 --> 00:21:32.065
Для нерекурсивного алгоритма определим
класс Chart Line.

00:21:32.371 --> 00:21:36.048
Для представления линии, которая подлежит
отрисовке.

00:21:36.887 --> 00:21:43.842
Класс для методов отрисовки рисунка
представлен файл линия, начальная точка

00:21:44.122 --> 00:21:45.881
и конечная точка.

00:21:46.640 --> 00:21:47.479
Общая схема

00:21:49.257 --> 00:21:55.178
Алгоритм обхода состоит в следующем:
линии, определяемые при обходе плекса,

00:21:55.258 --> 00:21:56.698
помещаются в стек.

00:21:57.179 --> 00:22:02.140
При линии, извлекаемые из стека,
последовательно определяется начальная и

00:22:02.300 --> 00:22:03.700
конечная точка.

00:22:04.741 --> 00:22:09.022
Для определения начальной точки
используется метод Джерт.

00:22:09.832 --> 00:22:12.191
First Point линии.

00:22:13.110 --> 00:22:17.988
Если получаемый указатель указывает на
линию обработки текущей линии,

00:22:18.068 --> 00:22:24.506
откладывается линия помещается в стек и
начинается

00:22:24.706 --> 00:22:26.025
анализ новой линии.

00:22:26.753 --> 00:22:32.631
Данная процедура выполняется итеративно до
получения линии с известной начальной

00:22:33.071 --> 00:22:39.948
точкой. Для определения конечной точки
используется метод

00:22:40.108 --> 00:22:42.147
Get Last Point — линии.

00:22:42.858 --> 00:22:47.932
Если получаемый указатель указывает на
линию обработки текущей линии, снова

00:22:48.652 --> 00:22:53.247
откладывается текущая линия, помещается в
стек.

00:22:53.487 --> 00:22:58.881
После этого формируется описание новой
линии, которая также помещается в стек.

00:22:59.271 --> 00:23:02.550
И цикл алгоритма обхода повторяется.

00:23:03.350 --> 00:23:09.189
При получении линий с определёнными
граничными точками следует выполнить

00:23:09.309 --> 00:23:11.868
обработку линий, отрисовать.

00:23:12.268 --> 00:23:16.347
Из стека извлекается новая линия, для
которой конечная точка

00:23:17.300 --> 00:23:22.790
Обработанной линии используется в качестве
первой неизвестной граничной точки.

00:23:23.631 --> 00:23:28.199
Выполнение обхода завершается при
опустошении стека линии.

00:23:40.423 --> 00:23:42.345
Следующая структура программы.

00:23:43.106 --> 00:23:47.711
Это модуль с классом для формульного
транслятора.

00:23:48.032 --> 00:23:51.276
Шаблонный класс для формульных значений.

00:23:51.756 --> 00:23:56.762
Шаблонный базовый абстрактный класс, класс
для точки.

00:23:58.705 --> 00:24:02.146
Класс для составного геометрического
объекта.

00:24:02.906 --> 00:24:08.308
Модуль с классами конструируемого
геометрического объекта и линии.

00:24:09.028 --> 00:24:11.789
Модуль программы тестирования.

00:24:12.310 --> 00:24:15.711
Модуль функций, реализующих визуальный,
диалоговый

00:24:16.383 --> 00:24:20.186
Интерфейс для взаимодействия с
пользователем.

00:24:20.906 --> 00:24:25.228
Прошу заполнить и записать данные модули.

00:24:26.949 --> 00:24:28.510
Даю вам несколько минут.

00:26:55.059 --> 00:27:00.818
На рисунке далее показаны отношения между
классами стрелками с незакрашенными

00:27:00.938 --> 00:27:05.858
треугольниками показаны отношения
наследования: базовый класс — производный

00:27:05.978 --> 00:27:12.457
класс. Рамбовидными стрелками — отношения
ассоциации: класс владелец, класс

00:27:12.577 --> 00:27:13.177
компонент.

00:27:14.122 --> 00:27:14.290
Абы

00:27:39.328 --> 00:27:42.731
Объекта. Класс для точки.

00:27:50.138 --> 00:27:51.500
Класс для конструк.

00:28:02.110 --> 00:28:03.629
Спецификации классов.

00:28:03.709 --> 00:28:10.104
С учётом предложенных к реализации
алгоритмов, спецификации классов могут

00:28:10.184 --> 00:28:15.421
состоять в следующем: класс Эфтран для

00:28:17.180 --> 00:28:18.938
формульного транслятора.

00:28:21.668 --> 00:28:23.628
Предложен вам файл.

00:28:25.028 --> 00:28:29.108
Далее — шаблонный класс для формульных
значений.

00:28:59.856 --> 00:29:03.539
Следующий файл — шаблонный базовый
абстрактный класс.

00:29:22.631 --> 00:29:29.232
Далее класс Thardoint для точки, в

00:29:29.392 --> 00:29:32.753
которой необходимо указать координаты
точки.

00:29:33.913 --> 00:29:39.754
Далее произвести операции визуализацию
объекта, скрытие

00:29:39.874 --> 00:29:42.835
объекта, вычислить параметры.

00:29:43.590 --> 00:29:45.348
...и создать копию.

00:29:48.344 --> 00:29:55.257
Следующий файл, класс Thar Group для
создания геометрического объекта.

00:30:06.140 --> 00:30:12.908
который входит в список графических
элементов группы Необходимо будет вставить

00:30:13.349 --> 00:30:17.994
объект в группу, где есть визуализация
объекта

00:30:18.920 --> 00:30:25.834
При вскрытии объекта необходимо вычислить
параметры и создание

00:30:26.034 --> 00:30:32.549
копии класс Techart для

00:30:32.749 --> 00:30:36.706
конструируемого геометрического объекта
представлен.

00:30:45.797 --> 00:30:51.719
В данном случае класс для методовки
рисунков.

00:30:52.480 --> 00:30:57.001
Линия, начальная точка, конечная точка.

00:31:01.923 --> 00:31:02.923
Нужно получить начал-

00:31:08.131 --> 00:31:14.850
конечной точку Необходима визуализация
рисунка и скрытие

00:31:15.090 --> 00:31:16.290
рисунка.

00:31:18.530 --> 00:31:21.049
Предлагаются этапы разработки.

00:31:21.529 --> 00:31:27.089
Выполнение лабораторной работы должно быть
разделено на несколько этапов.

00:31:27.729 --> 00:31:29.128
Каждый из этих этапов

00:31:30.550 --> 00:31:33.432
Должен иметь достаточно небольшую
длительность.

00:31:33.593 --> 00:31:40.119
При этом должна обеспечиваться возможность
решения поставленной прикладной задачи в

00:31:40.239 --> 00:31:46.605
той или иной ограниченной постановке на
как можно более ранних этапах выполнения

00:31:46.725 --> 00:31:47.085
работ.

00:31:48.600 --> 00:31:52.480
С учётом высказанных рекомендаций,
последовательность разработки программ

00:31:52.960 --> 00:31:54.400
может быть следующей.

00:31:54.880 --> 00:32:00.160
Этап первый — реализация программ для
работы с флексами простой структуры,

00:32:00.240 --> 00:32:02.040
например, для одной линии.

00:32:02.960 --> 00:32:03.920
Этап второй.

00:32:04.660 --> 00:32:09.702
Реализация программ для работы с основными
геометрическими объектами.

00:32:10.262 --> 00:32:12.102
Поддержка группирования.

00:32:13.223 --> 00:32:19.784
Этап третий. Реализация отрисовки чертежа
на основе алгоритма обхода плексов без

00:32:20.025 --> 00:32:20.785
подплексов.

00:32:21.478 --> 00:32:26.157
Этап должен включать развитие диалоговой
формы управления.

00:32:27.197 --> 00:32:33.635
Этап четвёртый — реализация операций
чтения и записи информации в файл.

00:32:34.555 --> 00:32:38.314
Этап пятый — реализация общего алгоритма
обхода

00:32:38.900 --> 00:32:41.981
Флексов. Этап шесть.

00:32:42.261 --> 00:32:46.182
Реализация дополнительных операций обхода
флексов.

00:32:46.943 --> 00:32:52.224
Результаты выполнения каждого этапа
требуют проведения самого тщательного

00:32:52.424 --> 00:32:58.026
тестирования, поскольку возможные ошибки
могут проявляться только после некоторого

00:32:59.932 --> 00:33:01.214
...с плексами.

00:33:01.454 --> 00:33:07.623
Ошибочные ситуации могут возникать не при
каждом сценарии выполнения программ.

00:33:08.985 --> 00:33:10.387
Рекомендации по разработке...

00:33:46.499 --> 00:33:49.778
...поддержки, тестирование и другое.

00:33:52.498 --> 00:33:56.137
Вам предложены возможные темы
дополнительных заданий.

00:33:56.337 --> 00:34:01.656
Для развития навыков практического
программирования рекомендуются следующие

00:34:01.816 --> 00:34:04.975
направления расширения постановки задачи.

00:34:05.772 --> 00:34:09.817
Реализовать построение чертежа с
использованием дополнительных

00:34:09.977 --> 00:34:11.339
геометрических элементов.

00:34:35.504 --> 00:34:42.110
...с использованием флексов реализовать
построение блоков схем.

00:34:43.592 --> 00:34:48.076
Критерии оценивания выполнения данной
лабораторной работы.

00:34:48.557 --> 00:34:53.401
Лабораторная работа считается выполненной
при выполнении следующего минимального

00:34:53.521 --> 00:34:54.482
набора требований.

00:34:55.632 --> 00:34:57.432
Реализованы все классы.

00:34:57.712 --> 00:35:03.312
Разработанные программы обеспечивают
демонстрацию методов отрисовки плекса без

00:35:03.552 --> 00:35:08.753
подплекса. Данные для построения
считываются из файла.

00:35:09.033 --> 00:35:13.793
В качестве примера может быть использован
чертёж, представленный на рисунке шесть.

00:35:15.032 --> 00:35:20.149
В расширенном варианте выполнения
лабораторной работы должен быть реализован

00:35:20.349 --> 00:35:27.026
обход плекса с подплексами, организован
визуальный пользовательский интерфейс с

00:35:27.186 --> 00:35:30.584
функциями чтения записи данных о плексе
файлов.

00:35:31.430 --> 00:35:38.187
обеспечена поддержка анимации и другое
Вопросы и задания для

00:35:38.347 --> 00:35:39.747
самоконтроля.

00:35:40.106 --> 00:35:42.985
Какие возможные модели можно использовать
для представ

00:35:52.275 --> 00:35:57.919
Какие преимущества и недостатки есть у
рекурсивного и нерекурсивного алгоритмов

00:35:58.079 --> 00:35:59.400
обхода плекса?

00:36:00.241 --> 00:36:06.285
Как можно модифицировать алгоритм обхода
плекса для проверки чертежа на связность?

00:36:10.787 --> 00:36:17.584
Теперь переходим к изучению лабораторной
работы номер восемь, в которой мы должны

00:36:19.183 --> 00:36:26.141
научиться статистической обработке
результатов экзаменационной

00:36:26.301 --> 00:36:28.380
сессии, где

00:36:29.119 --> 00:36:34.755
Постановка учебной задачи, основные
понятия и определения, требования,

00:36:34.915 --> 00:36:40.750
предложенные к лабораторной работе,
условия и ограничения, методы решения,

00:36:41.110 --> 00:36:42.229
структуры данных.

00:36:57.655 --> 00:36:58.935
Дополнительных заданий

00:37:06.334 --> 00:37:12.453
Критерии оценивания выполнения данной
лабораторной работы, вопросы и задания для

00:37:12.773 --> 00:37:13.853
самоконтроля.

00:37:17.685 --> 00:37:23.084
Статистическая обработка результатов
экзаменационной сессии.

00:37:23.164 --> 00:37:29.522
Таблицы. Представление данных во многих
задачах из разных областей

00:37:29.642 --> 00:37:33.681
человеческой деятельности может быть
организовано при помощи таблиц.

00:37:34.814 --> 00:37:39.496
Таблица представляет собой
последовательности строк, записей.

00:37:39.697 --> 00:37:46.501
Структура строк может быть различной, но
обязательным является поле, задающее имя

00:37:47.141 --> 00:37:48.742
ключ записи.

00:37:53.705 --> 00:37:55.427
Таблицы применяется в бухгалтерской

00:38:04.768 --> 00:38:08.021
Ведомости и является одним из наиболее
распрощенных

00:38:33.810 --> 00:38:40.082
Подобное. Существование отношения иметь
имя является обязательным

00:38:41.001 --> 00:38:45.716
в большинстве разрабатываемых
программистами структур данных.

00:38:46.075 --> 00:38:49.271
Доступ по имени в этих структурах служит
для получения

00:38:50.173 --> 00:38:55.779
Соответствие между адресным принципом
указания элементов памяти ЭВМ и

00:38:55.939 --> 00:39:01.865
общепринятым, более удобным для человека
способом указания объектов по их

00:39:01.945 --> 00:39:03.506
именам.

00:39:03.987 --> 00:39:09.512
Целью данной лабораторной работы помимо
изучения способов организации таблиц

00:39:10.203 --> 00:39:16.003
Является начальное знакомство с принципами
проектирования структур

00:39:16.083 --> 00:39:21.043
хранения, используемых в методах решения
прикладных задач.

00:39:21.403 --> 00:39:27.283
На примере таблиц изучается возможность
выбора разных вариантов структур хранения.

00:39:27.792 --> 00:39:34.114
Анализ их эффективности и определение
областей приложения, в которых выбираемые

00:39:34.194 --> 00:39:38.035
структуры хранения являются наиболее
эффективными.

00:39:39.876 --> 00:39:45.558
В качестве практической задачи, на примере
которой будет продемонстрированы возможные

00:39:45.718 --> 00:39:47.318
способы организации таблиц

00:39:48.059 --> 00:39:53.383
Рассматривается проблема статистической
обработки результатов экзаменационной

00:39:53.543 --> 00:39:59.508
успеваемости студентов, выполнения таких,
например, вычислений, как определение

00:39:59.789 --> 00:40:01.550
среднего балла по предмету.

00:40:02.312 --> 00:40:07.269
...или по программе при назначении
студентов на стипендию или при

00:40:07.468 --> 00:40:12.146
распределении студентов по кафедрам и тому
подобное.

00:40:14.184 --> 00:40:16.343
Постановка учебной задачи.

00:40:16.703 --> 00:40:18.702
Основные понятия и определения.

00:40:19.159 --> 00:40:21.360
Таблица доска.

00:40:21.560 --> 00:40:26.963
Перевод с латинского — это динамическая
структура данных, базисным множеством,

00:40:27.003 --> 00:40:31.285
которым является семейство линейных
структур и записей.

00:40:31.925 --> 00:40:35.646
Базисное отношение включения определяется
операциями

00:40:36.062 --> 00:40:38.059
Вставки и удаление записей.

00:40:40.175 --> 00:40:45.168
Запись — кортеж, каждый элемент которого
обычно именуется полем.

00:41:00.942 --> 00:41:07.258
Двоичное дерево поиска — это представление
данных в виде дерева, для которого

00:41:07.538 --> 00:41:10.576
выполняются следующие условия.

00:41:12.855 --> 00:41:18.012
Для любого узла, вершины дерева,
существует не более двух потомков —

00:41:18.132 --> 00:41:19.171
двоичное дерево.

00:41:20.449 --> 00:41:27.371
Для любого узла значение во всех узлах
левого под дерева меньше значения в узле.

00:41:27.972 --> 00:41:34.294
Для любого узла значение во всех узлах
правого под дерева больше значения в узле.

00:41:35.094 --> 00:41:37.135
Кэш-функция — это функция

00:41:37.938 --> 00:41:43.972
Стоящие в соответствии ключу номер записи
в таблице используется при организации

00:41:44.211 --> 00:41:49.926
таблиц с вычислимым входом.

00:41:51.564 --> 00:41:53.522
Требования к лабораторной работе.

00:41:54.615 --> 00:41:59.132
В рамках данной лабораторной работы
ставится задача создания программных

00:41:59.251 --> 00:42:05.407
средств, поддерживающих табличные
динамические структуры данных, таблицы и

00:42:05.607 --> 00:42:07.685
базовые операции над ними.

00:42:08.365 --> 00:42:09.564
Поиск записи.

00:42:10.595 --> 00:42:15.550
Вставка записи без дублирования, удаление
записи.

00:42:16.390 --> 00:42:21.984
Выполнение операций над таблицами может
осуществляться с различной степенью

00:42:22.104 --> 00:42:27.739
эффективности в зависимости от способа
организации таблицы.

00:42:28.736 --> 00:42:33.531
В рамках лабораторной работы как
показатель эффективности предлагается

00:42:33.771 --> 00:42:38.847
использовать количество операций,
необходимых для выполнения операции

00:42:39.166 --> 00:42:41.244
поиска-записи в таблице.

00:42:42.203 --> 00:42:45.321
Величина этого показателя должна
определяться

00:42:45.965 --> 00:42:52.843
...как аналитически при использовании тех
или иных упрощающих предложений, так

00:42:53.083 --> 00:42:58.281
и экспериментально на основе проведения
вычислительных экспериментов.

00:42:58.880 --> 00:43:01.919
В лабораторной работе предлагается
реализовать

00:43:02.600 --> 00:43:05.522
Следующие типы таблиц.

00:43:09.806 --> 00:43:15.892
Просмотровательные неупорядоченные
упорядоченные сортированные

00:43:16.853 --> 00:43:18.494
таблицы со структурами.

00:43:18.692 --> 00:43:25.094
Хранение на основе деревьев поиска
кэш-таблицы или перемешанные с

00:43:25.175 --> 00:43:32.097
вычисляемыми адресами Необходимо
разработать интерфейс доступа к операциям

00:43:32.217 --> 00:43:38.299
поиска, вставки и удаления, независящий от
способа организации таблицы.

00:43:39.364 --> 00:43:44.439
Демонстрацию работоспособности,
разрабатываемых при выполнении

00:43:45.038 --> 00:43:50.832
лабораторной работы программ следует
проводить на примере таблиц, содержащих

00:43:50.952 --> 00:43:55.467
данные о результатах экзаменационной
успеваемости студентов.

00:43:56.351 --> 00:44:01.394
Для данного примера следует реализовать
следующие операции.

00:44:02.875 --> 00:44:08.798
Таблицы для таблицы с результатами
успеваемости отдельной студенческой

00:44:08.998 --> 00:44:14.682
группы. Это получение сведений об
успеваемости отдельного студента.

00:44:15.483 --> 00:44:17.925
Оценка по конкретному предмету.

00:44:18.086 --> 00:44:20.728
Сравнение оценки по всем предметам.

00:44:21.609 --> 00:44:28.216
Определение средней оценки по группе по
отдельным предметам или по всем предметам.

00:44:30.859 --> 00:44:33.622
Подсчитать количество
студентов-отличников.

00:44:40.826 --> 00:44:47.061
Курса. Получение средних оценок по всем
студенческим группам по отдельному

00:44:47.181 --> 00:44:50.418
предмету или по всем предметам.

00:44:52.376 --> 00:44:56.093
Определение студенческой группы с лучшей
успеваемостью.

00:44:56.601 --> 00:45:03.082
по конкретному предмету или по всем
предметам экзаменационной сессии подсчёт

00:45:03.242 --> 00:45:10.043
количества студентов-отличников для всего
курса и тому подобное Задача

00:45:10.244 --> 00:45:16.045
обработки результатов успеваемости может
быть расширена возможностью хранения

00:45:16.245 --> 00:45:16.525
данных

00:45:17.201 --> 00:45:22.527
для нескольких экзаменационных сессий,
например, за весь период обучения

00:45:22.727 --> 00:45:29.133
студентов Указанный выше набор операций
обработки результатов успеваемости

00:45:29.854 --> 00:45:34.739
является минимально необходимым
определение полного перечня

00:45:35.236 --> 00:45:40.554
Необходимых операций должно выполня
выполняться на этапе постановки

00:45:40.794 --> 00:45:42.273
лабораторной работы.

00:45:42.673 --> 00:45:48.951
В том числе, например, могут быть выбраны
различающиеся выборы операций для

00:45:49.151 --> 00:45:52.989
получения разных постановок лабораторной
работы.

00:45:55.208 --> 00:46:00.402
Результаты обработки успеваемости
рекомендуется дополнять построением

00:46:00.522 --> 00:46:04.119
графиков и диаграмм различного вида.

00:46:04.918 --> 00:46:10.672
Например, диаграммы по средним баллам для
разных студенческих групп, графики

00:46:10.832 --> 00:46:13.549
успеваемости студентов по разным
предметам.

00:46:15.863 --> 00:46:21.703
Полезным расширением постановки
лабораторной работы является реализация

00:46:22.063 --> 00:46:28.022
возможности передачи данных в офисные
программы семейства Microsoft Office.

00:46:28.382 --> 00:46:31.622
Например, в систему обработки электронных
таблиц.

00:46:37.798 --> 00:46:40.238
Условия и ограничения.

00:46:41.678 --> 00:46:44.838
Сделаем следующие основные допущения.

00:46:46.398 --> 00:46:47.358
В качестве ключа

00:46:47.735 --> 00:46:53.609
Будем рассматривать фамилию и инициалы
студента в качестве полей данных.

00:46:54.088 --> 00:46:58.164
Это экзаменационные оценки по учебным
дисциплинам.

00:46:59.402 --> 00:47:02.599
Сведения об экзаменационной успеваемости.

00:47:03.187 --> 00:47:08.593
Должны быть разнесены по разным таблицам
для каждой студенческой группы в

00:47:08.673 --> 00:47:15.641
отдельности. Исходные данные, количество и
наименование дисциплин, данные

00:47:16.242 --> 00:47:18.404
о результатах сессии должны

00:47:22.388 --> 00:47:25.148
...каждой студенческой группы в
отдельности.

00:47:26.668 --> 00:47:32.628
При изменении состояния таблиц должна
обеспечиваться возможность сохранения

00:47:32.908 --> 00:47:35.467
данных в текстовых файлах.

00:47:36.347 --> 00:47:38.987
Для контроля правильности работы
программы...

00:47:39.563 --> 00:47:44.798
Должна обеспечиваться возможность
пакетного выполнения операций.

00:47:45.317 --> 00:47:51.351
Наименования операций и их параметры
задаются при помощи текстового файла.

00:47:52.670 --> 00:47:54.987
После выполнения пакета операций

00:47:55.594 --> 00:48:00.315
И сохранения данных должна быть
реализована возможность сравнения

00:48:00.555 --> 00:48:07.115
полученных файлов с заранее
подготовленными проверочными файлами.

00:48:09.236 --> 00:48:12.676
Метод решения структуры данных.

00:48:14.397 --> 00:48:20.274
Под таблицей следует понимать динамическую
структуру данных, которая в каждый момент

00:48:20.833 --> 00:48:26.790
выполнения вычислений состоит из конечного
набора элементов записей.

00:48:27.429 --> 00:48:31.587
Записи таблицы могут подразделяться на
несколько полей.

00:48:33.158 --> 00:48:39.278
При этом количество и тип полей являются
одинаковыми для всех записей таблицы.

00:48:40.318 --> 00:48:44.237
Первое поле всех записей таблицы является
ключом.

00:48:45.037 --> 00:48:48.957
Поля записи без ключевого поля образуют
тело записи.

00:48:50.961 --> 00:48:54.518
Первое поле всех записей таблицы является
ключом.

00:48:54.998 --> 00:49:01.194
Например, задавая соответствие между
интентификаторами переменных, именами и

00:49:01.354 --> 00:49:06.670
адресами памяти AVM, мы можем получить
простейшую таблицу вида.

00:49:08.258 --> 00:49:15.257
Имя, в которой есть и адрес в которой
каждая

00:49:15.377 --> 00:49:21.576
строка записи состоит из двух полей: поля
ключа, имени и поля тела записи

00:49:21.776 --> 00:49:27.815
адреса. Таблица, содержащая
экзаменационные оценки, имеет следующий

00:49:27.895 --> 00:49:28.175
вид.

00:49:29.301 --> 00:49:32.062
Фамилия, имя, отчество студента.

00:49:32.863 --> 00:49:37.385
Дисциплина: первая, вторая, третья,
четвёртая и так далее.

00:49:38.426 --> 00:49:42.188
И соответствующие оценки по каждой
дисциплине.

00:49:43.428 --> 00:49:48.311
Для этой таблицы каждая строка состоит из
ключа: фамилия, имя, отчество.

00:49:49.241 --> 00:49:54.924
...и телозаписи поля, содержащее оценки по
четырём дисциплинам.

00:49:55.844 --> 00:49:59.246
Основные операции, выполняемые над
таблицами.

00:49:59.846 --> 00:50:03.808
Поиск записи по одному или нескольким
ключам.

00:50:04.208 --> 00:50:07.690
Вставка записи с контролем возможных
повторений.

00:50:08.947 --> 00:50:10.946
Удаление записи.

00:50:13.786 --> 00:50:20.226
Операции вставки и удаления служат для
формирования требуемого набора

00:50:20.386 --> 00:50:24.345
записей. Операция поиска записи по ключу.

00:50:25.214 --> 00:50:30.212
Обеспечивает доступ по имени-ключу к
записям таблицы.

00:50:34.531 --> 00:50:40.129
Алгоритмы просматриваемые таблицы.

00:50:40.489 --> 00:50:46.207
Простейшим способом отыскания нужного
элемента является метод полного просмотра

00:50:46.875 --> 00:50:52.597
Сканирование, когда искомый ключ
сравнивается по очереди со всеми ключами

00:50:52.797 --> 00:50:59.479
таблицы, начиная с первого, вплоть до
отыскания совпадающего элемента

00:50:59.919 --> 00:51:01.960
или до исчерпывания записей.

00:51:03.031 --> 00:51:08.068
Если ключи в таблице расположены в
произвольном порядке неупорядоченная

00:51:08.188 --> 00:51:12.546
таблица, этот способ является единственно
возможным.

00:51:13.545 --> 00:51:19.622
Операция вставки в неупорядоченную таблицу
может быть выполнена путём добавления

00:51:19.862 --> 00:51:22.220
новой записи в конец таблицы.

00:51:23.150 --> 00:51:26.992
С корректировкой номера последней занятой
строки.

00:51:28.233 --> 00:51:34.596
Операция удаления строки может быть
реализована при помощи переписывания

00:51:34.836 --> 00:51:39.118
последней записи таблицы на место
удаляемой.

00:51:39.289 --> 00:51:43.688
...и соответствующие корректировки номера
последней строки.

00:51:45.207 --> 00:51:51.765
Среднее количество просматриваемых записей
таблицы при поиске записи по ключу при

00:51:52.045 --> 00:51:56.004
предположении равной вероятности
использования ключей...

00:51:56.486 --> 00:51:59.443
Определяются следующим соотношением.

00:51:59.563 --> 00:52:06.474
Т среднее равно p умножить на N большое,
делённое на 2 плюс разность 1 минус

00:52:06.554 --> 00:52:08.991
p, умноженное на N.

00:52:21.443 --> 00:52:23.162
Упорядоченные таблицы.

00:52:23.601 --> 00:52:29.997
При большом количестве записей в таблице
Nного больше единицы, затраты на

00:52:30.077 --> 00:52:34.873
выполнение полного просмотра становятся
значительными.

00:52:35.153 --> 00:52:37.032
Эффективность процедуры поиска

00:52:37.740 --> 00:52:44.256
Может повысить при размещении записей в
таблице в порядке возрастания или убывания

00:52:44.456 --> 00:52:51.252
ключей упорядоченная или сортированная
таблица Упорядоченность

00:52:51.412 --> 00:52:53.411
таблиц может быть организована

00:52:54.142 --> 00:52:57.139
Только при возможности сравнения ключей.

00:52:57.539 --> 00:53:02.574
На множестве ключей задано отношение
линейного порядка.

00:53:02.933 --> 00:53:09.447
Для поиска нужной записи в таких таблицах
может быть использованным

00:53:10.005 --> 00:53:14.640
Использован быстрый метод бинарного
двоичного поиска.

00:53:15.199 --> 00:53:21.633
Вместе с тем, в упорядоченных таблицах
усложняется реализация операций вставки и

00:53:21.713 --> 00:53:27.267
удаления записей, при выполнении которых,
для сохранения упорядоченности

00:53:28.048 --> 00:53:31.967
становится необходимой перепаковка записей
таблицы.

00:53:32.967 --> 00:53:39.405
Среднее количество просматриваемых записей
таблицы при использовании бинарного поиска

00:53:39.605 --> 00:53:43.564
определяется следующим образом: T среднее
равно

00:53:44.164 --> 00:53:48.287
Логарифмы по основанию 2 числа N.

00:53:51.048 --> 00:53:54.010
Таблицы на основе деревьев поиска.

00:53:54.850 --> 00:54:01.054
Снижение трудоёмкости операций вставки и
удаления за счёт исключения перепаковок.

00:54:01.704 --> 00:54:06.629
Может быть обеспечена при использовании
списковых структур хранения.

00:54:07.429 --> 00:54:13.956
При этом сохранение эффективности
двоичного поиска требует прямого доступа к

00:54:14.076 --> 00:54:17.119
звену со средней записью таблицы.

00:54:18.515 --> 00:54:23.792
Из этого звена должна существовать
возможность доступа к средним записям

00:54:23.911 --> 00:54:27.429
левой и правой частей таблицы и так далее.

00:54:28.628 --> 00:54:34.184
Данные требования могут быть обеспечены
при использовании деревьев поиска для

00:54:34.384 --> 00:54:35.823
представления таблицы.

00:54:37.287 --> 00:54:43.371
Использование деревьев поиска обеспечивает
сложность среднем логарифм по основанию 2

00:54:43.611 --> 00:54:49.776
числа Н для всех операций обработки,
поиска, вставки и удаления таблиц.

00:54:50.696 --> 00:54:54.379
Среднее равно логарифму по основанию 2
числа Н.

00:54:55.765 --> 00:55:01.964
Максимальная сложность обработки деревьев
поиска имеет порядок Bn большого в случае

00:55:02.404 --> 00:55:09.123
вырождения деревьев список для исключения
вырожденных случаев

00:55:09.723 --> 00:55:10.683
деревья поиска

00:55:11.448 --> 00:55:18.363
Обобщается до сбалансированных деревьев
поиска, в которых высота поддерев

00:55:18.803 --> 00:55:23.559
для любых узлов отличается не более, чем
на первое.

00:55:24.159 --> 00:55:29.955
Подобные деревья обеспечивают сложность
порядка логарифма по основанию двух числа

00:55:32.367 --> 00:55:38.483
Для любых вариантов исходных данных нот
расхода времени на проведение

00:55:38.962 --> 00:55:45.518
балансировки Методы балансировки деревьев
поиска могут быть рассмотрены в качестве

00:55:45.838 --> 00:55:47.637
дополнительного задания.

00:55:50.345 --> 00:55:53.065
Таблицы с вычисляемыми адресами.

00:55:53.585 --> 00:55:59.467
Иной возможный способ построения таблиц
при большом количестве записей состоит в

00:55:59.587 --> 00:56:04.388
предварительном перед непосредственным
поиском по таблице вычисления

00:56:04.708 --> 00:56:07.228
месторасположения искомой записи.

00:56:10.234 --> 00:56:15.909
Данный метод предполагает наличие
некоторой простой функции H, которая

00:56:17.467 --> 00:56:22.542
отображает множество имён на множество
номеров строк таблицы.

00:56:23.182 --> 00:56:25.260
Эта функция называется функцией

00:56:26.327 --> 00:56:31.644
Хэширование или расстановки таблиц,
получаемые при таком способе

00:56:31.804 --> 00:56:33.523
построения.

00:56:34.163 --> 00:56:40.320
Называются хэш-таблицами, таблицами с
вычисляемыми адресами или

00:56:40.680 --> 00:56:42.919
перемешиваемыми таблицами.

00:56:46.475 --> 00:56:50.555
Функции расстановки могут быть построены
разными способами.

00:56:51.875 --> 00:56:57.314
Например, в качестве номера строки, в
которой хранится или будет храниться при

00:56:57.474 --> 00:57:02.753
вставке некоторый ключ, можно взять код
первого символа имени.

00:57:03.650 --> 00:57:10.454
либо сумму всех кодов символов, ключая по
модулю числа M, где M —

00:57:10.534 --> 00:57:15.817
длина таблицы, размер массива, отведённого
для её хранения.

00:57:17.819 --> 00:57:19.260
При использовании таблицы

00:57:19.978 --> 00:57:25.495
С вычисляемыми адресами может возникнуть
ряд дополнительных проблем.

00:57:26.934 --> 00:57:32.729
Так, например, при вставке новой записи
функция расстановки может выдавать номер

00:57:33.209 --> 00:57:34.928
занятой строки массива.

00:57:36.257 --> 00:57:42.577
Функция расстановки может определять один,
то есть для значения для нескольких

00:57:42.697 --> 00:57:44.418
различных ключей.

00:57:45.778 --> 00:57:51.458
Такая ситуация при вставке записи
называется относительным переполнением

00:57:51.538 --> 00:57:52.218
таблицы.

00:57:52.710 --> 00:57:59.632
...или коллизии при возникновении

00:57:59.872 --> 00:58:03.874
коллизий возможны разные методы их
решения.

00:58:04.274 --> 00:58:05.794
Рассмотрим два из них.

00:58:06.675 --> 00:58:12.357
Метод открытого перемешивания состоит в
добавлении к вычисленному занятому номеру.

00:58:12.772 --> 00:58:15.814
некоторого фиксированного смещения.

00:58:16.535 --> 00:58:23.180
Повторное перемешивание K равно Клюс p
умножить на модуль

00:58:23.300 --> 00:58:28.544
N. Есть новый адрес Kже является занятым

00:58:29.470 --> 00:58:34.305
Следует повторить процедуру повторного
перемешивания до тех пор, пока не

00:58:34.425 --> 00:58:39.661
обнаружится свободная строка, либо таблица
не будет исчерпана.

00:58:39.980 --> 00:58:44.936
Или значения P и N большое являются
взаимнопростыми.

00:58:45.558 --> 00:58:51.158
Открытое перемешивание обеспечивает
нахождение свободной строки массива.

00:58:53.158 --> 00:58:55.197
Следующий метод цепочек.

00:58:55.517 --> 00:59:01.277
При возникновении коллизий формирует
линейные списки, цепочки.

00:59:02.353 --> 00:59:08.798
В каждом из которых располагаются записи с
одинаковым значением функции расстановки.

00:59:09.359 --> 00:59:14.844
В этом случае в строках массива для
размещения записей следует добавить ещё

00:59:15.164 --> 00:59:19.688
одно поле для рассылки на следующее звено
списка.

00:59:21.833 --> 00:59:27.755
Среднее количество рассматриваемых записей
при поиске записи в перемешиваемых

00:59:27.915 --> 00:59:34.517
таблицах при предположении равной
вероятности использования ключей и при

00:59:34.717 --> 00:59:36.998
использовании функции расстановки

00:59:37.695 --> 00:59:44.170
С равномерным рассеиванием ключей по
строкам массива определяется следующим

00:59:44.329 --> 00:59:50.484
соотношением разрешение коллизии по методу
открытого перемешивания.

00:59:52.242 --> 00:59:53.042
Среднее равно

00:59:53.790 --> 00:59:59.310
Отношению числителя 1 минус альфа,
делённое на два к знаменателю 1 минус

00:59:59.390 --> 01:00:04.549
альфа. Где альфа — это коэффициент
заполненности таблицы.

01:00:04.629 --> 01:00:08.269
Альфа равно Н относится к N.

01:00:08.589 --> 01:00:12.709
M большое — количество строк в массиве для
хранения записей.

01:00:13.729 --> 01:00:19.491
большое количество записей в таблице
Следует отметить, что количество сравнений

01:00:19.731 --> 01:00:25.012
при поиске в перемешиваемых таблицах
зависит не от количества записей в

01:00:25.092 --> 01:00:30.934
таблице, а от заполненности памяти,
отведённой для размещения записей.

01:00:31.774 --> 01:00:36.939
Для примера: при заполненности массива на
75% альфа равно

01:00:36.979 --> 01:00:43.225
0,75, количество сравнений в среднем равно
2,5%

01:00:44.786 --> 01:00:46.988
Разработка программного комплекса.

01:00:47.473 --> 01:00:53.116
Структура. При выполнении данной
лабораторной работы следует разработать

01:00:53.316 --> 01:00:59.518
иерархию классов, учитывая, что все
таблицы имеют как общие свойства, их

01:00:59.598 --> 01:01:03.520
описание следует поместить в определении
базового класса.

01:01:04.500 --> 01:01:10.065
Так и особенности выполнения отдельных
операций реализуются в отдельных классах

01:01:10.185 --> 01:01:12.186
для каждого вида таблиц.

01:01:13.947 --> 01:01:20.232
При разработке классов используется ранее
разработанный класс TDoliver.

01:01:23.097 --> 01:01:26.498
Рекомендуемый состав классов приведён
ниже.

01:01:27.618 --> 01:01:32.980
В данном случае это модуль с классом
объектов-значений для записи таблицы.

01:01:34.221 --> 01:01:39.143
Абстрактный базовый класс содержит
спецификации методов таблицы.

01:01:43.469 --> 01:01:47.752
Абстрактный базовый класс для таблиц с
непрерывной памятью.

01:01:50.914 --> 01:01:56.078
Модуль с классом, обеспечивающим
реализацию просматриваемых таблиц.

01:02:01.001 --> 01:02:05.204
Модуль с классом, обеспечивающим
реализацию упорядоченных таблиц.

01:02:10.077 --> 01:02:16.910
Модуль с абстрактным базовым классом
объектов-значений для деревьев.

01:02:17.349 --> 01:02:22.064
Модуль с классом, реализующим таблицы в
виде деревьев поиска.

01:02:24.262 --> 01:02:29.177
Модуль с базовым классом объектов-значений
для сбалансированных деревьев.

01:02:33.651 --> 01:02:38.485
Модуль с классом, реализующим таблицы в
виде сбалансированных деревьев поиска

01:02:42.120 --> 01:02:48.152
модуль с базовым классом, обеспечивающим
реализацию таблиц с вычислительным

01:02:48.592 --> 01:02:49.151
входом.

01:02:52.669 --> 01:02:56.985
Модуль с классом, обеспечивающим
реализацию хэш-таблиц.

01:02:57.624 --> 01:03:01.741
Разрешение коллизий на основе открытого
перемешивания.

01:03:04.778 --> 01:03:08.654
Модуль с классом, обеспечивающим
реализацию хэш-таблиц.

01:03:09.483 --> 01:03:12.880
Разрешение коллизий на основе метода
цепочек.

01:03:16.677 --> 01:03:19.116
Модуль программы тестирования.

01:03:21.714 --> 01:03:23.353
Спецификации классов.

01:03:23.473 --> 01:03:27.789
С учётом предложенных к реализации
алгоритмов можно сделать следующие

01:03:27.949 --> 01:03:28.988
объявления классов.

01:03:29.980 --> 01:03:33.180
Класс объектов-значений для записи
таблицы.

01:03:33.740 --> 01:03:40.459
Вам предложен файл,

01:03:41.339 --> 01:03:46.819
в котором есть тип ключа записи, класс
объектов-значений для записи таблицы.

01:03:47.783 --> 01:03:50.583
Поля, ключи записи.

01:03:50.863 --> 01:03:54.143
Указатель на значение, методы.

01:03:54.383 --> 01:03:58.463
Конструктор. Установить значение ключа.

01:03:58.663 --> 01:04:00.823
Получить значение ключа.

01:04:01.943 --> 01:04:04.423
Установить указатель на данные.

01:04:04.623 --> 01:04:06.343
Получить указатель на данный.

01:04:07.189 --> 01:04:13.673
Изготовить копию, присваивание, сравнение
равно

01:04:13.833 --> 01:04:15.594
больше/меньше.

01:04:15.915 --> 01:04:19.357
Дружественные классы для различных типов
таблиц.

01:04:20.277 --> 01:04:21.278
Смотрите далее.

01:04:30.516 --> 01:04:35.032
Данный тип описывает значение ключей
записи.

01:04:37.230 --> 01:04:42.585
В данном примере для типа ключей
использован класс стринг из стандартной

01:04:42.705 --> 01:04:45.183
библиотеки шаблонов STL.

01:04:45.702 --> 01:04:46.981
Абстрактный базовый

01:04:47.554 --> 01:04:54.037
Класс содержит спецификации методов
таблицы Table R, в которой у нас

01:04:54.197 --> 01:05:00.039
предлагается определять количество записей
в таблице, показатель эффективности

01:05:00.359 --> 01:05:02.119
выполнения операций.

01:05:04.840 --> 01:05:06.121
Далее, деструктор.

01:05:06.623 --> 01:05:08.424
Информационные методы.

01:05:08.625 --> 01:05:15.390
Количество записей, эффективность пуста,
пустая запись заполнена.

01:05:15.710 --> 01:05:19.113
Доступ основные методы.

01:05:19.193 --> 01:05:21.915
Найти запись, вставить, удалить.

01:05:22.476 --> 01:05:23.277
Навигация.

01:05:28.273 --> 01:05:30.033
Переход к следующей записи.

01:05:34.953 --> 01:05:38.552
Все методы данного класса разделены на
четыре группы.

01:05:38.952 --> 01:05:43.432
Информационные методы — это получить
количество записей.

01:05:44.615 --> 01:05:47.731
Получить эффективность последней операции.

01:05:48.451 --> 01:05:51.208
Проверить, не является ли таблица пустой.

01:05:52.047 --> 01:05:54.684
Проверить, не является ли таблица полной.

01:05:56.163 --> 01:05:58.680
Второй метод доступа к записям.

01:05:59.359 --> 01:06:02.157
Получить значение ключа текущей записи.

01:06:03.323 --> 01:06:06.643
Получить указатель на значение текущей
записи.

01:06:07.804 --> 01:06:12.365
Третий метод — методы навигации по таблице
итератор.

01:06:13.405 --> 01:06:16.845
Установить текущую позицию на первую
запись.

01:06:17.966 --> 01:06:19.886
Проверка завершения таблицы.

01:06:20.552 --> 01:06:24.874
Под ситуацией завершения таблицы
понимается состояние после применения

01:06:25.035 --> 01:06:31.878
метода Go-Next для текущей позиции
установления установленной на последней

01:06:31.958 --> 01:06:33.399
записи таблицы.

01:06:34.439 --> 01:06:37.881
Переместить текущую позицию на следующую
запись.

01:06:40.167 --> 01:06:42.809
Четвёртые методы обработки таблицы.

01:06:43.449 --> 01:06:46.611
Поиск записи по значению ключа.

01:06:46.851 --> 01:06:50.373
Вставка записи в таблицу, удаление записи.

01:06:51.413 --> 01:06:56.416
Абстрактный класс для таблиц с непрерывной
памятью служит для управления структурой.

01:06:57.059 --> 01:07:03.785
Хранения предложен к вашему рассмотрению
файл, в который включён «память для

01:07:03.945 --> 01:07:09.509
записи таблицы», максимально возможное
количество записей из таблицы.

01:07:10.190 --> 01:07:13.352
Номер текущей записи нумерация начинается
с нуля.

01:07:16.898 --> 01:07:20.419
Диструктор информационные методы.

01:07:20.899 --> 01:07:27.742
Затем определяется вопрос: заполнена ли
таблица количество записи,

01:07:27.942 --> 01:07:34.544
доступ основные методы: найти запись,
вставить, удалить

01:07:34.704 --> 01:07:35.144
запись.

01:07:36.017 --> 01:07:39.494
Навигация. Установить на первую запись.

01:07:39.814 --> 01:07:41.452
Таблица завершена.

01:07:41.932 --> 01:07:43.930
Переход к следующей записи.

01:07:45.369 --> 01:07:48.486
После применения для последней записи
таблицы.

01:07:49.085 --> 01:07:51.283
Установить текущую запись.

01:07:51.483 --> 01:07:53.441
Получить номер текущей записи.

01:07:57.398 --> 01:08:03.283
Данный класс обеспечивает управление
памятью, выделение и освобождение памяти.

01:08:03.803 --> 01:08:08.807
Методы доступа применимы к первой, текущей
и последней записям таблицы.

01:08:09.168 --> 01:08:12.210
Желаемый вариант доступа задаётся через
параметр

01:08:12.801 --> 01:08:14.082
Метода доступа.

01:08:14.883 --> 01:08:21.410
Методы Set Corenposs установить текущую
позицию на запись с

01:08:21.490 --> 01:08:27.937
заданным номером и получить номер текущей
записи вводят операции

01:08:28.137 --> 01:08:29.298
прямого доступа к за

01:08:30.574 --> 01:08:33.695
В классе реализованы методы навигации.

01:08:34.575 --> 01:08:39.936
Следующий файл — класс, обеспечивающий
реализацию просматриваемой таблицы.

01:08:47.057 --> 01:08:50.738
В данном классе реализованы методы
обработки таблиц.

01:08:52.748 --> 01:08:58.503
Далее файл упорядочение таблицы Tsort
Table.

01:09:00.461 --> 01:09:03.699
Метод сортировки, сортировка данных.

01:09:03.979 --> 01:09:07.376
Метод вставок, слияние.

01:09:08.015 --> 01:09:09.334
Быстрая сортировка.

01:09:19.544 --> 01:09:23.945
Установить метод сортировки, основные
методы.

01:09:24.345 --> 01:09:28.426
Найти запись, вставить или удалить запись.

01:09:29.146 --> 01:09:33.028
В данном классе приводится три метода
сортировки.

01:09:33.228 --> 01:09:37.029
Другие методы сортировки могут
рассматриваться как задания для

01:09:37.149 --> 01:09:38.629
самостоятельного выполнения.

01:09:39.869 --> 01:09:45.509
Метод поиска записи основан на алгоритме
бинарного поиска.

01:09:46.510 --> 01:09:53.510
В методах вставки и удаления происходит
обращение к

01:09:53.590 --> 01:09:57.630
методу поиска, и производится перепаковка
таблицы.

01:10:01.828 --> 01:10:06.946
Файл абстрактного базового класса объектов
значений для деревьев.

01:10:14.984 --> 01:10:19.703
Также предложен файл таблицы со структурой
хранения в виде деревьев поиска.

01:10:20.913 --> 01:10:26.477
в котором выполняются функции указатель на
корень дерева, адрес указателя на вершину

01:10:26.637 --> 01:10:33.521
результата указатель на текущую вершину,
номер текущей вершины стэп

01:10:33.601 --> 01:10:37.403
для итератора удаление диструктор

01:10:39.122 --> 01:10:40.803
Информационные методы.

01:10:40.923 --> 01:10:43.806
Запись заполненная ли таблица.

01:10:44.006 --> 01:10:49.371
Основные методы: найти, вставить либо
удалить запись.

01:10:50.692 --> 01:10:55.056
Навигация. Установить на первую запись.

01:10:56.245 --> 01:10:57.765
Завершение таблицы.

01:10:58.164 --> 01:11:00.083
Переход к следующей записи.

01:11:03.722 --> 01:11:07.960
Для обхода дерева используется стек из
библиотеки СТЛ.

01:11:08.120 --> 01:11:11.718
В нём запоминаются указатели на пройденные
узлы дерева.

01:11:13.469 --> 01:11:17.914
Базовый класс значений для
сбалансированных деревьев будет иметь

01:11:17.994 --> 01:11:19.196
следующий вид.

01:11:21.759 --> 01:11:26.325
Далее, класс для сбалансированных
деревьев.

01:11:35.203 --> 01:11:41.357
Дерево является сбалансированным, если для
каждого из узла высота левого и правого

01:11:41.516 --> 01:11:45.113
поддерев различается не более чем на
единицу.

01:11:46.032 --> 01:11:51.705
Так как операции вставки и удаления могут
нарушить сбалансированность дерева.

01:11:52.203 --> 01:11:56.402
То необходимо в таких случаях проводить
процедуру балансировки.

01:11:57.282 --> 01:12:03.441
Базовый класс для таблицы с вычислимым
входом Thash Table.

01:12:04.200 --> 01:12:10.679
В классе содержится хэш-функция,
вычисляющая по ключу записи номер строки.

01:12:10.966 --> 01:12:12.288
...структуре хранения.

01:12:13.810 --> 01:12:19.498
Класс для таблицы с вычислимым входом,
использующим для решения коллизий открытое

01:12:19.698 --> 01:12:22.222
перемещение.

01:12:27.803 --> 01:12:32.528
Предложен вам файл, в который включены
функции память для записи таблицы,

01:12:32.568 --> 01:12:38.375
максимально возможное количество записей,
функция «шаг вторичного перемещения».

01:12:39.016 --> 01:12:43.221
Первая свободная строка обнаружения при
поиске; строка

01:12:54.718 --> 01:12:57.517
Структоров информационные методы.

01:12:57.876 --> 01:13:04.832
Затем определяется функция заполнения
таблицы, доступы, основные методы,

01:13:04.912 --> 01:13:10.148
навигация. При открытом перемешивании,
добавлении новых записей возможно

01:13:11.195 --> 01:13:13.874
При наличии свободных строк таблице.

01:13:14.193 --> 01:13:19.871
Разрешение коллизии происходит путём
вычисления нового адреса для записи, пока

01:13:19.991 --> 01:13:22.430
не будет найдена свободная строка.

01:13:22.790 --> 01:13:26.748
Поэтому при удалении строка таблицы
помещается как удалённая

01:13:27.456 --> 01:13:34.176
без фактического удаления и освобождения
памяти но сохраняется возможность записи

01:13:34.656 --> 01:13:37.816
в неё нового значения при необходимости

01:13:43.177 --> 01:13:43.817
класс таблиц

01:13:47.582 --> 01:13:53.027
С вычислимым входом, использующим для
разрешения коллизий метода цепочек.

01:13:53.787 --> 01:13:58.992
Включены следующие функции: память для
массива указателей на списке записей,

01:13:59.112 --> 01:14:03.556
размер массива указателей, список, котором
выполняется поиск.

01:14:04.649 --> 01:14:09.931
Конструктор. Информационные методы,
заполнена ли таблица.

01:14:10.051 --> 01:14:12.332
Доступ основные методы.

01:14:12.412 --> 01:14:15.774
Найти запись, вставить, удалить запись.

01:14:19.416 --> 01:14:22.017
Навигация. Установить на первую запись.

01:14:22.570 --> 01:14:25.767
Таблица завершена, переход к следующей
записи.

01:14:26.526 --> 01:14:32.041
В методе цепочек добавления новых записей
в случае возникновения коллизии происходит

01:14:32.281 --> 01:14:34.959
путём добавления значений в список.

01:14:35.518 --> 01:14:40.394
В связи с тем необходимо использовать
ранее разработанный клад для списков ТД.

01:14:44.076 --> 01:14:45.714
Этапы разработки.

01:14:46.074 --> 01:14:52.307
Как и ранее выполнение лабораторной работы
должно быть разделено на несколько этапов.

01:14:52.427 --> 01:14:53.346
Каждый из этапов

01:14:59.706 --> 01:15:04.383
Возможность решения поставленной
прикладной задачи в той или иной

01:15:04.743 --> 01:15:10.859
ограниченной постановке на как можно более
ранних этапах выполнения работ.

01:15:11.298 --> 01:15:15.576
С учётом высказанных рекомендаций,
последовательность разработки программ

01:15:16.095 --> 01:15:17.614
может быть следующей.

01:15:18.358 --> 01:15:24.675
Этап первый. Реализация программ для
работы с просматриваемыми таблицами.

01:15:25.394 --> 01:15:31.350
Выполнение этапа может быть разделено на
несколько итераций: реализация некоторой

01:15:31.470 --> 01:15:35.468
упрощённой схемы начального заполнения
таблицы.

01:15:36.387 --> 01:15:38.587
Реализация операции поиска.

01:15:39.387 --> 01:15:41.667
Реализация операции вставки.

01:15:42.267 --> 01:15:44.667
Реализация операции удаления.

01:15:45.427 --> 01:15:50.627
Результаты каждой итерации должны быть
протестированы, переход к следующей

01:15:50.667 --> 01:15:52.067
итерации разработки.

01:15:52.718 --> 01:15:57.998
Должен осуществляться только после
успешного выполнения всех запланированных

01:15:58.198 --> 01:16:04.719
тестов. На данном этапе должен быть
разработан начальный вариант диалоговой

01:16:04.879 --> 01:16:08.239
формы управления табличными операциями.

01:16:09.743 --> 01:16:15.984
Этап второй. Реализация первой очереди
операций прикладной задачи из постановки

01:16:16.224 --> 01:16:17.865
лабораторной работы.

01:16:18.105 --> 01:16:22.706
Статистическая обработка результатов
экзаменационной сессии.

01:16:23.186 --> 01:16:27.987
В числе реализуемых операций может быть,
например, ввод исходных данных.

01:16:28.548 --> 01:16:34.105
Из текстовых файлов получение данных об
успеваемости отдельных студентов

01:16:34.624 --> 01:16:41.541
вычисление средних оценок по отдельным
предметам и другое Этап

01:16:41.660 --> 01:16:45.218
должен включать развитие диалоговой формы
управления.

01:16:45.777 --> 01:16:50.898
Третий этап — реализация программ для
работы с упорядоченными таблицами.

01:16:51.298 --> 01:16:56.419
Для проверки правильности работы программ
результаты выполнения должны сравниваться

01:16:56.579 --> 01:17:00.860
с результатами, получаемыми при помощи
просматриваемых

01:17:01.460 --> 01:17:07.661
Таблиц. На этом же этапе может быть
расширен список реализованных операций

01:17:08.102 --> 01:17:13.542
прикладной задачи и продолжено развитие
диалоговой формы управления.

01:17:14.183 --> 01:17:19.023
На данном этапе должны быть начаты работы
по получению графических форм.

01:17:19.584 --> 01:17:22.900
результатов обработки экзаменационных
данных.

01:17:23.380 --> 01:17:29.013
Например, построение диаграмм по средним
баллам для различных студенческих групп,

01:17:29.213 --> 01:17:33.568
графики успеваемости студентов по разным
предметам и другое.

01:17:34.567 --> 01:17:35.645
Этап четвёртый.

01:17:36.700 --> 01:17:41.816
Реализация программ для работы с таблицами
на основе деревьев поиска.

01:17:42.615 --> 01:17:49.530
Дальнейшее расширение списка реализованных
операций, прикладной задачи, диалоговой

01:17:49.690 --> 01:17:52.088
формы управления, графических форм.

01:17:59.622 --> 01:18:03.146
...для работы с таблицами с вычислимым
входом.

01:18:03.706 --> 01:18:08.911
Дальнейшее расширение списка реализованных
операций прикладной задачи, диалоговой

01:18:09.071 --> 01:18:14.717
формы управления графических форм вывода
результатов тести.

01:18:15.397 --> 01:18:16.398
Этап шестой.

01:18:16.885 --> 01:18:22.398
Выполнение вычислительных экспериментов
для оценки эффективности различных

01:18:22.518 --> 01:18:24.835
способов организации таблиц.

01:18:25.195 --> 01:18:30.708
Разработка различных генераторов
последовательности выполняемых операций.

01:18:31.427 --> 01:18:31.867
Генератор

01:18:32.294 --> 01:18:38.538
...только операций поиска, генерация
потока операций всех типов, генерация

01:18:38.778 --> 01:18:43.861
потоков операций с равномерным
использованием ключей и тому подобное.

01:18:45.221 --> 01:18:46.982
Рекомендации по разработке.

01:18:48.030 --> 01:18:53.431
Следует уделить большое внимание
определению состава реализуемых операций

01:18:53.911 --> 01:18:59.152
прикладной задачи по статистической
обработке результатов экзаменационной

01:18:59.272 --> 01:19:03.912
сессии. Набор операций может быть
достаточно ограничен.

01:19:04.237 --> 01:19:10.037
Но должен обеспечивать поддержку основных
процедур анализа успеваемости, обычно

01:19:10.197 --> 01:19:12.877
выполняемых работниками деканата.

01:19:13.877 --> 01:19:18.798
Ориентированность на практическое
использование предъявляет особые

01:19:18.998 --> 01:19:21.958
требования к проектированию диалоговой
формы.

01:19:22.540 --> 01:19:29.378
Управление таблицами обычное требование
для интерфейса с

01:19:29.498 --> 01:19:35.257
пользователем состоит в обеспечении
наглядности, понятности, дружественности и

01:19:35.417 --> 01:19:36.257
тому подобного.

01:19:37.097 --> 01:19:42.258
При практическом использовании программ
особое значение имеет наличие графических

01:19:42.378 --> 01:19:45.259
форм представления результатов обработки.

01:19:46.259 --> 01:19:51.621
Как и прежде, должно быть обеспечено
надёжное функционирование разработанных

01:19:51.741 --> 01:19:52.221
программ.

01:19:53.337 --> 01:19:59.103
С этой целью может быть разработан тот или
иной генератор текстовых данных для

01:19:59.303 --> 01:20:02.467
многократной проверки правильности
программ.

01:20:03.428 --> 01:20:07.712
В числе тестов должны быть и таблицы
достаточно большого объёма.

01:20:09.756 --> 01:20:14.877
При выполнении лабораторной работы может
быть рекомендована командная форма

01:20:15.077 --> 01:20:16.478
разработки программ.

01:20:16.958 --> 01:20:22.399
В составе команды один разработчик может
отвечать за реализацию программ для

01:20:22.559 --> 01:20:25.760
таблиц. Другой разработчик может отвечать

01:20:26.424 --> 01:20:30.908
за разработку диалоговых форм управления
таблицами.

01:20:31.069 --> 01:20:36.674
Ещё один может заниматься разработкой
графических форм, вывода результатов

01:20:36.994 --> 01:20:42.439
разработки и наконец, отдельный
разработчик может проводить тестирование

01:20:43.512 --> 01:20:49.153
Обязанности разработчиков могут изменяться
в ходе выполнения лабораторной работы.

01:20:49.554 --> 01:20:52.114
Возможны и темы дополнительных заданий.

01:20:52.594 --> 01:20:57.595
Для развития навыков практического
программирования рекомендуются следующие

01:20:57.675 --> 01:21:00.356
направления расширения постановки задачи.

01:21:00.849 --> 01:21:04.689
Реализовать дополнительные операции над
таблицами.

01:21:04.929 --> 01:21:10.368
Реализовать методы балансировки деревьев,
поиска и выполнить вычислительные

01:21:10.568 --> 01:21:16.847
эксперименты по оценке эффективности
операций с таблицей при балансировке.

01:21:17.475 --> 01:21:23.077
Сравнить работу с таблицей при наличии и в
отсутствии методов балансировки.

01:21:23.877 --> 01:21:30.599
Реализовать дополнительный набор операций
для обработки результатов успеваемости.

01:21:30.959 --> 01:21:33.920
Реализовать дополнительный набор
графических форм.

01:21:34.340 --> 01:21:36.782
Вывода результатов обработки.

01:21:37.022 --> 01:21:40.544
Реализовать расширенное представление
таблиц.

01:21:43.066 --> 01:21:48.990
Выполнить замену разработанных программ
для реализации таблиц на средства работы с

01:21:49.070 --> 01:21:51.112
таблицами библиотеки СТЛ.

01:21:51.664 --> 01:21:55.704
Оценить трудоёмкость выполнения такой
замены.

01:21:56.224 --> 01:22:00.664
Выполнить лабораторную работу на примере
другой прикладной задачи.

01:22:01.823 --> 01:22:05.103
Критерии оценивания данной лабораторной
работы.

01:22:05.463 --> 01:22:11.423
Лабораторная работа считается данной при
выполнении минимального набора требований.

01:22:12.623 --> 01:22:19.509
Реализованы просматриваемая упорядоченная
хэш-таблица, таблицы

01:22:19.629 --> 01:22:21.911
на основе деревьев поиска.

01:22:22.272 --> 01:22:26.635
Эффективность поиска в лучшем, худшем и
среднем случаях соответствует

01:22:26.996 --> 01:22:28.517
теоретическим оценкам.

01:22:29.745 --> 01:22:35.222
Для рассматриваемой прикладной задачи
реализованы четыре-пять операций для

01:22:35.462 --> 01:22:41.619
обработки результатов экзаменационной
сессии и две-три графические формы вывода.

01:22:42.619 --> 01:22:47.217
В более полном варианте выполнения
лабораторной работы реализованы два

01:22:47.497 --> 01:22:50.775
варианта разрешения коллизий в
хеш-таблице.

01:22:51.188 --> 01:22:55.787
Реализован класс таблиц на основе
сбалансированного дерева.

01:22:57.106 --> 01:22:59.666
Вопросы и задания для самоконтроля.

01:23:00.025 --> 01:23:05.104
Приведите примеры прикладных задач, при
решении которых могут быть использованы

01:23:05.224 --> 01:23:10.462
таблицы. Какие дополнительные операции
могут быть полезны при обработке

01:23:10.622 --> 01:23:11.262
результатов?

01:23:11.668 --> 01:23:13.667
Экзаменационной сессии.

01:23:15.146 --> 01:23:20.181
Для разных способов организации таблиц
приведите примеры задач, в которых эти

01:23:20.421 --> 01:23:23.219
способы являются наиболее эффективными.

01:23:23.858 --> 01:23:29.893
Какова трудоёмкость алгоритма сортировки
вставками, алгоритма сортировки слиянием

01:23:30.213 --> 01:23:32.052
методом быстрой сортировки?

01:23:33.195 --> 01:23:37.839
В чём различие сбалансированных и идеально
сбалансированных деревьев поиска?

01:23:38.640 --> 01:23:42.925
Почему при реализации таблиц не
используются идеально сбалансированные

01:23:43.085 --> 01:23:48.730
деревья поиска? Какие рекомендации следует
учитывать при выборе хэш-функции?

01:23:49.854 --> 01:23:53.252
Какие существуют методы разрешения
коллизий?

01:23:53.332 --> 01:23:55.970
Укажите их сильные и слабые стороны.

