Т1: представление знаний. Виды знаний - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Представление знаний 1 54.76kb.
Знаний. Модели представления знаний: логическая, сетевая, фреймовая... 1 137.62kb.
Самоанализ урока 1 98.42kb.
Самоанализ урока 1 24.8kb.
Квантификация знаний и умений 1 148.73kb.
Методические рекомендации по проведению Дня Знаний 1 71.61kb.
Новые ресурсы в экономике знаний 1 101.1kb.
Базы знаний, формы и методы представления знаний в разработке учебных... 1 108.23kb.
Образ художественной культуры Японии 1 63.44kb.
Отчет «Экономика знаний» 6 547.14kb.
Простые и составные числа 1 92.45kb.
Российская экономическая академия им. Г. В. Плеханова 1 88.73kb.
Направления изучения представлений о справедливости 1 202.17kb.

Т1: представление знаний. Виды знаний - страница №1/1

Т1: представление знаний. Виды знаний. Традиционно знания в ЭВМ представляются ввиде программ,но это эффективно лишь в случае если знания формализованы,т.е представлены в общей универсальной форме ввиде формул,общих утверждений,законов,чаще всего знания о предметной области в такой форме не представлены. В ЭВМ такие знания представляются ввиде баз знаний,а программные системы работающие на их основе назыв интеллектуальными. Знания делят на:* декларативные- описыв х-ки,св-ва,особенности объектов и явлений;* процедурные-описыв действия,операции,процессы. В основе реализации знаний ввиде баз знаний лежит опр-ая модель их представления.В настоящее время наиб широко использ 4 модели:1)логическая;2)продукционная;3)фреймовая;4)семантическая сеть.

(I)*1)логическая:основные особенности:любая модель представл знаний явл. спец-м языком с присущими ему опр-ным синтаксисом и семантикой.В любом языке должны быть опр-ны: а)мн-ва знаков кот допустимо использовать(алфавит);б)семантич правила опр-е слов ч/з знаковые последовательн и образов предложений из слов;в)семантич правила опр-е смысл знаков,слов,предложений. Конструкции языка для каждой предметной области кот мы намерены описать,устанавливаются свои языковые соответствия. Отношения кот описыв соотношени м/у понятиями предметной обл. и отдельными элементами языка,а также вопрос об их истинности образуют семантику языка.Установление этих отношений соответст-я назыв интерпретацией.Одной из осн. операций языка явл получение заключений из некоторой групы заданных утверж-й,такая операция назыв выводом.Резуль-том вывода явл опр-ное утверж-е приэтом оно д/б истинно при всех возможных интерпретациях в кот одновремен истины все исходные утверждения.Это означ что группа утверж-й явл посылкой и утверждение явл-щееся заключением д/б семантически согласованными.Отношения выраженые утверж-ями исходной группы могут быть самыми разными.В частности это могут быть утверж-я истиные при любых допустимых интерпретациях.Такие очевидно истинные утверж-я назыв товтологиями.Изначально в языке выделяется група основных не следующ друг из друга товтологии назыв аксиомами.В логике предикотов отчетливо проявляются все языковые аспекты:синтаксис,семантика и операции вывода.Язык опр-ный в системе логики предикатов назыв языком предикатов,построение этого языка проводится выбором из естествен-го языка тех его составных частей,кот не содержат внутри себя нечеткостей.

