. Информация. Виды и свойства информации.



Работа добавлена на сайт TXTRef.ru: 2019-12-03

1. Информация. Виды и свойства информации. Информационные процессы и технологии. Общие принципы кодирования информации и формы ее представления в ЭВМ.

Пон-ие инф-ии явля-ся фунд. пон-ем в любой науке вообще и базовым в И. Формаль-го опр-ия не имеет. Каждая наука рассм. это понятие со своей стороны. В филос-ии под инф-ей понимают отражение реального мира. Инф. м/о классиф-ть по: форме, структуре, способу передачи и восприятия (обмену), области возникновения. С пон-ем инф-ии связаны след-ие пон-ия: 1) Сигнал - представл-ий собой любой физ. процесс, несущий инф-ию. 2) Сообщение - инф-ия, представл-ая в опред-ой форме и предназ-ая для передачи. 3) Данные - инф-ия, представл. в формализованном виде и подготовленная для обраб-ки технич-и устр-ми.

Инф-ия может перед-ся сигналами 2-ух типов: непрер-ый (парам-ры сигнала м. принимать любые зн-ия из данного диапазона); дискретный (пар-ры сигнала приним-ют конечное число знач-ий из данного диапазона).

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

Ед. измер. инф-ии. Сущ. 2 подхода: вер-ый и объемный. 1) Кол-вом инф-ии наз-ют числ. хар-ку сигнала, отраж-ую ту степень неопр-сти, кот. исчезает после пол-ия сигнала. Под единицей инф-ии понимают такое ее кол-во, кот. уменьшает неопредел-сть в 2 раза. Ед-ца изм. инф. - бит.

N - кол-во событий, i - кол-во инф-ии N=2i ; I=log2N.Если кол-во равновер-ых соб-ий = N, то кол-во инф-ии i, полученное при выпадении этого соб-ия, м/б выч-но по фор-ле Хартли i=log2N. За ед-цу инф-ии в сист. СИ принимают 1 байт=8 бит. 2) Объем инф-ии в памяти ЭВМ или на носителе равен кол-ву бит.

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

ИТ - процессы, испол-ие сов-сть ср-в и м-дов для обеспечения ИП: сбора, обраб-ки и передачи данных (первичной инф-ии), для пол-ия инф-ии нового кач-ва о сост-ии объекта, процесса или явл-ия (инф. продукта). Цель ИТ - произ-во инф-ии для ее анализа чел-ком и принятия на его основе реш-ия по вып-ию к-л действия. Внедрение ПК в инф-ую сферу и прим-ие телекоммуникаций опред-ли новый этап раз. инф. технологий. НИТ - ИТ с «дружественным» интерфейсом р-та пользователя, исп-ая ПК и телекомм-ые ср-ва.

Общие принципы код-я информации и формы ее представления в ЭВМ

Пр-п Фон-Неймана. В основу построения больш-ва комп-ров положены следующие общие принципы сформ-ные в 1945году Фон-Нейманом: п-п программного управ-я. Из него =>, что прогр-ма состоит из набора команд, кот-е выпол-ся процессором авто-ки друг за другом в опред-ой послед-сти. Выборка программ из памяти осущ-ется с помощью счетчика команд. П-п однородности памяти. Прог-мы и данные хранятся в одной и той же памяти комп-р не различает что хранится в данной ячейке: прог-ма, число, текст или команда. Над ком-ми м. выполнять такие же действия, как и над данными. П-п адресности. Структурно осн. память состоит из перенумерованных ячеек. Проц-ру в произвольный момент t доступна любая ячейка, следовательно сущ-ет возмо-ть давать имена областям памяти так, чтобы к заполненным в них знач-ям м. было в последствии обращаться или менять их в процессе выполнения прог-мм с испол-ем присвоенных имен. Запись инф-ции. ОЗУ ЭВМ состоит из физических устройств элементов памяти - битов, способных устойчиво нах-ся в одном из состояний условно обознач-х 0 и 1. Каж. элемент хранит один бит инф-ции. Исторически сложилось 8 бит = 1 байту, ко-й в соврем. Вычис-х сис-х явл-ся мин-ой адрес-ой областью памяти. Байты м. объед-ся в машинные слова. Маш. слово имеет адрес младшего байта. Рассмотрим принципы код-я инф-и в 2-х байтовых словах. Кодирование целых чисел.

+ые числа. В стар-й бит запис-ся 0, в остальные разряды запис-тся 2-ое предст-ие числа, начиная с младшего бита. Своб-ые левые разряды запол-ся 0.

–ые числа. Код-е + чисел наз-ся код-ем в прямом коде. - числа принято код-ть в допол-ном коде. Его м. получить по след-му алгоритму: двоичное предст-ние модуля числа инвертируют, т.е. 10, а 01. К получен-му прибавляем 1.признаком отр. числа является 1 в старшем бите. Восстановить число м. по тому же алгоритму. Все выше изложенное применимо к целым со знаком, для целых без знака не происходит резервирование бита под знак. Код-ие символов. В совр. Выч-ых сис-х каждому сим ставят в соотв-ии нек. число назыв-ое кодом символов. Код-ые символы состоят из групп: управляющие, цифры, латинские буквы и специальные символы. Су-ет несколько стандартов код-ия. Большинство современных ВС используют стандарт ASCII в кот-ом каж. символ кодируется в один байт. Т.е. можно закодирова-ть 256 сим-в кодами от 0 до 255. Сим-ы с кодами от 0 до 127 явл-ся стандар-ми, а с кодами от 127 до 255 явл-ся переменной частью кодовой таблицы и м. включать символы нац. алфавита, псевдографики. Истор-ки для больших ЭВМ первым был разработан стандарт EBC DIC занимал 12 бит. В наст. вр разработана сис-ма код-я в 2 байта – UNICOD. Может закод-ть 216-1 символ. Код-ние команд. Коды к-д записывают в два поля, одно из кот-ых (обычно 1 байт) код-т код операции, второе наз-тся адресным. В зав-сти от ВС ком-ы бывают: без-,одно-,двух-, трех-, четырехадресные. В адресной части могут хранится: ад-са двух операндов, ад-с следующей ком-ы, адрес результата. Для экономии памяти часто исп-ют 2-х адр-ые ком-ы, кот-ые хранят лишь ад-са операндов, а рез-ат запис-ся по адресу одного из операндов. Код-ние графической информации. Код-ие растр-х изобр-ний. Растр изоб-е предст-ет собой совокуп-ь точек (пикселей) разн. цветов(BMP, GIF и JPEG). В формате BMP задается цветность всех пикселов изоб-я. Этот формат требует много памяти. В формате GIF исп-ся спец. методы сжатия кода, причем поддер-ся только 256 цветов. Формат JPEG исп-ет методы сжатия, приводящие к потерям нек-х деталей.Кодирование векторных изображений. Вект. Изоб-е пред-ет собой совокуп-ть граф-х примитивов (точка, отрезок, эллипс…). Каж примитив описывается мат. формулами. В век графике, в отличие от раст графики, базовым объектом явл-ся линия. фрактальная графика, в ко-й формир-ие изо-ий целиком основано на мат формулах, уравн-х, описывающих те или иные фигуры, поверх-и, тела. Двоичное код-ие звука. Подход к записи звука наз-ся преобр-ем в цифровую форму, оцифровыванием или дискретизацией, так как непрер-й звуковой сигнал замен-ся дискретным набором знач-й сиг-ла в нек-ые моменты вр-ни. Кол-во отсчетов сигнала в единицу t наз-ся частотой диск-ации. В нас время при записи звука в мульт-х технях прим-ся частоты 8, 11, 22 и 44 кГц.

Кодирование и декодирование.

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

Понятие о теоремах Шеннона. Теоремы Шеннона затрагивают проблему эффективного кодирования. Первая теорема декларирует возможность создания системы эффективного кодирования дискретных сообщений, у которой среднее число двоичных символов на один символ сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех). Вторая теорема Шеннона гласит, что при наличии помех в канале всегда можно найти такую систему кодирования, при которой сообщения будут переданы с заданной достоверностью.Международные системы байтового код-ния. Наиболее распрост-ны две такие системы: EBCDIC (Extended Binary Coded Decimal Interchange Code) и ASCII (American Standard Information Interchange).

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

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

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

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

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

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

Моделирование случайных величин с равномерным распределением.

1) Метод середины квадратов(Нейман). Идея метода: Пусть задано 4-значное число Х1= 9568. Возведем его в квадрат: X1^2= 91546624. Возьмем 4 средних цифры этого числа и обозначим через X2=5466. Далее х2^2=29877156, х3=8771; х3^2=76930441, Х4=9304 и т.д. В качестве исходного псевдослучайного числа фон Нейман предлагал использовать значения: 0,9568; 0,5466; 0,8771; 0,9304; ...

2) Метод вычетов, или линейный конгруэнтный метод. Схема, предложена Д. X. Лемером в 1948 году. Выбираем четыре целых положительных числа: Х0 - начальное значение последовательности, а - множитель, с - приращение, m - модуль. Тогда искомая последовательность случайных чисел Х[i] получается из соотношения Х[n+1] = (а*Х[n] + с) mod m, n>0 (3) и называется линейной конгруэнтной последовательностью.

Но, при Х0 = а = с = 7, m = 10 последовательность выглядит так: 7,6,9,0,7,6,9,0,.... Случай а=1 можно так же отбросить, так как при этом Х[n] = (Х0 + nc) mod m и очевидно, что последовательность тоже неслучайная. Все подобные последовательности всегда "зацикливаются". Это свойство присуще всем последовательностям, имеющим вид Х[n+1]=F(Х[n]). Это следует из того, что в коде ЭВМ можно записать лишь конечное число различных чисел. Следовательно, рано или поздно одно из чисел, например, Х[L], совпадет с одним из предыдущих чисел, например, с X[F], тогда из формулы вытекает, что Х[L+i] = Х[F+i] i=1..n. то есть в последовательности имеется период длины Р=L-F. Длина периода не может быть больше m.

m принимается равным размеру слова (то есть на 1 больше максимального целого числа, размещающегося в слове вычислительной машины = степень 2).

Множитель а следует выбирать так, чтобы получать период максимальной длины. Для любой последовательности, предназначенной в качестве источника случайных чисел, важен большой период. а и m были взаимно простыми, иначе, если НОД(a,m)=d мы можем получить не больше, чем m/d значений величины Хk, то есть период последовательности уменьшается в d раз.

Последовательность Yn = (Xn+1)/(m+1), (n=0,1,..,). При удачном выборе а, с, m, Хо последовательность Yn будет хорошо имитировать последовательность равномерно распределенных в интервале (0,1) случайных чисел.

3) Квадратичный конгруэнтный метод. Линейный конгруэнтный метод можно обобщить, превратив его в квадратичный конгруэнтный метод:  Х[n+1] = (d*Х[n]^2 + а*Х[n] + с)) mod m

4) Для случая, когда m представляется степенью двойки, интересный квадратичный метод предложил Р. Ковэю:

Х0 mod 4 = 2, Х[n+1] = Х[n]*(Х[n]+1) mod 2^c, n>=0.

5) Другие обобщения линейно-конгруэнтного метода: Вводится зависимость Х[n+1] от Х[n] и Х[n-1] вместо простой зависимости только от Х[n]. Тогда длину периода мы можем увеличить до m^2, так как последовательность начнет повторяться не раньше, чем будет выполнено равенство (Х[n+l],Х[n+l+1]) = (Х[n], Х[n+1]).

Простейший случай зависимости Х[n+1] от более чем одного из предыдущих значений реализуется в последовательности Фибоначчи: Х[n+1] =(Х[n]+Х[n-1])mod m.

6) Аддитивный датчик случайных чисел. Можно так же рассмотреть датчики вида Х[п+1]=(Х[n]+Х[n-k]) mod m.

7) Метод А. Энгеля (1979). Пусть имеем число Х0 из (0,1), тогда следующее случайное число получается по закону Х[n+1] = {(Х[n]+а)^8}. Эффективность метода зависит от выбора а; а должно быть отличным от 1 и не быть близким к 1, а<>sgrt8(2); хорошие результаты получаются при а = Pi.

8) Метод Н.М. Коробова (1963). Пусть Х0=1, Х[n+1]=(k*Х[n])mоd р, где р - простое число вида р=2*р1+1, где р1 - также простое число. По выбранному числу р подбирают число k, близкое к числу р/2 и имеющее вид k=р-З^m. где m - натуральное число. Все члены последовательности Хn - целые числа из промежутка [1, р-1]. С их помощью можно построить последовательность чисел, принадлежащих любому промежутку [а,b]. Предлагаются следующие значения р и b: (2027,1298), (5087,2900), (10079,3518), (20183, 3622), (40127, 20444), (50147, 30464), (100103, 41054), (220919, 161870).

9) Случайные числа получают по формуле: Х[n+2] = (7*Х[n+1] + 3*Х[n] + 123) mod 10^4. Датчик работает с четырехзначными числами. Эффективность метода зависит от начальных значений, хорошие результаты получаются при X1:=1234, Х2=4321.

10) Комбинации датчиков случайных чисел для получения "еще более случайных" последовательностей.

Zn = (Хn+ Уn) mod m. Желательно, чтобы длины периодов последовательностей Хn, и Уn были взаимно простыми числами.

11) Метод М.Д. Макларена и Дж. Марсальи. Удобен для программирования. При заданных методах выработки двух последовательностей Хn и Yn этот метод позволяет генерировать члены "значительно более случайной" последовательности.

Алгоритм. Используется вспомогательная таблица V[0], V[1],..., V[k-1], где k - некоторое число, выбираемое обычно для удобства, равным примерно 100. Сначала V-таблица заполняется первыми k значениями Х-последэвательности,

Шаг 1. [Выработать X,У] Установить в Х и Y значения очередных членов последовательностей Хn и Yn соответственно.

Шаг 2. [Вычислить j] Установить j = [k*Y/m], где m - модуль, использующийся в последовательности Yn. Таким образом, j принимает случайное значение, определяемое с помощью Y; 0<=j<=k.

Шаг 3. [Заменить] Выдать V[j] и установить V[J] = Xn.

Этот метод позволяет получать очень большие периоды, если периоды последовательностей Хn и Yn взаимно просты. И даже если длина периода не очень существенна, соседние члены последовательности почти не коррелируют друг с другом; полученная последовательность будет удовлетворять фактически любому критерию случайности.

4. ЯП пролог и логическое программирование. Структура программ. Особенности исполнения.

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

