WEBVTT

00:00:15.900 --> 00:00:20.379
Преподаватель, кандидат пенаук, доцент
Романова Татьяна Николаевна.

00:00:21.019 --> 00:00:26.378
План занятия: технические и программные
средства реализации информационных

00:00:26.498 --> 00:00:31.697
процессов, архитектура компьютера, уровни
программного обеспечения.

00:00:32.292 --> 00:00:38.934
Современные операционные системы, их
разновидности и различия: защита

00:00:39.094 --> 00:00:44.256
информации на персональном компьютере,
классификация программного обеспечения,

00:00:44.536 --> 00:00:48.298
информационные технологии, определения и
задачи.

00:00:48.852 --> 00:00:54.238
Работа со сжатыми данными, архивирование,
периферийные устройства.

00:01:48.973 --> 00:01:53.010
Чертежом в рамках лабораторной работы
называют графическое изображение

00:01:53.769 --> 00:01:59.525
моделируемого объекта, характеризующее его
форму и размеры и выполненное по

00:01:59.645 --> 00:02:05.040
определённым правилам проектирования с
применением общепринятых соглашений по

00:02:05.160 --> 00:02:08.517
изображению и обозначению графических
элементов.

00:02:09.357 --> 00:02:15.038
По чертежам изготавливает детали и
производят сборку узлов машин и

00:02:15.158 --> 00:02:20.359
конструкций, чертёж на производстве — это
основной технический документ, в котором

00:02:20.479 --> 00:02:24.800
указаны необходимые сведения о деталях, их
материале.

00:02:25.198 --> 00:02:28.160
Термической обработки и технические
условия.

00:02:28.281 --> 00:02:33.965
На изготовление по нему проверяют качество
обработки на всех стадиях технического

00:02:34.205 --> 00:02:41.131
процесса, различают чертёж детали,
сборочный чертёж, чертёж общего вида и

00:02:41.291 --> 00:02:41.772
другого.

00:02:44.180 --> 00:02:50.294
В рамках лабораторной работы ставится
задача разработки программного комплекса

00:02:50.494 --> 00:02:55.769
для представления, редактирования
отображения на экране дисплея конкретного

00:02:55.969 --> 00:03:01.604
типа графических данных, чертежей,
образуемых из ограниченного набора

00:03:01.843 --> 00:03:04.361
различных геометрических элементов.

00:03:04.846 --> 00:03:07.882
...точек, линий окружностей и тому
подобное.

00:03:08.481 --> 00:03:14.713
Разрабатываемый комплекс должен
обеспечивать представление чертежей в

00:03:14.793 --> 00:03:20.426
памяти ЭВМ, демонстрацию хранимых чертежей
на экране дисплея, редактировани...

00:03:21.181 --> 00:03:24.063
...ставку и удаление линий.

00:03:26.104 --> 00:03:29.786
Запись чтения данных о чертежах в файлах.

00:03:30.667 --> 00:03:35.430
Данная лабораторная работа является одной
из завершённых работ лабораторного

00:03:35.630 --> 00:03:40.032
практикума учебного курса по методам
программирования.

00:03:40.352 --> 00:03:43.034
Тем самым постановка лабораторной работы.

00:03:43.441 --> 00:03:48.519
Должна иметь повышенную сложность с тем,
чтобы для выполнения работы потребовалось

00:03:49.318 --> 00:03:52.157
участие нескольких разработчиков.

00:03:53.077 --> 00:03:58.474
Освоение принципов командной работы
является одной из ключевых учебных задач

00:03:58.674 --> 00:03:59.914
лабораторной работы.

00:04:01.485 --> 00:04:06.887
Для успешного выполнения данной
лабораторной работы, её реализация должна

00:04:07.007 --> 00:04:10.968
поручаться группе студентов из
трёх-четырех человек.

00:04:11.408 --> 00:04:16.450
Для лучшей координации выполняемых работ в
каждой группе может быть выделен

00:04:16.530 --> 00:04:17.090
ответственный

00:04:17.832 --> 00:04:23.066
за разработку главный программист, в
задачу которого входило бы согласование

00:04:23.306 --> 00:04:30.098
задания на разработку распределение работ
между участниками разработки согласование

00:04:30.338 --> 00:04:34.573
спецификации и тому подобное отдельный
разработчик

00:04:35.062 --> 00:04:39.990
Тестировщик может отвечать за тестирование
разрабатываемого кода.

00:04:40.230 --> 00:04:40.430
Ещё

00:04:52.633 --> 00:04:57.468
Важной частью разработки программной
системы является реализация диалоговой

00:04:57.588 --> 00:05:00.945
программы для взаимодействия с
пользователем.

00:05:01.464 --> 00:05:07.978
Данная часть разработки также может быть
поручена отдельному участнику группы

00:05:08.257 --> 00:05:09.097
разработчиков.

00:05:10.425 --> 00:05:16.351
С другой стороны, возможный вариант
выполнения лабораторной работы может

00:05:16.711 --> 00:05:22.597
состоять в использовании уже имеющихся
ранее разработанных диалоговых программ.

00:05:23.037 --> 00:05:24.839
В этом случае группе разработчиков

00:05:35.902 --> 00:05:38.460
Ролей участников группы разработчиков.

00:05:38.820 --> 00:05:44.935
От тестировщика зависит безошибочность,
надёжность разработанного кода программ.

00:05:45.375 --> 00:05:50.531
От разработчика диалоговой программы
зависит удобство использования программной

00:05:50.651 --> 00:05:51.210
системы.

00:05:51.887 --> 00:05:57.805
И наконец, от технического редактора
зависит лёгкость сопровождения и развития

00:05:57.925 --> 00:06:03.883
проекта и возможность более широкого
привлечения потенциальных потребителей

00:06:04.243 --> 00:06:06.283
разработанных программ.

00:06:07.602 --> 00:06:09.402
Условия и ограничения.

00:06:10.123 --> 00:06:15.926
В рамках выполнения данной лабораторной
работы могут быть использованы следующие

00:06:16.086 --> 00:06:17.887
основные допущения.

00:06:18.647 --> 00:06:24.491
В качестве чертежа будем рассматривать
плоский геометрический объект, состоящий

00:06:24.971 --> 00:06:26.452
из отрезков прямых линий.

00:06:27.278 --> 00:06:32.241
...и ограниченных и граничных точек этих

00:06:34.802 --> 00:06:41.404
линий. Представление других геометрических
элементов может рассматриваться как

00:06:41.604 --> 00:06:43.725
тема дополнительных заданий.

00:06:50.373 --> 00:06:56.096
Чертеж должен быть связным, то есть любая
линия чертежа должна иметь общую точку,

00:06:56.136 --> 00:06:58.857
хотя бы с одной другой линией чертежа.

00:06:59.938 --> 00:07:04.300
Пример возможного чертежа представлен на
следующем рисунке.

00:07:05.020 --> 00:07:05.300
Итак

00:07:11.548 --> 00:07:17.709
В данном случае прямоугольная система
координат — треугольник, который состоит

00:07:17.949 --> 00:07:22.509
из трёх отрезков и точек A, B, Ц.

00:07:24.709 --> 00:07:27.590
Метод решения структуры данных.

00:07:30.764 --> 00:07:36.009
Может быть представлен в виде множества
базовых геометрических объектов, точек,

00:07:36.089 --> 00:07:38.531
линий, окружностей и так далее.

00:07:39.933 --> 00:07:46.539
Информационное описание объектов включает
в себе параметры, фигуры, координаты,

00:07:46.659 --> 00:07:46.979
размер

00:07:47.723 --> 00:07:53.444
Радиус и другие с различной степенью
детализации в зависимости от требований,

00:07:53.524 --> 00:07:57.524
предъявляемых к чертежу данной предметной
области.

00:07:58.084 --> 00:08:03.244
В общем случае для описания фигуры
необходимо предусмотреть хранение

00:08:03.524 --> 00:08:06.244
координат некоторой опорной точки.

00:08:07.326 --> 00:08:13.445
Операции обработки геометрических объектов
состоят в задании и изменении

00:08:13.725 --> 00:08:19.204
параметров, а также визуализации на
примерном экране дисплея фигур.

00:08:22.284 --> 00:08:24.084
Для обеспечения возможностей

00:08:24.764 --> 00:08:28.367
Динамической визуализации геометрических
объектов.

00:08:28.527 --> 00:08:33.852
В лабораторной работе вводится тип данных,
значения которых вычисляются в

00:08:33.932 --> 00:08:37.935
соответствии с задаваемым формульным
выражением.

00:08:42.010 --> 00:08:47.053
Возможная схема иерархии классов для
представления базовых геометрических

00:08:47.173 --> 00:08:49.454
элементов может состоять в следующем.

00:08:49.654 --> 00:08:52.295
В дальнейшем мы посмотрим на рисунке семь.

00:08:52.815 --> 00:08:58.698
Наиболее общие свойства геометрических
фигур и методы их разработки выделяются в

00:08:58.818 --> 00:08:59.898
абстрактных базовых

00:09:00.646 --> 00:09:07.240
Классов. От него наследуются классы для
представления точки, на основе которого

00:09:07.520 --> 00:09:12.994
реализуется класс для представления линии
и классы для других геометрических

00:09:13.154 --> 00:09:18.469
элементов. Точка определяется координатами
на плоскости.

00:09:19.078 --> 00:09:24.079
Значения координат определяются при помощи
формальных объектов класса.

00:09:25.720 --> 00:09:31.961
При формировании чертежа следует обратить
внимание, что одна и та же точка в чертеже

00:09:32.281 --> 00:09:34.281
может присутствовать несколько раз.

00:09:34.816 --> 00:09:39.935
В этом случае необходимо обеспечить
однократное представление точки без

00:09:40.135 --> 00:09:46.054
дублирования, для обеспечения корректной
работы операции вставки и удаления.

00:09:47.054 --> 00:09:50.214
Для представления линии в наиболее простом
варианте

00:09:50.945 --> 00:09:54.383
Необходимо хранить начальную и конечную
точку.

00:09:54.703 --> 00:09:59.780
В общем случае при формировании чертежа в
объекты линии могут храниться не

00:09:59.940 --> 00:10:04.497
координаты точек, а указатели на другие
линии чертежа.

00:10:05.416 --> 00:10:08.095
Данная ситуация допускается при выполнении

00:10:08.868 --> 00:10:10.465
Следующих условий.

00:10:12.183 --> 00:10:17.616
Начальная точка текущей линии может
определяться при помощи указателя на