(II)Синтаксис. Определим мн-во знаков кот допустимо пользоваться в языке предикатов.Знак-условное обознач какого-либо понятия,объекта,связей,св-в предметной области.Знаки могут состоять как из одного символа(# А,В,С,Х), так и из последоват-ти символов(# НАЧАЛЬНИК).Это мн-во знаков как и в любом зыке назыв алфавитом.В нем присутствуют:1)знаки обознач объекты предметн области(const и переменные).const-обознач конкретные объекты предметн обл-ти,а переменные использ для для записи утверж-ний,относящихся ко всем объектам или к некоторым из них,когда неизвестно или неважно к каким именно(# ах+ву=с,авс-конкретные числа,х и у переменные);2)знаки обознач атрибуты,св-ва объектов,а также отношения истинности м/у объектами,эти знаки назыв предикатами или предикатн знаками; 3)знаки обознач функц-рование зависимости м/у объектами,эти знаки назыв ф-ями или функцион. знаками; 4)спец знаки кот использ для удобства записи(,())и формирования сложн утверж-й(#логич связки:и или).

Различия м/у знаками 2 и 3 групы оч существенно: знаки 2 групы(предикаты)обознач какие-либо отнош кот могут быть либо истинными либо ложными,а знаки 3-й групы(ф-и)таким отношением результатом кот явл-ся const.

Предикаты позволяют записать простейшее утверж-е относительно своих аргументов,рез-том кот явл-ся истина или ложь.Предикаты обознач прописными буквами.Предикат-это отбражение всех кортежей констант в мн-ве I={"истина","ложь"},др словами предикат-это полное отображ декартова произведения мн-ва всех const(обозначим его D)самого на себя(D*D...D)столько раз сколько аргументов из данного предиката в мн-ве I => если Pn предикатн знак от n аргументов,то можем записать: Pn:D в степени n->I;D в степени n-обознач декартово произвед.D*D...D n раз.

Ф-и обознач строчными буквами.Ф-я каждому кортежу const явл-щихся ее аргументами ставит в соответсв const,т.е полное отображ декартова произвед.D*D...D (стока раз скока аргументов) в мн-ве D(мн-во всех const)=> если fn:D в степени n->D.Аргументами м/б const,переменные,ф-и(с указанием аргементов).Как ф-и так и предикаты могут иметь разное кол-во аргументов,если у ф-и или предиката 1 аргумент,то ф-и или предикат назыв одноместные предикаты или одноместн ф-и, если 2 аргемента то двухместными,n аргументов то n местными.Обычно для представл-я знаний использ логика предикатов 1-го порядка,в ней в качестве аргументов предикатов недопускаются предикаты.Далее рассмотр язык предикатов 1 порядка: Важным понятием логики предикатов явл ТЕРМ. Это понятие охватывает весь спектр возможных аргументов предиката и опр-ся рекурсивно с помощью последоват правил: 1 правило)const – есть терм; 2 правило)переменная есть терм; правило 3) если fn- местный функционаяльн знак и t1,t2,t3…tn термы то f(t1,t2…tn) есть терм;правило 4)термы пораждаются конечным числом применений правил 1,2,3.

Любое конечное выражение,т.е состоящее из конечн числа знаков алфавита в языке предикатов назыв логическ(предикатной)формулой или просто формулой.Кроме понятия терм есть еще одно базовое понятие логического языка:атомарная формула(атом).Атом в разговорном языке соответств предложению наиболее простого вида нераспрастраненому предложению. Атомарной формулой назыв Р(t1,t2…tn), где Р-n местный предикатн знак, а t1,t2…tn- термы.Предикаты описыв св-ва объектов или отношения истинности м/у объектами.Отображ с помощью предиката осуществ в процессе интерпретации кот заключ в следующ: обозначим мн-во объектов предметн области R, а мн-во всех const обознач эти объекты D,тогда в процессе интерпретации каждой const имеющейся в формуле ставица в соответствие опр-й объект из мн-ва R для каждого функциональн знака, кортежу const кот явл его аргументами ставица в соответствие объект обознач-й const-той полученной в рез-те отображения: fn:D в степени n->D . Для n местного предикатн знака Рn кортежу const кот явл его аргументами ставица в соответствие рез!т оторажения: Pn: D в степени n->I. (I={«истина», «ложь»} х-щий истиность или ложность соответствующего отношения предметн обл-ти.В обычном языке из простых предложений,с помощью союза и др частей речи строяца более сложные конструкции,аналогично этому в алфавите логики предикатов есть знаки используемые с той же целью, с их помощью мона синтаксически правильно составить сложн утверд-е, кот также как и атом явл правильно построенной формулой.В языке предикатов описыв тока логич факты,поэтому для устранения избыточности опр-ся несколько основных знаков: # союзы и,но,однако логически действуют одинаково поэтому описыв одним и тем же языком.В логике предикатов выдел 2 группы рассмотрен-х знаков: 1)логические связки;2)кванторы. *1)логич связки использ для составления сложных утверд-й(формул) и задаюца с помощью след знаков ד-отрицание; Λ-конъюнкция;Ѵ-дизъюнкция;  - импликация; - эквивалентность. В процессе интерпретации уставления истинности утверд-я содержащего логич связки производица с помощью так называемой таблицы истинности…далее табличка и ее объяснение. *2) кванторы позволяют в языке предикатов формулировать какие-либо утверд-я.Они задаюца с помощью след знаков: ∀-квантор общности,использ след образом: (∀х)Р(х), т.е формула Р(х) явл истинной при любой интерпретации; квантор существования(  ) использ след образом: (х)Р(х) означает что сущ-ет хотя бы 1 интерпретации,при кот формула Р(х) будет истинной.

Переменные к кот в формуле следует принимать кванторы назыв связанными соответствующими кванторами.Несвязан переменные назыв свободными.Комбинирую имеющиеся в алфавите знаки можно опр-ть формулу удовлетвор синтаксич правилам,кот назыв правильно построенной формулой(ППФ). Применительно к естествен языку ППФ соответв предложению общего вида. ППФ опр-ся рекурсивно: правило 1)атом-есть ППф; правило 2)если F и G ППФ то ד F; F Λ G; F Ѵ G; F G; FG есть ППФ; правило 3)если F есть ППФ,а х связанная переменная в F,то (∀ х)F(х) и ( х)F(х) есть ППФ; правило 4)ППФ порождаются конечным числом применений правил 1,2,3. Эти правила опр-ют синтаксические правила кот должна удовлетворять ППФ.Правило 2 опр-ет правильное использов логических связок,а рпавило 3 применение кванторов,правило 4 обеспечивает запись составленных формул в кот логич связками связыв нетока атомарные формулы,но и составные.И кванторы применяются нетока к атомарным формулам но и к составным. Теперь синтаксис языка опр-н полностью. Мы имеем алфавит(const,переменные,ф-и,предикаты,логические связки,кванторы и специальные знаки( ; , ; ) и мн-ва синтаксич правил с помощью кот мона записать ППФ.



(III) Семантика. Установления соотве-я м/у элементами языка(const,переменными,ф-ями,предикатами и формулами)и элементами предметн области назыв интерпретацией. В языке предикатов такая интерпретац производица на основании строго установленных семантич правил. Они состоят из 2-х групп одна из кот вкл правила понимания знаков обознач имеющиеся в предметн обл-ти объектов и отношения м/у ними, а др правила понимания формул.Обозначим R мн-ва объектов предметн области. Интерпретация элементов алфавита опр-ся правилами включения знаков в алфавит: правило 1)для объектов из R задаюца обознач их const и переменные включаемые в алфавит; правило 2)для каждого функционального отношения м/у объектами предметн обл-ти опр-го на мн-ве n аргументов из R,т.е опр-го на декартовом произведении: R в степени n=Rx Rx…R n раз назначаеца в соответств n местный функциональный знак опр!й на декартовом произвед D в степени n,кот также вкл в алфавит; правило 3) каждому отношению истинности м/у n объектами из R назначаеца соответств n-местный предикатный знак, опр-ный на D в степени n и его значение истина или ложь после чего он вкл в алфавит.