Пролог, по принципам своей работы, не относится к алгоритмическим (процедурным) языкам. Однако полностью отказаться от процедур не представляется возможным. Процедурный стиль программирования остался при организации ввода и вывода информации, особенно при работе с файлами - для совместимости с операционными системами. Свое название Пролог получил от слов "ПРОограммирование на языке ЛОГики". На самом деле Пролог не считается чистым языком логического программирования, но его создание - важный этап в этом направлении. Теоретической основой Пролога является раздел символьной логики, называемый исчислением предикатов. Прологу присущ ряд свойств, которыми не обладают традиционные языки программирования. К таким свойствам относятся механизм вывода с поиском и возвратом, встроенный механизм сопоставления с образцом, и простая, но выразительная структура данных с возможностью ее изменения. В программе на любом языке программирования всегда можно выделить две части: процедурную - где находятся действия, шаги алгоритма, и декларативную - где располагаются описания.

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

Отличительную особенность "Пролога" от алгоритмических языков программирования можно сформулировать: алгоритмический язык: Подробное описание действий с исходными данными и их порядка для получения результата.

пролог: Описание всех возможных действий (правил вывода) исходных данных и цели. Результат - ответ на вопрос, можно ли достичь цели не выходя за рамки правил. Побочный результат - путь достижения цели.

Необходимость помещения всех частей большой программы в один файл несомненно является неудобством. Это ведет к тому, что программа становится нечитаемой и иногда неправильной. Prolog предусматривает возможность деления текста программы на отдельные файлы, используя среду IDE (Integrated Development Environment) и, кроме того, IDE позволяет помещать логически связанные фрагменты текста программы в отдельные файлы. Несмотря на такое разделение программы на части, сущности, находящиеся в общем использовании, доступны.

Например, если имеется домен, который используется несколькими файлами, то объявление домена делается в отдельном файле и к этому файлу из других файлов существует доступ.

Для упрощения этого руководства мы будем использовать один файл для разработки текста программы. На самом деле в процессе построения программы среда IDE создавала бы автоматически несколько файлов, но мы сейчас будем это умалчивать. Об этом написано в других руководствах.

•Для представления знаний используются фразы Хорна;

•Программа описывает логическую модель Предметной Области в виде фактов относительно свойств Предметной Области и отношений между этими свойствами + правила вывода новых свойств и отношений из уже заданных;

•Использование терма как единообразной структуры данных;

•Отсутствие операторов присваивания, ветвлений, безусловных переходов и указателей.

•Для объяснения смысла программы применяются три семантические модели : декларативная, процедурная модели и модель в виде абстрактной машины.

3.Методы приближенного решения дифференциальных уравнений. Погрешность методов.

Многие матем., физич., технич. з-чи в к-ых рассм-ся ск-ть измен. одной велич. по отнош. к др. приводят к ДУ-ям. Рассм. ДУ 1-го порядка с 1-ой переем.: F(x,y,y’)=0; y=y(x); Привед. ДУ к виду y’=f(x,y) (1) б/м искать частное реш., для чего зададим нач. услов.: y(x0)=y0 (наз. з-ча КОШИ).

Реш. б/м искать в виде таблицы на некот. отр. [a,b] с некот. шагом h постоянным или нет, обычно за x0=a 

Реш ДУ с пом-ю ряда Тейлора. Доп-м реш. ур. y’=f(x,y) раскл-ся в ряд Тейлора в окрестн. т. x0 :

Пусть x1=x0+h, обозн. y(x0)=y0 подст-яя вместо x=x1, получ.: y0  -дано

y0’=f(x0,y0) из (1). Для нахожд. y’’…y(n)продиф-м правую часть (1) как сложную ф-цию: и т.д.

анал-но, полагая x=x2= x1+h наход. y2 и т.д. Т.о. дан. м-д реш. з-чу полн-ю, погрешность реш. опред-ся на основе остаточ. члена ряда Тейлора. Недост. яв-ся необх-ть вычисл. производ. высших порядков, что затруднительно на ЭВМ.

Реш. ур-ий м-дом Рунге-Кутта (РК).

М-д сост. из группы м-дов объед-х общей идеей и дающих различ. точн. Не треб. вычисл. частных произв-х. Кажд. м-д хар-ся порядком. М-д наз. м-дом порядка k, если расчет. ф-ла м-да совпад. с ф-лой Тейлора до слогаемого с hk.

I. М-д Эйлера (м-д РК 1-го порядка)

Пусть изв-но реш. ДУ y=F(x), к-ое прох. ч/з т. (x0,y0) Провед. касат. к y=F(x) ч/з т. (x0,y0) ч/з т. x1=x0+h провед. перпен-ляр к Ox до пересеч. с касат. в т.А1 за y1 примем ординату этой точки, y1 найдем из ур. касат.: y-y0=F’(x0)(x-x0) полагая x=x1=x0+h; y=y1; y1=y0+f(x0,y0)h. Провед. касат. к y=F(x) к т. (x1,y1), рассужд. анал-но нах-м А2 и т.д.:

Недост. м-да яв-ся довол. больш. погреш., к-ая с каждым шагом увелич., п/у м-д в осн. использ. для предварит. оценок. Оч-дно, что погреш-ть ↓ с ↓ h (шага)

II. Исправл. м-д Эйлера (м-д РК 2-го порядка). Пусть анал-чно постр. 2 касат l1, l2 с углов. коэф-ми k1 и k2 соот-но. Ч/з т. (x0,y0) пров. прямую L с коэф-том наклона

За y1 возьм. ординату пресеч. прямых L и

x=x1=x0+h. Найдем y1. Имеем k1=F’(x0)=f(x0,y0); k2=F’(x1)=f(x1,y1)= f(x0+h,y0+ f(x0,y0)h).

Ур-ние прямой L: y-y0=k(x-x0), полагая y=y1, x=x1, получим:y1=y0+kh, найдем y2 и т.д., зная точку xi,yi найдем yi+1:

М/но показ., что ф-ла совпадает с рядом Тейлора до слагаемого с h2

III. М-д Эйлера модифиц.

Общий вид для всех случаев:

IV. М-д РК 4-го порядка. Этот м-д яв-ся дважды применим. модиф. м-дом Эйлера к одной точке. (xi,yi), то

где где

***

Приведем сист. огранич. к канонич. виду

Вновь введенные переменные не явл-ся предпочтительными и случай 4 явл-ся к случаю 3.

Общая идея симплекс метода  и ее реализация в таблице

Чаще всего реализацию симпл.метода сводят к следующему: на нач. этапе систему ограничений, т.е.д/б выделен базис, базисное реш-е не должно быть отрицательным или что равносильно все правые части должны быть не отрицат. числами. Из ЦФ должны/б исключены основные или базисные переменные. Удобно для преобр. Сист использ.шаги жардано-гаусса.

погрешность метода Когда задача в точной постановке не решается, ее заменяют близкой по результатам приближенной задачей. Выбор более сложно решаемой задачи иногда позволяет уменьшить погрешность ценой возрастания объема вычислений;

5. Основы понятия "алгоритм". Алгоритм: содержательный и формализованный подходы к понятию "алгоритм". Свойства алгоритма и способы его описания.

Алгоpитм — точное и понятное пpедписание исполнителю совеpшить последовательность действий, направленных на решение поставленной задачи.

Основные свойства алгоритмов следующие: Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять; Дискpетность (прерывность, раздельность) — т.е. алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов); Опpеделенность — т.е. каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче; Pезультативность (или конечность). Это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов; Массовость. Это означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.

Формы представления алгоритмов.

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

Как фундаментальное научное понятие алгоритм требует обстоятельного изучения. Оно невозможно без уточнения понятия «алгоритм», без его формализации. Известно, несколько подходов к формализации понятия «алгоритм»: • теория конечных и бесконечных автоматов; • теория вычислимых (рекурсивных) функций; • -исчисление Черча. Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Мы рассмотрим постановку этой проблемы и некоторые результаты теории алгоритмической разрешимости задач, но вначале обсудим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюринга, а также нормальных алгоритмов Маркова, а затем — основы теории рекурсивных функций. Идеи исчислений Черча реализованы в языке программирования Лисп. Вместе с тем, формально определенный любым из известных способов алгоритм не может в практическом программировании заменить то, что мы называли алгоритмами в предыдущем подразделе. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения.

Пон-ие алг-ма в И. явл-ся фундам-ным. Алгоритм - заранее заданная послед-сть четко определенных правил или команд для пол-ия реш-ия з-чи за конеч. число шагов.

Алг-м - понятное и точное предписание исполнителю совершить послед-сть действий, напр-ых на достиж-ие опр-ых целей или на реш-ие пост-ой з-чи.

Св-ва: 1.Массовость - кажд. алг-м справедлив для к-л мн-ва исх. данных 2.Дискретность - алг-м д/б разбит на послед-сть отдельных действий; только после вып-ия одного действия переходят к вып-ию след-го 3. Определенность и однозначность - формул-ка алг-ма д/б точна и однозначна 4. Конечность - алг-м д. всегда зак-ся после конеч. числа шагов 5. Детерминированность (предопределение) - все действия и указания однозначны; не д/б неясных ситуаций 6. Результативность - после заверш-ия исполнения алг-ма всегда д/б получен рез-т.

Способы опис-ия алг-мов: словесная запись, алгор. язык, формула, блок-схема, структурограмма.

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

Граф. изобр-ие алг-ма наз-ся структурной схемой алг-ма (блок-схемы и структурограммы).

Б-с явл-ся ориент-м графом, у кот. графич. обозн-ия эл-тов соотв-ют вершинам графа, линии потока - его ребрам. Граф - конечное мн-во вершин, соед. ребрами.

Алг-м из-ся в виде послед-ти блоков, предписывающих вып-ие отд-ых ф-ций, и связей м/у ними. Внутри блоков помещают инф-ию, кот. поясняет вып-ие действия. Б-с показывают орг-ию алг-ма и е отр-ют орг-ию данных или структуру модулей ввода-вывода.

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

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

6. Граф. Вершины и ребра графа. Виды графов. Пути. Связность, мосты и точки сочленения. Компоненты связности. Двудольный граф. Способы задания графа.

Теория Г. – удобн. язык в описании программ-х моделей. Граф – это сов-сть точек и линий в к-рой каждая линия соедин. 2 точки. Точки – вершина Г. Линии – ребра Г. Г. G=G(V,E) это пара двух множеств V-кон-ое множество вершин, Е- двухэлементные подмнож-ва из множ-ва V. G=({V1, : ,Vn},{(V1,V2), (V2,V3), : , (V1,Vn)}).Если ребро е=(V1,V2) Г G, тогда V1-смежна с вершиной V2 и наоборот. Ребро е инцидентно вершине V1 и V2. Любые две вершины инцидентны одному ребру – смежные. Два ребра инцидентны одной вершине – смежные. Если 2 ребра инцидентны 1 и той же паре вершин – кратные рёбра. Если Е=0, то граф пустой. Если каждому ребру приписано направление – граф направленный.

Т.1.Пусть Т дерево с мн-ом вершин V и мн-вом рёбер Е, тогда: 1.Для кажд. пары различных вершин сущест. единст-ый путь в Т связ-щий их; 2. Удаления любого ребра из Т прив-ит к обр-ию Г. с 2мя компон-ми, каждое из кот. яв-ся деревом;

3. Кол-во рёбер |Е|=|V|-1.

Связ-ый Г. удовл-ий люб. из этих условий явл. деревом

Граф –– это множество точек называемых ребрами которые соединяют пары вершин или вершину саму с собой в виде дуги.

Т.1.Пусть Г произ-ый плоский граф с числом вершин |V|,с числом рёбер|E|, кот-ый разбивает пл-ть на |F|граней, тогда |F|=|E|-|V|+2.

Элементы теории графов. Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом.  Граф называется связанным, если любая пара его вершин связанна.  

 Ориентированные графы. Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными ребрами – ориентированным графом:

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

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

Способы задания графа:

Явное задание графа как алгебраической системы

 <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>.

Геометрический – рисуются вершины и грани на плоскости.

          

Степенью вершины назовём удвоенное количество петель, инцидентных этой вершине плюс количество остальных инцидентных ей рёбер.

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

Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежны.

Графы часто используют для изображения различных отношений (например, иерархических отношений, т.е., на языке математики – отношений частичного порядка).

7. ЭВМ как средство обработки информации. Классификация ЭВМ. Перспективы развития вычислительной техники.

Осн. назн-ие ЭВМ – хр-ие и обраб-ка инф-ии. Поэтому необ-мы знания не только об арх-ре ЭВМ, но и об устр-ве и р-те его процессора, о предст-ииинф-ии в памяти ЭВМ, о языке команд процессора. Слово «к-р» озн-ет «вычислитель». Но к-ры в отличии от арифмометров позв-ют проводить без участия чел-ка сложные послед-сти выч. операццй по заранее заданной инструкции – программе. Для хран-ия данных и рез-тов выч-ий к-ры сод-т память. К-ры созд-сь для числен. расчетов, но оказалось, что они м. обраб-ть и др. виды инф., т.к. практически все они м. быть предст-ны в числ. форме. Для обраб-ки разл. инф-ии на ЭВМ необх. иметь ср-ва для преобр-ия нужного вида инф. в числ. форму и обр-но. В данное время ЭВМ превр-сь в универс. ср-во для обраб-ки всех фидов инф-ии, исп. чел-ком. Для обраб-ки на ЭВМ инф-ии, отличной от числовой исп-ся кодировка символов (соотв-ие м/у символом и числом). ЭВМ обычно р-ет в двоичной СС, а единицей инф. в к-ре явл-ся 1 бит – двоичный разряд, кот. приним. зн-ие 0 или1. Класс-ия ЭВМ По поколениям (нестрогая кл-ия по степени раз. аппаратных и прогр. ср-в): 1) 1946 – вакуумно-ламповые технологии, память на ртутных линиях зад-ки барабанах эл-луч. трубках. Ввод/вывод: перфоленты, перфокарты, магн. ленты, печат. устр-ва. Впервые реализ. концепция хранимой прог-ммы. 2) 1955 – замена лампы на транзисторы, возросло быстродействие, снизилось потребление энергии, память – на магнит. сердечниках,, исп-ие первых ЯП высокого уровня. 3) 1964 – микросхемы малой и сред. спени интеграции, возн. пон-ие арх-ры ЭВМ, появилась кэш-память 4) 1975 - большие и сверхбольшие инт. схемы, исп-сь быстродейств. с-мы памяти на инт. схемах. По мощности (условно): малые, средние, большие, суперЭВМ. По области прим.: универс., специализир-ые. По пр-пу действия: цифровые (раб-ют с дискрет. сигналами), аналоговые. По степени параллелизма в обраб. инф. 1) послед-ые (! процессор), 2) с параллельн. вводом/выводом: по быстродейств. внеш. устр-в: быстрые (селекторные), медленные (мультиплексные) 3) параллельные (неск. центр. проц). По взаимод-ию центр. проц. и внутр. памяти: одиноч. поток ком-д – один. поток данных (ОКОД); ОКМД; МКОД, МКМД. Что впереди? В 1990-х гг. микроэлектроника подошла к пределу, разрешенному физическими законами. Фантастически высока плотность упаковки компонентов в интегральных схемах и почти предельно велика возможная скорость их работы. В совершенствовании будущих ЭВМ видны два пути. На физическом уровне это переход к использованию иных физических принципов построения узлов ЭВМ — на основе оптоэлектроники, использующей оптические свойства материалов, на базе которых создаются процессор и оперативная память, и криогенной электроники, использующей сверхпроводящие материалы при очень низких температурах. На уровне совершенствования интеллектуальных способностей машин, отнюдь не всегда определяемых физическими принципами их конструкций, постоянно возникают новые результаты, опирающиеся на принципиально новые подходы к программированию. Уже сегодня ЭВМ выигрывает шахматные партии у чемпиона мира, а ведь совсем недавно это казалось совершенно невозможным. Создание новейших информационных технологий, систем искусственного интеллекта, баз знаний, экспертных систем продолжатся. Наконец, уже сегодня огромную роль играют сети ЭВМ, позволяющие разделить решение задачи между несколькими компьютерами. В недалеком будущем и сетевые технологии обработки информации станут, по-видимому, доминировать, существенно потеснив персональные компьютеры (точнее говоря, интегрировав их в себя).

