Файл: ответы.doc

Примером схемы нормального алгоритма в пятибуквенном алфавите | * abc может служить схема

Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгоритма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая верхняя. Если эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгоритма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDSсчитается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову | * | | последовательно возникают слова | b * | , ba | * | , a | * | , a | b * , aba | * , baa | * , aa | * ,aa | c, aac, ac | и c | | , после чего алгорифм завершает работу с результатом | | . Другие примеры смотрите ниже.

Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языкеРефал.

Пример

Данный алгоритм преобразует двоичные числав «единичные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:

Правила:

«|0» → "0||"

«1» → "0|"

«0» → "" (пустая строка)

Исходная строка:

«101»

Выполнение:

«0|01»

«00||1»

"00||0|"

"00|0|||"

"000|||||"

"00|||||"

"0|||||"

"|||||"

2. Парадигмы интерфейсов.

Для пользовательских интерфейсов (ПИ) программ существует три парадигмы: технологическая, метафорическая и идиоматическая. Технологическая парадигма основана на понимании механизма работы программы – сложный подход. Метафорическая основана на интуитивном понимании – проблематичный подход. Идиоматическая парадигма основана на знании о том, как решать ту или иную задачу – естественный для человека процесс.

Технологическая парадигма ПИ означает, что интерфейс выражается в понятиях его конструкции, как он был построен. Чтобы успешно им пользоваться, пользователь должен понимать, как работает программа. Технологическая парадигма понятна инженерам, которые хотят знать, как все устроено. Они предпочитают видеть все шестеренки, рычаги и клапаны, потому что это позволяет им понять, что происходит внутри машины. Им кажется неважным, что эти артефакты без необходимости засоряют интерфейс. Но большинство пользователей – не инженеры и совершенно не хотят разбираться в устройстве программ или же не имеют на это времени. Для них важнее выполнять свою работу, а не набираться опыта, что инженерам часто трудно понять.

Метафорическая парадигма

Современный графический интерфейс пользователя был изобретен в Исследовательском Центре Пало Альто фирмы Хerox (PARC) и был сразу же подхвачен промышленностью. Графический интерфейс пользователя, разработанный в PARC состоял из различных объектов: окна, кнопки, иконки, метафоры, меню. Первой успешной в коммерческом плане реализацией интерфейса PARC стал Макинтош, с его метафорами рабочего стола, мусорной корзины и папок с файлами.

Метафоры плохо "масштабируются". Метафора, хорошо работающая для простого случая в простой программе часто перестает работать, как только задача усложняется и увеличивается в размере. Метафоры мы понимаем интуитивно. Мы схватываем смысл метафорического элемента управления в интерфейсе, мысленно отождествляя его с каким-либо другим процессом или предметом, на познавание которого мы уже затратили время и силы. Эффективность этого метода огромна, потому что она использует грозное оружие человеческого ума – способность делать логические выводы. Процессор этого делать не умеет. Слабая сторона этого метода в том, что он зависит от капризного человеческого ума, который может не иметь знаний или логических способностей, необходимых для совершения отождествления. Метафоры не ответственны за то, как их понимают. Метафорическая парадигма – шаг вперед, потомучто ее интуитивное понимание происходит без всякого знания механизма работы программ.

Идиоматическая парадигма

Идиоматический метод разработки ПИ основан на том, как мы узнаем и используем идиомы, или фигуры речи, как например "рояль в кустах" или "первый блин комом". Они легко понятны, но не так, как метафоры. Мы понимаем идиомы, потому что уже знаем их. Большинство элементов управления в графическом интерфейсе пользователя – идиомы. Кнопки, выпадающие списки и полосы прокрутки – это то, что мы узнаем автоматически, а не догадываемся метафорически.

Всем хорошо знакомая мышь не является метафорой чего-либо. Люди обучаются работе с ней идиоматически. В мыши нет ничего, что указывало бы на цель ее применения. Она также не напоминает ничего из нашего опыта, так что обучение работе с ней не интуитивно. Однако научиться работать мышью очень легко. Некто наверняка потратил секунды три, чтобы в первый раз показать вам, как она работает, и вы сразу поняли. Нам не нужно знать, как устроена мышь, но, тем не менее, мы можем прекрасно ею пользоваться. Это и есть идиоматическое обучение.