Значение формул оцениваеца на основании след правил: правило 1) если F и G известны,то значения формул с логическими связками,т.е ד F; F ΛG; F Ѵ G; F G; FG оцениваюца по таблицам истинности; правило 2)если для всех const из мн-ва D формула F(x) оценена,как истина,то истинной явл-ся формула (∀ х)F(х); правило 3) если хотя бы для одной const из мн-ва D формула F(x) истинна то формула ( х)F(х) тоже истинна.



Формула истинная при всех возможных интерпретациях назыв общезначимой.Формула ложная при всех возможных интерпретациях назыв противоречивой. Если значения формул совпадают при любой интерпретации то они назыв эквивалентными. Важнейшей ф-ей языка явл возможность получения значения логических формул истинность кот неясна и используя для этого заранее оцененные формулы,т.е получение заключений из известных формул явл-хся посылкой.Такое опр-е значения формулы производица в процессе интерпретации и она не должна противоречить имеющимся знаниям о предметной обл. В языке предикатов семантич корректность опр-ся след образом: пусть имеется мн-во формул , если сущ-ет интерпретация при кот формулы мн-ва принимают значение истины,то интерпретация назыв моделью мн-ва формул . Модель может быть неединствен. их может быть мн-во. Если для всех моделей мн-ва  формула G равна истине,то эта формула назыв логическим заключением в .Факт реализации такого логического заключения записыв след образом: = G. Т.О если истинность формулы G неистинна и это надо установить, исходя из мн-ва формул , то процедура получения логического заключ с помощью интерпретации,состоит в выявлении всех моделей для  и проверке для каждой из них истинности формулы G, такой метод назыв методом индукции. Аксиомы- утверждения невыводимые одна из др, кот истинны по опр-ю. Аксиомы могут быть истинными для любой предметн обл.