8. Основы анализа алгоритмов. Асимптотическая временная сложность алгоритмов. Классификация скоростей роста сложности алгоритма. О-символика.

Для оценки эф-ти алг-ов введено понятие сложности алг-ма. Вычисл.процессом, порожденным алг-ом, н-ся послед-ть шагов алг-ма, пройденных при исп-ии этого алг-ма. Слож-ть алг-ма- это кол-во элем-ных шагов в вычислит.процессе этого алг-ма. Временная слож-ть алг-ма – это время Т, необх-ое для его вып-ия в зав-ти от исх.д-ых. Оно равно произв-ю числа элем-ых действий k на среднее время вып-ия 1го действия t: T=kt. Емкостная слож-ть опред-ся числом занятых ячеек памяти и не м.б. больше Ci (1<i<k), где Ci – кол-во ячеек, занятых на i шаге. Если положить С=maxCi , то Ci  <=C*k, т.е. и емкостную слож-ть м.свести к временной.

Для анализа алг-ов исп-ся еще 1 подход, основанный на подсчете времени работы алг-ма при возрастании размерности задачи, т.е. на вычислении асим-ой эф-ти алг-та. Асимптотика - это искусство оценивания и сравнения скорости роста ф-ций (обозн. О-символика).

Время вып-ия алг-ма А прямо пропорц-о ф-ции f(n). Если время реш-я задачи прямо пропорц-о ее размеру n, то сложн-ть задачи = О(n), т.е. имеет порядок n. Если время реш-я задачи прямо пропорц-о квадрату ее размера n2, то сложн-ть задачи = О(n2) Точное знание кол-ва операций, вып-ых алг-ом, не играет существ-ой роли, важно знать скорость роста этого числа при возрастании объема входных д-ых. Оно н-ся скоростью роста слож-ти алг-ма.

Пусть f- нек-ая ф-ция. Алг-мы м. сгруппировать по скорости роста их сложн-ти:

1) алг-мы, слож-ть к-ых растет по кр.мере так же быстро, как дан.ф-ция f;

2) алг-мы, слож-ть к-ых растет с той же скоростью, что и дан.ф-ция f;

3) алг-мы, слож-ть к-ых растет медленнее, чем дан.ф-ция f.

Омега большое. Класс ф-ций, растущих по кр.мере так же быстро, как g, обозн. ч\з (g). Ф-ция, f(g), если при всех знач-ях арг-та n0, и нек-го полож-го с вып-ся нерав-во f(n)>c g(n). М. считать, что класс (g) задается указанием своей нижней границы: все ф-ции этого класса растут по кр.мере так же быстро, как g.

О большое. Оценка О треб-ет только, что бы ф-ция f(n) не превышала g(n) начиная с n>n0, с точностью до постоянного множителя. Класс ф-ций, растущих не быстрее, чем g, обозн. ч\з О(g). Ф-ция, fО(g), если при всех знач-ях арг-та n,  больших нек-го порога n0, и нек-ого полож-го с вып-ся нерав-во f(n)<=c g(n).

Тета большое. f(n)=(g(n)), если сущ-ют полож-ые с1,с2,n0, такие, что: с1*g(n)<=f(n)<=c2*g(n), при n>n0. Ч\з (g) обоз-им класс ф-ций, растущих с той же скоростью, что и g. Этот класс явл-ся пересечением 2х предыд.

9. Машина Тьюринга. Операции над машинами Тьюринга. Вычислимость по Тьюрингу частично-рекурсивных функций. Совпадение класса всех нормально вычислимых функций с классом функций вычислимых по Тьюрингу.

Машина Тьюринга - это универсальная учебная машина, созданная для уточнения понятия алгоритм. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.

Машина Тьюринга так же, как и конечный автомат, является дискретным устройством преобразования информации. Приведём её точное определение, а затем интерпретацию её работы.

Машиной Тьюринга называется частичное отображение (множество состояний)

Где  обозначает “лево”, “право”. Тот факт, что отображение  частичное, означает, что  может быть определено не для всех наборов аргументов. Машина Тьюринга  работает с бесконечной в обе стороны лентой, разбитой на ячейки, в каждой из которых написан один из символов 0, 1. Считывающая головка машины обозревает в каждый момент времени одну из ячеек и за один такт, сменяющий два последовательных момента времени, может перемещаться влево или вправо. Машина Тьюринга в каждый момент времени находится в одном из состояний  а в следующий момент времени переходит в другое состояние или остаётся в том же. Кроме того, машина может изменять символ, стоящий в обозреваемой ячейке. Все эти преобразования — изменение состояния, информация на ленте, направление движения полностью определяются отображением  А именно, если  то в случае, когда машина находится в состоянии  а на обозреваемой в данный момент ячейке написан символ  машина должна записать в эту ячейку  вместо  перейти в состояние  и сдвинуться на одну ячейку влево. Например, равенство  означает, что, находясь в состоянии  и обозревая ячейку, в которой написан символ 1, машина должна сохранить в этой ячейке символ 1, сдвинуться вправо и перейти в состояние  Если же не определено, то машина, находясь в состоянии  и обозревая ячейку с символом  прекращает работу, не изменяя своего состояния, информации на ленте и никуда не сдвигаясь.

Более удобна запись программы, которая заключает в себе всю информацию о работе машины (таким образом, задания машины с помощью отображения и с помощью программы эквивалентны между собой). Опишем составление программы. Для каждого равенства вида  где  номера состояний,  направление движения, а  символы на ленте, запишем строку и назовём её командой. Совокупность всех команд — это и есть программа. Если  не определено, то в программе нет ни одной команды, начинающейся с  Кроме того, для любых  в программе есть не более одной команды, начинающейся с

Будем говорить, что машина Тьюринга  вычисляет функцию  если для любого набора  натуральных чисел машина  находясь в состоянии  и обозревая крайнюю левую единицу в  (причём [xi]=i+1 единиц, как и значение f )останавливается в том и только в том случае, когда значение  определено, и в конце работы ленте должно быть записано ...00..., а считывающая головка машины должна стоять напротив крайней левой единицы.

Таким образом, если, например,  то мы должны иметь

а если  не существует, то машина, запущенная на ленте  должна работать бесконечно долго (при условии, что начальное состояние  а обозреваемая в начальный момент времени ячейка — крайняя левая единица.

Если информация на ленте не имеет вид  или начальное состояние не  или обозреваемая ячейка — не крайняя левая единица, то поведение машины может быть каким угодно.

Рекурсивные функции. Напомним, что в этой главе множество N натуральных чисел содержит 0, т.е.  Будем рассматривать функции (возможно, частичные)  Таким образом, если  то либо  либо  не определено. Введём в рассмотрение простейшие функции о s I

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

Оператор суперпозиции. Пусть даны функция  от  переменных и  функций  от  переменных.. Суперпозицией функций  называется функция

Мы говорим, что функция  получается применением оператора суперпозиции  к функциям  и пишем

Например, (s,o) — это функция s(o т.е. функция, тождественно равная 1, а  (s,s) — это функция

Оператор примитивной рекурсии. Пусть даны функции  и  Построим функцию  Пусть зафиксированы значения  Тогда положим:

Эти равенства определяют функцию  однозначно. Функция  называется функцией, полученной с помощью оператора примитивной рекурсии. Используется запись

Индуктивное определение функции (продемонстрированное в операторе примитивной рекурсии) в математике не редкость. Например, индуктивно определяются степень с натуральным показателем:   факториал:   и т.д.

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

Оператор минимизации. Пусть дана функция  Зафиксируем какие-либо значения  первых  переменных и будем вычислять   и т.д. Если  наименьшее натуральное число, для которого  (т.е. значения   все существуют и не равны  то полагаем Таким образом,

Если такого  нет, то считаем, что  не определено. Итак, возможны три случая:

1)    существуют и не равны  а

2)    существуют и не равны  а  не существует;

3)    существуют при всех  и отличны от

Если имеет место 1-й случай, то  а если 2-й или 3-й, то  не определено. Про функцию  полученную таким образом, говорят, что она получена из  применением оператора минимизации Мы пишем

Оператор минимизации — это очевидное обобщение оператора взятия обратной функции. Обобщение довольно глубокое, так как от функции  не требуется, чтобы она была взаимно однозначной (по переменной

Функции, которые могут быть получены из простейших о s I применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными. Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга (см. предыдущий раздел). Наоборот, всякая функция, вычислимая на машине Тьюринга, рекурсивна. В предыдущем разделе, впрочем, были построены машины Тьюринга, реализующие функцииo s I С другой стороны, не всякая функция натуральных аргументов и даже не всякая функция одного аргумента является рекурсивной,. В самом деле, рекурсивных функций имеется лишь счётное число (т.е. их можно занумеровать натуральными числами), а все функции  образуют несчётное множество. Существование нерекурсивных функций и является “математической причиной” наличия алгоритмически неразрешимых задач.

11. Нейр. сети. Одн. перцептр. Актив. ф-ия. Лог. операц. на основе прст. перцептр.

Нейронные сети представляют собой упрощенную модель человеческого мозга. Мозг состоит из нейронов, которые яв-ся индивидуальными процессорами. Нейроны соединяются друг с другом с помощью нервных окончаний двух типов: синапсов, через которые в ядро поступают сигналы, и аксонов, через которые нейрон передает сигнал далее. Человеческий мозг состоит примерно из 1011 нейронов. Каждый нейрон связан примерно с 1000 других нейронов (это не относится к коре головного мозга, где плотность нейронных связей намного выше).

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

Ячейка включает три входа (u1, u2 и u3). Кроме этого, есть вход смещения (W0), о котором будет рассказано позже. Каждое входное соединение имеет вес (w1, w2 и w3). Наконец, существует единый выход, О. Состояние нейрона обозначено как Y и определяется уравнением. Y = w0 + u1*w1 + u2*w2 + u3*w3

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

y = -1, если (y<=0) (5.2)

y = 1, если (y> 0)

Если значение состояния больше нуля, то выходное значение будет равно 1. Иначе оно составит -1.

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

функция И имеет значение 1, если оба входа равны 1, в противном случае функция возвращает значение 0. Поэтому если заданы оба входа (вектор u = (1,1)), то, используя активационную функцию в качестве порога, получим следующий результат:

Y = смещение + u1*w1, + u2*w2 или 1 = nopoг(-1+(1*l)+(l*1)).

Теперь попробуем подставить вектор и = (0,1):

Y = смещение + u1*w1, + u2*w2 или 1 = порог(-1 + (0*1)+(1*1)).

Как показывают оба примера, модель простого перцептрона правильно реализует логическую функцию И (а также функции ИЛИ и НЕ).

10. Элементы теории игр. Понятие об игровых моделях. Нижняя и верхняя цены игры. Принцип минимакса. Вполне определенные игры, не содержащие седловой точки. Решение игр в смешанных стратегиях. Геометрическая интерпретация игры 2x2.

Математические методы анализа конфликтных ситуаций объединяются под названием теории игр, сама конфликтная ситуация носит название игры, а стороны, участвующие в конфликте, называются игроками. Исход игры называется выигрышем (или проигрышем) игроков. Если в игре участвуют только два игрока, то игра называется парной. Будем рассматривать в дальнейшем только парные игры. Если выигрыш одного игрока равен проигрышу другого, то игра называется антагонистической. 

Величина a называется нижнейценой игры или максимином. Это гарантированный выигрыш игрока А. С другой стороны, игрок В выбирая свою стратегию Вj понимает, что игрок А ответит такой стратегией Аi, чтобы его выигрыш был максимален. Поэтому из наилучших вариантов дляА (максимальных элементов каждого столбца)  игроку В рационально выбрать свою стратегию, соответствующую минимальному из этих чисел: .

Величина β называется верхней ценой игры или минимаксом. Это максимальный проигрыш игрока В. Реальный результат решения конфликтной ситуации, называемый ценой игры n, заключен между верхней и нижней ценой: . В случае, если верхняя и нижняя цены совпадают , то игра имеет решение в чистых стратегиях, то есть можно точно определить стратегии , которые выгодны для обоих сторон. Если одна сторона отойдет от своей оптимальной стратегии, то ее выигрыш от этого только уменьшится. 

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

Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pmпричем сумма вероятностей равна 1:  Смешанные стратегии игрока А записываются в виде матрицы или в виде строки SA = (p1, p2, ..., pi, ..., pm) Аналогично смешанные стратегии игрока В обозначаются:, или, SB = (q1, q2, ..., qi, ..., qn), где сумма вероятностей появления стратегий равна 1:  

Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*Bв общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: α ≤ v ≤ β, где α и β — нижняя и верхняя цены игры.

Решение игры 2×2 допускает наглядную геометрическую интерпретацию. Пусть игра задана платежной матрицей Р = (aij), i, j = 1, 2. По оси абсцисс (рис. 3.1) отложим единичный отрезок AA2 точка A1(х=0)изображает стратегию A1, а все промежуточные точки этого отрезка — смешанные стратегии SA первого игрока, причем расстояние от SA до правого конца отрезка — это вероятность p1 стратегии A1, расстояние до левого конца — вероятность p2 стратегии A2. На перпендикулярных осях II и IIII откладываем выигрыши при стратегиях A1 и A2 соответственно. Если 2-й игрок примет стратегию B1, то она дает выигрыши a11 и a21 на осях II и IIII, соответствующие стратегиям A1 и A2. Обозначим эти точки на осях I—I и II—II буквой B1. Средний выигрыш v1, соответствующий смешанной стратегии SA, определяется по формуле математического ожидания v1 = a11 p1 + a21 p2   и равен ординате точки M1, которая лежит на отрезке BB1 и имеет абсциссу SA (рис. 3.1).

Аналогично строим отрезок B2B2, соответствующий применению вторым игроком стратегии B2 (Рис. 3.2). При этом средний выигрыш v2 = a12 p1 + a22 p— ордината точки M2. В соответствии с принципом минимакса оптимальная стратегия S*A такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум. Ординаты точек, лежащих на ломаной (рис. 3.3 в примере 3.4.1), показывают минимальный выигрыш игрока А при использовании им любой смешанной стратегии (на участке BN — против стратегии B, на участке NB2 — против стратегии B2). Оптимальную стратегию S*A = ( p* p*2 ) определяет точка N, в которой минимальный выигрыш достигает максимума; ее ордината равна цене игры v. На рис. 3.3 (пример 3.4.1) обозначены также верхняя и нижняя цены игры α и β.

12. Приближенное решение уравнений. Методы бисекции, хорд,касательных, комбинированный, итераций. Погрешность методов.

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

Метод бисекций.

Пусть дано ур-ие  f(x)=0 где f(x)-непрерывно на некотором конеч или бесконеч интерв. Конем этого ур. Назовем число обращ-е f(x) в 0, если f(x0)=f /(x0)=…fk-1(x0)=0, то x0 корень кратности к точно решить данное ур-ие не всегда удается, будем гов-ть, что xесть приближенное решение ур-ия с точн-ю если  |a-x––| <=,где а точный корень –<= a-x––<= или a-<=x––<=a+.Задача о нахожд приближ корня обычно реш-ся в 2 этапа 1) отдел-ся корень т.е. ищется по возм-ти небольш отр-ок [ , ] содерж ровно один корень. 2) корень уточн-ся до нужной точности. 1)  а) отделение корня м.о. пр-ти графически. б) если график сложен, то ур-е мо переписать в виде g(x) =f(x) (и построить гр-ки y=g(x), y=f(x) и точка пересеч б.т. корень). в) мо для отделен корня исп-ть. теор. Т.если непрерыв ф-я на концах отр приним-ет значен разных знаков, то на отр-ке она имеет по кр-не. мере один корень. Если ф-я монотонна, то кор-нь один. Пусть изв-но, что корни Ур-я нах-ся на конц отр-ка [a,b]          разделим отрезок на равные части точками a=0<1<…<n=b и проверим знаки на концах отр-ка [i ,i+1] i=0,n-1 если условие теор вып-ся отр-к содерж корень, алгор-м метода м.б. следующим а,в концы отрезка, n-кол-во отр-ов деления.

 