00:10:17.776 --> 00:10:23.489
линию, конечная точка которой является
начальной точкой текущей линии.

00:10:31.044 --> 00:10:37.803
Квадратный базовый класс линия,
окружность,

00:10:37.923 --> 00:10:39.523
квадрат.

00:10:40.483 --> 00:10:44.002
Прошу вас переписать данную схему.

00:14:15.109 --> 00:14:20.468
Конечная точка текущей линии может
определяться при помощи указателя на

00:14:20.588 --> 00:14:25.986
линию. Конечная точка, которая является
конечной точкой текущей линии.

00:14:26.306 --> 00:14:29.545
Наряду с базовыми геометрическими
элементами

00:14:30.087 --> 00:14:34.325
требующих для своего представления
разработки отдельных классов в

00:14:34.405 --> 00:14:39.643
лабораторной работе предлагается
реализовать несколько различных способов

00:14:39.882 --> 00:14:45.040
формирования составных геометрий

00:14:47.139 --> 00:14:53.020
образуемых на основе уже существующих
геометрических фигур, как базовых, так и

00:14:53.100 --> 00:14:58.700
составных, и рассматриваемых при
выполнении операций обработки как единое

00:14:58.940 --> 00:15:03.820
целое Возможные способы формирования
составных объектов

00:15:04.354 --> 00:15:06.474
Объектов состоят в следующем.

00:15:06.954 --> 00:15:13.197
Группирование, когда составной объект
представляет набор уже

00:15:13.597 --> 00:15:19.999
существующих, как базовых, так и базовых,
так и составных геометрических фигур.

00:15:20.885 --> 00:15:25.480
Подобной операцией является, например,
группирование в графическом редакторе

00:15:25.600 --> 00:15:27.038
системы Word.

00:15:28.357 --> 00:15:34.470
Конструирование, когда составной объект
определяется на основе уже существующих

00:15:34.590 --> 00:15:36.149
геометрических фигур.

00:15:36.865 --> 00:15:43.151
Например, ломаная может быть определена
через набор конечных точек составляющих

00:15:43.311 --> 00:15:49.357
отрезков. Конструирование приводит к
созданию новой, сложной геометрической

00:15:49.517 --> 00:15:55.122
фигуры, которая не может быть разделена на
составные геометрические элементы.

00:16:01.094 --> 00:16:04.256
...при помощи сборки существующих
объектов.

00:16:04.536 --> 00:16:08.779
Так, например, чертёж может быть образован
из точек и линий.

00:16:09.299 --> 00:16:15.183
В рамках сконструированного объекта,
входящего в состав элемента,

00:16:15.264 --> 00:16:15.984
по-прежнему...

00:16:16.652 --> 00:16:20.970
Могут обрабатываться как отдельные
геометрические фигуры.

00:16:22.250 --> 00:16:27.287
Для представления данных, описывающих
структуру чертежа, предлагается

00:16:27.527 --> 00:16:30.566
использовать структуру хранения типа
плекс.

00:16:30.966 --> 00:16:35.524
Плекс есть структура хранения, включающая
звенья различных типов

00:16:36.160 --> 00:16:40.482
Отношения между которыми задаются при
помощи сцепления.

00:16:41.203 --> 00:16:46.846
Таким образом, плекс является
разновидностью многосвязного списка и

00:16:46.966 --> 00:16:50.648
используется для хранения сетевых моделей
данных.

00:16:51.448 --> 00:16:52.489
Основу плексов

00:16:53.033 --> 00:16:59.949
Для представления чертежей, состоящих из
линий и точек, составляют вершины, узлы, в

00:17:00.069 --> 00:17:06.025
каждой из которых располагается информация
о той или иной линии чертежа.

00:17:06.425 --> 00:17:09.423
Имя линия, координаты начальной и
конечной.

00:17:09.933 --> 00:17:16.210
Точки. Вам представлен пример
разработанной структуры

00:17:16.330 --> 00:17:20.129
хранения. На рисунке восемь приведён плекс
для чертежа

00:17:43.103 --> 00:17:49.188
Операции обхода плексов, необходимых,
например, при отрисовке чертежа.

00:17:49.748 --> 00:17:56.393
Реализация алгоритмов обхода плексов может
быть выполнена поэтапно.

00:17:56.513 --> 00:17:58.515
На первом этапе можно реализовать

00:17:59.341 --> 00:18:04.699
Частный алгоритм обхода плексов без
подплексов, как намер было предложено на

00:18:04.819 --> 00:18:10.576
рисунке «Три» в предыдущей лабораторной
работе, и только затем приступить к

00:18:10.616 --> 00:18:11.616
разработке общего

00:18:20.500 --> 00:18:26.304
...представление чертежей, которые можно
нарисовать без отрыва карандаша от бумаги.

00:18:26.704 --> 00:18:32.027
Пример такого объекта: треугольник
представлен на рисунке один,

00:18:32.147 --> 00:18:35.749
соответствующий плекс без подплексов
приведён на рисунке три.

00:18:36.510 --> 00:18:40.995
Для того чтобы нарисовать линию,
необходимо знать её начальную и конечную

00:18:41.195 --> 00:18:47.402
точку. Так как вепускается вместо
указателя точки хранения указатель

00:18:47.682 --> 00:18:53.248
линии, то необходимо найти первую линию, у
которой указатель начала — точка.

00:18:54.368 --> 00:18:59.531
В приведённом ранее примере на рисунке три
— это линия BC.

00:18:59.851 --> 00:19:05.014
Тогда конечная точка этой линии будет
начальной точкой предыдущей линии в

00:19:05.094 --> 00:19:06.535
примере CA.

00:19:07.095 --> 00:19:10.537
То есть, на первом этапе необходимо
отыскать линию

00:19:11.307 --> 00:19:13.905
У которой указатель начало точка.

00:19:14.184 --> 00:19:20.420
При этом указатели на все пройденные линии
необходимо запомнить в стеке.

00:19:21.139 --> 00:19:26.056
На втором этапе из стека извлекаются
линии, для которых в качестве начальной

00:19:26.176 --> 00:19:28.454
точки выступает конечная точка.

00:19:29.150 --> 00:19:30.711
Обработанной линии.

00:19:30.832 --> 00:19:36.598
Процесс заканчивается, когда в стеке
больше не содержится указателей на линии.

00:19:39.200 --> 00:19:41.363
Обход плекса с подплексами.

00:19:41.803 --> 00:19:45.527
Плекс с подплексами служит для
представления чертежей.

00:19:45.938 --> 00:19:49.620
...который нельзя нарисовать без отрыва
карандаша от бумаги.

00:19:50.260 --> 00:19:52.621
Пример такого чертежа представлен на
рисунке...

00:20:17.412 --> 00:20:23.727
Далее представлен пример чертежа, для
представления которого требуется плекс с

00:20:23.807 --> 00:20:30.681
подплексом. Верхняя горизонтальная линия
состоит из двух отрезков: DB и

00:20:38.179 --> 00:20:43.738
Для таких плексов указатель на конечную
точку может также указывать на линию.

00:20:43.938 --> 00:20:49.657
То есть конечная точка линии верхнего узла
плекса может являться конечной точкой

00:20:49.817 --> 00:20:51.697
линии правого подплекса.

00:20:52.017 --> 00:20:53.897
Для обхода плекса с подплексами

00:20:54.482 --> 00:20:58.760
Можно предложить рекурсивный и
нерекурсивный вариант.

00:20:59.120 --> 00:21:04.798
Общая схема рекурсивного алгоритма состоит
в следующем: вам предложен

00:21:05.237 --> 00:21:10.115
файл. То есть нужно отрисовать подплекс,
на кото-

00:21:10.538 --> 00:21:10.893
указывает

00:21:34.417 --> 00:21:39.257
Чартлайн для представления линии, которая
подлежит отрисовке.

00:21:40.057 --> 00:21:47.018
Класс для методов отрисовки рисунка
представлен файл линия, начальная точка

00:21:47.298 --> 00:21:49.018
и конечная точка.

00:21:49.818 --> 00:21:50.658
Общая схема

00:21:52.429 --> 00:21:58.353
Алгоритм обхода состоит в следующем:
линии, определяемые при обходе плекса,

00:21:58.393 --> 00:21:59.873
помещаются в стек.

00:22:00.314 --> 00:22:05.316
При линии, извлекаемые из стека,
последовательно определяется начальная и

00:22:05.437 --> 00:22:06.837
конечная точка.

00:22:07.918 --> 00:22:12.160
Для определения начальной точки
используется метод.

00:22:12.987 --> 00:22:19.954
First Point линии получаемый указатель
указывает на линию обработки

00:22:20.155 --> 00:22:26.922
текущей линии, откладывается линия
помещается в стек и

00:22:27.202 --> 00:22:29.204
начинается анализ новой линии.

00:22:29.908 --> 00:22:35.781
Данная процедура выполняется итеративно до
получения линии с известной начальной

00:22:36.221 --> 00:22:43.092
точкой. Для определения конечной точки
используется метод

00:22:46.047 --> 00:22:51.091
Если получаемый указатель указывает на
линию обработки текущей линии, снова

00:22:51.852 --> 00:22:56.415
откладывается текущая линия помещается в
стек.

00:22:56.656 --> 00:23:02.060
После этого формируется описание новой
линии, которая также помещается в стек.

00:23:02.460 --> 00:23:05.744
И цикл алгоритма обхода повторяется.

00:23:06.505 --> 00:23:12.351
При получении линий с определёнными
граничными точками следует выполнить

00:23:12.472 --> 00:23:15.034
обработку линий, отрисовать.

00:23:15.475 --> 00:23:19.559
Из стека извлекается новая линия, для
которой конечная точка

00:23:20.461 --> 00:23:25.936
Обработанной линии используется в качестве
первой неизвестной граничной точки.

00:23:26.775 --> 00:23:31.970
Выполнение обхода завершается при
опустошении стека линии.

00:23:33.288 --> 00:23:36.245
Какова же разработка программного
комплекса?

00:23:36.405 --> 00:23:38.563
Структура с учётом рассмотр

00:23:43.507 --> 00:23:45.467
Следующая структура программы.

00:23:46.267 --> 00:23:52.509
Это модуль с классом для формульного
транслятора, шаблонный класс для

00:23:52.709 --> 00:23:54.590
формульных значений.

00:23:54.910 --> 00:23:59.912
Шаблонный базовый абстрактный класс, класс
для точки.

00:24:01.803 --> 00:24:05.240
Класс для составного геометрического
объекта.