(IV) правила вывода: в языке предикатов процесс логич вывода явл-ся док-вом теорем, а формулы выводимые в рез-те этой процесса назыв теоремами. Правилом вывода назыв процедура представленная в опр-ной форме,кот из мн-ва  автоматически выводит такую формулу G, что справедливо “все модели для формул из  явл моделями и для G ”. Следовательно любое правило вывода гарантирует что если формулы из  истинны, то и формула выведенная из этого мн-ва тоже будет истинной. Формула G назыв логическим следствием формул G1,G2,.. Gn полученные применением некоторым правилом вывода, если для каждой интерпретации истинность формулы G1ΛG2 Λ... Λ Gn влечет за собой истинность формулы G. Получение формулы G примением конечного числа раз правил вывода к заданному мн-ву формул  назыв дедукцией и записыв ввиде: - G. Т.О как метод индукции так и метод дедукции сущ-ет для одной и той же цели – получение новых формул из имеющихся, истинных при тех интерпретациях что и формулы посылки, т.е получение новых знаний.Однако различие м/у ними оч существенно. Метод индукции состоит в том что с помощью интерпретации выявляются все модели для  и для каждой из них проверяется истинность формулы G.Этот метод полезен в том сл-е если кол-во таких моделей ограничено и эффективен када их немного. Кроме того метод индукции предполагает что формула G известна и мы проверяем лишь семантич согласованность с посылкой. Метод дедукции обеспечив формальный вывод( с помощью правил вывода) формулы G из мн-ва заранее заданных формул , при этом он гарантирует, что выведенная т.о формула будет истинна при любых интерпретациях явл-хся моделями для  независимо от их кол-ва. Формула дедуктивно выведенная из  может быть заранее неизвестна.

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

(Т2)Продукционная модель. Этот способ основан на представлении знаний ввиде мн-ва так называемых продукций(правил). Правила обеспечив способ представления рекомендаций,указаний или стратегий. Продукция выражается ввиде конструкции: ЕСЛИ_ТО_ и представл собой пару “ситуация-действие”, “посылка-заключение”, “причина-следствие” итд. В частном сл-е если слева и справа логич утверж-я то продукция близка по смыслу импликации. Продукция обознач знаком сиквенции (). Базы знаний построенные на основе такой модели назыв продукционными.А програм системы обработки знаний представленные в такой модели назыв продукционными системами.Основной проблемой продукц систем явл-ся скорость поиска необходимой продукции в мн-ве продукций и время затрачиваемое на проверку выполнимости условий, поэтому при > кол-ве продукций с такой базой знаний стараюца реализовать различные способы ускорения этих процессов.В продукцион модели предметные знания представл мн-вом продукций,кот проверяются на мн-ве фактов х-щих текущую ситуацию.Информацион база в таких системах сост из базы фактов(БФ) и базы правил(БП). В БП содержится мн-во продукций,а в БФ помещаются исходные данные,а также рез-ты промежуточных и окончательных расчетов.В продукцион систем ах реализ-ся 2 механизма логического вывода:* прямой и * обратный вывод. При прямом выводе поиск инфы происходит в направлении секвенции разделяющей левые и правые части продукции. Система использует инфу из левых частей,чтобы получить инфу из правых частей.Процесс начинаеца с запроса к пользователю об известных ему фактах,эти факты помещаюца в БФ, затем система обращаеца к БП и производит поиск такой продукции кот может быть выполнена.Найденная продукция выполняеца и полученные факты добавляются в БФ.Затем система опять ищет в БП такую продукцию кот может быть выполнена итд.Процесс заканчив в том сл-е если в БП нет такой продукции кот может быть выполнена. При обратном выводе система начинает с опр-я того что необходимо получить, затем происходит проверка выполнения тех продукций в правой части кот имеют требуемый факт. Процесс начинаеца с выяснения у пользователя какой факт надо установить или получить,затем система обращается к БФ опр-ют имеются ли в ней данный факт,если он есть то процесс завершается, если его нет в БФ то система обращаеца к БП и производит поиск такой продукции в правой части кот имеется требуемый факт, затем проверяеца может ли быть выполнена найденная продукция,если да то процесс завершается. В противном сл-е требованными фактами считать те кот указаны в левой части продукции, процесс заканчивается если требуемые факты установлены или в БП нет продукций с помощью кот их можно установить.

(Т3) Семантическая сеть. (I)семантическая сеть общего вида:

семантич сетья назыв модель представл знаний, ввиде графа, с помеченными вершинами и дугами(ребрами).В семантич сети общего вида(n-арная сеть) вершинами сопоставляются понятия предметн обл,а дугами бинарное отношение существующее м/у этими понятиями.в семантич сети выделяют 3 типа вершин: 1)вершины-понятия. Каждая такая вершина изображается кругом, соответств опр-му элементу из W и отмечено его знаком из мн-ва Х; 2)вершина-отношения.Каждая вершина этого типа изображ овалом, соответствует какому-либо отношению из мн-ва U и отмечено его знаком из мн-ва R; 3)вершины-связи. Каждая вершина этого типа изображ треугольником,соответствует конкретной реализации какого-либо отношения из мн-ва U и имеет метку однозначно идентифицирующую этот элемент.