2) одним из простейших способов уточнения корня явл-ся метод бисекции сост-ий в следующем: пусть на отр. [a,b] yf[-cz ровно 1 корень уровн. Найдем корень с точн-ю . Разделим отр. Пополам. Точкой x1 =(a+b)/2, половину содерж корень вновь делим пополам итд. Процесс прекращ, когда длина отр-ка не станет <=2  тогда за приближ значение корня x–– возьмем середину этого отр-ка.

Алгоритм следующий.

Метод итераций (последов-ых приближений)Уравнение f(x)=0 перепишем в виде x=(x), пусть каким либо образом найдено приближенное значение корня x0 подставляя x0 в правую часть ур-я получим число x1=(x), продолжая таким же обр-ом получим xn=(xn-1) получим бесконеч числов посл-ть {xn }допустим, что она имеет lim т.е. limxn=с (n–>беско-ть)тогда предполагая непрерыв (x) и переходя к пределу для xn получим limxn=lim(xn-1) (xn,n–> беск-ти)=> c=(c) т.е. с-корень.  Вопрос о сходимости {xn} решает теорема Т. Пусть ф-я (x) определена и диффер на некотор отр [a,b] и удовл услов 1) (x) принадлеж [a,b], 2)  /(x)<=q<=1 x принадлеж [a,b] тогда посл-ть {xn} задаваемая соотнош xn=(xn-1) сходится при x0 взятом из [a,b]

Теорема явл-ся достаточной но не обязат для сходимости.   

Геометрич смысл метода итераций.

Если  (x)  услов теор не удовлетвор мо провести след преобр f(x)=0 умнож обе части на , f(x)=0 и прибавим x, x=x+ f(x), тогда (x)=x+ f(x) подбирая  добиваемся выполнения условия теоремы .На практике для получения приближ значения корня с точностью вычисл прекращ, когда      |xn-xn-1|<= за корень бирут x––=xn.

Алгоритм  имеет вид

методами хорд и касс-ых.

М-д хорд.

Пусть корень Ур-ния f(x)=0, [a,b] допустим, что на [a,b] существ. f’’(x), к-ое не мен. знак. Пусть для определ-ти f(a)<0. Пусть f’’>0 (рис.): провед. хорду АВ и найдем ее пересеч. с осью x. Пусть А1 пересечение y=f(x) и прямой x=x1, проводим хорду А1В, пусть x2 – ее пересеч. с осью x и т.д.

Получ. ∞ числов. послед-ть {xn}. Для нахожд. xi используем Ур-ние прямой, прох. ч/з 2 точки:

найдем:

В послед-сти xn: a=x0<x1<…<xn<…<b т.е. посл-ть xn имеет предел, как возрост-ая и ограниченная сверху, т.е.

перейдя к пределу:

т.е.с-кор-нь

М-д касательных. Пусть корень ур-ния f(x)=0 отделен на отрез. [a,b], причем f’’ не меняет знака на [a,b]. Возьмем для опред-сти f(a)<a, f’’>0

Провед. касат. к тому концу дуги АВ в к-ром f*f’’>0. Пусть x1 ее пересеч. с Ox обозначим ч/з b1 пересеч. прямой x=x1 и дуги АВ. Провед. касат. в т.В1 пусть x2 ее пересеч. с Ox и т.д. Получ. ∞ послед-ть {xn} имеющую предел как убывающая и огранич. xn – б/м искать из ур-ния касат. Ищем x1:

y-f(b)=f’(b)(x-b), полагая y=0 x=x1

анал-но…

т.к. то переходя к пределу, получим:

т.е. с – корень

На практике для получ. корня с точн. ε заканчив. вычисл., когда

Методические погрешности — погрешности, обусловленные несовершенством метода, а также упрощениями, положенными в основу методики.

13. Виды компьютерной памяти. Устройства памяти, принципы их рабты и характеристики.

Прежде всего, нужно сказать, что самым главным компонентом компьютера является его процессор. Он считается “сердцем” компьютера, обеспечивающим циркуляцию системы. Но со всеми своими возможностями вычисления и обработки информации, компьютер не будет являться выдающимся устройством памяти. Память позволяет хранить всю необходимую и важную информацию на компьютере. Существует множество видов компьютерной памяти для хранения различных типов данных. Они также имеют различные возможности и особенности, в отношении хранения необходимых данных в компьютере. Общеизвестной компьютерной памятью является RAM (память с произвольной выборкой), более известная как оперативная память. Её называют памятью производной выборкой, так как любые сохранённые данные могут быть доступны напрямую, только если вы знаете точный ряд и колонку, где находится определённая ячейка памяти. Противоположностью RAM является SAM или память с последовательным доступом, которая хранит данные в последовательных ячейках памяти, которые могут быть расположены только в определённом порядке.

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

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

Внешняя (долговременная) память — это место  длительного хранения данных (программ, результатов расчётов, текстов и т.д.), не используемых в данный момент в оперативной памяти компьютера. Внешняя память, в отличие от оперативной, является энергонезависимой. Носители внешней памяти, кроме того, обеспечивают транспортировку данных в тех случаях, когда компьютеры не объединены в сети (локальные или глобальные).

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

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

14. Классификация ППО. Программы создания рисунков. Методы представления графических изображений. Растровая и векторная графика. Системы цветов в компьютерной графике. Форматы графических файлов.

ППО- это часть ПО, пред-ная д/ того, чт. обеспечить примен-ие ВТ в разл. сферы деят-ти ч-ка. Стр-ра и прин-п постр-ия ПП зависит от ЭВМ и ОС, в рамках кот. она будет функц-ть. ПП реал-ся на конкр языке прог-ия.Внаст. время предл-ся разл. ППП, автомат-щие сферы чел. деят-ти (редакторы, эл. таб , банки дан., информ-но – поисковые сис-мы, мат. прог-мы, эксперт. сис-мы).

 ППО: универсальн. и специализир-ое. УППО: сис-мы обр-ки текстов, ср-ва машин. графики, СУБД, ср-ва обр-ки эл-ных таб., интегрир. пакеты. Эти прог.ср-ва не привязаны к к.-л. предм. обл-ти.=> возм-ть исп-ть их в разл. обл-тях. Особ-ти разраб-ки- отсут-ие конкр. заказчика. УППО д\б мобильным, легко адаптируемым к разл. моделям ЭВМ, просты в освоен. и эксплуат-и.

СППО: расчит. на конкр. группу польз-лей, тесно связ с опред. предм. обл-ю; оно д/б надежным, корректным, соотв-ть спец-ке условий экспл-ции. Тираж-ие возм-но , но в значит. меньших масштабах. К ним относ-ся: сис-мы автомат-го проект-ия, банковские фин. сис-мы, сист. управл-ия произв-вом, бух. учета, эксперт. сис-мы д/ конкр. зад., мат. пакеты и др. Выд-ют еще уникальное ППО- разраб. по инд.. заказу, исп-ся для науч. и инж.. расчетов, созд сис-мы иск. ител-та.

Растровая графика  Растровое изображение представляет из себя мозаику из очень мелких элементов — пикселей. Растровый рисунок похож на лист клетчатой бумаги, на котором каждая клеточка закрашена определённым цветом, и в результате такой раскраски формируется изображение.  Здесь компьютерный художник водит «кистью» — курсором мыши по «электронному полотну» — экрану, закрашивая каждый из пикселей рисунка в нужный цвет. Таким образом каждому пикселю присваивается цвет. Растровая графика работает с сотнями и тысячами пикселей, которые формируют рисунок. Экран дисплея разбит на фиксированное число видеопикселей(наименьший элемент изображения на экране), которые образуют графическую сетку (растр) из фиксированного числа строк и столбцов. Размер графической сетки обычно представляется в форме NxM, где N — количество видеопикселей по горизонтали, а М — по вертикали. Изображение на экране дисплея создаётся путём избирательной засветки электронным лучом определённых видеопикселей экрана. (+)растровой графики 1. Если размеры пикселей достаточно малы (приближаются к размерам видеопикселей), то растровое изображение выглядит не хуже фотографии. 2. Компьютер легко управляет устройствами вывода, которые используют точки для представления отдельных пикселей.

(-) растровой графики 1. Например, если размер графической сетки — 1240 х 1024, а количество используемых цветов — 16777216, то объём растрового файла составляет около 4 Мб, так как информация о цвете видеопикселей в файле занимает 1240 х 1024 х 24 = 30474240 бит или 30474240 бит : 8 = 3809280 байт или 3809280 байт : 1024 - 3720 Кб или 3720 Кб : 1024 = 3,63 Мб. Т.о. для хранения растровых изображений требуется большой объём памяти. Самым простым решением проблемы хранения растровых изображений является увеличение ёмкости запоминающих устройств компьютера. Другой способ решения проблемы заключается в сжатии графических файлов, т. е. использовании программ, уменьшающих размеры файлов растровой графики за счет изменения способа организации данных. Векторная графика В векторной графике изображения строятся из простых объектов — прямых линий, дуг, окружностей, эллипсов, прямоугольников, областей однотонного или изменяющегося цвета (заполнителей) и т. п., называемых примитивами.В трёхмерной компьютерной графике могут использоваться «пространственные» примитивы — куб, сфера и т. п. Векторные примитивы задаются с помощью описаний. Например: рисовать линию от точки А до точки В.Для компьютера подобные описания представляются в виде команд, каждая из которых определяет некоторую функцию и соответствующие ей параметры. Символические команды для приведённых выше примеров описаний в векторном формате WMF (Windows Metafile) записываются так: LINETO X2, Y2 Нарисовать линию от текущей позиции до позиции (X2.Y2). Информация о цвете объекта сохраняется как часть его описания, т. е. в виде векторной команды. Для получения векторных изображений, как правило, используются программы иллюстративной графики (Adobe Illustrator, CorelDraw!), (+) векторной графики 1. векторные изображения занимают относительно небольшой объём памяти. 2. векторные изображения могут быть легко масштабированы без потери качества. В ряде случаев возможно преобразование растровых изображений в векторные. Этот процесс называется трассировкой. Программа трассировки растровых изображений отыскивает группы пикселей с одинаковым цветом, а затем создаёт соответствующие им векторные объекты. (-) векторной графики 1. векторная графика не позволяет получать изображений фотографического качества. Дело в том, что фотография — мозаика с очень сложным распределением цветов и яркостей пикселей и представление такой мозаики в виде совокупности векторных примитивов — достаточно сложная задача. 2. Векторные изображения описываются десятками, а иногда и тысячами команд. В процессе печати эти команды передаются устройству вывода (например, принтеру). При этом может случиться так, что на бумаге изображение будет выглядеть совсем иначе, чем хотелось пользователю, или вообще не распечатается. Графические программы — это инструменты компьютерного художника, с помощью которых он создаёт и редактирует изображения. Для создания иллюстраций обычно используются векторные программы, которые также называют программами рисования. Любая графическая программа содержит набор инструментов для работы с изображениями. Несмотря на то, что растровые и векторные программы могут использовать одинаковые инструменты, способ представления создаваемых ими изображений различен.

В графических программах реализованы возможности, позволяющие перемещать, копировать, удалять, масштабировать, зеркально отражать, вращать отдельные части изображений. Прежде, чем выполнить операцию над фрагментом изображения, его необходимо выделить. В векторных программах выделяют объекты, (векторные примитивы), а в растровых — области (наборы пикселей). Так как основное понятие растровой графики — пиксель, большинство инструментов и команд растровых программ изменяют яркость и цветовые оттенки отдельных пикселей. Основное понятие векторной графики — объект. Поэтому векторные программы содержат команды упорядочивания, взаимного выравнивания, пересечения объектов, исключения одних объектов из других. Система цветов в компьютерной графике: RGB • CMYK • XYZ • HSV (HSB) • HSL • RYB • LAB • PMS (Пантон) • LMS • Cистема Манселла • NCS • YUV • YCbCr • YPbPr • YDbDr • YIQ