Профессионалам маркетинга хорошо знаком способ взять простое действие или символ и наполнить его смыслом. Синтезированные идиомы – основа продвижения торговой марки продукта, когда компания наполняет свое название или название продукта новым смыслом. Конечно, идиомы могут быть и визуальными. Золотые арки МакДональдс, три алмаза Мицубиси и даже летящее окно Майкрософт – не метафорические идиомы, которые наполнены внутренним смыслом и опознаются сразу же.

Ирония в том, что большинство знакомых нам элементов GUI, которые считаются метафорическими, на самом деле являются идиоматическими. Такие артефакты, как кнопки закрытия окна, бесконечно вложенные папки с файлами, щелчки мышью и перетаскивание пиктограмм – не метафорические операции, потому что их нет в реальном мире. Их сила лишь в простой идиоматической узнаваемости.

3. На языке С++ вычислить сумму ряда целых чисел от 1 до n.

#pragma hdrstop

//---------------------------------------------------------------------------

#include <iostream.h>

void main()

{

int N,S=0,i;

cout<<"\n Vvedite N ==";

cin>>N;

for(i=1;i<=N;i++) S=S+i;

cout<<"\n Summa =="<<S;

}

Билет 5.

1. Понятие процесса. Состояние процессов. Алгоритмы планирования процессов.

Важнейшей частью операционной системы, непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами. Процесс (или по-другому, задача) - абстракция, описывающая выполняющуюся программу. Для операционной системы процесс представляет собой единицу работы, заявку на потребление системных ресурсов. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает взаимодействие между процессами.

Алгоритмы планирования процессов

Планирование процессов включает в себя решение следующих задач:

А) определение момента времени для смены выполняемого процесса;

Б)выбор процесса на выполнение из очереди готовых процессов;

В)переключение контекстов "старого" и "нового" процессов.

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

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

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

А)процесс завершился и покинул систему,

Б)произошла ошибка,

В)процесс перешел в состояние ОЖИДАНИЕ,

Г)исчерпан квант процессорного времени, отведенный данному процессу.

Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.

Другая группа алгоритмов использует понятие "приоритет" процесса. Приоритет - это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии.

Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими.

Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты.

В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности.

Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов.

2. Общие сведения об ассиметричных криптоалгоритмах. Понятие электронной цифровой подписи.

Асимметричная криптография изначально задумана как средство передачи сообщений от одного объекта к другому (а не для конфиденциального хранения информации, которое обеспечивают только симметричные алгоритмы). Поэтому дальнейшее объяснение мы будем вести в терминах "отправитель" – лицо, шифруюшее, а затем отпраляющее информацию по незащищенному каналу и "получатель" – лицо, принимающее и восстанавливающее информацию в ее исходном виде. Основная идея асимметричных криптоалгоритмов состоит в том, что для шифрования сообщения используется один ключ, а при дешифровании – другой.

Кроме того, процедура шифрования выбрана так, что она необратима даже по известному ключу шифрования – это второе необходимое условие асимметричной криптографии. То есть, зная ключ шифрования и зашифрованный текст, невозможно восстановить исходное сообщение – прочесть его можно только с помощью второго ключа – ключа дешифрования. А раз так, то ключ шифрования для отправки писем какому-либо лицу можно вообще не скрывать – зная его все равно невозможно прочесть зашифрованное сообщение. Поэтому, ключ шифрования называют в асимметричных системах "открытым ключом", а вот ключ дешифрования получателю сообщений необходимо держать в секрете – он называется "закрытым ключом". Напрашивается вопрос : "Почему, зная открытый ключ, нельзя вычислить закрытый ключ ?" – это третье необходимое условие асимметричной криптографии – алгоритмы шифрования и дешифрования создаются так, чтобы зная открытый ключ, невозможно вычислить закрытый ключ.

В целом система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей : "открытый" Ej и "закрытый" Dj, где j – номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. Если абонент, скажем под номером 7, собирается передать информацию абоненту под номером 9, он шифрует данные ключом шифрования E9 и отправляет ее абоненту 9. Несмотря на то, что все пользователи сети знают ключ E9 и, возможно, имеют доступ к каналу, по которому идет зашифрованное послание, они не могут прочесть исходный текст, так как процедура шифрования необратима по открытому ключу. И только абонент №9, получив послание, производит над ним преобразование с помощью известного только ему ключа D9 и восстанавливает текст послания. Заметьте, что если сообщение нужно отправить в противоположном направлении (от абонента 9 к абоненту 7), то нужно будет использовать уже другую пару ключей (для шифрования ключ E7, а для дешифрования – ключ D7).