00:24:06.079 --> 00:24:11.434
Модуль с классами конструируемого
геометрического объекта и линии.

00:24:12.153 --> 00:24:14.911
Модуль программы тестирования.

00:24:15.430 --> 00:24:18.867
Модуль функций, реализующих визуальный,
диалоговый

00:24:19.573 --> 00:24:23.377
Интерфейс для взаимодействия с
пользователем.

00:24:24.098 --> 00:24:28.382
Прошу заполнить и записать данные модули.

00:24:30.144 --> 00:24:31.626
Даю вам несколько минут.

00:26:58.255 --> 00:27:04.008
На рисунке далее показаны отношения между
классами стрелками с незакрашенными

00:27:04.088 --> 00:27:09.003
треугольниками показаны отношения
наследования: базовый класс — производный

00:27:09.123 --> 00:27:15.596
класс. Рамбовидными стрелками — отношения
ассоциации: класс владелец, класс

00:27:15.716 --> 00:27:16.315
компонент.

00:27:17.347 --> 00:27:23.662
Обычными стрелками показано наличие поля
типа указатель на другой класс.

00:27:25.860 --> 00:27:31.455
Класс формального транслятора, класс
формальных значений.

00:27:32.055 --> 00:27:35.812
Абстрактный базовый класс для объектов
значений.

00:27:36.691 --> 00:27:38.770
Далее, абстрактный базовый класс.

00:27:39.936 --> 00:27:43.055
Класс для составного геометрического
объекта.

00:27:43.535 --> 00:27:45.455
Класс для точки.

00:27:53.293 --> 00:27:57.292
Класс для конструируемого геометрического
объекта.

00:27:58.313 --> 00:28:00.234
Класс для отрисовки линий

00:28:05.157 --> 00:28:06.798
Спецификации классов.

00:28:06.878 --> 00:28:13.281
С учётом предложенных к реализации
алгоритмов, спецификации классов могут

00:28:13.361 --> 00:28:15.323
состоять в следующем.

00:28:17.044 --> 00:28:18.044
Класс эфстран.

00:28:18.630 --> 00:28:25.387
Для формульного транслятора предложен вам

00:28:25.627 --> 00:28:32.263
файл. Далее, шаблонный класс для
формульных значений.

00:29:03.012 --> 00:29:07.692
Следующий файл — шаблонный базовый
абстрактный класс.

00:29:25.712 --> 00:29:32.384
Далее класс Tharpoint для точки, в

00:29:32.543 --> 00:29:35.939
которой необходимо указать координаты
точки.

00:29:36.978 --> 00:29:37.737
Далее произвести

00:29:44.500 --> 00:29:48.662
Вычислить параметры и создать копию.

00:29:51.544 --> 00:29:57.988
Следующий файл, класс Thar Group для
создания геометрического объекта.

00:30:09.311 --> 00:30:16.076
который входит в список графических
элементов группы Необходимо будет вставить

00:30:16.517 --> 00:30:21.200
объект в группу, где есть визуализация
объекта

00:30:21.991 --> 00:30:28.397
При скрытии объекта необходимо вычислить
параметры и

00:30:28.557 --> 00:30:30.438
создание копии.

00:30:33.481 --> 00:30:39.526
Класс Echart для конструируемого
геометрического объекта представлен

00:30:48.953 --> 00:30:54.906
В данном случае класс для методов
отрисовки отрисовки рисунков.

00:30:55.625 --> 00:31:00.181
Линия, начальная точка, конечная точка.

00:31:05.015 --> 00:31:05.295
Нужно

00:31:05.653 --> 00:31:12.135
Получить начальную точку, конечную точку
вставить начальную и конечную точку

00:31:14.336 --> 00:31:19.378
Необходима визуализация рисунка и скрытие
рисунка.

00:31:21.778 --> 00:31:23.899
Предлагаются этапы разработки.

00:31:24.779 --> 00:31:29.982
Выполнение лабораторной работы должно быть
разделено на несколько этапов.

00:31:30.903 --> 00:31:36.586
Каждый из этих этапов должен иметь
достаточно небольшую длительность.

00:31:36.786 --> 00:31:42.630
При этом должна обеспечиваться возможность
решения поставленной прикладной задачи.

00:31:43.396 --> 00:31:49.798
...той или иной ограниченной постановки на
как можно более ранних этапах выполнения

00:31:49.958 --> 00:31:55.640
работ С учётом высказанных рекомендаций,
последовательность разработки программ

00:31:56.120 --> 00:31:57.601
может быть следующей.

00:31:58.001 --> 00:31:58.881
Этап первый.

00:31:59.429 --> 00:32:04.349
Реализация программ для работы с флексами
простой структуры, например, для одной

00:32:04.469 --> 00:32:07.310
линии. Этап второй.

00:32:07.750 --> 00:32:09.110
Реализация программ для

00:32:16.467 --> 00:32:22.942
Этап третий — реализация отрисовки чертежа
на основе алгоритма обхода плексов без

00:32:23.182 --> 00:32:29.298
подплексов. Этап должен включать развитие
диалоговой формы управления.

00:32:30.337 --> 00:32:31.616
Этап четвёртый.

00:32:31.976 --> 00:32:36.333
Реализация операций чтения и записи
информации в файл.

00:32:37.853 --> 00:32:42.889
Этап пятый — реализация общего алгоритма
обхода флексов.

00:32:44.128 --> 00:32:49.283
Этап шесть — реализация дополнительных
операций обхода флексов.

00:32:50.083 --> 00:32:54.799
Результаты выполнения каждого этапа
требуют проведения самого тщательно

00:32:54.992 --> 00:32:59.907
Тщательного тестирования, поскольку
возможные ошибки могут проявляться только

00:33:00.346 --> 00:33:04.062
после некоторого длительного времени
работы с плексами.

00:33:04.582 --> 00:33:08.817
Ошибочные ситуации могут возникать не при
каждом сценарии

00:33:15.067 --> 00:33:19.341
Набор программ для работы с прексами
представляет собой достаточно сложную

00:33:19.541 --> 00:33:20.939
программную систему.

00:33:21.458 --> 00:33:24.334
При выполнении лабораторной работы следует
уделять

00:33:55.694 --> 00:33:59.213
Вам предложены возможные темы
дополнительных заданий.

00:33:59.493 --> 00:34:04.852
Для развития навыков практического
программирования рекомендуются следующие

00:34:04.972 --> 00:34:08.491
направления расширения постановки задачи.

00:34:08.850 --> 00:34:12.929
Реализовать построение чертежа с
использованием дополнительных

00:34:13.049 --> 00:34:13.729
геометрических

00:34:14.131 --> 00:34:19.246
...элементов, окружности и их дуг,
прямоугольников и другое.

00:34:20.046 --> 00:34:25.800
Разработка операции динамического
изменения, вставка и удаление линий для

00:34:26.000 --> 00:34:27.758
чертежа флекса.

00:34:28.437 --> 00:34:33.712
Реализовать проверку тождественности
чертежей для разных схем структур.

00:34:35.388 --> 00:34:40.742
Разработка представления арифметических
выражений с использованием флексов.

00:34:41.940 --> 00:34:45.217
Реализовать построение блоков, схем.

00:34:46.735 --> 00:34:51.090
Критерии оценивания выполнения данной
лабораторной работы.

00:34:51.818 --> 00:34:56.533
Лабораторная работа считается выполненной
при выполнении следующего минимального

00:34:56.653 --> 00:34:57.972
набора требований.

00:34:58.691 --> 00:35:04.167
Реализованы все классы, разработанные
программы обеспечивают демонстрацию

00:35:04.326 --> 00:35:07.843
методов отрисовки плекса без подплекса.

00:35:08.443 --> 00:35:11.600
Данные для построения считываются из
файла.

00:35:12.389 --> 00:35:17.395
В качестве примера может быть использован
чертёж, представленный на рисунке шесть.

00:35:18.076 --> 00:35:23.322
В расширенном варианте выполнения
лабораторной работы должен быть реализован

00:35:23.563 --> 00:35:27.408
обход плекса с подплексами, организован
визуальный

00:35:40.120 --> 00:35:42.677
Вопросы и задания для самоконтроля.

00:35:43.277 --> 00:35:47.592
Какие возможные модели можно использовать
для представления чертежа?

00:35:47.912 --> 00:35:50.269
В чём состоит модель чертежа?

00:35:51.028 --> 00:35:54.624
Какая структура хранения используется для
чертежа?

00:35:55.291 --> 00:36:01.045
Какие преимущества и недостатки есть у
рекурсивного и нерекурсивного алгоритмов

00:36:01.245 --> 00:36:02.563
обхода плекса?

00:36:03.403 --> 00:36:09.357
Как можно модифицировать алгоритм обхода
плекса для проверки чертежа на связность?

00:36:13.965 --> 00:36:20.732
Теперь переходим к изучению лабораторной
работы номер восемь, в которой мы должны

00:36:22.334 --> 00:36:26.778
научиться статистической обработке
результатам.

00:36:31.701 --> 00:36:37.976
где будет постановка учебной задачи,
основные понятия и определения требования,

00:36:38.056 --> 00:36:43.572
предложенные к лабораторной работе,
условия и ограничения методы решения

00:36:44.292 --> 00:36:50.047
структуры данных алгоритмы разработка
программного комплекса

00:36:50.767 --> 00:36:53.285
структура спецификация

00:36:54.786 --> 00:37:01.422
Этапы разработки, рекомендации по
разработке, возможные темы дополнительных

00:37:01.622 --> 00:37:02.701
заданий.

00:37:09.497 --> 00:37:13.374
Критерии оценивания выполнения данной
лабораторной работы.

00:37:14.215 --> 00:37:17.337
Вопросы и задания для самоконтроля.

00:37:20.618 --> 00:37:26.221
Статистическая обработка результатов
экзаменационной сессии.

00:37:26.301 --> 00:37:29.823
Таблицы. Представление данных.

00:37:30.156 --> 00:37:34.716
Во многих задачах и из разных областей
человеческой деятельности может быть

00:37:34.876 --> 00:37:37.116
организована при помощи таблиц.

00:37:37.796 --> 00:37:42.716
Таблицы представляет собой
последовательности строк, записей.

00:37:42.876 --> 00:37:45.196
Структура строк может быть различной.

00:37:45.721 --> 00:37:52.005
Но обязательным является поле, задающее
имя ключ записи.

00:37:56.889 --> 00:38:03.013
Таблицы применяются в бухгалтерском учёте,
ведомости разработанной платы, в торговле

00:38:03.253 --> 00:38:04.174
прайс-листы.