RGB Изображение в данной цветовой модели состоит из трёх каналов. При смешении основных цветов (основными цветами считаются красный, зелёный и синий) —При смешении всех трёх цветовых компонентов мы получаем белый цвет (W). Четырёхцветная (CMYK: Cyan, Magenta, Yellow, Key colour) —схема формирования цвета, используемая прежде всего в полиграфии для стандартной триадной печати. Схема CMYK, как правило, обладает сравнительно небольшим цветовым охватом CIE XYZ — линейная 3-компонентная цветовая модель, основанная на результатах измерения характеристик человеческого глаза. Построена на основе зрительных возможностей так называемого «стандартного наблюдателя», то есть гипотетического зрителя, возможности которого были тщательно изучены и зафиксированы в ходе длительных исследований

Форматы графических файлов:

Растровая GIF, BMP, WBMP, PCX, PCD, PSD, FLM, IFF, PXR, PNG, SCT/PICT, PCT, RAW, TIF/TIFF, BMP, JPEG , TGA, FPX, GIF , PhotoCD, MNG, ICO, FLA/SWF.

Векторная: WMF, EMF, CGM, EPS, WPG, AutoCAD, DXF, DWG, CDR, AI, PCT, FLA/SWF

17. Элементы теории двойственности. Прямая и двойственная задачи линейного программирования. Основные теоремы двойственности. Применение двойственного симплексного метода.

В каждой задаче лин.прогр-ия существует другая двойственная или сопряженная ей задача. Теория двойственности оказалась полезной для проведения качеств. исследований в обл. ТО.

Прямая и двойственная ЗЛП.Основное содержание плановой экономической работы на предприятии составл. реш-ие задачи достижение наилучшего экономич. эффекта при огранич.ресурсах; математически св-ся к ЗЛП и м/б решена известными методами. Причем план выпуска новой продукции оказ-ся тесно связан с так называемой системой цен (системой оценок) прим-х к ресурсам (отходы основн.произ-ва), пусть на некот. предприятии решено использ отходы основн. произв-ва , для этого намеч-ся наладить выпуск изделий широкого потребления. Известно, что сбыт новой продукции обеспечен, при этом кол-во исх-х материалов сырья ограничено. Ставится задача, достичь наибольшей прибыли от произв-ва.

Зная прямую задачу всегда можно построить двойств.и наоборот.

Прямая. Необходимо найти такой план произв-ва х1,х2,…,хn удовлетв.сисетеме огранич. Х=(х1,х2,…,хn)

xi>=0(i=1,n). Для кот.

Тогда двойственная или сопряж. задача будет сформулирована след.образом. Необходимо найти такую систему оценок У=(у1у2...уm).

 Основная теорема двойственности.

Т.1. Для любых  допустимых решений Х=(х1х2...хn) и У=(у1у2…уm) пары двойственных задач справедливо нер-во:

-основное нер-во теории двойств-ти.

Экономич-ое содерңание этого нер-ва закл-ся в том, что обәая стоим-ть всего произведенного продукта не больше суммарной оценки ресурса.

Т.2.(т. О минимаксе необход. Признак оптим-ти доп-х реш-ий).

Если одна из двойств-х задач имеет оптимальное реш-е, то другая двойств. Задача также имеет оптимальное реш-е причем вып-ся рав-во

Zmax=Tmin

Т.3. Достаточный признак сущ-ия оптимального реш-я, если Х и У доп-ые реш-ия пары двойств-х задач, для кот вып-ся рав-во Zmax=Tmin

То Х есть оптим-ое реш-е  прямой задачи, У есть оптим. Реш-е двойственности.

Т.4. Для того чтобы реш-е Х явилось оптим. реш-м пары двойств-х задач необходимо и достаточно чтобы выполнялось след. Усл-е:

 

15. Принципы функционирования локальных вычислительных сетей. Устройства поддержки работы ЛВС. Типы ЛВС. Одноранговые сети. Сети на основе сервера. Комбинированные сети.

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

ЛВС получили большое распространение из-за невысокой стоимости и не большой сложности. Их основные компоненты – 1. серверы, т.е. аппаратно программные комплексы, которые исполняют функции управления распределением сетевых ресурсов; 2. рабочие станции, осуществляющие доступ к сетевым ресурсам при помощи сервера; 3. физическая среда передачи данных/сетевой кабель (оптоволоконный, коаксиальный, витая пара, беспроводные каналы связи). Выделяют 2 типа ЛВС: одноранговые ЛВС и сети на основе сервера. выбор типа ЛВС зависит от размеров предприятия, необходимого уровня безопасности, обмена сетевым трафиком, финансовых затрат, от уровня допустимости сетевой административной поддержки. При этом задача сетевого администрирования обычно состоит в следующем: -управление работой пользователя; -защита данных; -обеспечение доступа к ресурсам; -поддержка приложений; - использование прикладного ПО. 

Одноранговая сеть в этих сетях компьютеры равноправны, в них нет иерархии и сервера. В такой сети каждый компьютер может быть и рабочей станцией и сервером. Все пользователи решают сами какие данные и какие ресурсы на своем компьютере сделать общедоступными. Рабочая группа это небольшой коллектив объединенный общей целью или интересами. В одноранговых сетях бывает не более 10 компьютеров. Такие сети обычно дешевле. Требования к производительности и уровню защиты в них так же значительно ниже. Однако сами компьютеры, входящие в одноранговую сеть, должны быть достаточно мощными, чтобы справляться со всеми основными и дополнительными задачами (административными, защитой от вирусов и т. д.). Если фирме нужна конфеденциальность, такую сеть использовать нельзя.

СЕТЬ НА ОСНОВЕ СЕРВЕРА. Выделенным называется сервер который функционирует только как сервер. Такие серверы оптимизированы для быстрой обработки запросов, но с увеличением размеров сети, будет увеличиватся объем сетевого трафика, следовательно понадобятся новые сервера. При расположении нескольких серверов в сети эффективно распределить задачи между ними, т.е.каждая задача будет выполняться своим сервером. Круг задач которые выполняют серверы многообразен и сложен. Существуют следующие типы серверов: - файл серверы и принтсерверы (работа и доступы к ресурсам); - серверы приложений, в т.ч. база данных и веб-серверов, на них выполняются прикладные части клиент-серверных приложений; почтовые серверы; - факс-серверы; - коммуникационные серверы, управляют передачей ресурса и почтовых сообщений между данной ЛВС и другими сетями; -  сервер служб каталогов, для поисков, хранения и защиты информации. ПРЕИМУЩЕСТВА СЕТИ НА ОСНОВЕ СЕРВЕРА: разделение ресурсов, сервер спроектирован так чтобы предоставить доступ к множеству файлов и принтеров при этом обеспечивая высокую защиту и производительность. Управление и администрирование доступом централизованно; защита, в такой сети защитой занимается только администратор, он формирует политику каждого пользователя; резервное копирование данных, т.к. вся важная информация расположена централизованно, то ее удобно регулярно копировать; избыточность, благодаря ей любые данные могут дублироваться в любой момент времени; аппоратное обеспечение. КОМБИНИРОВАННЫЕ СЕТИ. Сетевые ОС так же как Novel Net Ware и Windows NT,могут отвечать за совмесное использование основных приложений и данных. На рабочих станциях устанавливают ОС windows NT,95,98, которые будут управлять доступом к ресурсам выделенного сервера и предоставлять свои жесткие диски и разрешать доступ к данным на них. Комбинированные сети – самый распространенный вид сетей.

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

16. Моделирование стохастических систем. Общая схема метода Монте-Карло. Особенности моделирования систем массового обслуживания. Математическая модель систем массового обслуживания.

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

Наличие простых и экономных способов формирования последовательности случайных чисел во многом определяет возможности использования вероятностного моделирования.

Случайные числа полезны - для проверки всевозможных алгоритмов; - для решения ряда задач вычислительной математики (к примеру, вычисление кратных интегралов) можно применить (метод Монте-Карло); - моделирования стохастических явлений (поиск оптимальных стратегий в теории игр).

Общая схема метода Монте – Карло.

Основная идея метода Монте-Карло состоит в использовании выборок для получения искомых оценок. Для получения выборок нужно чтобы решаемая задача была описана соответствующим вероятностным распределением.

Пусть нужно вычислить неизвестную величину m. Подберем /ksi чтобы М(/ksi) = m и существует D(/ksi)=b^2.

Рассмотрим N независимых реализаций /ksi1, /ksi2, ... /ksiN случайной величины /ksi.

Если N достаточно велико, то согласно центральной предельной теореме распределение суммы Y(N) = /ksi1+/ksi2+ ...+/ksiN будет асимптотически нормальным с параметрами /а=Nm,

\sigma^2=b^2*N.

По правилу трех сигм имеем:

вероятность P{N*m - Зb*sqrt(N) < Y(N) < N*m + 3b*sqrt(N)}= 0,997 или р{m - Зb/sqrt(N) < Y(N)/N < m + 3b/sqrt(N)}= 0,997

Среднее арифметическое N значений случайной величины /ksi. будетm. С вероятностью 0,997 погрешность такого приближения не превосходит величины 3*sqrt(D(/ksi))/sqrt(N). Эта ошибка стремится к нулю с ростом N.

Особенности моделирования систем массового обслуживания.

Системы массового обслуживания - это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью системы каналов обслуживания.

Все СМО различают по числу каналов обслуживания:

-одноканальные системы;

- многоканальные системы.

Различают два основных вида СМО:

-системы с отказами (заявка получает отказ и покидает очередь т.к. в данный момент все каналы заняты);

- системы с ожиданием (очередью), (заявка становится в очередь, т.к. в данный момент времени все каналы обслуживания заняты). СМО с ожиданием делятся на системы с ограниченным и неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться:

- длина очереди;

- время пребывания в очереди.

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

обслуживается машинный парк, состоящий из N машин, бригадой R механиков (N > R), причем каждая машина может обслуживаться только одним механиком.

Машины – заявки на обслуживание

Механики – обслуживающий канал

Интенсивностьзависит от того, сколько машин в данный момент находится в эксплуатации (N - k) и сколько машин обслуживается или стоит в очереди, ожидая обслуживания (k).

В рассматриваемой модели емкость источника требований следует считать ограниченной. Входящий поток требований исходит из ограниченного числа эксплуатируемых машин (N - k), которые в случайные моменты времени выходят из строя и требуют обслуживания. При этом каждая машина из (N - k) находится в эксплуатации. Генерирует пуассоновский поток требований с интенсивностью X независимо от других объектов, общий (суммарный) входящий поток имеет интенсивность. Требование, поступившее в систему в момент, когда свободен хотя бы один канал, немедленно идет на обслуживание. Если требование застает все каналы занятыми обслуживанием других требований, то оно не покидает систему, а становится в очередь и ждет, пока один из каналов не станет свободным.

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

Состояние Sk  системы характеризуется общим числом требований, находящихся на обслуживании и в очереди, равным k. Для рассматриваемой замкнутой системы, очевидно, k = 0, 1, 2, ... , N. При этом если система находится в состоянии Sk , то число объектов, находящихся в эксплуатации, равно (N - k).

18. Основные типы кабельных сред передачи данных. Узкополосная и широкополосная передача сигналов. Асинхронная передача и автоподстройка. Сетевой адаптер. Беспроводные сети. Передача "точка-точка". Инфракрасные лазерные ЛВС. Беспроводные ЛВС с радиопередачей.

Существует несколько различных типов кабелей, используемых в современных сетях. Ниже приведены наиболее часто используемые типы кабелей. Множество разновидностей медных кабелей составляют класс электрических кабелей, используемых как для прокладки телефонных сетей, так и для инсталляции ЛВС. По внутреннему строению различают кабели на витой паре и коаксиальные кабели.

Кабель типа «витая пара» Витой парой называется кабель, в котором изолированная пара проводников скручена с небольшим числом витков на единицу длины. Скручивание проводов уменьшает электрические помехи извне при распространении сигналов по кабелю, а экранированные витые пары еще более увеличивают степень помехозащищенности сигналов.

Кабель типа «витая пара» используется во многих сетевых технологиях, включая Ethernet, ARCNet и IBM Token Ring.Кабели на витой паре подразделяются на: неэкранированные (UTP – Unshielded Twisted Pair) и экранированные медные кабели. Последние подразделяются на две разновидности: с экранированием каждой пары и общим экраном (STP – Shielded Twisted Pair) и с одним только общим экраном (FTP – Foiled Twisted Pair). Наличие или отсутствие экрана у кабеля вовсе не означает наличия или отсутствия защиты передаваемых данных, а говорит лишь о различных подходах к подавлению помех. Отсутствие экрана делает неэкранированные кабели более гибкими и устойчивыми к изломам. Кроме того, они не требуют дорогостоящего контура заземления для эксплуатации в нормальном режиме, как экранированные. Неэкранированные кабели идеально подходят для прокладки в помещениях внутри офисов, а экранированные лучше использовать для установки в местах с особыми условиями эксплуатации, например, рядом с очень сильными источниками электромагнитных излучений, которых в офисах обычно нет.

Коаксиальные кабели  Коаксиальные кабели используются в радио и телевизионной аппаратуре. Коаксиальные кабели могут передавать данные со скоростью 10 Мбит/с на максимальное расстояние от 185 до 500 метров. Они разделяются на толстые и тонкие в зависимости от толщины. Типы коаксиальных кабелей: RG-8 и RG-11, RG-58/U, RG-58 А/U, RG-59, RG-59 /U, RG-62Кабель Thinnet, известный как кабель RG-58, является наиболее широко используемым физическим носителем данных. Сети при этом не требуют дополнительного оборудования и являются простыми и недорогими. Хотя тонкий коаксиальный кабель (Thin Ethernet) позволяет передачу на меньшее расстояние, чем толстый, но для соединений с тонким кабелем применяются стандартные байонетные разъемы BNC типа СР-50 и ввиду его небольшой стоимости он становится фактически стандартным для офисных ЛВС. Используется в технологии Ethernet 10Base2, описанной ниже. Толстый коаксиальный кабель (Thick Ethernet) имеет большую степень помехозащищенности, большую механическую прочность, но требует специального приспособления для прокалывания кабеля, чтобы создать ответвления для подключения к ЛВС. Он более дорогой и менее гибкий, чем тонкий. Используется в технологии Ethernet 10Base5, описанной ниже. Сети ARCNet с посылкой маркера обычно используют кабель RG-62 А/U.

Оптоволоконный кабель