Под конкретными реализациями какого-либо отношения может понимаца как отношение м/у интенсионалами объектов, так и отношение м/у их конкретными экземплярами. Каждая вершина-связь соединяется : 1)с вершиной-отношением дугой с меткой(is a-явл-ся); 2) с вершинами-понятиями дугами с метками указывающими роли кот играют в данной связи эти понятия. Иногда это номер соответствующей позиции в кортеже.Заметим, что дуга с меткой is a показыв обобщение и обеспечив наследование св-в от вершин-понятий к вершинам-связям.

(II)Бинарная семантическая сеть. Если в предметн обл. все отношения бинарны,то для представл знаний мона использ более простой вид семантич сети,кот назыв бинарной семантич сетью.Сеть представл собой граф с помеченными вершинами и дугами,кот вершинам соответствуют понятия(объекты,события)а дугам бинарное отношение сущ-ее м/у этими понятиями.В бинарной сети использ тока 1 тип вершины,вершины-понятия, кот отмечается соответствующими знаками из мн-ва Х.Дуги связывающие вершины отмеч знаками из мн-ва R.Семантич сети могут быть однородными и неоднородн. В однородн сети все дуги соответствуют одному и тому же отношению,поэтому дуги не отмечаюца.Такие сети использ для предметн областей,в кот мн-во отношений состоит из единствен элемента,т.е все объекты если и связаны то тока одним отношением.Бинарная семантич сеть может быть ориентированной и неориентированной. В 1 сл-е направление дуг определено, в неориентирован сети направления дуг не указаны.

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

(Т4)Фреймовая модель. Фреймовая модель ориентирована на такие значения в кот объект,явление описыв мн-вом х-к или св-в, приэтом в предметн обл-ти кол-во объектов сравнительно невелико,но описыв > кол-вом св-в или х-к. В этом сл-е база знаний состоит из фреймов, кажд из кот представл объект или явление,он состоит из частей(назыв СЛОТАМИ) в кажд из кот размещается х-ка или св-во объекта. Фреймы делят на группы основными из кот явл: 1)фреймы-описания(фреймы-структуры);2)ролевый фреймы(фреймы-роли). Во фрейме описании имена слотов это названия х-к,св-в.В ролевом фрейме в качестве имен выступают вопросительные фразы,ответы на кот явл значениями слотов.В качестве значений слотов м/б ссылки на др фреймы и др слоты.Если в общем выражении для фрейма убрать все значения слотов,оставив их имена,то получим конструкцию кот назыв фреймпротатит или фрейм-интенсионал. Фрейм с конкретными значениями слотов назыв фреймом-экземпляром или фреймом-примером.Для фреймовой модели разработан язык FRK.

(Т5)Алгоритмы. Алгоритм-это конечный свод правил позволяющий решать любую задачу из некоторого класса однотипных,при условии что исходные данные изменяются в заданных пределах.Алгоритм рассматрив как основа использования программных средств. Термин возник в матике в средние века от имени ученого аль Хорезми. Каждый из мн-ва алгоритмов снабжаеца именем,а шаги алгоритма обознач этим именем и порядковым номером шага.При описании действий использ спец знаки.Знак «  » обознач операцию замещения(действие кот необходимо произвести); Знак « = » означ условие кот необходимо проверить. В общем сл-е запись: переменная  формула означ что в соответствии с данной формулой д/б произведены вычисления.При текущих значениях входящих в нее переменных, после чего переменную стоящую слева от знака  надо заместить полученным значением. Когда несколько переменных надо заместить одним и тем же значением то мона использов сокращенную запись: mnr. Операция взаимного обмена значениями 2-х переменных записыв с помощью двунаправленной стрелки: mn.В настоящее время использ несколько способов описания алгоритомов,основными из кот явл: 1)словесно-формульный(пошагавый);2)структурный(ввиде блок-схемы).

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