00:38:04.851 --> 00:38:10.049
В образовательных учреждениях
экзаменационные ведомости и является одним

00:38:10.249 --> 00:38:15.568
из наиболее распространённых структур
данных, используемых при создании

00:38:15.728 --> 00:38:19.687
системного и прикладного математического
обеспечения.

00:38:20.926 --> 00:38:22.446
Таблица широко применяется

00:38:34.977 --> 00:38:37.659
...активной памяти и тому подобное.

00:38:39.099 --> 00:38:44.902
Существование отношения иметь имя является
обязательным в большинстве

00:38:45.263 --> 00:38:48.865
разрабатываемых программистами структур
данных.

00:38:49.265 --> 00:38:52.707
Доступ по имени в этих структурах служит
для получения...

00:38:53.379 --> 00:38:58.900
Соответствие между адресным принципом
указания элементов памяти ЭВМ и

00:38:59.100 --> 00:39:05.021
общепринятым, более удобным для человека
способом указания объектов по их

00:39:05.101 --> 00:39:06.661
именам.

00:39:07.141 --> 00:39:12.662
Целью данной лабораторной работы помимо
изучения способов организации таблиц

00:39:13.393 --> 00:39:20.269
Является начальное знакомство с принципами
проектирования структур хранения,

00:39:20.508 --> 00:39:24.186
используемых в методах решения прикладных
задач.

00:39:24.546 --> 00:39:30.422
На примере таблиц изучается возможность
выбора разных вариантов структур хранения.

00:39:30.981 --> 00:39:37.265
Анализ их эффективности и определение
областей приложения, в которых выбираемые

00:39:37.345 --> 00:39:41.227
структуры хранения являются наиболее
эффективными.

00:39:43.028 --> 00:39:48.711
В качестве практической задачи, на примере
которой будет продемонстрированы возможные

00:39:48.871 --> 00:39:50.552
способы организации таблицы

00:39:51.193 --> 00:39:56.549
Рассматривается проблема статистической
обработки результатов экзаменационной

00:39:56.709 --> 00:40:02.625
успеваемости студентов, выполнения таких,
например, вычислений, как определение

00:40:02.904 --> 00:40:07.461
среднего балла по предмету или по
программе при назначении

00:40:12.658 --> 00:40:19.186
кафедрам и тому подобное постановка
учебной задачи

00:40:19.906 --> 00:40:22.149
основные понятия и определения.

00:40:22.309 --> 00:40:24.512
Таблица доска.

00:40:24.712 --> 00:40:28.557
Перевод с латинского — это динамическая
структура данных.

00:40:28.902 --> 00:40:34.455
Базисным множеством, к которым является
семейство линейных структур и записей.

00:40:35.054 --> 00:40:41.246
Базисное отношение включения определяется
операциями вставки и удаления записей.

00:40:43.284 --> 00:40:44.442
Запись кортеж.

00:40:45.062 --> 00:40:48.660
Каждый элемент которого обычно именуется
полем.

00:40:49.780 --> 00:40:56.177
Имя записи — ключ — одно из полей записи,
по которому обычно осуществляется поиск

00:40:56.657 --> 00:40:58.376
записи в таблице.

00:40:58.696 --> 00:41:02.094
Остальные поля образуют тело записи.

00:41:03.933 --> 00:41:05.732
Двоичное дерево поиска.

00:41:11.910 --> 00:41:13.749
Следующие условия.

00:41:15.988 --> 00:41:22.785
Для любого узла вершины дерева существует
не более двух потомков — двоичное дерево.

00:41:23.504 --> 00:41:27.982
Для любого узла значение во всех узлах
левого поддерева

00:41:28.646 --> 00:41:30.605
Меньше значение в узле.

00:41:31.085 --> 00:41:37.443
Для любого узла значение во всех узлах
правого под дерево больше значения в узле.

00:41:38.202 --> 00:41:44.680
Кэш-функция — это функция, ставящая в
соответствии ключу номер записи в таблице.

00:41:45.470 --> 00:41:51.986
используется при организации таблиц с
вычислимым

00:41:52.185 --> 00:41:57.102
входом Требования к лабораторной работе.

00:41:57.621 --> 00:42:02.178
В рамках данной лабораторной работы
ставится задача создания программных

00:42:02.298 --> 00:42:02.578
средств

00:42:03.514 --> 00:42:09.307
поддерживающих табличные динамические
структуры данных, таблицы и базовые

00:42:09.427 --> 00:42:16.020
операции над ними Поиск записи Вставка
записи без дублирования

00:42:17.139 --> 00:42:18.976
удаление записи.

00:42:19.496 --> 00:42:20.255
Выполнение опер

00:42:29.586 --> 00:42:31.227
Организации таблицы.

00:42:31.747 --> 00:42:36.710
В рамках лабораторной работы как
показатель эффективности предлагается

00:42:36.950 --> 00:42:42.713
использовать количество операций,
необходимых для выполнения операции поиска

00:42:42.913 --> 00:42:44.434
записи в таблице.

00:42:45.394 --> 00:42:48.476
Величина этого показателя должна
определяться

00:42:49.178 --> 00:42:56.018
Как аналитически при использовании тех или
иных упрощающих предложений, так

00:42:56.258 --> 00:43:01.538
и экспериментально на основе проведения
вычислительных экспериментов.

00:43:02.058 --> 00:43:07.778
В лабораторной работе предлагаются
реализовать следующие типы таблиц.

00:43:13.107 --> 00:43:19.023
Просмотровые неупорядочены упорядочены
сортированные

00:43:19.903 --> 00:43:20.342
таблицы

00:43:39.520 --> 00:43:41.879
Способы организации таблицы.

00:43:42.439 --> 00:43:47.596
Демонстрацию работоспособности
разрабатываемых при выполнении

00:43:48.196 --> 00:43:53.992
лабораторной работы программ следует
проводить на примере таблиц, содержащих

00:43:54.112 --> 00:43:55.472
данные о результатах.

00:43:55.902 --> 00:43:58.981
Экзаменационной успеваемости студентов.

00:43:59.421 --> 00:44:04.059
Для данного примера следует реализовать
следующие операции

00:44:06.019 --> 00:44:11.937
таблицы для таблицы с результатами
успеваемости отдельной студенческой

00:44:12.137 --> 00:44:12.617
группы.

00:44:13.711 --> 00:44:19.995
Это получение сведений об успеваемости
отдельного студента, оценка по конкретному

00:44:20.116 --> 00:44:23.998
предмету, сравнение оценки по всем
предметам.

00:44:24.759 --> 00:44:28.642
Определение средней оценки по группе по
отдельным предметам.

00:44:29.118 --> 00:44:36.036
Или по всем предметам Подсчитать
количество студентов,

00:44:36.156 --> 00:44:42.114
отличников и тому подобное для нескольких
таблиц с результатами успеваемости для

00:44:42.314 --> 00:44:44.914
всех студенческих групп курса.

00:44:45.434 --> 00:44:50.192
Получение средних оценок по всем
студенческим группам по отдельному

00:44:50.312 --> 00:44:50.872
предмету.

00:44:51.256 --> 00:44:53.418
...или по всем предметам.

00:44:55.539 --> 00:45:01.664
Определение студенческой группы с лучшей
успеваемостью по конкретному предмету или

00:45:01.904 --> 00:45:05.026
по всем предметам экзаменационной сессии.

00:45:05.787 --> 00:45:08.388
Подсчёт количества студентов-отличников...

00:45:09.251 --> 00:45:15.724
для всего курса и тому подобное Задача
обработки результатов успеваемости

00:45:16.603 --> 00:45:22.437
может быть расширена возможностью хранения
данных для нескольких экзаменационных

00:45:22.557 --> 00:45:26.352
сессий, например, за весь период обучения
студентов

00:45:28.191 --> 00:45:33.035
Указанный выше набор операций обработки
результатов успеваемости является

00:45:33.555 --> 00:45:35.276
минимально необходимым.

00:45:36.077 --> 00:45:43.002
Определение полного перечня необходимых
операций должно выполняться на этапе

00:45:43.162 --> 00:45:45.283
постановки в лабораторной работе.

00:45:46.005 --> 00:45:52.121
В том числе, например, могут быть выбраны
различающиеся выборы операций для

00:45:52.321 --> 00:45:56.399
получения разных постановок лабораторной
работы.

00:45:58.318 --> 00:46:03.515
Результаты обработки успеваемости
рекомендуется дополнять построением

00:46:03.634 --> 00:46:04.234
графиков.

00:46:04.747 --> 00:46:07.146
...и диаграмм различного вида.

00:46:08.106 --> 00:46:13.825
Например, диаграммы по средним баллам для
разных студенческих групп, графики

00:46:13.985 --> 00:46:16.984
успеваемости студентов по разным
предметам.

00:46:18.864 --> 00:46:22.263
Полезным расширением постановки
лабораторной работы...

00:46:22.710 --> 00:46:29.350
Является реализация возможности передачи
данных в офисные программы семейства

00:46:29.590 --> 00:46:36.350
Microsoft Office, например, в систему
обработки электронных таблиц Microsoft

00:46:36.510 --> 00:46:42.990
Excel. Условия и ограничения.

00:46:44.938 --> 00:46:48.018
Сделаем следующие основные допущения.

00:46:49.578 --> 00:46:55.377
В качестве ключа будем рассматривать
фамилию и инициалы студента, в качестве

00:46:55.617 --> 00:47:00.856
полей данных — это экзаменационные оценки
по учебным дисциплинам.

00:47:02.803 --> 00:47:09.165
Сведения об экзаменационной успеваемости
должны быть разнесены по разным таблицам

00:47:09.605 --> 00:47:12.767
для каждой студенческой группы в
отдельности.

00:47:14.167 --> 00:47:18.729
Исходные данные, количество и наименования
дисциплин, данные

00:47:19.439 --> 00:47:25.720
О результатах сессии должны извлекаться из
текстовых файлов для каждой

00:47:25.800 --> 00:47:28.281
студенческой группы в отдельности.

00:47:29.841 --> 00:47:34.602
При изменении состояния таблиц должна
обеспечиваться возможность

00:47:35.249 --> 00:47:38.488
Сохранение данных в текстовых файлах.

00:47:39.528 --> 00:47:44.846
Для контроля правильности работы программ
должна обеспечиваться возможность

00:47:45.365 --> 00:47:47.964
пакетного выполнения операций.

00:47:48.484 --> 00:47:54.242
Наименования операций и их параметры
задаются при помощи текстового файла.

