Процессы управления и устойчивость

Зубов П.А., Меньшиков Г.Г.

Санкт-Петербургский государственный университет

Новые варианты

интервальной программной системы

В учебном пособии [1] описана интервальная программная си-

стема "Знак", предназначенная для выяснения знака функций, вы-

раженных композициями стандартных функций. Программа была

рассчитана на использование в микрокомпьютерах типа "Электро-

ника" МК 85 [2] и SHARP PC-1500 [3]. Для работы на IBM PC тре-

бовалась известная доработка. В результате неё возникло несколько

вариантов программной системы, представленных в данной работе.

В качестве базового языка избран QBasic, хотя для создания ба-

зовой интервальной программной системы (БИПС) годится любой

другой язык програмирования, удовлетворяющий гипотезам о ма-

шинной арифметике из [4].

Надпись БИПС означает текст БИПС из [4].

Сохранены блок-схемы программ из [1]. Полный текст програм-

мы, оформленный как файл znak1.bas, приводится ниже.

Приняты следующие аббревиатуры: SL, PR, G, RET для SLEEP,

PRINT, GOSUB и RETURN.

Операторы SLEEP и большая часть PRINT нужны для индика-

ции сведений о трассировке: номеров бэйсик-строк. Останов говорит

о необходимости нажать на Enter, в результате чего на экран вы-

водится сообщение о характере достигнутого нуля функции f и о

числе понадобившихся для этого шагов.

Подпрограмма ППf, составленная согласно правилам, изложен-

ным в [4], занимает бэйсик-строки, начиная с 400. Ниже дан её ва-

риант для f (x) = x +

1

1+x

2

.

Как это принято для языка QBasic, программная система запус-

кается записью в командной строке qbasic znak1.bas и последую-

щего нажатия клавиш Enter и F5 .

Если убрать из текста программной системы все операторы SL

1, то процесс резко ускорится, но труднее будет отслеживать трас-

сировку. Наоборот, замена их операторами SL 5 облегчит это отсле-

живание.

341

Полный текст системы.

1 G 2: GOTO 1000

БИПС

REM Главная программа ЗНАК

200 PR "Машинный расчёт знака":

PR "Ввести ОМР Х . "; : A = 2: G 51: R = 0

REM 200 - блок А2. Вызов 200 - блок А1.

210 PR "Предварительный расчёт":

G 60: A = 3: G 40: G 340

REM Блок В1.

212 PR "F(X): "; : A = 0: G 50

REM Блок В2

215 IF D $<>$ 0 THEN PR "SGN="; D: GOTO 395

REM Блоки В3, В4 и В5

217 PR "Уточняющий расчёт"

220 SL 1: PR 220: E = K(2): L(3) = E: F = L(2) - K(2): I = 0: GOTO

240

REM Блок С3.

230 SL 1: PR 230: IF L(3) $>=$ L(2) THEN K(3) = L(2): G 380: GOTO

395

REM Блок C10.

235 SL 1: PR 235: F = 2 $*$ F: K(3) = L(3): REM Блок С11

SL 1: PR 235.1: G 330: REM Блок С12.

SL 1: PR 235.2: IF D $<>$ 0 THEN 230: REM Блок С13.

240 SL 1: PR 240: F = F / 2: J = C $*$ ABS(K(3)) + D1: IF F $<$ J

THEN F = J

REM Блок С14.

250 G 330: REM Блок С15.

SL 1: PR 250: IF D $<>$ 0 THEN I = D: GOTO 230

REM Блоки С16, С18.

260 SL 1: PR 260: IF F $<>$ J THEN 240

REM Блок С17.

270 SL 1: PR 270: IF I = 0 THEN 295

REM Блок С191.

280 SL 1: PR 280: G 390

REM Блок С192.

290 SL 1: PR 290: IF L(3) = L(2) THEN 315

REM Блоки С193, С194.

295 SL 1: PR 295: I = 0

REM Блок С21.

300 SL 1: PR 300: K(3) = L(3): F = C $*$ ABS(K(3)) + D1

REM Блок С22

SL 1: PR 300.1: G 330

REM Блок С23

SL 1: PR 300.2: IF L(3) = L(2) THEN K(3) = L(2): G 380: GOTO 315

REM Блок С26.