Оптоволоконный кабель обеспечивает высокую скорость передачи данных на большом расстоянии. Они также невосприимчивы к интерференции и подслушиванию. В оптоволоконном кабеле для передачи сигналов используется свет. Волокно, применяемое в качестве световода, позволяет передачу сигналов на большие расстояния с огромной скоростью, но оно дорого, и с ним трудно работать.Для установки разъемов, создания ответвлений, поиска неисправностей в оптоволоконном кабеле необходимы специальные приспособления и высокая квалификация. Оптоволоконный кабель состоит из центральной стеклянной нити толщиной в несколько микрон, покрытой сплошной стеклянной оболочкой. Все это, в свою очередь, спрятано во внешнюю защитную оболочку.Оптоволоконные линии очень чувствительны к плохим соединениям в разъемах. В качестве источника света в таких кабелях применяются светодиоды (LED - Light Emitting Diode), а информация кодируется путем изменения интенсивности света. На приемном конце кабеля детектор преобразует световые импульсы в электрические сигналы.Существуют два типа оптоволоконных кабелей – одномодовые и многомодовые. Одномодовые кабели имеют меньший диаметр, большую стоимость и позволяют передачу информации на большие расстояния. Поскольку световые импульсы могут двигаться в одном направлении, системы на базе оптоволоконных кабелей должны иметь входящий кабель и исходящий кабель для каждого сегмента. Оптоволоконный кабель требует специальных коннекторов и высококвалифицированной установки. Узкополосная и широкополосная передача сигналов

В современных компьютерных сетях для передачи кодированных сигналов по сетевому кабелю наибольшее применение находят две наиболее распространенные технологии: узкополосная передача сигналов; широкополосная передача сигналов.

Узкополосные системы передают данные в виде цифрового сигнала одной частоты.Сигналы представляют собой дискретные электрические или световые импульсы. При таком способе вся емкость коммуникационного канала используется для передачи одного сигнала или, другими словами, цифровой сигнал использует всю полосу пропускания кабеля. Полоса пропускания - это разница между max и min частотой, которая может быть передана по кабелю. Каждое устройство в таких сетях посылает данные в обоих направлениях, а некоторые могут одновременно их передавать и принимать. Широкополосные системы передают данные в виде аналогового сигнала, который использует некоторый интервал частот. Сигналы представляют собой непрерывные (а не дискретные) электронные или оптические волны. При таком способе сигналы передаются по физической среде в одном направлении.Если обеспечить выделение необходимой полосы пропускания, то по одному сетевому кабелю одновременно можно передавать несколько сигналов (например, кабельного телевидения, телефона и передача данных).

Обычно беспроводные компоненты взаимодействуют с сетью, в которой — как среда передачи — используется кабель. Такая сеть со смешанными компонентами называется гибридной. Возможности Идея беспроводной среды весьма привлекательна, так как ее компоненты: обеспечивают временное подключение к существующей кабельной сети;

помогают организовать резервное копирование в существующую кабельную сеть: гарантируют определенный уровень мобильности; позволяют снять ограничения на максимальную протяженность сети, накладываемые медными или даже оптоволоконными кабелями. Применение Трудность установки кабеля — фактор, который дает беспроводной среде неоспоримое преимущество. Она может оказаться особенно полезной в следующих ситуациях: в помещениях, заполненных людьми (например, в прихожей или приемной); для людей, которые не работают на одном месте (например, для врачей или медсестер; в изолированных помещениях и зданиях; в помещениях, планировка которых часто меняется; в строениях (например, памятниках истории или архитектуры), где прокладывать кабель непозволительно. Типы беспроводных сетей В зависимости от технологии беспроводные сети можно разделить на три типа: локальные вычислительные сети; расширенные локальные вычислительные сети; мобильные сети (переносные компьютеры). Промежуточным этапом от кабельных сетей к беспроводным является способ передачи «точка-точка». Трансивер-устройство для подключения компьютера к сети, т.е. устройство устанавливающее прием и передачу сигнала. ПЕРЕДАЧА «ТОЧКА-ТОЧКА». Позволяет передавать сигналы между двумя компьютерами или между компьютером и другим устройством (принтер,сканер). Трансивер для беспроводной передачи данных иногда называют точкой доступа. В беспроводных сетях чаще всего используют переносные или настенные трансиверы. Они устанавливают радиоконтакт между переносными устройствами. Однако такую сеть нельзя назвать полностью беспроводной из-за подключения трансиверов. Технология тока точка основана на последовательной передаче данных и обеспечивает высокоскоростную и безошибочную передачу данных применяя радиоканал точка точка а также проникновении сигнала через стены и перекрытия. ИНФРАКРАСНЫЕ И ЛАЗЕРНЫЕ БЕСПРОВОДНЫЕ ЛВС. Инфракрасные ЛВС в качестве среды передачи данных используют инфракрасные излучения. В подобных системах надо генерировать очень сильный сигнал. Этот способ обеспечивает большую скорость передачи данных т.к. инфракрасный свет имеет большой диапазон частот. Инфракрасные сети нормально функционируют на скорости 10Мбит/с. Разлдичают 4 типа инфракрасных сетей: - сети прямой видимости, между приемником и передатчиком (икапорт в телефоне); - сети на рассеянном излучении, сигнал отражается от стен, потолка и достигает приемника, дальность сети до 30 метров, скорость низкая; - сети на отраженном излучении, оптические трансиверы  от рабочих станций передают сигналы в определенное место, откуда сигнал транслируется к приемнику; - широкополосные оптические сети, предоставляют услуги соответствующие жестким требованиям мультимедийной среды и не уступают кабельным системам. Достоинство инфракрасных сетей: скорость; удобство использования. Недостатки: трудность передачи сигнало более 30 метров; подверженность помехам со стороны сильных источников света. Лазарная технология похожа на инфракрасную. источником среды передачи данных является лазерный луч. ЛВС С РАДИОПЕРЕДАЧЕЙ ДАННЫХ. При одночастотной радиопередаче приемник и передатчик настраивают на одну частоту. Прямая видимость не обязательна. Площадь вещания 4,5 кв.км. при этом методе сигнал высокой частоты способен проникать через металлические или железобетонные конструкции. При радиопередаче в рассеянном спектре сигналы передаются в некотором диапазоне частот. Доступные частоты делятся на каналы. Каждый канал - некоторый интервал частот. Адаптер в течение некоторго промежутка времени настроен на один интервал затем переключается на следующий и т.д. причем переключение всех компьютеров сети должно происходить синхронно. Сети основанные на такой передаче данных работают со скоростью до 2х Мбит/с на расстоянии 3,2 км на открытой местности и соскоростью до 2х Мбит/с на расстоянии 120 метров внутри здания. МОБИЛЬНЫЕ СЕТИ. В беспроводных мобильных сетях в качестве среды передачи выступают мобильные телефонные системы и общественные службы. Существует 3 способа организации таких сетей: - на пакетном радиосоединении; - сотовые сети; - микроволновые системы. Имея при себе переносной компьютер при помощи мобильных сетей возможно обмениваться файлами, электронной почтой и др.информацией, но такая система довольно медленна. Скорость передачи данных от 8 до 34 Кбит/с. Для подключения такого способа передачи данных используют сетевые адаптеры использующие технологию сотовой связи. Небольшие антенны переносных ПК связывают их с окружающими радиотрансляторами. При пакетном радиосоединении данные разбиваются на пакеты в которых содержатся: имя отправителя, имя получателя, информация для коррекции ошибок и сами данные. Пакеты отправляются на спутник и со спутника транслируются в шировещательном режиме. Сотовые сети при передаче данных используют сотовые цифровые пакеты. Такие паекты работают по технологии сотовых телефонов. Данные передаются по существующим каналам для передачи речи в те моменты когда эти сети не заняты. Достоинства: быстрая переча данных. Микроволновые системы. Такая система включает в себя два радиотрансивера (приемник и передатчик) для генерации сигналов и две направленные антенны. Система работает в зоне прямой видимости либо через спутник. Микроволновая технология – самый распространенный способ передачи данных на большие расстояния.

19. Геометрическое моделирование. Представление геометрических объектов (точка, прямая, линия, плоскость, поверхность, фигура). Представление геометрических преобразований плоскости и пространства. Алгоритмы построения линий и поверхностей.

Рассмотрим линейное преобразование плоскости, т. е. уравнения с помощью которых некоторые точки плоскости (x, y) ставятся в соответствии точка (x”, y”) этой же плоскости. Итак, x”=A11x+A12y+A13 ; y”= A21 y+A22y+A23.

Добавим к этим уравнениям еще одно 1= A31 x+A32x+A33. это уравнение будет справедливым, если A31 =A32 =0 и A33=1. Теперь систему уравнений м/о представить в матричной форме.

Эта матрица квадратная. Кривая на плоскости задает зависимость м/у значениями x и y координат. Эта зависимость называется функциональной. М/о задавать значения точек с помощью пар. Прямую м/о задать уравнением Ay=Bx+C. С др. стороны это же уравнение м/о задать формулой двух неизвестных . Называется функциональной формулой прямой. Точка принадлежит прямой тогда и только тогда, когда =0. Т. о. вся плоскость оказывается разделенной на три области:

Область, в которой >0 2)Область, в которой < 0 3)Прямая, т. е. =0.  единственен. Запишем что =Bx+C-Ay. Область положительных значений совпадает с областью отрицательных значений предыдущей функции и наоборот. Функциональное представление прямой позволяет не только указать с какой стороны от прямой лежит эта точка, но и вычислить расстояние от этой точки до прямой. По определению область называется выпуклой, если отрезок, соединяющий любые две точки этой области, целиком принадлежит этой области. Рассмотрим выпуклый n-угольник, который задан координатами вершин в порядке обхода по и против часовой стрелки. Две соседние точки определяют прямую, которую можем записать в виде функциональной зависимости. Следовательно, точка лежит на прямой, и подстановка координат даст или положительное, или отрицательное число в зависимости от направления обхода прямоугольника.

Перенос, растяжение, поворот вокруг точки плоскостей

Перенос Точка (x, y) переносится в точку(x”, y”) путем перемещения на вектор (tx, ty), т. е. x=1*x+0*y+tx; y”=0*x+1*y+ty. Этому преобразованию

соответствует матрица

Растяжение. При таком преобразовании координата x уменьшается на cx, а y*cy. x”=cx*x+0*y+0; y”=0*x+cy*y+0

Матрица имеет вид:  обычно cx, cy положительны, но они могут быть и отрицательными. Например, если cx=-1, cy=1, то имеем симметрию относительно cy.

Вращение относительно начало координат. Будем поворачивать на угол  против часовой стрелки (положительное направление):     

Матрица:

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

Над трехмерными векторами можно производить две операции: умножать на число - К * (X,Y,Z) = (K*X,K*Y,K*Z); складывать - сумма векторов Р1=(X1,Y1,Z1) и Р2=(X2,Y2,Z2) есть вектор (X1+Х2, Y1+Y2, Z1+Z2), то есть при сложении векторов соответствующие координаты складываются.

Определение прямой. Теперь мы определили прямую, проходящую через две точки (X1,Y1,Z1), (X2,Y2,Z2), что можно сделать, задав уравнение этой прямой: (X-X1)*(Y2-Y1)=(Y-Y1)*(X2-X1), (Y-Y1)*(Z2-Z1)=(Z-Z1)*(Y2-Y1), (Z-Z1)*(X2-X1)=(X-X1)*(Z2-Z1). Хотя здесь приведены три уравнения, их решение определяет прямую, а не единственную точку, что связано с тем, что эти уравнения линейно зависимы так, что, задавая одну из координат, можно однозначно получить значение двух других. Так же, как и в случае двух измерений, это не единственный способ задавать прямую. Существует еще параметрический способ задания прямой, проходящей через точки Р1 иР2: P(M) = (1-M)*P1 + M*P2, или I P(M)=( (1-M)*X1+M*X2, (1-M)*Y1+M*Y2, (1-M)*Z1+M*Z2 ), где M - действительный параметр.  Параметрический вид прямой в точности совпадает с двумерным случаем. Если M = 1 дает точку Р2, а М = 0 - точку Р1. Мы можем записать параметрическое уравнение кривой в таком виде: P(M) = Р1 + M*(P2 - P1).  вектор Р1 называется базовым вектором, а вектор (Р2-Р1) - направляющим вектором. Определим норму вектора (которую так же называют модулем вектора, его длиной), обозначаемую ABS(P), как расстояние от точки, определяемой вектором, до начала координат: ABS(D) = SQRT(X^2 + Y^2 + Z^2).  Если вектор D=(X,Y,Z) составляет с осью X, Y, Z углы ТЕТx, TETy и TETz , то X:Y:Z = COS(TETX) : COS(TETY) : COS(TETZ) -/ Координаты единичного вектора назыв. направляющими косинусами.

Определение плоскости.   Точки плоскости задаются уравнением: N*X=K, где К - скаляр, а N - вектор, перпендикулярный плоскости Если А принадлежит плоскости, то N*A = К, заменяя К в предыдущем уравнении получим: N*X=N*A, N*(X-A)=0. откуда N*(X-A)=0 откуда (X-A) принадлежит пл-ти откуда N-норм-ый вектор к плоскости.

Функциональное представление поверхности.  Мы видели, что в двумерном случае кривые можно задавать с помощью функциональных зависимостей. Этот метод можно использовать для исследования поверхностей в трехмерном пространстве. Простейшей формой поверхности является плоскость с нормалью N = (N1, N2, N3), которая, как мы знаем, задается уравнением:  N*X-K = N1*X+N2*Y+N3*Z-K = 0, которое можно переписать в функциональной форме:

F(X)=F(X,Y,Z)=N1*X+N1*Y+N*Z-K=N*X-K, где X=(X,Y,Z).

Это простое выражение позволяет нам разбить пространство на три множества: множество точек Х таких, что F(X) < 0 - отрицательная область, множество точек X, лежащих на плоскости, таких, что F(X) = 0, и множество точек Х таких, что F(X)>0 - положительная область. Если поверхность разбивает пространство на две связные области (область называется связной, если любые две точки области можно соединить кривой, целиком лежащей в этой области), то эти области можно отождествлять с областью положительных и отрицательных значений. Следует иметь в виду, что многие поверхности делят пространство на большое число компонентов. Примером такой поверхности является поверхность, задаваемая уравнением:

F(X,Y,Z) = COS(Y) - SIN(Х^2+Z^2). Однако имеется ряд поверхностей, удовлетворяющих требуемому условию. Примером такой поверхности является сфера: F(X)=R^2-ABS(X)^2 .  Или по компонентам: F(X,Y,Z)=R^2-X^2-Y^2-Z^2 .