(III)Структурное описание алгоритма. При структурном(в виде блок-схемы) описание алгоритма, он изображ ориентированной бинарной семантич сетью,в вершинах(блоках)записыв шаги алгоритма. Дуги показыв последовательность выполнения этих шагов,т.е соответствуют отношениям условного или безусловного следования.В блок-схеме присутствуют вершины разного типа,основными из кот явл: 1)вершины-начала и окончания(изображ овалами),у верщины начало нет входящих дуг,есть лишь одна исходящая,направленная к вершине с кот начинается алгоритм.У вершины-окончание нет исходящих дуг,и м/б несколько входящих; 2)вершины-действия(изображ прямоугольниками)соответствуют шагам в кот выполняются действия.Такая вершина может иметь несколько входящих дуг и тока 1 исходящую; 3)вершины-ввода,вывода(изображ параллелограммами) соответствуют шагам в кот выполняется ввод или вывод данных. Такая вершина может иметь несколько входящих дуг и тока 1 исходящую; 4)вершины-условия(изображ ромбами)соответствуют шагам в кот проверяются условия. Такая вершина может иметь несколько входящих дуг и обязательно не менее 2-х исходящих.Если условием явл логическое выражение,то исходящих дуг две: одна из них соответствует отношению следования при условии что проверяемое логич выраж истинно.Такая дуга отмечается меткой «да», др исходящая дуга соответствует отношению следования при условии что проверяемое логич выраж ложно,эта дуга отмеч меткой «нет»; 5)если у вершины несколько входящих дуг,то для их объединения можно использовать специальную вершину изображ кругом небольшого размера. Исходящая из нее дуга направлена к вершине имеющей эти входящие дуги. Блок-схема м/б краткой и подробной(укрупненной).В краткой в вершинах указывается лишь наименование и основная суть шагов. Далее алгоритм Евклида…В подробной блок-схеме в вершинах указыв полное описание шагов…далее блок-схема…

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



(IV)элементарные алгоритические структуры.

САМОСТОЯТЕЛЬНО!!!!!



(V)требования предъявляемые к алгоритму. Алгоритм это непросто последоват действий для решения той или иной задачи.Он должен удовлетворять след основным требованиям: 1)конечность(результативность);2)определенность;3)наличие входных и выходных данных. *1)последоват действий заданная алгоритмом должна заканчиваться получением результата после выполнения конечного числа шагов,этим алгоритм отличается от вычислит метода; *2) каждый шаг алгоритма должен быть точно определен, т.е действие кот необходимо выполнить должны быть строго и недвусмысленно определены для каждого возможного сл-я; *3)алгоритм должен обязательно иметь некоторое кол-вл входных данных,т.е величин заданных ему до начала работы эти данные берутся из конкретного мн-ва объектов,кроме этого алгоритм должен иметь одну или несколько выходных величин, получаемых в рез-те его выполнения.

Если для решения одной и той же задачи имеется несколько алгоритомов, то необходимо проводить сравнительный анализ алгоритмов для выбора наилучшего из них,при этом использ такие х-ки,как: 1)эффективность; 2) массовость; 3) время необходимое для выполнения алгоритма. *1)Эффективность означает что все операции алгоритма д/б как можно более простыми; *2)Массовость означ что алгоритм можно применить для решения мн-ва задач; *3)время выполнения алгоритма можно оценивать по-разному # представить числом указывающим сколько раз в среднем выполняется каждый шаг алгоритма.



РАЗДЕЛ: ПРОГРАММНЫЕ СР-ВА ИНФОРМАТИКИ:

(Т6)Виды и особенности программных ср-в:

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



(Т7)системное программное обеспечение.

  1. операц системы: 1.1)поколение операц систем.

Операс системы(ОС) подобны ЭВМ на пути своего развития прошли ч/з ряд радикальных изменений, так называемых поколений.В 1 ЭВМ ОС не было,пользователи писали программы непосредственно на машинном языке и имели полный доступ к аппаратным средствам.Каждая программа загружалась отдельно,после ее выполнения вручную производилась подготовка ЭВМ к выполнению след программы.

1 поколение(50-е г). Первые ОС были разработаны с целью ускорения и упрощения перехода от одной программы к дрДо их создания много времени терялось на в промежутках м/у завершение одной програмы и началом выполнения след.Первые ОС предусматривали объединение отдельных программ в группы,кот стали назыв пакетами.Каждая запущенная на выполнение программа получала в распоряжение все ресурсы ЭВМ,а после ее завершения управление ресурсами возвращалось ОС,кот приводила их в исходное состояние и обеспечивало ввод в оперативную память и запуск на выполнение след программы,такой режим управления программами получил название пакетная обработка.В ОС были включены стандартные программы ввода,вывода,чтобы пользователю не приходилось писать программы на машинном языке.

