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

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смешанной стратегией S_A игрока А называется применение чистых стратегий A₁, A₂,..., A_m с вероятностями p₁, p₂,..., p_i,..., p_m причем сумма вероятностей равна 1: Смешанные стратегии игрока А записываются в виде матрицы

или в виде строки S_A = (p₁, p₂,..., p_i,..., p_m) Аналогично смешанные стратегии игрока В обозначаются: , или, S_B = (q₁, q₂,..., q_i,..., q_n), где сумма вероятностей появления стратегий равна 1:

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

Решение игры 2×2 допускает наглядную геометрическую интерпретацию. Пусть игра задана платежной матрицей Р = (a_ij), i, j = 1, 2. По оси абсцисс (рис. 3.1) отложим единичный отрезок A₁ A₂ точка A₁(х=0) изображает стратегию A₁, а все промежуточные точки этого отрезка — смешанные стратегии S_A первого игрока, причем расстояние от S_A до правого конца отрезка — это вероятность p₁ стратегии A₁, расстояние до левого конца — вероятность p₂ стратегии A₂. На перпендикулярных осях I — I и II — II откладываем выигрыши при стратегиях A₁ и A₂ соответственно. Если 2 -й игрок примет стратегию B₁, то она дает выигрыши a₁₁ и a₂₁ на осях I — I и II — II, соответствующие стратегиям A₁ и A₂. Обозначим эти точки на осях I—I и II—II буквой B₁. Средний выигрыш v₁, соответствующий смешанной стратегии S_A, определяется по формуле математического ожидания v₁ = a₁₁ p₁ + a₂₁ p₂ и равен ординате точки M₁, которая лежит на отрезке B₁ B₁ и имеет абсциссу S_A (рис. 3.1).

Рис. 3.1	Рис. 3.2

Аналогично строим отрезок B₂B₂, соответствующий применению вторым игроком стратегии B₂ (Рис. 3.2). При этом средний выигрыш v₂ = a₁₂ p₁ + a₂₂ p₂ — ордината точки M₂. В соответствии с принципом минимакса оптимальная стратегия S*_A такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум. Ординаты точек, лежащих на ломаной (рис. 3.3 в примере 3.4.1), показывают минимальный выигрыш игрока А при использовании им любой смешанной стратегии (на участке B₁ N — против стратегии B₁ , на участке NB₂ — против стратегии B₂). Оптимальную стратегию S*_A = (p*₁ , p*₂) определяет точка N, в которой минимальный выигрыш достигает максимума; ее ордината равна цене игры v. На рис. 3.3 (пример 3.4.1) обозначены также верхняя и нижняя цены игры α и β.

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

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

 

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

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

 

|a-b|>=2e

f(x)f(a)<=0

a фfgф b:=x a:=x x:=(a+b)/2 X=(a+b)/2 a,b, e   |x1-x0| >e

x0 b

c x2 x1

=f(x)

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

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

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

y

x2=j(x1)

)     x1=j(x0)

y=x x=j(x) x1=j(x0) x2=j(x1) x3=j(x2

x0,e

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

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

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

М-д хорд.

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

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

найдем:

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

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

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

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

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

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

анал-но …

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

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

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

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

Применение

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

Типы беспроводных сетей

В зависимости от технологии беспроводные сети можно разделить на три типа:

локальные вычислительные сети;

расширенные локальные вычислительные сети;

мобильные сети (переносные компьютеры).

Промежуточным этапом от кабельных сетей к беспроводным является способ передачи «точка-точка». Трансивер-устройство для подключения компьютера к сети, т.е. устройство устанавливающее прием и передачу сигнала.

ПЕРЕДАЧА «ТОЧКА-ТОЧКА». Позволяет передавать сигналы между двумя компьютерами или между компьютером и другим устройством (принтер,сканер). Трансивер для беспроводной передачи данных иногда называют точкой доступа. В беспроводных сетях чаще всего используют переносные или настенные трансиверы. Они устанавливают радиоконтакт между переносными устройствами. Однако такую сеть нельзя назвать полностью беспроводной из-за подключения трансиверов. Технология тока точка основана на последовательной передаче данных и обеспечивает высокоскоростную и безошибочную передачу данных применяя радиоканал точка точка а также проникновении сигнала через стены и перекрытия.

МОБИЛЬНЫЕ СЕТИ.

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

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

Рассмотрим линейное преобразование плоскости, т. е. уравнения с помощью которых некоторые точки плоскости (x, y) ставятся в соответствии точка (x”, y”) этой же плоскости. Итак, x”=A₁₁x+A₁₂y+A₁₃ ; y”= A₂₁ y+A₂₂y+A₂₃.

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

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

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

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

Алгебра выск. – это раздел матем., изуч выск-я, рассм. со стороны их логич. зн-й (ист-ти или лож-ти) и логич. операций над ними. Алгебра выск. возникла в середине ХIХ века в трудах англ. матем. Буля.

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

Отрицание выск. А – выск. А, кот ист. ттт, когда А – ложно.

Конъюнкция (дизъюнкция) выск. А и В – новое выск. А В (А В), ист. ттт, когда А и В – ист (ложны).

Импликация – выск. А В, ложное ттт, когда А – ист., В – ложно.

Эквиваленция – выск. А В, ист. ттт, когда оба приним. одинак. зн-я. Переменные вместо которых можно подставить высказывания называют позициональными или переменными высказываниями.

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

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

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

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

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

ДНФ наз-ся с овершенной, если все конъюнктивные одночлены совершенны.

КНФ наз-ся совершенной, если все дизъюнктивные одночлены совершенны.

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

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

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

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

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

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

 

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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