00:47:56.016 --> 00:48:01.975
После выполнения пакета операций и
сохранения данных должна быть реализована

00:48:02.135 --> 00:48:08.893
возможность сравнения полученных файлов с
заранее подготовленными проверочными

00:48:09.213 --> 00:48:13.412
файлами. Метод решения.

00:48:14.916 --> 00:48:16.195
Структуры данных.

00:48:17.274 --> 00:48:23.428
Под таблицей следует понимать динамическую
структуру данных, которая в каждый момент

00:48:23.987 --> 00:48:29.981
выполнения вычислений состоит из конечного
набора элементов записей.

00:48:30.541 --> 00:48:31.939
Записи таблицы могут

00:48:32.500 --> 00:48:35.342
Подразделяться на несколько полей.

00:48:36.142 --> 00:48:42.466
При этом количество и тип полей являются
одинаковыми для всех записей таблицы.

00:48:43.427 --> 00:48:47.430
Первое поле всех записей таблицы является
ключом.

00:48:48.190 --> 00:48:52.113
Поля записи без ключевого поля образуют
тело записи.

00:48:54.133 --> 00:48:57.692
Первое поле всех записей таблицы является
ключом.

00:48:58.172 --> 00:49:04.370
Например, задавая соответствие между
интентификаторами переменных, именами и

00:49:04.530 --> 00:49:09.848
адресами памяти AVM, мы можем получить
простейшую таблицу видов.

00:49:11.447 --> 00:49:18.408
Имя, в которой есть и адрес в которой
каждая

00:49:18.568 --> 00:49:24.729
строка записи состоит из двух полей: поля
ключа, имени и поля тела записи

00:49:24.969 --> 00:49:30.970
адреса. Таблица, содержащая
экзаменационные оценки, имеет следующий

00:49:31.050 --> 00:49:31.330
вид.

00:49:32.457 --> 00:49:38.700
Фамилия, имя, отчество студента,
дисциплина: первая, вторая, третья,

00:49:38.820 --> 00:49:40.541
четвёртая и так далее.

00:49:41.581 --> 00:49:45.343
И соответствующие оценки по каждой
дисциплине.

00:49:46.584 --> 00:49:51.467
Для этой таблицы каждая строка состоит из
ключа: фамилия, имя, отчество.

00:49:52.397 --> 00:49:58.080
...и телозаписи поля, содержащее оценки по
четырём дисциплинам.

00:49:59.001 --> 00:50:02.403
Основные операции, выполняемые над
таблицами.

00:50:03.044 --> 00:50:06.846
Поиск записи по одному или нескольким
ключам.

00:50:07.407 --> 00:50:11.129
Вставка записи с контролем возможных
повторений.

00:50:11.970 --> 00:50:13.691
Удаление записи.

00:50:16.998 --> 00:50:23.363
Операции вставки и удаления служат для
формирования требуемого набора

00:50:23.563 --> 00:50:30.488
записей. Операция поиска записи по ключу
обеспечивает доступ по имени ключ

00:50:31.129 --> 00:50:32.890
к записям таблицы.

00:50:37.720 --> 00:50:43.196
Алгоритмы. Просматриваемые таблицы.

00:50:43.636 --> 00:50:49.831
Простейшим способом отыскания нужного
элемента является метод полного просмотра,

00:50:49.911 --> 00:50:54.267
сканирования, когда искомый ключ
сравнивается по очереди

00:50:54.863 --> 00:51:00.180
Со всеми ключами таблицы, начиная с
первого, вплоть до отыскания

00:51:00.899 --> 00:51:05.496
совпадающего элемента или до исчерпывания
записей.

00:51:06.095 --> 00:51:09.573
Если ключи в таблице расположены в
произвольном порядке

00:51:10.382 --> 00:51:12.221
Неупорядоченная таблица.

00:51:12.501 --> 00:51:15.580
Этот способ является единственно
возможным.

00:51:16.700 --> 00:51:22.777
Операция вставки в неупорядоченную таблицу
может быть выполнена путём добавления

00:51:23.017 --> 00:51:25.336
новой записи в конец таблицы.

00:51:26.329 --> 00:51:30.129
С корректировкой номера последней занятой
строки.

00:51:31.408 --> 00:51:37.728
Операция удаления строки может быть
реализована при помощи переписывания

00:51:38.008 --> 00:51:44.687
последней записи таблицы на место
удаляемой и соответствующей корректировки

00:51:44.887 --> 00:51:46.527
номера последней строки.

00:51:48.570 --> 00:51:54.891
Среднее количество просматриваемых записей
таблицы при поиске записи по ключу при

00:51:55.251 --> 00:52:00.292
предположении равной вероятности
использования ключей определяется

00:52:00.492 --> 00:52:04.733
следующим соотношением: среднее равно П
умножить

00:52:05.445 --> 00:52:12.405
На n большое делённое на два плюс разность
1 минус p умноженное на N.

00:52:14.485 --> 00:52:21.085
Где P вероятность того, что искомая запись
имеется в таблице большое N количество

00:52:21.285 --> 00:52:22.325
записей в таблице?

00:52:24.598 --> 00:52:26.318
Упорядоченные таблицы.

00:52:26.758 --> 00:52:33.158
При большом количестве записей в таблице
Nного больше единицы, затраты на

00:52:33.238 --> 00:52:38.038
выполнение полного просмотра становятся
значительными.

00:52:38.318 --> 00:52:40.198
Эффективность процедуры поиска

00:52:40.919 --> 00:52:47.402
Может повысить при размещении записей в
таблице в порядке возрастания или убывания

00:52:47.602 --> 00:52:54.445
ключей упорядоченная или сортированная
таблица Упорядоченность

00:52:54.565 --> 00:52:56.566
таблиц может быть организована

00:52:57.292 --> 00:53:00.252
Только при возможности сравнения ключей.

00:53:00.692 --> 00:53:05.733
На множестве ключей задано отношение
линейного порядка.

00:53:06.133 --> 00:53:12.535
Для поиска нужной записи в таких таблицах
может быть использованым

00:53:13.211 --> 00:53:17.814
Использован быстрый метод бинарного
двоичного поиска.

00:53:18.334 --> 00:53:24.818
Вместе с тем в упорядоченных таблицах
усложняется реализация операций вставки и

00:53:24.899 --> 00:53:30.422
удаления записей, при выполнении которых,
для сохранения упорядоченности

00:53:31.221 --> 00:53:35.144
становится необходимой перепаковка записей
таблицы.

00:53:36.145 --> 00:53:42.590
Среднее количество просматриваемых записей
таблицы при использовании бинарного поиска

00:53:42.790 --> 00:53:46.753
определяется следующим образом: среднее
равно

00:53:47.337 --> 00:53:51.456
Логарифмы по основанию 2 числа N.

00:53:54.216 --> 00:53:57.136
Таблицы на основе деревьев поиска.

00:53:57.976 --> 00:54:04.176
Снижение трудоёмкости операций вставки и
удаления за счёт исключения перепаковок.

00:54:04.893 --> 00:54:09.807
Может быть обеспечена при использовании
списковых структур хранения.

00:54:10.566 --> 00:54:17.078
При этом сохранение эффективности
двоичного поиска требует прямого доступа к

00:54:17.198 --> 00:54:20.235
звену со средней записью таблицы.

00:54:21.688 --> 00:54:26.971
Из этого звена должна существовать
возможность доступа к средним записям

00:54:27.091 --> 00:54:30.613
левой и правой частей таблицы и так далее.

00:54:31.814 --> 00:54:37.377
Данные требования могут быть обеспечены
при использовании деревьев поиска для

00:54:37.538 --> 00:54:38.978
представления таблиц.

00:54:40.459 --> 00:54:46.386
Использование деревьев поиска обеспечивает
сложность среднего логарифмов по основанию

00:54:46.506 --> 00:54:52.953
2 числа N для всех операций обработки,
поиска, вставки и удаления таблиц.

00:54:53.874 --> 00:54:57.518
Среднее равно логарифму по основанию 2
числа Н.

00:54:58.960 --> 00:55:05.117
Максимальная сложность обработки деревьев
поиска имеет порядок Bn большого в случае

00:55:05.557 --> 00:55:08.435
вырождения деревьев список.

00:55:09.595 --> 00:55:13.872
Для исключения вырожденных случаев деревья
поиска

00:55:14.576 --> 00:55:21.535
обобщается до сбалансированных деревьев
поиска, в которых высота поддерев

00:55:21.935 --> 00:55:26.774
для любых узлов отличается не более чем на
первое.

00:55:27.334 --> 00:55:33.134
Подобные деревья обеспечивают сложность
порядка логарифма по основанию двух числа

00:55:35.505 --> 00:55:41.621
Для любых вариантов исходных данных нот
расхода времени на проведение

00:55:42.101 --> 00:55:48.697
балансировки Методы балансировки деревьев
поиска могут быть рассмотрены в качестве

00:55:49.017 --> 00:55:50.775
дополнительного задания.

00:55:53.500 --> 00:55:56.221
Таблицы с вычисляемыми адресами.

00:55:56.741 --> 00:56:02.622
Иной возможный способ построения таблиц
при большом количестве записей состоит в

00:56:02.742 --> 00:56:07.543
предварительном перед непосредственным
поиском по таблице вычислении

00:56:07.904 --> 00:56:10.384
месторасположения искомой записи.

00:56:13.407 --> 00:56:19.048
Данный метод предполагает наличие
некоторой простой функции H, которая

00:56:20.648 --> 00:56:25.730
отображает множество имён на множество
номеров строк таблицы.

00:56:26.330 --> 00:56:31.771
Эта функция называется функцией
хэширования или расстановки.

00:56:39.991 --> 00:56:46.026
Таблицами с вычисляемыми адресами или
перемешиваемыми таблицами

00:56:49.423 --> 00:56:50.462
функции расстановки

00:56:56.510 --> 00:57:01.787
...номера строки, в которой хранится или
будет храниться при вставке некоторый

00:57:01.907 --> 00:57:08.864
ключ, можно взять код первого символа
имени, либо сумму всех кодов символов

00:57:09.024 --> 00:57:12.062
ключа по модулю числа M.

00:57:12.992 --> 00:57:18.997
Где M — длина таблицы — размер массива,
отведённого для её хранения.

00:57:20.998 --> 00:57:26.882
При использовании таблиц с вычисляемыми
адресами может возникнуть ряд

00:57:27.042 --> 00:57:28.363
дополнительных проблем.

00:57:30.323 --> 00:57:35.890
Так, например, при вставке новой записи
функция расстановки может выдавать номер