2 поколение(начало 60-х г). Основной особенностью ОС этого поколения была их нацеленность на увеличение объема работ за ед. времени. Такие ОС создавались, как системы пакетной обработки с так называемым мультипрограммным режимом управления программами.В то время для ускорения выполнения программ появились мультипроцессорные вычислит системы, в кот устанавлив несколько процессоров. Были созданы ОС,кот обеспечивали пользователя диалоговым режимом взаимод с выполняемыми программами.Суть этого режима заключается в том что в процессе выполнения программы на экран выводится различная информация(вопрос,рез-ты,итд).В ответ пользователь мог ввести какие-либо данные,ответить на вопрос. ОС кот управляли программами обеспечивая такой режим работы стали назыв системами с разделением времени,а режим управления программами получил назв режим разделения времени.Появились ОС обеспечив немедленную реакцию рпограмм на ввод инфы,такой режим был назван режимом реального времени.В отличии от режима разделения времени, при кот прерывание программы и передача ей вводимой инфы происходит тока по инициативе выполняемой программы,в данном режиме любая выполняемая программа прерывается сразу же,как тока начинаеца ввод инфы.В рез-те у пользоват возникает иллюзия мгновенной р-и программы на ввод инфы.ОС реальн времени использ для управления технологич процессами.

3 поколение(с сер 60 до сер 70г). ОС были многорежимными.Эти ОС стали мощной программной прослойкой м/у пользовательскими программами и аппаратными средствами.Они были столь громоздкими что для выполнения простейшей задачи пользователь был вынужден изучать сложные спец языки управления для описыв задания и требуемые для них р-сы.

4 поколение(с сер 70 г). Эти ОС обеспечивают значительно более простое взаимод пользователей с программами,работу в сети,защиту инфы от несанкциониров доступа.В эти ОС есть режимы пакетной обработки,разделение времени,мультипрограм режим.

(II.I.II) Основные особенности ОС.

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

1 задача обеспечив:*взаимод программ др с др;*работа с внешними устройствами;* появление сбойных и ошибочных ситуаций; * обработка прерываний связанных с реализацией мультипрограмн режима,режима разделения времени;*получение инфы о состоянии оборудования и его настройка;*распределен вычислит р-сов м/у программами.

2 задача:общее управление ОС осуществ командами ОС.Наиб распрастранение получили ОС семейств: UNIX и Microsoft Windows.

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

(II.I.III.)Cостав ОС. В составе ОС для ПВМ мона выделить часть кот явл-ся основой системы и назыв ее ядром.В состав ядра входят наиболее часто используемые компоненты,такие как ср-ва распределения основных ресурсов,управление файловой структурой,итд.Программы входящие в состав ядра при загрузке ОС помещаются в оперативную память,где нах-ся постоянно до окончания работы с ОС,такие программы назыв резидентными.

ОС для ПВМ содержат след компоненты: 1)BIOS нах-ся в ПЗУ системного блока.Основными ф-ями явл-ся: а)тестирование аппаратных ср-в при включении питания; б) выполнение обмена данными с внешними устройствами на уровне ввода,вывода; в)считывание с диска загрузчика ОС и передача ему управления; г)автоматич обнаружение и подключение вновь установленных устройств.

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

3)подсистема управления файловой структурой. Файлов система вкл программы и файлы данных необходимые для манипулирования файлами.

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

5)Подсистема управления драйверами и драйверы внешних устройств.Драйверы как и подсистема управления ими явл резидентными.


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

(II.II)вспомогательные(сервисные)программы. Эти программы использ для технич обслуживания,еще их назыв утилитами.

(II.II.I)программные упаковщики(архиваторы). Позволяют за счет спец методов создавать копии файлов меньшего размера обеспеч объединение копий в один файл-архивный. Архивный файл содержит оглавление и может состоять из нескольких частей.Разные архиваторы имеют примерно одинаковые возможности и не превосходят по всем параметрам. Rari,Zipi,Arji,Ace,Lha.Для архиваторов разработаны спец оболочки обеспечив их исправления ОС, #WinRar,WinZip.Название имееть расширение указыв на архиватор,как правило расширение совпадает с архиватором,но исключение Lha он создает архивные файлы Lzh.

(II.II.II)антивирусные программы. Вирус-это небольшая программа,кот может переписывать сама себя,а также выполнять различные нежелательные последствия.Программа в кот нах-ся вирус-зараженная.Как тока файл с такой программой запускается,на выполнение сначало идет вирус.Он находит и заражает др программы.Вирус может действовать так невсегда,а при выполнении опр-х условий.После выполнения вирус передает выполнение программе,кот работает как обычно.Вирус может испортить любой файл,но заразит лишь файлы опр-го типа: 1)файлы с программами(их название имеет расширение ЕХЕ,сom); 2)загрузчик ОС и главная загрузочная запись диска.Вирусы назыв загрузочными, при начальной загрузки ОС становится резидентным распрастр зараж загрузки записи.