Если F(X) = 0, то Х лежит на сфере, если F(X)<0, то точка лежит вне сферы, если F(X)>0, то точка лежит внутри сферы. Функциональное представление поверхностей весьма полезно при нахождении точек пересечения поверхностей. Однако это представление особенно ценно при выяснении того, лежат ли две точки Р и Q по одну сторону от поверхности. Для этого достаточно сравнить знаки F(P) и F(Q): если они одного знака, то точки Р и Q лежат по одну сторону от поверхности, а если разного - то по разные, что означает, что любая кривая, соединяющая Р и Q, пересекает поверхность хотя бы в одной точке. Ниже приведен пример, иллюстрирующий вышесказанное.

20. Алгебра высказываний. Нормальные формы. Совершенные нормальные формы. Теорема существования нормальной формы. Приложение алгебры высказываний к логико-математической практике.

Алгебра выск. – это раздел матем., изуч выск-я, рассм. со стороны их логич. зн-й (ист-ти или лож-ти) и логич. операций над ними. Алгебра выск. возникла в середине ХIХ века в трудах англ. матем. Буля. Высказывание – повествовательное предложение, кот. либо ист., либо ложно. Существует 5 видов логических операций. Отрицание выск. А – выск. А, кот ист. ттт, когда А – ложно. Конъюнкция (дизъюнкция) выск. А и В – новое выск. АВ (АВ), ист. ттт, когда А и В – ист (ложны). Импликация – выск. АВ, ложное ттт, когда А – ист., В – ложно. Эквиваленция – выск. АВ, ист. ттт, когда оба приним. одинак. зн-я. Переменные вместо которых можно подставить высказывания называют позициональными или переменными высказываниями.

1. Всякая пропозициональная перем. есть ф-ла.

2. Если А и В – ф-лы, то А, АВ, АВ, АВ, АВ – ф-лы.

3. Других ф-л нет. классификация формул алгеб.выс-й:1. Ф-ла F(x1xn) наз-ся выполнимой (опровержимой) если существует ее истинная (ложная) конкретизация. 2. Ф-ла F(x1xn) наз-ся тавтологией или тождественно истинной (ложной) тавтологией, если любая ее конкретизация истина (ложна). Две формулы F(x1xn) и G(x1xn) будем наз-ть равносильными, если для любых конкретных высказываний А1 …Аn их конкретизации совпадают, т.е. .

Т1. Две формулы F и H равносильны формула FH является тавтологией. Одной из равносильных формул является нормальная форма. Конъюнктивным одночленом от перем. x1xn наз-ся конъюнкция этих перем. и их отрицаний. Дизъюнктивным одн-ном от перем. x1xn наз-ся дизъ. этих перем. и их отрицаний. ДНФ от перем. x1xn наз-ся дизъ. конъюнктивных одн-в от этих перем. КНФ от перем. x1xn наз-ся конъ. дизъюнктивных одн-в от этих перем. Очевидно, что у данной формулы F существует неограниченно много как дизъюнктивных, так и конъюнктивных нормальных форм. Одни из них более громоздкие и сложные, другие – более простые. Среди множества дизъюнктивных (конъюнктивных) нормальных форм, которыми обладает данная формула, существует уникальная форма – единственная для данной формулы.

Конъюнктивный (дизъюнктивный) одночлен  наз-ся совершенным, если в нем каждая переменная встречается только один раз, с отрицанием или без. ДНФ наз-ся совершенной, если все конъюнктивные одночлены совершенны. КНФ наз-ся совершенной, если все дизъюнктивные одночлены совершенны.

Т1. Для любой нетождественно ист. ф-лы алгебры выск. сущ-ет единств. равносильная СКНФ.

Т2. Для любой нетождественно лож. ф-лы алгебры выск. сущ-ет единств. равносильная СДНФ.

Приложение. АВ – прямая т-ма. ВА – обратная. АВ – противопол. ВА – противопол. к обратной. Способы док-ва т-м:

1. От прот. АВА.

2. Метод приведения к абсурду. АВ(СС).

3. Правило силлогизма. Надо найти такое С, чтобы (АС) (СВ) – выполн.

21. Классификация ППО. Табличная организация информации. Табличные модели. Табличные процессоры.

ППО - это часть ПО, пред-ная д/ того, чт. обеспечить примен-ие ВТ в разл. сферы деят-ти ч-ка. Стр-ра и прин-п постр-ия ПП зависит от ЭВМ и ОС, в рамках кот. она будет функц-ть. ПП реал-ся на конкр языке прог-ия. Внаст. время предл-ся разл. ППП, автомат-щие сферы чел. деят-ти (редакторы, эл. таб , банки дан., информ-но – поисковые сис-мы, мат. прог-мы, эксперт. сис-мы).

ППО: универсальн. и специализир-ое. УППО: сис-мы обр-ки текстов, ср-ва машин. графики, СУБД, ср-ва обр-ки эл-ных таб., интегрир. пакеты. Эти прог.ср-ва не привязаны к к.-л. предм. обл-ти.=> возм-ть исп-ть их в разл. обл-тях. Особ-ти разраб-ки- отсут-ие конкр. заказчика. УППО д\б мобильным, легко адаптируемым к разл. моделям ЭВМ, просты в освоен. и эксплуат-и.

СППО: расчит. на конкр. группу польз-лей, тесно связ с опред. предм. обл-ю; оно д/б надежным, корректным, соотв-ть спец-ке условий экспл-ции. Тираж-ие возм-но , но в значит. меньших масштабах.Кним относ-ся: сис-мы автомат-го проект-ия, банковские фин. сис-мы, сист. управл-ия произв-вом, бух. учета, эксперт. сис-мы д/ конкр. зад., мат. пакеты и др. Выд-ют еще уникальное ППО- разраб. по инд.. заказу, исп-ся для науч. и инж.. расчетов, созд сис-мы иск. ител-та.

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

Под электронными таблицами будем понимать ПС обработки крупноформатных электронных динамических таблиц. Средства данного типа обрабатывают таблицы, состоящие из строк и столбцов, на пересечении которых располагаются клетки. Каждая клетка такой таблицы может содержать числовое значение, формулу или текст. Клетки идентифицируются именами, состоящими из номера строки и номера столбца, например, A55,G50,S3 и т.д. Значение в числовой клетке таблицы может быть записано или вычислено по ассоциируемой с данной клеткой формуле; в формуле могут присутствовать ссылки на другие клетки таблицы. Каждый раз при изменении значения в клетке таблицы в результате записи в нее нового значения с консоли ЭВМ, перевычисляются и значения всех тех клеток, которые содержат величины, зависящие от изменяемой клетки. Возможность запоминания текста в привязке к клеткам таблицы используется для присваивания заголовков столбцам, названий строкам и т.д. Электронные таблицы, в частности, весьма удобны для реализации на ПК, поддерживающих режим быстрого и гибкого манипулирования цветными изображениями на экране монитора.

Общей характерной чертой всех электронных таблиц является использование экрана в качестве окна обзора таблицы целиком либо по выбранным ее участкам; если число строк и столбцов слишком велико, то окно обзора можно перемещать по таблице по горизонтали и вертикали, обозревая ее невидимые части. Для изменения какого-либо значения достаточно поместить курсор в соответствующую клетку таблицы, визуализируемую на экране, и записать с консоли в нее новое значение. При этом, обеспечиваются хранение в памяти ПК и просмотр на экране монитора таблиц большой размерности; размещение крупных работ (макросов), содержащих ссылки на другие клетки документа и встроенные функции; отображение на экране значений, вычисляемых по формулам, хранящимся в клетках документа; автоматическая корректировка результатов документа при изменениях содержимого клеток, на которые в формулах имеются ссылки; графическое отображение информации и т.д. Электронные таблицы оказываются весьма эффективным способом обработки различного рода информации, которую можно представлять в табличной форме (научная, деловая, коммерческая и т.д.). Среди средств данного типа наиболее известными и популярными являются пакеты Lotus 1-2-3, Quattro Pro [17,18], SuperCalc и Ms Excel

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

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

Пусть некот. ф-ция задана таблично (n+1) знач.: (x0,y0),(x1,y1),…,(xn,yn). Треб-ся найти ф-лу f(x) такую, что yi=f(xi), где i=0,n. В данной постан-ке з-ча неопред., т.к. реш. неединс-но. Для единст-ти реш., выбир. конкрет. класс ф-ций (показат., log, и т.д.). Чаще всего реш. ищут в классе многочлен. и формулир. з-чу т.о.: по (n+1)-точке построить многочлен n-ой степ. y=Pn(x) такой, что yi=Pn(xi). Процесс нахожд. реш. наз. интерполив-ем, ф-ция интерпол-ной, h=xi-xi-1-шагом инт-ия точки yi,xi-узлами интер-ния. Если строится многоч., говорят о параболич. интерпол-нии. Если h=const для i=0,n – узлы наз-ют равноотстоящими.

I. Интер-ный многочлен Ньютона для ф-ий с равноотс. узлами. Пусть даны (n+1)-точка и причем. xi+1=xi+h=x0+ih; для i=0,n. Построим многоч. n-ой степ.т/что Pn(xi)=yi. Реш. б/м искать в виде: Pn(x)=a0+a1(x-x0)+…+an(x-x0)(x-x1)…(x-xn-1). Найд. коэф-ты ai, i=0,n; для этого б/м подст-ть посл0но в выражен. вместо x знач. x0,x1,…,xn. Положим x=x0 => a0=y0, положим x=x1 => a1=(y1-y0)/hy0/h, положим x=x2 => a22y0/2h2 и т.д. Т.О.: Наз. ф-лой интерпол-ния вперед (пригодна для вычисл. точек, лежащ. в нач. таблицы). Для вычис знач. в точках, лежащ. в конце таблицы использ. 2-ой интерпол-ый многоч. или ф-лу интерпол-ия назад:

II. Интерпол-ый многоч. Лагранжа для ф-ций с неравноотст. узлами. Введ. вспомог. ф-ию: Gi(x)-есть многочлен n-ой степ., причем

Рассм-м сумму:

нетрудно видеть, что Ln(x)-многоч. n-ой степ., причем Ln(xi)=yi, т.е. Ln(x) есть интерпол-ный многоч. наз. многоч. Лагранжа.

23. Понятие типа данных. Простые (базовые) типы данных. Ссылочный тип. Структурированные типы данных (массивы, записи, множества, файлы). Переменные. Область видимости переменных.

Суть всех алгоритмов и комп-х программ состоит в том, что они описывают преобр-ние нек. начальных данных в конечные. Какие-то данные алгоритма (программа) м. использовать как промежуточные. Тип данных - множество величин, объединенных определенной совокупностью допустимых операций. Т.Д. разделены на 2 важные группы: простые и структурированные. переменная простого типа м. хранить единственное значение. Структ-нный набор данных – это Т.д., который строится, исходя из конечного набора базовых типов с помощью операций. Знание типа переменной существенно для понимания алгоритма. Каждая из переменных программы предназначена для хранения некоторых значений, а каждый тип данных требует для своего хранения определенное количество элементов памяти. Чтобы распределить память для хранения значений переменных, компилятору необходимо знать диапазоны их значений. Все данные, для которых допустим определенный набор компьютерных операций называется базовым. Во многих процедурных ЯП базовые типы – это множества целых чисел, логических значений, конечных приближений вещественных чисел. Например в паскале базовыми явл-ся: integer, real, char, Boolean.

Базовые (простые) Т.Д. Для работы с данными этих типов  достаточно только указать тип. Идентификатор, код-ие и набор операций заложены в транслятор. Есть возм-сть увеличения набора операций (функции пользователя). Т.Д. "целое число". Знач-ми цел. типа яв-ся элементы подмн-ва целых чисел, границы кот-го зависят от реализации языка. Цел. числа в любой вычислительной системе д. представляться точно и все опре-нные над ними операции также д. выполняться точно. Над целочис-ми знач-ми в Пас. определены 5 основ. операций, рез-том кот-х явл-ся также цел. число. Этими операциями являются:(+),(-),(*), (DIV) и (MOD). К цел. величинам м.  применять операции отношения. Результат этих операций имеет логич. тип.К цел. величинам м. применять поразрядные операции and, or, xor и not. При выполнении этих операций каждая величина предст-тся как совок-сть двоичных разрядов. Действие выполняется над каждой парой соответствующих разрядов операндов: первый разряд с первым, второй - со вторым и т.д. Для работы с целыми величинами предназначены также и операции сдвига влево shl и вправо shr. Слева от знака операции указывается, с какой величиной будет выполняться операция, а справа - на какое число двоичных разрядов требуется сдвинуть величину. Вещественный тип (real). Областью значений типа real является определяемое реализацией языка подмножество всех дей-ых чисел. Особенность типа real связана со следующими обстоятельствами. Дейст. числа в ЭВМ обычно представляются в форме с плавающей точкой, т.е. внутреннее представление вещ. числа состоит из двух частей - мантиссы и порядка, и каждая часть имеет знак. Т.к. для изображения мантиссы отводится тоже фиксированное количество разрядов, то в машине точно м.б. представлено лишь ограниченное множество дей. чисел. Для хранения переменных типа Real компилятор Турбо Пас. выделяет 6 байтов в ОЗУ (1 бит для знака, 39 бит для мантиссы и 8 бит для порядка).

С вещ. величинами м. выполнять арифм. операции: (+),(-),(*),(/).К вещ. Вел-нам можно также применять операции отношения. Результат этих операций имеет лог. тип. Логический тип (boolean).В языке Паскаль имеется две константы лог. типа: true (истина) и false (ложь). Этот тип определен так, что false < true (упорядоченность!), причем эти лог. значения имеют порядковые номера 0 и 1 соот-но. Переменные типа Boolean, ByteBool занимают 1 байт памяти. Над данными лог. типа м. выполняться следующие операции: 1. Лог. not, "не"-является унарной операцией and -  or, хоr. 2. Операции сравнения (равно «=» и неравно «<>»).