305 SL 1: PR 305: IF D = 0 THEN 300

REM Блок С24

310 SL 1: PR 310: G 390

342

REM Блок С25.

SL 1: PR 310.1: IF L(3) $<$ L(2) THEN 230

REM Блок С27

315 SL 1: PR 315: GOTO 395

REM Блок С28.

330 SL 1: PR 330: PR "(F)="; F: L(3) = K(3) + F: IF L(3) $>$ L(2)

THEN L(3) = L(2)

REM 330...400 - ПП для различных блоков главной программы системы

ЗНАК.

340 SL 1: PR 340: G 400: R = R + 1: PR R:

IF SGN(K(0)) $*$ SGN(L(0)) <= 0 THEN D = 0: RET

345 SL 1: PR 345: D = SGN(SGN(K(0)) + SGN(L(0))): RET

380 SL 1: PR 380: PR "Шаг = "; R, "SGN = "; I; "

x= "; K(3): SL:

RET

390 SL 1: PR 390: G 380: E = K(3): I = D: RET

395 INPUT "Конец расчёта. Нажмите Enter.", Y: END}

REM 400...430 - тест-программа f:

400 A = 3: G 22

410 A = 1: G 80

420 A = 0: G 23

430 A = 3: G 10

440 RETURN

Литература

1. Меньшиков Г.Г. Интервальный анализ и методы вычислений:

Конспект лекций. Выпуск 5. Исследование функций одной пере-

менной. Дифференцирование функций. СПб.: ООП НИИ Химии

СПбГУ, 1998. 72 с.

2. Микрокомпьютер "Электроника МК 85", "Электроника МК 85":

руководство по эксплуатации. М.: Завод "Ангстрем", 1992. 72 с.

3. SHARP Pocket Computer PC-1500. Instruction Manual. SHARP

Electronics Corporation. Osaka, Japan. 164 p.

4. Меньшиков Г.Г. Локализующие вычисления: Конспект лекций.

Выпуск 1. Введение в интервально-локализующую организацию

вычислений. СПб.: ООП НИИ Химии СПбГУ, 2003. 90 с.

343

Иванов А.А., Хохлов Н.В.

Санкт-Петербургский государственный университет

AJAX: история появления, преимущества и

примеры использования

Рекомендовано к публикации старшим преподавателем

Ивановой О.А.

Новое направление разработки интерактивных веб-приложений

– AJAX появился совсем недавно. Первые примеры использования

AJAX – проекты www.map.google.com и www.gmail.com – появились

в 2004 году. Первое упоминание о данном направлении появилось в

интернете в статье Джесса Гарретта 18 февраля 2005 г., основате-

ля известной консалтинговой фирмы Adaptive Path. Джесс Гарретт

условно именует "AJAX" как "асинхронный JavaScript плюс XML"

или точнее, "асинхронный JavaScript+CSS+DOM+XMLHttpRequ-

est". В отличие от множества "перспективных" подходов AJAX

очень нагляден. Сайт, сделанный с помощью AJAX, работает гораз-

до быстрее обычного сайта. По крайней мере, он быстрее "откли-

кается" на любые действия пользователя. Запросы пользователей

обрабатываются очень быстро, потому что использование идеологии

AJAX позволяет не перезагружать страничку целиком, а обновлять

на ней только те элементы, которые требуют обновления.

AJAX расшифровывается как Asynchronous JavaScript +

XML (асинхронный JavaScript+XML) и технологией в строгом

смысле слова не является. Это просто аббревиатура, обозначающая

подход к созданию веб-приложений с помощью следующих техноло-

гий.

• JavaScript – универсальный язык сценариев. Интерпретатор

JavaScript в web-браузере позволяет взаимодействие со многи-

ми из встроенных возможностей браузера. Приложения AJAX

написаны на JavaScript.

• CSS определяет визуальные стили многократного использова-

ния для элементов web-страницы. В приложении AJAX, интер-

фейс пользователя может измениться в интерактивном режиме

через CSS.

• DOM представляет структуру web-страниц как набор про-

граммируемых объектов, которые могут управляться при по-

344

мощи JavaScript. Создание сценария DOM позволяет приложе-

нию AJAX изменять интерфейс пользователя "на лету", эф-

фективно изменяя части страницы.