00:57:36.370 --> 00:57:38.413
занятой строки массива.

00:57:39.294 --> 00:57:43.860
Функция расстановки может определять один,
то есть для значения

00:57:49.284 --> 00:57:54.606
Такая ситуация при вставке записи
называется относительным переполнением

00:57:54.726 --> 00:57:57.807
таблицы или коллизией

00:58:01.689 --> 00:58:06.771
при возникновении коллизий возможны разные
методы их решения.

00:58:07.488 --> 00:58:08.968
Рассмотрим два из них.

00:58:09.808 --> 00:58:15.449
Метод открытого перемешивания состоит в
добавлении к вычисленному занятому номеру

00:58:15.929 --> 00:58:18.889
некоторого фиксированного смещения.

00:58:19.689 --> 00:58:26.290
Повторное перемешивание c-штрих равно K +
P умножить на модуль

00:58:27.343 --> 00:58:32.300
Есть новый адрес К-штрих также является
занятым.

00:58:32.579 --> 00:58:37.576
Следует повторить процедуру повторного
перемешивания до тех пор, пока не

00:58:37.695 --> 00:58:42.732
обнаружится свободная строка, либо таблица
не будет исчерпана.

00:58:43.324 --> 00:58:48.403
Или значения P и N большое являются
взаимнопростыми.

00:58:48.762 --> 00:58:54.481
Открытое перемешивание обеспечивает
нахождение свободной строки массива.

00:58:56.360 --> 00:58:58.240
Следующий метод цепочек.

00:58:58.866 --> 00:59:05.462
При возникновении коллизий формирует
линейные списки-цепочки-цепочки, в

00:59:05.581 --> 00:59:12.137
каждом из которых располагаются записи с
одинаковым значением функции расстановки.

00:59:12.617 --> 00:59:14.696
В этом случае в строках массива

00:59:15.370 --> 00:59:21.652
Для размещения записей следует добавить
ещё одно поле для рассылки на следующее

00:59:21.812 --> 00:59:23.212
звено списка.

00:59:24.973 --> 00:59:31.014
Среднее количество рассматриваемых записей
при поиске записи в перемешиваемых

00:59:31.175 --> 00:59:31.735
таблицах

00:59:32.555 --> 00:59:38.789
При предположении равной вероятности
использования ключей и при использовании

00:59:38.949 --> 00:59:44.943
функции расстановки с равномерным
рассеиванием ключей по строкам массива

00:59:45.662 --> 00:59:48.460
определяется следующим соотношением.

00:59:49.311 --> 00:59:53.707
Разрешение коллизии по методу открытого
перемешивания.

00:59:55.505 --> 01:00:01.899
Среднее равно отношению числителя 1 минус
альфа, делённое на два к знаменателю 1

01:00:02.179 --> 01:00:03.498
минус альфа.

01:00:03.857 --> 01:00:05.496
Где альфа — это коэффициент

01:00:06.423 --> 01:00:11.458
Заполненности таблицы Альфа равно Н
относится к N.

01:00:11.897 --> 01:00:17.811
M большое количество строк в массиве для
хранения записей N большое количество

01:00:18.051 --> 01:00:19.609
записей в таблице.

01:00:20.169 --> 01:00:25.324
Следует отметить, что количество сравнений
при поиске в перемешиваемых таблицах

01:00:26.049 --> 01:00:31.614
Зависит не от количества записей в
таблице, а от заполненности памяти,

01:00:31.935 --> 01:00:34.497
отведённой для размещения записей.

01:00:34.978 --> 01:00:41.224
Для примера, при заполненности массива на
75% Альфа равно 0,75

01:00:42.377 --> 01:00:46.972
Количество сравнений в среднем равно 2,5%.

01:00:47.971 --> 01:00:50.368
Разработка программного комплекса.

01:00:50.568 --> 01:00:56.362
Структура. При выполнении данной
лабораторной работы следует разработать

01:00:56.561 --> 01:00:57.201
иерархию

01:00:57.824 --> 01:01:03.898
классов, учитывая, что все таблицы имеют
как общие свойства, их описание следует

01:01:04.018 --> 01:01:10.172
поместить в определении базового класса,
так и особенности выполнения отдельных

01:01:10.332 --> 01:01:14.927
операций. Реализуются в отдельных классах
для каждого вида таблиц.

01:01:17.393 --> 01:01:24.320
При разработке классов используется ранее
разработанный класс TDaliu.

01:01:26.322 --> 01:01:29.766
Рекомендуемый состав классов приведён
ниже.

01:01:30.887 --> 01:01:35.892
В данном случае это модуль с классом
объектов значений для записи таблицы.

01:01:37.586 --> 01:01:42.821
Абстрактный базовый класс содержит
спецификации методов таблицы.

01:01:46.378 --> 01:01:50.853
Абстрактный базовый класс для таблиц с
непрерывной памятью.

01:01:54.170 --> 01:01:58.606
Модуль с классом, обеспечивающим
реализацию просматриваемых таблиц.

01:02:04.339 --> 01:02:08.936
Модуль с классом, обеспечивающим
реализацию упорядоченных таблиц.

01:02:13.254 --> 01:02:18.570
Модуль с абстрактным базовым классом
объектов значений для деревьев.

01:02:20.609 --> 01:02:24.807
Модуль с классом, реализующим таблицы в
виде деревьев поиска.

01:02:27.610 --> 01:02:32.410
Модуль с базовым классом объектов значений
для сбалансированных деревьев

01:02:36.810 --> 01:02:41.850
модуль с классом, реализующим таблицы в
виде сбалансированных деревьев поиска.

01:02:45.463 --> 01:02:51.425
Модуль с базовым классом, обеспечивающим
реализацию таблиц с вычислительным

01:02:51.865 --> 01:02:58.586
входом. Модуль с классом, обеспечивающим
реализацию

01:02:58.906 --> 01:03:00.266
хэш-таблиц.

01:03:00.907 --> 01:03:04.547
Разрешение коллизий на основе открытого
перемешивания.

01:03:08.194 --> 01:03:13.920
Модуль с классом, обеспечивающим
реализацию хэш-таблиц разрешения коллизий

01:03:14.000 --> 01:03:16.363
на основе метода цепочек.

01:03:19.926 --> 01:03:22.369
Модуль программы тестирования.

01:03:24.971 --> 01:03:26.373
Спецификация классов.

01:03:26.801 --> 01:03:31.077
С учётом предложенных к реализации
алгоритмов можно сделать следующие

01:03:31.237 --> 01:03:36.473
объявления классов: класс объектов
значений для записи таблиц.

01:03:36.952 --> 01:03:37.472
Вам предложен

01:03:37.831 --> 01:03:44.625
файл, в

01:03:44.785 --> 01:03:46.864
котором есть тип ключа записи.

01:03:47.209 --> 01:03:50.291
Класс объектов значений для записи
таблицы.

01:03:50.932 --> 01:03:53.854
Поля, ключи записи.

01:03:54.094 --> 01:03:57.296
Указатель назначение, методы.

01:03:57.616 --> 01:03:58.857
Конструктор.

01:03:59.497 --> 01:04:03.580
Установить значение ключа, получить
значение ключа.

01:04:05.310 --> 01:04:12.191
Установить указатель на данные, получить
указатель на данные, изготовить копию.

01:04:12.351 --> 01:04:18.392
Присваивание, сравнение равно
больше/меньше.

01:04:19.152 --> 01:04:21.993
Дружественные классы для различных типов
таблиц.

01:04:23.727 --> 01:04:25.048
Смотрите далее.

01:04:33.734 --> 01:04:38.337
Данный тип описывает значение ключей
записи.

01:04:40.538 --> 01:04:43.540
В данном примере для типа ключей
использован класс

01:04:44.257 --> 01:04:48.420
Стринг из стандартной библиотеки шаблонов
STL.

01:04:48.940 --> 01:04:55.864
Абстрактный базовый класс содержит
спецификации методов таблицы Table Rh,

01:04:56.504 --> 01:05:01.147
в которой у нас предлагается определять
количество записей в таблице.

01:05:02.016 --> 01:05:05.533
Показатель эффективности выполнения
операции.

01:05:08.131 --> 01:05:14.446
Далее: диструктор, информационные методы,
количество записей, эффективность

01:05:14.726 --> 01:05:18.163
пусто. Пуста ли запись заполнена?

01:05:19.015 --> 01:05:22.377
Доступ. Основные методы.

01:05:22.498 --> 01:05:25.259
Найти запись, вставить, удалить.

01:05:25.780 --> 01:05:28.341
Навигация. Установить на первую.

01:05:28.621 --> 01:05:31.183
Запись таблица завершена.

01:05:31.423 --> 01:05:33.024
Переход к следующей записи.

01:05:38.399 --> 01:05:41.802
Все методы данного класса расподелены на
четыре группы.

01:05:42.242 --> 01:05:48.929
Информационные методы — это получить
количество записей, получить эффективность

01:05:49.170 --> 01:05:51.212
последней операции.

01:05:51.772 --> 01:05:54.175
Проверить, не является ли таблица пустой.

01:05:55.476 --> 01:05:57.958
Проверить, не является ли таблица полной.

01:05:59.479 --> 01:06:02.000
Второй метод доступа к записям.

01:06:02.681 --> 01:06:05.883
Получить значение ключа текущей записи.

01:06:06.524 --> 01:06:09.926
Получить указатель на значение текущей
записи.

01:06:11.087 --> 01:06:11.847
Третий метод

01:06:12.627 --> 01:06:15.709
Методы навигации по таблице итератор.

01:06:16.750 --> 01:06:20.112
Установить текущую позицию на первую
запись.

01:06:21.272 --> 01:06:23.634
Проверка завершения таблицы.

01:06:23.754 --> 01:06:28.196
Под ситуацией завершения таблицы
понимается состояние после применения

01:06:28.317 --> 01:06:29.517
метода Go Next.

01:06:30.154 --> 01:06:36.232
Для текущей позиции установления
установленной на последней записи таблицы

01:06:37.712 --> 01:06:41.710
переместить текущую позицию на следующую
запись.

01:06:43.310 --> 01:06:46.189
Четвёртые методы обработки таблицы.

01:06:46.749 --> 01:06:49.508
Поиск записи по значению ключа.

01:06:50.375 --> 01:06:52.175
Вставка записи в таблицу.

01:06:52.295 --> 01:06:53.736
Удаление записи.

01:06:54.776 --> 01:06:59.738
Абстрактный класс для таблиц с непрерывной
памятью служит для управления структурой