Литерный тип (char) Знач-ем перем-й лит. типа явл-ся один символ из набора сим-ов, опред-ого конкретной реализацией.  В каждой отдельной версии языка Паскаль это множество д. отвечать следующим требованиям:- для любого набора символов все символы фиксированы и упорядочены; -включены все прописные буквы лат. алфавита от А до Z;-это мн-во упорядочено по алфавиту; -включены десятичные цифры от 0 до 9; это мн-во упорядочено по возрастанию цифр и связно; -если в реализации допускаются строчные лат. буквы от а до z, то они д.б упорядочены по алфавиту; -включены такие символы, как пробел, запятая, точка и др.; -отношение порядка между двумя символами мн-ва значений типа char д. б таким же, как и между их порядковыми номерами. Элементы мн-ва типа char считаются перенумерованными, начиная с нуля. Переменные этого типа занимают 1 байт памяти. Перечисляемый тип. Переч-я позволяют программисту описывать новые типы данных, значения кот-х опр-ет программист. Описание переч-мого типа состоит из списка его элементов, разделяемых запятыми, заключенного в круглые скобки. Каждый из элементов представляет собой уникальный идентификатор(var Yestaday, Today, Tomorrow: WeekDay;) Интервальный тип. Инт. тип представляет собой диапазон (интервал) значений какого-либо порядкового типа, называемого базовым. При описании инт. типа указываются наим и наиб значения диапазона значений, допустимых для этого типа. Мин-ное и мак-ое значение интервала разделяются знаком «..» (две точки). Переменная интер. типа имеет все свойства переменной базового типа. Поэтому все стандартны функции и операции определенные для базового типа могут применяться и к его отрезку, В Паскале исп-ся динамич стр-ры. Отводимая под них память наз-ся динамической. Ею м/б вся своб. память. Р-та с динам. объектами позв-ет: 1) занимать и осв-ть память во время р-ты программы, 2) обр-ся ко всей своб. памяти 3) созд-ть стр-ры перем. длины. Р-та с динам. вел-ми связана с исп-ем ссылочного типа (указатель). Указатель сод-ит адрес ячейки динамич. памяти, хранящей вел-ну опр-го типа. Сам указатель расп-ся в статич. памяти. Сами динам. вел-ны перем-ой не имеют. Ссылочные типы опр-ся в описательной части программы, в разд. type, var.

Структурированные типы данных (массивы, записи, множества, файлы)

Суть всех алгоритмов и комп-х программ состоит в том, что они описывают преобр-ние нек. начальных данных в конечные. Какие-то данные алгоритм м. использовать как промежуточные. Тип данных (data type) - множество величин, объединенных определенной совокупностью допустимых операций. Т.Д. разделены на 2 важные группы: простые и структурированные. переменная простого типа м. хранить единственное значение. Структ-нный набор данных – это Т.д., который строится, исходя из конечного набора базовых типов с помощью операций. Массив (array) – поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в М-е. Обычный прием работы с М.- выборочное изменение отдельных его компонент. Важной особенностью М-а является его статичность. М. д.б. описан в программе и его характеристики не м.б. изменены в ходе выполнения программы. Компонентами М-а м.б. не только простейшие данные, но и структурные, в том числе М-ы. Можно представить три способа отведения памяти под элементы. Первый способ заключается в том, что кол-во элементов М-а и способ их индексации фиксируются еще в момент написания прог-мы. Тогда объекты типа М-а всегда будут занимать одно и то же место в памяти. Второй способ отведения памяти заключается в том, что память под элементы М-а отводится индивидуально для каждого объекта типа М-а, причем кол-во элем-ов М-а м.б. вычислено непосредственно перед отведением памяти. В этом случае говорят о динамическом М-е. Третий способ заключается в том, что размер отводимой под М. памяти вообще не фиксируется и может изменяться по ходу работы прог-мы. Такие М-ы м. наз-ть М-ми с гибкими границами. Работа с ними требует постоянного перераспределения памяти под уже сущ-щие элементы либо хранения всех эл-тов отдельно друг от друга, что приводит к сильному замедлению работы при индексации. Для М-а Т определены следующие операции:-создание М-а Т, имеющего N элементов, значения кот-х еще не определены;-"чтение" элемента с заданным индексом i=l,2,....N, результатом кот-го явл-ся элемент T(i), имеющий этот индекс, а также исхный М Т;-"замена" элемента, массива с данным индексом i на данный элемент G в результате кот-ой получается новый М, отличающийся от исх-го наличием элемента G на i-ом месте (T(i)=G). Главной особенностью алгоритмов обработки одномерных М-ов явся то, что обработка М-ов д. производиться поэлементно. Записи. Запись (record) - это структура данных, состоящая из фиксированного числа разнотипных компонент, называемых полями З-и. Поле (field) - часть З-и, имеющая функционально самостоятельное знач-е и обрабатываемая в программе как отдельный элемент данных. Тип данных З используется для объединения в единый объект разнородной инф-ции. Доступ к любому полю З осуществляется по его имени. Над этим типом данных опр-ется единственная операция - выборка поля. При работе с одной единственной З (что бывает не часто) имя поля м. исп-ть как обычную "переменную, т.е. м. изменять значение поля с помощью операции :=. Если же данная З - лишь часть набора данных, то имя поля состоит из двух частей и называется составным именем поля. И З, и М обладаю общим свойством - произвольным доступом к компонентам. Множество (set) – совок-ть к.-либо объектов, однородных элементов,  объединенных общим признаком и представляемых как единое целое. Основ. Операц-ми над МН являются:1.Проверка принадлежности МН-у.2Добавление элемента.3.Исключение элемента. Для МНва резервируется в памяти блок примерно так же как это делается для стека или очереди. Однако вместо того, чтобы хранить элементы МНва в последовательных ячейках внутри блока, они случайным образом рассеиваются по всему блоку. Файлы. Ф - это структура данных, обладающая двумя особенными св-вами: 1. обычно она располагается на к.-нибудь внешнем устройстве хранения, и, следовательно, ее размер м.б. значительно больше, чем размеры других типов структур данных; 2. ее время жизни может значительно превышать время выполнения программы, создавшей ее. Наиболее распространенным типом Фов яв-ся последовательные Ф, но во многих языках также используются Ф прямого доступа и индексно-последовательные Ф. Две основные задачи, кот-е выполняют Ф, достаточно очевидны - это ввод и вывод инф-ции, Для ввода и вывода данные обычно предст-ся в символьном виде. Компонентами Фов в таком случае становятся отдельные символы, а сам Ф называется текстовым Ф. Основные операции над послед. Фми.1. Открытие. Операция открытия получает в качестве параметров имя Ф и режим доступа. Операция открытая запрашивает у операционной системы информацию о расположении и свойствах Ф, отводит требуемый объем памяти для буферов и устанавливает указатель текущей позиции перед первым компонентом Ф.2.Чтение. Операция чтения передает содержимое текущего компонента Ф в определенную переменную программы.3.Запись. Операция записи создает новый компонент в текущей позиции Ф и передает содержимое программной переменной этому новому компоненту.4.Проверка конца Ф. Операция чтения не м.б. выполнена, если указатель текущей позиции достиг конца Ф. Поскольку длина Ф не фиксирована, требуется проводить явную проверку на достижение конца Ф, чтобы программа могла предпринять соответствующие действия в этом случае. 5. Закрытие Ф. Когда обработка Ф завершена, его требуется закрыть. Обычно эта операция приводит к передаче сообщения операционной системе о том, что Ф следует отсоединить от программы и возможно, освободить область памяти, которая использовалась для обработки файла. Ф прямого доступа организован так, что возможен доступ к произвольному компоненту Ф так же, как, например, осуществляется доступ к элементам масс-ов или записей. Индекс, используемый для доступа к компоненту, обычно называется ключом и м.б. или целым числом, или каким-нибудь идентификатором. Индексно-последовательный Ф похож на Ф прямого доступа, с тем лишь отличием, что для него предусмотрена дополнительная возможность последовательного доступа к компонентам, начиная с произвольно выбранного. Обычно под графом понимают множество точек, называемых вершинами графа. Дерево – граф в котором каждый узел, кроме корневого, связан не более чем с одним элементом вышестоящего уровня. Вершины представляют данные, ребра – связи между данными.

24. Теория рекурсивных функций. Классы вычислимых функций. Примитивно рекурсивные операции.

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения f(n) на основе значений , подобно рассуждению по индукции.Чтобы вычисление завершалось для любого n, необходимо, чтобы для некоторых n функция была определена нерекурсивно (например, для n = 0,1). Вот пример рекурсивной функции, дающей n-ое число Фибоначчи:

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

Например, рекурсивния функция:

может быть переведена в замкнутую форму: . Замкнутая форма может быть найдена не для всех рекурсивных функций (соотношений). Для некоторых из них найдены лишь приближенные замкнутые формы. Некоторые рекурсивные соотношения, такие как факториал, считаются элементарными математическими операциями.

Рекурсивные функции играют важную роль в теории алгоритмов, так как многие алгоритмы имеют рекурсивную структуру.

Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса базовых примитивно рекурсивных функций и двух операторов (подстановки и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся.

К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:

Нулевая функция O — функция без аргументов, всегда возвращающая 0.

Функция следования S одного переменного, сопоставляющая любому натуральному числу x непосредственно следующее за ним натуральное число x + 1.

Функции , где , от n переменных, сопоставляющие любому упорядоченному набору натуральных чисел число xm из этого набора.

Операторы подстановки и примитивной рекурсии определяются следующим образом:

Оператор подстановки. Пусть f — функция от m переменных, а  — упорядоченный набор функций от nпеременных каждая. Тогда результатом подстановки функций gk в функцию f называется функция h от n переменных, сопоставляющая любому

упорядоченному набору  натуральных чисел число

.

Оператор примитивной рекурсии. Пусть f — функция от n переменных, а g — функция от n + 2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n + 1 переменной вида

;

Множество примитивно рекурсивных функций — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.

25. Линейность, ветвление и цикл. Их реализация в языках программирования и обобщения. Подпрограммы. Реализация подпрограмм в языках программирования. Рекурсия. Модульное программирование.

Баз. структура – осн структура в методе струк програм: следование, ветвление, цикл(Ц).Наиболее простыми по своей стр-ре явл-ся алгоритмы, в кот-х все операции выпол-ся однократно и последовательно в порядке их расположения в алг-ме. Такой порядок С наз-ся естественным. Алг-м с естественным порядком выполнения операций наз-ся линейным. Решение практ-х задач не ограничивается линейным алгоритмом, а предусматривает различные пути вычисления решения. Причем выбор того или иного пути определяется либо условиями задачи, либо результатами, полученными в процессе решения. Каждое из возможных направлений вычисления наз-ся ветвью; в зависимости от выполнения неко-го условия вычислительный процесс м. идти по одной или другой ветви. Алгоритм такого вычислительного процесса наз-ся разветвляющимся алгоритмом. Т.о., для разветвляющейся структуры также характерно однократное выполнение послед-ости операций, но состав этой послед-ти явл-ся результатами проверки некоторого условия, т.е. зависит от обрабатываемой инф-ии. При реш.задач табулирования (т.е. построения таблиц значений функции на мн-ве) и т.п. возникает необходимость многократного повторения однотипных действий при различных значениях параметров, определяющих эти действия. Алгоритмы, реализующие такие вычисления, наз-ся циклическими, а повторяющиеся участки вычислений - телом Ц. Любой цикл может содержать внутри себя один или несколько других Ц. Такая структура называется вложенными Ц. Охватывающие Ц. называются внешними, охватываемые -внутренними. В теории программ-я доказано, что для записи любого сколь угодно сложного алгоритма достаточно трех базовых структур: - С;-В-Ц

1)  Следование состоит из двух функциональных блоков S1 и S2, выполняемых друг за другом. При реализации данной конструкций в алг. языке или языках программ-я порядок выполнения команд (операций) соответствует или порядку их написания (ШАЯ, Паскаль), или команды нумеруются (Бейсик), что обычно характерно для неструктурированных языков программ-я.

2) Полная структура ветвления состоит из логического блока В и двух функциональных блоков S1 и S2. Условие должно быть таким, что на него можно ответить "да" или "нет". Если условие В выполнено, то выполняется блок S1, а если не выполнено, то - блок S2.

В Школьный Алгоритмический Язык на длину блоков S1 и S2 ограничений нет, в Бейсике S1 и S2 или одна команда, или имеется ограничение на общую длину команды. В Паскале ограничений на длину S1 и S2 нет, т.е. имеем полное соответствие баз. Стр-ре. Неполная стр-ра вет-я состоит из логического блока В и функционального блока S1, выполняемого при соблюдении условия В.

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

(в большинстве версий Бейсика эта конструкция не реализована). Цикл "до" выполняется аналогично, только условие проверяется после выполнения блока S1; повторение происходит в том случае, если условие В не соблюдено, т.е. повторение производится до соблюдения условия (поэтому этот тип цикл называют циклом "до"). В отличие от Ц "пока" блок S1 в Ц "до" всегда выполняется хотя бы один раз. В ШАЯ конструкция не предусмотрена, в большинстве версий Бейсика также отсутствует, в Паскале имеет вид: repeat S1 until В; Как для Ц "пока", так и для Ц "до" перед входом в Ц обязательно начальное присваивание, т.е. задание начальных значений тем переменным, кот-е исп-ся для управления кол-вом повторений Ц и для накапливания результата. Отметим следующую важную особенность базовых структур: каждая из этих структур управления имеет один вход и один выход. Отсюда следует, что у любой блок-схемы, составленной из этих элементов, также будет один вход и один выход.

Подпрограммы. Их реализ. в ЯП. Рекурсия, модул. пр-ние

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

В теле ф-ции имени ф-ции присв-ся нек-ое знач-ие, а в пр-ре то же самое знач-ие нужно передать по ссылке. В пр-ре нужно задавать тип передаваемого по ссылке пар-ра. В ф-ции этот тип зад-ся в загол-ке ф-ции. Вызов ф-ции осущ-ся внутри нек. выр-ия.

Определение рекурсии: - способ определения функции, при котором значения в каждой точке определяется через значения в предыдущих точках.

Рекурсия - определение некоторого объекта через себя. Таковыми могут быть числовые функции (n!), комбинаторные объекты (дерево, путь), геометрические объекты (кривая Пеано), определения в программировании (ЦБЗ, идентификатор, арифметическое выражение) и пр.

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


      
x1

X1=(x0)

       x0,

y=x

x=(x)

x1=(x0)

x2=(x1)

x3=(x2)

x1=(x0)

x2=(x1)

y=f(x)

  c   x2      x1       x0                b

a

фfgф

b:=x

a:=x

x:=(a+b)/2

X=(a+b)/2

  a,b,

   

    |x1-x0| >

x0=x1

x1=(x0)

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

 f(x)f(a)<=0

 

|a-b|>=2

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3  

Другие работы

це наука Планіметрія це Аксіома це Основні ф...


Завдання для підготовки до підсумкового тестування за І семестр Геометрія це наука Планіметрія це Аксіома це Основні фігури планіметрії це Два ку...

Подробнее ...

головном вставлении.


1й момент мехма родовумеренное разгибание головки. Большой сегмент при данном предлежанииокружность головки3435 см. По мере продвижения по родов...

Подробнее ...

Московский педагогический государственный уни...


Семенова РЕЙТИНГПЛАН по дисциплине История древнего мира 20132014 учебный год 1 семестр Специальность 050100. История Древнего Востока. История ...

Подробнее ...

на тему- l Перериванняr Виконав- студент гру...


Загальні відомості Переривання англ. При цьому виконання поточної послідовності команд призупиняється і керування передається обробнику перерива...

Подробнее ...