• Объект XMLHttpRequest. Этот объект впервые реализован

Microsoft как объект ActiveX, но также доступен как част-

ный объект и в пределах других браузеров, дает возможность

JavaScript делать HTTP-запросы на отдаленный сервер без по-

требности перезагрузки страницы.

Рис. 1. Четыре основные компоненты AJAX.

Если в стандартном веб-приложении обработкой всей информа-

ции занимается сервер, тогда как браузер отвечает только за взаимо-

действие с пользователем, передачу запросов и вывод поступившего

HTML, то в AJAX-приложении между пользователем и сервером по-

является еще один посредник – движок AJAX. Он определяет, какие

запросы можно обработать "на месте", а за какими необходимо обра-

щаться на сервер. Поведение сервера тоже изменилось. Если раньше

на каждый запрос сервер выдавал новую страницу, то теперь он от-

сылает лишь те данные, которые нужны клиенту, а HTML из них

прямо в браузере формирует движок AJAX. Асинхронность прояв-

ляется в том, что далеко не каждый запрос пользователя доходит до

сервера, причем обратное тоже справедливо – далеко не каждая ре-

акция сервера обусловлена запросом пользователя. Большую часть

запросов формирует движок AJAX, причем его можно написать так,

345

что он будет загружать информацию практически мгновенно, преду-

гадывая действия пользователя. С такой схемой работы качествен-

ная нагрузка на сервер меняется – если раньше запросов было мало,

но каждый из них требовал значительных ресурсов (серверу нужно

вытащить информацию из базы данных, сформировать из нее веб-

страницу и отдать браузеру), то теперь задача сервера упрощается

(формировать web-страницы не нужно, да и объем передаваемых

данных меньше), но запросов обрабатывать приходится больше.

Рис. 2. Классическая модель веб-приложения (слева), веб-приложение,

использующее идеологию AJAX (справа)

Рассмотрим объект XMLHttpRequest – основной компонент AJAX

[1]. Именно он отвечает за обмен данными с сервером, позволяя

полностью заменить стандартную для web-приложений модель за-

просов. Его основная цель – прием и передача XML-документов

в асинхронном режиме поверх HTTP-протокола. На сегодняшний

день данный объект является частью стандартного инструментария

web-разработчика и поддерживается всеми распространенными бра-

узерами на всех платформах. Впрочем, небольшая разница меж-

ду его реализациями в различных современных браузерах все же

присутствует. В браузере Internet Explorer данный объект реализо-

ван в виде внешнего ActiveX-компонента, в браузерах же семейства

Mozilla и браузере Opera это объект является встроенным JavaScript-

компонентом.

Устроен данный объект следующим образом:

346

Таблица. UML схема объекта XMLHttpRequest

XMLHttpRequest

-readyState

-onReadyStateChange

+open()

+send()

Типичный цикл работы с ним выглядит так.

• Программист создает экземпляр объекта XMLHttpRequest, от-

крывает соединение с сервером и задает функцию, которую

данный объект должен вызвать в случае успешного прохожде-

ния запроса.

• При помощи метода XMLHttpRequest.send() на сервер отправ-

ляется необходимый запрос. При этом данный метод заверша-

ется до окончания всех действий, необходимых для успешной

отправки запроса и обработки ответа от сервера, что дает про-

грамме возможность выполнить некоторые действия пока идет

запрос, не ожидая его завершения.

• После того как запрос успешно обработан и принят ответ, объ-

ект XMLHttpRequest вызывает определенную пользователем

функцию, которая и должна этот ответ обработать.

Классические и, пожалуй, лучшие примеры использования AJAX

– проекты Google Maps – www.map.google.com – спутниковая карта

мира и www.gmail.com – почтовый сервер; а также поисковый сервер

Google Suggest – http://www.google.com/webhp?complete=1&hl=en,

показывающий наиболее популярные запросы и их количество.

AJAX также может быть успешно применен при дистанционном обу-

чении, в частности, при создании электронных учебников, словарей

и энциклопедий. Авторами данной статьи AJAX был успешно при-

менен для создания энциклопедии.

Литература

1. Crane D., Pascarello E. Ajax in Action. Special Sales Department

Manning Publications Co. 209 Bruce Park Avenue Greenwich, CT