01:07:00.298 --> 01:07:07.140
хранения. Предложен к вашему рассмотрению
файл, в котором включён «память для

01:07:07.260 --> 01:07:08.300
записи таблицы».

01:07:09.338 --> 01:07:12.738
Максимальное возможное количество записей
из таблицы.

01:07:13.498 --> 01:07:14.978
Номер текущей записи.

01:07:15.058 --> 01:07:17.298
Нумерация начинается с нуля.

01:07:18.458 --> 01:07:23.698
Конструктор, деструктор информационные
методы.

01:07:24.258 --> 01:07:27.858
Затем определяется вопрос: заполнена ли
таблица?

01:07:29.436 --> 01:07:31.037
Каково количество записей?

01:07:31.318 --> 01:07:33.479
Доступ.

01:07:33.720 --> 01:07:38.764
Основные методы: найти запись, вставить,
удалить запись.

01:07:39.284 --> 01:07:42.687
Навигация. Установить на первую запись.

01:07:43.047 --> 01:07:44.368
Таблица завершена.

01:07:45.349 --> 01:07:47.191
Переход к следующей записи.

01:07:48.633 --> 01:07:55.079
После применения для последней записи
таблицы установить текущую запись получить

01:07:55.239 --> 01:07:57.281
номер текущей записи.

01:08:00.525 --> 01:08:03.488
Данный класс обеспечивает управление
памятью.

01:08:03.962 --> 01:08:06.521
Выделение и освобождение памяти.

01:08:07.001 --> 01:08:11.998
Методы доступа применимы к первой, текущей
и последней записям таблицы.

01:08:12.358 --> 01:08:17.315
Желаемый вариант доступа задаётся через
параметр метода доступа.

01:08:18.115 --> 01:08:19.154
Методы set.

01:08:21.158 --> 01:08:27.920
Коренпос установить текущую позицию на
запись с заданным номером и получить номер

01:08:28.280 --> 01:08:34.202
текущей записи вводит операции прямого
доступа к записям таблицы в классе

01:08:34.282 --> 01:08:36.563
«Реализованные методы навигации».

01:08:37.999 --> 01:08:44.557
Следующий файл — класс, обеспечивающий
реализацию просматриваемой таблицы Test

01:08:50.276 --> 01:08:53.995
В данном классе реализованы методы
обработки таблиц.

01:08:55.971 --> 01:09:01.613
Далее файл упорядочение таблицы Tsort
Table.

01:09:03.693 --> 01:09:06.934
Метод сортировки, сортировка данных.

01:09:07.214 --> 01:09:10.655
Метод вставок, слияние.

01:09:11.256 --> 01:09:12.456
Быстрая сортировка.

01:09:20.575 --> 01:09:22.455
Получить метод сортировки.

01:09:22.775 --> 01:09:25.176
Установить метод сортировки.

01:09:25.696 --> 01:09:27.177
Основные методы.

01:09:27.537 --> 01:09:31.658
Найти запись, вставить или удалить запись.

01:09:32.378 --> 01:09:36.260
В данном классе приводится три метода
сортировки.

01:09:36.460 --> 01:09:38.340
Другие методы сортировки могут

01:09:49.880 --> 01:09:56.719
В методах вставки и удаления происходит
обращение к

01:09:56.839 --> 01:10:01.278
методу поиска, и производится перепаковка
таблицы.

01:10:04.917 --> 01:10:09.196
Файл абстрактного базового класса объектов
значений для деревьев.

01:10:26.670 --> 01:10:31.263
Корень дерева, адрес указателя на вершину
результата.

01:10:31.583 --> 01:10:35.658
Указатель на текущую вершину, номер
текущей вершины.

01:10:36.337 --> 01:10:37.495
Стек для итератора.

01:10:48.095 --> 01:10:51.975
Методы найти, вставить либо удалить запись

01:10:54.056 --> 01:10:55.976
навигация.

01:10:56.656 --> 01:11:01.297
Установить на первую запись завершение
таблицы.

01:11:01.537 --> 01:11:03.257
Переход к следующей записи.

01:11:07.146 --> 01:11:11.342
Для обхода дерева используется стек из
библиотеки СТЛ.

01:11:11.502 --> 01:11:15.337
В нём запоминаются указатели на пройденные
узлы дерева.

01:11:16.736 --> 01:11:21.251
Базовый класс значений для
сбалансированных деревьев будет иметь

01:11:21.291 --> 01:11:22.090
следующий вид.

01:11:25.169 --> 01:11:30.735
Далее класс для сбалансированных деревьев.

01:11:38.382 --> 01:11:40.625
Дерево является сбалансированным.

01:11:41.363 --> 01:11:46.882
Если для каждого из узла высота левого и
правого поддерева различается не более чем

01:11:47.122 --> 01:11:53.081
на единицу, так как операция вставки и
удаления могут нарушать

01:11:53.401 --> 01:11:58.320
сбалансированность дерева, то необходимо в
таких случаях проводить процедуру

01:11:58.520 --> 01:11:59.400
балансировки.

01:12:00.668 --> 01:12:06.671
Базовый класс для таблицы с вычислимым
входом — Thashevable.

01:12:07.512 --> 01:12:13.916
В классе содержится хэш-функция,
вычисляющая по ключу записи номер строки в

01:12:13.996 --> 01:12:15.516
структуре хранения.

01:12:17.037 --> 01:12:18.798
Класс для таблицы с вычислимым

01:12:19.287 --> 01:12:23.324
Кодом, использующим для решения коллизий
открытое перемещение

01:12:30.839 --> 01:12:35.636
Предложен вам файл, в котором включены
функции «память для записи таблицы»,

01:12:35.756 --> 01:12:38.354
максимально возможное количество записей.

01:12:39.059 --> 01:12:42.021
Функция шаг вторичного перемещения.

01:12:42.182 --> 01:12:45.905
Первая свободная строка: обнаружения при
поиске.

01:12:46.185 --> 01:12:52.832
Строка памяти при завершении поиска,
маркер для индикации строк с удалёнными

01:12:53.072 --> 01:12:58.317
записями. Конструктор.

01:12:58.836 --> 01:13:00.634
Информационные методы.

01:13:01.073 --> 01:13:07.866
Затем определяется функция заполнения
таблицы, доступы, основные методы,

01:13:07.986 --> 01:13:13.220
навигация. При открытом перемешивании,
добавления новых записей возможно

01:13:14.300 --> 01:13:16.897
При наличии свободных строк таблицы.

01:13:17.257 --> 01:13:23.012
Разрешение коллизии происходит путём
вычисления нового адреса для записи, пока

01:13:23.132 --> 01:13:25.570
не будет найдена свободная строка.

01:13:25.930 --> 01:13:29.887
Поэтому при удалении строка таблицы
помещается как удалённая

01:13:30.635 --> 01:13:37.322
Без фактического удаления и освобождения
памяти но сохраняется возможность записи

01:13:37.802 --> 01:13:40.965
в неё нового значения при необходимости

01:13:46.331 --> 01:13:48.013
класс таблиц вычисления

01:13:50.720 --> 01:13:56.200
С вычислимым входом, использующие для
разрешения коллизий метода цепочек.

01:13:56.920 --> 01:14:02.159
Включены следующие функции: память для
массива указателей на списке записей,

01:14:02.239 --> 01:14:07.158
размер массива указателей, список, в
котором выполняется поиск.

01:14:07.678 --> 01:14:12.038
Конструктор информационные методы
заполненная ли таблица.

01:14:13.261 --> 01:14:15.459
Доступ основные методы.

01:14:15.539 --> 01:14:18.057
Найти запись, вставить, удалить запись

01:14:22.613 --> 01:14:26.929
навигация. Установить на первую запись
Таблица завершена.

01:14:27.049 --> 01:14:28.727
Переход к следующей записи.

01:14:29.809 --> 01:14:35.164
В методе цепочек добавления новых записей
в случае возникновения коллизий происходит

01:14:35.444 --> 01:14:38.161
путём добавления значения в список.

01:14:38.640 --> 01:14:43.436
В связи с тем необходимо использовать
ранее разработанный класс для списков Teda

01:14:44.075 --> 01:14:48.471
List. Этапы разработки.

01:14:49.367 --> 01:14:55.452
Как и ранее выполнение лабораторной работы
должно быть разделено на несколько этапов.

01:14:55.572 --> 01:15:01.257
Каждый из этапов должен иметь достаточно
небольшую длительность, при этом должны

01:15:01.697 --> 01:15:07.061
обеспечиваться возможность решения
поставленной прикладной задачи в той или

01:15:07.301 --> 01:15:09.183
иной ограниченной постановкой.

01:15:10.147 --> 01:15:14.150
На как можно более ранних этапах
выполнения работ.

01:15:14.390 --> 01:15:18.673
С учётом высказанных рекомендаций,
последовательность разработки программ

01:15:19.234 --> 01:15:21.235
может быть следующая.

01:15:21.676 --> 01:15:27.840
Этап первый — реализация программ для
работы с просматриваемыми таблицами.

01:15:28.939 --> 01:15:33.021
Выполнение этапа может быть разделено на
несколько итераций.

01:15:33.581 --> 01:15:39.184
Реализация некоторой упрощённой схемы
начального заполнения таблицы.

01:15:39.705 --> 01:15:42.186
Реализация операции поиска.

01:15:42.786 --> 01:15:44.867
Реализация операции вставки.

01:15:45.685 --> 01:15:48.083
Реализация операции удаления.

01:15:48.803 --> 01:15:52.880
Результаты каждой итерации должны быть
протестированы.

01:15:52.960 --> 01:15:58.076
Переход к следующей итерации разработки
должен осуществляться только после

01:15:58.515 --> 01:16:01.833
успешного выполнения всех запланированных
тестов.

01:16:03.364 --> 01:16:08.642
На данном этапе должен быть разработан
начальный вариант диалоговой формы

01:16:08.802 --> 01:16:11.920
управления табличными операциями.

01:16:13.040 --> 01:16:19.397
Этап второй — реализация первой очереди
операций прикладной задачи из постановки

01:16:19.597 --> 01:16:20.997
лабораторной работы.

01:16:21.657 --> 01:16:26.056
Статистическая обработка результатов
экзаменационной сессии.

01:16:26.536 --> 01:16:31.815
В числе реализуемых операций может быть,
например, ввод исходных данных из

01:16:32.015 --> 01:16:37.494
текстовых файлов, получение данных об
успеваемости отдельных студентов.