3)создаваемые с помощью MS Word, MS EXCEL. Вирусы зараж такие файлы назыв макровирусы,они действуют када происходит работа с этими файлами; 4)почтовые сообщения.Вирус назыв почтовым.



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

1)детекторы или сканеры обслуживания;2)доктор или Фат-уничтож вирусов по возможности восстанавливающий программу; 3)ревизоры. Запоминают состояние системных областей дисков,некоторых программ и сранивает с текущим,при выявлении несоответствий сообщает и исправляет; 4)фильтры располаг резидентно, перехватывает управление и вирусов и сообщает пользователю.



(II.II.III)программа обслуживания дисков. Из таких утилит наиб часто использ след-ее: 1)программы-диагностики-проверяют работоспособность дисковых устройств; 2) программы-оптимизации-собирают все файлы в начале диска,перемещает все части каждого файла друг другу, за счет этого уменьшается число перемещений магнитный головок дискового устройства,в рез-те чего ускоряется доступ к инфе и снижается износ; 3)программы динамического сжатия.Динамически снижают инфу при записи на диск,а при считывании восстанавливают в первоначальный вид, за счет этого увеличив объем инфы кот мона записать на диск.

(Т8)Система программирования.

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

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

Для обеспечения этих этапов предназначены системы программирования.

(II)система программирован вкл в себя: 1)специализиров текстовые редакторы;2)трансляторы;3)редакторы связей;4)отладчики. Х-ка: 2)транслятор-это переводчик языка на кот написаны программы на машинный внутренний язык.Различают 2 вида:а)интерпретатор;б)компилятор.Х-ка:а)интерпретатор автоматизирует все этапы допуска программы на выполнение; *б)компилятор переводит текстовые программы модуля на машинный язык без его выполнения.В рез-те работы программы создается так называемый объектный модуль,этот модуль неготов к выполнению.

*3)редактор связей.В процессе работы выявляет ошибки неверно указанных связей м/у модулями,также добавляет служебную инфу,необходимую для ОС,для последующего управления программой.

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

Осн недостатки интерпр.: 1)низкая скорость исполнения программы,т.к во время ее выполнения производится синтаксический анализ каждой строки,перевод ее на машинный язык; 2)программа может выполняться тока под управлением интерпретатора.

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



(III)осн принципы технологии программирования. Под стилем програмир подразумев приемы и методы кот использ программисты чтобы получить правильные и легко читаемые программы.Рассмотрим осн приемы и методы отличающие хороший стиль програмиров: 1)легкость чтения программы. Для достижения легкости чтения программы,следует использовать возможности написания ясного теста,имеющегося в языках програмиров.Программа д/б прокоментирована полностью.комментарий писать в процессе написания программы.Программа д/б как мона более простой.Требование простаты связано с обеспечением качества программы. 2 подхода к обеспеч кач-ва программы: 1)проведение исчерпывающего тестирования; 2)обеспечение высокого кач-ва на всех стадиях разработки. *1)для большинства рпограмм провед затруднительно,поэтому приходица добиваться наим сложности программы.

2)Полн. И правильн. опр. Требований к программе .

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

3)Составление алгоритма .

4) Структурный подход .

Является одним из основных подходов существенно улучшающий программу . Он основан на составляющих :

А)Проектирование сверху в низ

Б)модульность ( модульное програмирование

Х – ка : *А)Заключается в реализации принципа “ от общего к частному», «от цели к задачам».Этот метод представляет собой последоват шагов.Разработку начинаю с опр-я целой и осн задач,ведущих к достижению этих целей,затем задачи разбивают на подзадачи,кот разбив на подзадачи след уровня иерархии итд до тех пор пока эти подзадачи не станут достаточно простыми.

*Б)это процесс разделения программы на части,назыв модулями и последоват програмиров каждой части.Программные модули должны удовлетвор след условиям: -)небольшой размер,текст модуля недолжен превышать 2-3-х экранных страниц, такой модуль удобен для восприятия(легко охватывается взглядом и запоминается); -)независимость,для достижения этого требуется чтобы модуль независил от: 1)источников входных данных;2)место размещ входных данных;3)предыстория.



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

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




Небо религии заменили небом культуры. Но и оно — для избранных. Анджей Бискупский
ещё >>