06830. 2005.

347

Карабельников И.А.

Санкт-Петербургское высшее военное училище радиоэлектроники

Модель защиты компакт-дисков

от нелицензионного копирования

Рекомендовано к публикации доцентом Кривцовым А.Н.

В настоящее время наиболее часто употребляемым методом за-

щиты программных продуктов при их распространении является

применение специальных паролей (серийных номеров), без знания

которых невозможна установка программного продукта. Существен-

ным недостатком данного метода является высокая вероятность

утечки серийного номера, как умышленной, так и неумышленной.

Более действенным методом защиты является применение специ-

альных носителей информации, хранящих ключ, необходимый для

функционирования программы [1]. Для хранения ключевой информа-

ции могут применяться следующие носители:

– электронные ключи;

– оптические носители (компакт-диски, DVD и т.п.);

– магнитные носители (дискеты, ZIP и т.п.).

Электронные ключи обычно содержат перезаписываемую энерго-

независимую память и генерируют защитную функцию. Встроенная

в программу система защиты получает через ключ информацию, ко-

торая используется для аутентификации пользователя и определе-

ния набора доступных функций. Основным недостатком электрон-

ных ключей является необходимость использования для их изготов-

ления специального оборудования и, как следствие, высокая стои-

мость. Поэтому их применение оправдано при защите весьма дорого-

стоящих программных продуктов. В частности, электронные ключи

применяются для защиты системы «1С: Предприятие».

При разработке модели защиты программного обеспечения от

нелицензионного копирования стояла задача минимизации наклад-

ных расходов с сохранением высокой стойкости системы защиты.

В качестве информационного носителя был выбран компакт-диск,

так как при невысокой стоимости он позволяет хранить значитель-

ный объем данных, а стоимость приводов, позволяющих записывать

компакт-диски за последние несколько лет значительно снизилась.

348

Способы защиты магнитных и оптических носителей во многом

схожи, поэтому магнитные носители в данной работе не рассматрива-

ются. Для защиты компакт-дисков от копирования могут приме-

няться следующие методы [2]:

– методы защиты, использующие нестандартные форматы диска;

– методы, основанные на привязке к носителю;

– методы защиты от пофайлового копирования диска.

Методы защиты, использующие нестандартные форматы дис-

ка, основаны на том факте, что программы копирования компакт-

дисков не создают точной копии диска, не копируя некоторые слу-

жебные области диска. В эти служебные области возможно внедре-

ние ключевых меток, позволяющих идентифицировать защищенный

диск.

Методы, основанные на привязке к носителю, используют тот

факт, что двух абсолютно идентичных лазерных дисков не суще-

ствует, каждый из них обладает рядом уникальных характеристик,

отличающих его от других. Сюда относятся, например, методы,

привязывающиеся к физическим дефектам носителя, временным ха-

рактеристикам чтения групп секторов, показателям стабильности

чтения и т.д.

В настоящее время особую важность приобрела не только защи-

та кода программного продукта, но и конфиденциальность содержа-

щихся в нем данных (информационного наполнения). Для защиты

от несанкционированного доступа к данным используются методы

защиты дисков от пофайлового копирования. Для достижения вы-

сокой устойчивости защитного механизма эти методы необходимо

применять в комплексе с методами защиты дисков от посекторного

копирования, рассмотренными выше.

Для защиты от пофайлового копирования предлагается примене-

ние криптографических систем защиты информации. При использо-

вании криптографических систем производится специальное шифро-

вание, кодирование или иное преобразование данных, в результате

которого их содержимое становится недоступным для использования

без предъявления некоторого специального ключа и обратного пре-

образования.

Криптографические системы защиты информации подразделя-

ются на одноключевые (симметричные), двухключевые (несиммет-

ричные) и составные.

В одноключевых криптографических системах процесс шифрова-

349

ния и расшифрования можно представить следующим образом [1]:

Y = Ez

c

(X, Z

c

),

X = Dz

c

(Y, Z

c

) = Dz

c

(Ez

c

(X, Z

c

)),

где X – открытый текст, Y – зашифрованный текст, Z

c

– секретный

ключ, Ez

c

— функция шифрования, Dz

c

– функция расшифрования.

Двухключевые криптографические системы характеризуются ис-