01:16:38.032 --> 01:16:42.549
Вычисление средних оценок по отдельным
предметам и другое.

01:16:44.467 --> 01:16:48.665
Этап должен включать развитие диалоговой
формы управления.

01:16:48.984 --> 01:16:54.021
Третий этап — реализация программ для
работы с упорядоченными таблицами.

01:16:54.675 --> 01:16:59.715
Для проверки правильности работы программ
результаты выполнения должны сравниваться

01:16:59.916 --> 01:17:05.396
с результатами, получаемыми при помощи
просматриваемых таблиц.

01:17:06.316 --> 01:17:10.957
На этом же этапе может быть расширен
список реализованных операций.

01:17:11.410 --> 01:17:16.766
прикладной задачи и продолжено развитие
диалоговой формы управления.

01:17:17.405 --> 01:17:23.240
На данном этапе должны быть начаты работы
по получению графических форм, результатов

01:17:23.520 --> 01:17:26.197
обработки экзаменационных данных.

01:17:26.557 --> 01:17:28.395
Например, построению диаграмм.

01:17:28.758 --> 01:17:33.712
по средним баллам для различных
студенческих групп графики успеваемости

01:17:33.872 --> 01:17:40.624
студентов по разным предметам и другое
Этап четвёртый реализация программ

01:17:41.063 --> 01:17:44.060
для работы с таблицами на основе деревьев
поиска

01:17:45.633 --> 01:17:52.428
Дальнейшее расширение списка реализованных
операций прикладной задачи, диалоговой

01:17:52.628 --> 01:17:58.145
формы управления графических форм вывода
результатов тестирования.

01:17:59.104 --> 01:18:04.860
Этап пятый. Реализация программ для работы
с таблицами с вычислимым

01:18:06.594 --> 01:18:11.754
Дальнейшее расширение списка реализованных
операций прикладной задачи, диалоговой

01:18:11.914 --> 01:18:17.554
формы управления графических форм вывода
результатов тестирования.

01:18:18.274 --> 01:18:24.434
Этап шестой. Выполнение вычислительных
экспериментов для оценки эффективности

01:18:24.794 --> 01:18:25.874
различных способов

01:18:48.167 --> 01:18:50.366
Рекомендации по разработке.

01:18:50.806 --> 01:18:56.364
Следует уделить большое внимание
определению состава реализуемых операций

01:18:56.804 --> 01:19:02.042
прикладной задачи по статистической
обработке результатов экзаменационной

01:19:02.162 --> 01:19:02.642
сессии.

01:19:03.690 --> 01:19:08.534
Набор операций может быть достаточно
ограничен, но должен обеспечивать

01:19:08.735 --> 01:19:13.939
поддержку основных процедур анализа
успеваемости, обычно выполняемых

01:19:14.099 --> 01:19:15.901
работниками деканата.

01:19:16.902 --> 01:19:20.505
Ориентированность на практическое
использование предъявляет

01:19:21.443 --> 01:19:27.486
Особые требования к проектированию
диалоговой формы управления таблицами.

01:19:27.807 --> 01:19:34.650
Обычное требование для интерфейса с
пользователем состоит в обеспечении

01:19:34.851 --> 01:19:36.652
наглядности, понятности.

01:19:37.141 --> 01:19:39.423
...дружественности и тому подобное.

01:19:39.984 --> 01:19:45.268
При практическом использовании программ
особое значение имеет наличие графических

01:19:45.389 --> 01:19:48.271
форм представления результатов обработки.

01:19:49.232 --> 01:19:53.396
Как и прежде, должно быть обеспечено
надёжное функционирование.

01:19:53.967 --> 01:19:55.650
разработанных программ.

01:19:56.211 --> 01:20:01.658
С этой целью может быть разработан тот или
иной генератор текстовых данных

01:20:15.785 --> 01:20:19.746
Может быть рекомендована командная форма
разработки программ.

01:20:20.186 --> 01:20:25.547
В составе команды один разработчик может
отвечать за реализацию программ для

01:20:25.708 --> 01:20:32.509
таблиц. Другой разработчик может отвечать
за разработку диалоговых форм управления

01:20:32.669 --> 01:20:33.430
таблицами.

01:20:34.309 --> 01:20:39.832
Ещё один может заниматься разработкой
графических форм, выводом результатов

01:20:40.152 --> 01:20:45.915
разработки и, наконец, отдельный
разработчик может проводить тестирование.

01:20:46.556 --> 01:20:51.998
Обязанности разработчиков могут изменяться
в ходе выполнения лабораторной работы.

01:20:52.770 --> 01:20:55.294
Возможные темы дополнительных заданий.

01:20:55.734 --> 01:21:00.460
Для развития навыков практического
программирования рекомендуется следующие

01:21:00.580 --> 01:21:03.544
направления расширения постановки задачи.

01:21:03.784 --> 01:21:07.028
Реализовать дополнительные операции над
таблицами.

01:21:07.914 --> 01:21:13.478
Реализовать методы балансировки деревьев,
поиска и выполнить вычислительные

01:21:13.678 --> 01:21:20.202
эксперименты по оценке эффективности
операций с таблицей при балансировке,

01:21:20.483 --> 01:21:22.844
сравнить работу с таблицей при наличии

01:21:23.652 --> 01:21:26.052
В отсутствии методов балансировки.

01:21:27.012 --> 01:21:33.574
Реализовать дополнительный набор операций
для обработки результатов успеваемости.

01:21:33.934 --> 01:21:38.615
Реализовать дополнительный набор
графических форм вывода результатов

01:21:38.935 --> 01:21:39.495
обработки.

01:21:40.347 --> 01:21:43.747
Реализовать расширенное представление
таблиц.

01:21:46.307 --> 01:21:52.107
Выполнить замену разработанных программ
для реализации таблиц на средства работы с

01:21:52.147 --> 01:21:54.467
таблицами библиотеки СТЛ.

01:21:54.707 --> 01:21:55.947
Оценить трудоёмкость

01:21:56.900 --> 01:21:58.858
...выполнения такой замены.

01:21:59.297 --> 01:22:03.692
Выполнить лабораторную работу на примере
другой прикладной задачи.

01:22:04.931 --> 01:22:08.207
Критерии оценивания данной лабораторной
работы.

01:22:08.527 --> 01:22:11.923
Лабораторная работа считается сданной при
выполнении...

01:22:12.422 --> 01:22:14.861
Минимального набора требований.

01:22:15.621 --> 01:22:22.617
Реализованы просматриваемая упорядоченная
хэш-таблица, таблицы

01:22:22.737 --> 01:22:24.856
на основе деревьев поиска.

01:22:25.216 --> 01:22:29.454
Эффективность поиска в лучшем, худшем и
среднем случаях соответствует

01:22:30.027 --> 01:22:31.749
Теоретическим оценкам.

01:22:32.550 --> 01:22:38.196
Для рассматриваемой прикладной задачи
реализовано четыре-пять операций для

01:22:38.437 --> 01:22:44.564
обработки результатов экзаменационной
сессии и две-три графические формы вывода.

01:22:45.793 --> 01:22:50.193
В более полном варианте выполнения
лабораторной работы реализованы два

01:22:50.472 --> 01:22:53.872
варианта разрешения коллизий в
хэш-таблице.

01:22:54.152 --> 01:22:58.752
Реализован класс таблиц на основе
сбалансированного дерева.

01:23:00.072 --> 01:23:02.392
Вопросы и задания для самоконтроля.

01:23:03.107 --> 01:23:08.073
Приведите примеры прикладных задач, при
решении которых могут быть использованы

01:23:08.193 --> 01:23:13.480
таблицы. Какие дополнительные операции
могут быть полезны при обработке

01:23:13.600 --> 01:23:16.284
результатов экзаменационной сессии?

01:23:18.277 --> 01:23:23.152
Для разных способов организации таблиц
приведите примеры задач, в которых эти

01:23:23.392 --> 01:23:26.109
способы являются наиболее эффективными.

01:23:26.828 --> 01:23:32.582
Какова трудоёмкость алгоритма сортировки
вставками, алгоритма сортировки слиянием

01:23:32.901 --> 01:23:34.779
методом быстрой сортировки?

01:23:35.901 --> 01:23:40.737
В чём различие сбалансированных и идеально
сбалансированных деревьев поиска?

01:23:41.536 --> 01:23:45.813
Почему при реализации таблиц не
используются идеально сбалансированные

01:23:45.973 --> 01:23:51.768
деревья поиска? Какие рекомендации следует
учитывать при выборе хэш-функта?

01:23:53.075 --> 01:23:56.309
Какие существуют методы разрешения
коллизий?

01:23:56.429 --> 01:23:59.024
Укажите их сильные и слабые стороны.

01:24:07.862 --> 01:24:12.141
Самостоятельная работа обучающихся
является одной из важнейших составляющих

01:24:12.221 --> 01:24:13.660
образовательного процесса.

01:24:13.820 --> 01:24:18.498
Независимо от направления подготовки и
характера работы, любой начинающий

01:24:18.538 --> 01:24:21.417
специалист должен обладать
фундаментальными знаниями,

01:24:21.537 --> 01:24:25.775
профессиональными умениями и навыками
деятельности своего профиля.

01:24:26.380 --> 01:24:30.542
опытом творческой исследовательской
деятельности по решению новых проблем.

01:24:30.942 --> 01:24:36.265
Самостоятельная работа определяется как
индивидуальная или коллективная учебная

01:24:36.465 --> 01:24:43.348
деятельность, осуществляемая обучающимися
по заданиям преподавателя и под его

01:24:43.548 --> 01:24:44.068
контролем

01:24:48.717 --> 01:24:54.002
Также просим ответить на следующие
вопросы: технические и программные

01:24:54.122 --> 01:24:59.287
средства реализации информационных
процессов, архитектура компьютера, уровни

01:24:59.447 --> 01:25:05.173
программного обеспечения, современные
операционные системы и разновидности и

01:25:05.293 --> 01:25:05.893
различия.

01:25:07.977 --> 01:25:13.094
Защита информации на ПК, классификация
программного обучения, информационные

01:25:13.214 --> 01:25:18.970
технологии, определения и задачи, работа
со сжатыми данными, архивирование,

01:25:19.090 --> 01:25:21.168
периферийные устройства.

01:25:24.646 --> 01:25:28.803
Вашему вниманию предлагается перечень
основной и дополнительной учебной

01:25:28.923 --> 01:25:29.603
литературы.

01:25:30.157 --> 01:25:33.781
необходимой для освоения дисциплины
Спасибо за внимание