пользованием двух ключей: открытого (несекретного) и закрытого

(секретного). Процесс шифрования и расшифрования в этих систе-

мах может быть представлен следующими выражениями [1]:

Y = Ez

o

(X, Z

o

),

X = Dz

c

(Y, Z

c

) = Dz

c

(Ez

o

(X, Z

o

)),

где X – открытый текст, Y – зашифрованный текст, Z

o

– открытый

ключ, Z

c

– секретный ключ, Ez

o

— функция шифрования, Dz

c

–

функция расшифрования.

Анализ существующих криптографических систем показал, что

наиболее подходящими для защиты информации при распростране-

нии на оптических носителях являются одноключевые криптографи-

ческие системы, использующие поточное (потоковое) шифрование.

Основными преимуществами этих систем являются:

– высокая криптостойкость, обусловленная тем, что размер клю-

ча равен размеру шифруемой последовательности;

– высокая скорость шифрования и расшифрования;

– ограниченное распространение ошибок;

– простота программной реализации.

Процесс шифрования и расшифрования в системах поточного

шифрования можно представить в виде следующей схемы (рис. 1):

Рис. 1. Система поточного шифрования

В качестве ключевой последовательности в системах поточного

шифрования обычно используют псевдослучайные последовательно-

сти, формируемые генераторами псевдослучайных последовательно-

350

стей. При этом ключом обычно является начальная установка гене-

ратора.

Необходимо отметить, что системы поточного шифрования по

способу синхронизации подразделяются на синхронные и само-

синхронизирующиеся. В синхронных поточных шифрах ключевая

последовательность формируется независимо от последовательности

символов открытого текста и каждый символ шифруется независи-

мо от других. Преимуществом синхронных шифров является отсут-

ствие эффекта размножения ошибок. В самосинхронизирующихся

поточных шифрах символы открытого текста шифруются с учетом

ограниченного числа предшествующих символов, которые прини-

мают участие в формировании ключевой последовательности. При

этом секретным ключом является функция обратной связи генерато-

ра псевдослучайных чисел. Преимущество самосинхронизирующих-

ся шифров заключается в автоматическом восстановлении режима

синхронизации в случае вставки или выпадения двоичного символа.

Для защиты диска от посекторного копирования в разработан-

ной модели защиты используется нестандартный формат диска, а

для защиты от пофайлового копирования – поточное шифрование.

Получаемый компакт-диск содержит:

– дистрибутив программы;

– данные, зашифрованные с использованием поточного шифро-

вания;

– некопируемую ключевую метку.

Таким образом, в данной работе предложена модель защиты про-

граммного обеспечения, позволяющая создавать защищенные от ко-

пирования компакт-диски с минимальными затратами при помо-

щи широко распространенных в настоящее время пишущих CD-

приводов.

Литература

1. Соколов А.В., Степанюк О.М. Методы информационной защиты

объектов и компьютерных сетей. М.: ООО «Фирма «Издательство

АСТ»; СПб.: ООО «Издательство «Полигон», 2000. 272 с.

2. Касперски К. Техника защиты компакт-дисков от копирования.

СПб.: БХВ-Петербург, 2004. 464 с.

351

Караковский С. А.

Санкт-Петербургский государственный университет

Автоматическая классификация текстовых

документов в задаче кластеризации

Рекомендовано к публикации доцентом Добрыниным В.Ю.

Введение. В человеческом мире всегда существовал вопрос по-

иска наработанной и сохраненной информации по возникшей зада-

че. Любое исследование начинается с изучения сделанных достиже-

ний. Современная постановка задачи с интенсивным увеличением

количества сохраняемой и доступной большому количеству людей

информации ещё включает очень актуальный вопрос об эффектив-

ности и скорости работы поисковой системы. Одним из подходов к

решению данного вопроса является разделение информации по неко-

торым признакам. Например, отбрасывать тексты о разведении ба-

бочек при поиске информации по теме объектно-ориентированного

программирования и наоборот.

Кластеризация данных [1] – это общая техника для статистиче-

ской обработки информации, которая используется во многих сфе-

рах компьютерной науки: машинное самообучение, извлечение дан-

ных, распознавание образов, анализ изображений, биоинформатика.

Под кластеризацией документов будем понимать разбиение множе-

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: