Рекурсивная фаза

Одним и тем же методом обрабатываются два подсписка: Sl(A[0] – A[4]) и Sh(A[6] – A[9]). Элемент А[5] обрабатывать не надо, так как он уже находится на своем месте. Тот же алгоритм применяется для каждого подсписка, разбивая эти подсписки на меньшие части, пока в подсписке не останется одного элемента или пока подсписок не опустеет.

28. Состояния процесса и граф переходов.

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

Процесс из состояния бездействия может перейти в состояние готовности в следу­ющих случаях.

- По команде оператора

- При выборе из очереди планировщиком

- При вызове из другой задачи

- По прерыванию от внешнего инициативного устройства

- При наступлении запланированного времени запуска программы

Из состояния выполнения процесс может выйти по одной из следующих при­чин.

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

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

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

29. Способы описания грамматики.

Формальное определение грамматики. Форма Бэкуса—Наура

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

Грамматику языка можно описать различными способами. Например, грамматика русского языка описывается довольно сложным набором правил, которые изуча­ют в начальной школе. Для некоторых языков (в том числе для синтаксических конструкции языков программирования) можно использовать формальное опи­сание грамматики, построенное на основе системы правил (пли продукций). Правило (пли продукция) — это упорядоченная пара цепочек символов (α, β). В пра­вилах важен порядок цепочек, поэтому их чаще записывают в виде α → β (или α::=β). Такая запись читается как «α порождает β» или «β по определению есть α». Грамматика языка программирования содержит правила двух типов; первые (определяющие синтаксические конструкции языка) довольно легко поддаются фор­мальному описанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме. Поэтому любое описание (или стан­дарт) языка программирования обычно состоит из двух частей: вначале фор­мально излагаются правила построения синтаксических конструкции, а потом на естественном языке дается описание семантических правил.

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквива­лентными, если заданные ими языки различаются не более чем на пустую цепоч­ку символов:

Формально грамматика G определяется как четверка G(VT,VN, P, S), где: VT — множество терминальных символов или алфавит терминальных символов; VN — множество нетерминальных символов пли алфавит нетерминальных сим­волов;

P — множество правил (продукций) грамматики, вида α → β, где ;

S — целевой (начальный) символ грамматики .

Алфавиты терминальных и нетерминальных символов грамматики не пересека­ются: . Это значит, что каждый символ в грамматике может быть либо терминальным, либо нетерминальным, но не может быть терминальным и нетерминальным одновременно. Целевой символ грамматики — это всегда не­терминальный символ. Множество называют полным алфавитом грамматики G.

Во множестве правил грамматики может быть несколько правил, имеющих оди­наковые левые части, вида: α → β₁, α → β₂,.. α → β_n. Тогда эти правила объеди­няют вместе и записывают в виде: α → β₁| β₂|…| β_n. Одной строке в такой записи соответствует сразу n правил.

Такую форму записи правил грамматики называют формой Бэкуса—Наура. Форма Бэкуса—Наура предусматривает, как правило, также, что нетерминальные симво­лы берутся в угловые скобки: < >.

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

G({0,1,2,3,4,5,6,7,8,9,+,-}, {<число>, <чс>, <цифра>}, P, <число>)

P:

<<число> → <чс> | +<чс> | -<чс>

<<чс> → <цифра> | <чс><цифра>

<<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Запись правил грамматик с использованием метасимволов

Запись правил грамматик с использованием метасимволов предполагает, что в строке правила грамматики могут встречаться специальные символы — мета­символы, — которые имеют особый смысл и трактуются специальным образом. В качестве таких метасимволов чаще всего используются следующие символы: () (круглые скобки), [ ] (квадратные скобки), { } (фигурные скобки), " " (кавыч­ки) и, (запятая). Эти метасимволы имеют следующий смысл:

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

Вот как должны выглядеть правила рассмотренной выше грамматики G, если их записать с использованием метасимволов:

<число> → [(+, -)]<цифра>{<цифра>}

<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Вторая строка правил не нуждается в комментариях, а первое правило читается так: «число есть цепочка символов, которая может начинаться с символов + или -, должна содержать дальше одну цифру, за которой может следовать любое количество цифр». В отличие от формы Бэкуса—Наура, в форме записи с помо­щью метасимволов, как видно, во-первых, убран из грамматики малопонятный нетерминальный символ <чс>, а во-вторых — удалось полностью исключить ре­курсию. Грамматика в итоге стала более понятной.

Форма записи правил с использованием метасимволов — это удобный и понят­ный способ представления правил грамматик. Она во многих случаях позволяет полностью избавиться от рекурсии, заменив ее символом итерации { } (фигур­ные скобки). Как будет понятно из дальнейшего материала, эта форма наиболее употребительна для одного из типов грамматик — регулярных грамматик. Кроме указанных выше метасимволов в целях удобства записи в описаниях грамматик иногда используют и другие метасимволы, при этом предварительно дается разъяснение их смысла. Принцип записи от этого не меняется. Также иногда дополняют смысл уже существующих метасимволов. Например, для ме­тасимвола { } (фигурные скобки) существует удобная форма записи, позво­ляющая ограничить число повторений цепочки символов, заключенной внутри них:{ }n, где и n > 0. Такая запись означает, что цепочка символов, стоящая в фигурных скобках, может быть повторена от 0 до n раз (не более n раз). Это очень удобный метод наложения ограничений на длину цепочки. Для рассмотренной выше грамматики G таким способом можно, например, запи­сать правила, если предположить, что она должна порождать целые десятичные числа, содержащие не более 15 цифр:

<<число> → [(+, -)]<цифра>{<цифра>}14

<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Для записи того лее самого ограничения в форме Бэкуса—Наура или в форме с ме­тасимволами потребовалось бы 15 правил.

Запись правил грамматик в графическом виде

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

В такой форме записи каждому нетерминальному символу грамматики соответ­ствует диаграмма, построенная в виде направленного графа. Граф имеет следую­щие типы вершин:

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

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

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

Это удобный способ описания правил грамматик, оперирующий образами, а по­тому ориентированный исключительно на людей. Даже простое изложение его основных принципов здесь оказалось довольно громоздким, в то время как суть способа довольно проста. Это можно легко заметить, если посмотреть на описа­ние понятия «число» из грамматики G с помощью диаграмм на рисунке. Как уже было сказано выше, данный способ в основном применяется в литерату­ре при изложении грамматик языков программирования. Для пользователей — разработчиков программ — он удобен, но практического применения в компиля­торах пока не имеет.

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

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

30. Унифицированный язык моделирования UML: общая характеристика.

UML — стандартный язык для написания моделей анализа, проектирования и реализации объектно-ориентированных программных систем. UML может использоваться для визуализации, спецификации, конструирования и до­кументирования результатов программных проектов. UML — это не визуальный язык программирования, но его модели прямо транслируются в текст на языках программирования (Java, C++, Visual Basic, Ada 95, Object Pascal) и даже в таблицы для реляционной БД.

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

Предметы – это абстракции, которые являются основными элементами в модели, отношения связывают эти предметы, диаграммы группируют коллекции предметов.

Предметы в UML

В UML имеются четыре разновидности предметов:

• структурные предметы;
• предметы поведения;
• группирующие предметы;
• поясняющие предметы.

Структурные предметы являются существительными в UML-моделях. Они представляют статические части модели – понятийные и физические элементы. Перечислим 8 разновидностей структурных предметов.

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

2. Интерфейс — набор операций, которые определяют услуги класса или компонента. Интерфейс описывает поведение элемента, видимое извне. Интерфейс может представлять полные услуги класса или компонента или часть таких услуг. Интерфейс определяет набор спецификаций операций (их сигнатуры), а не набор реализаций операций. Графически интерфейс изображается в виде кружка с именем, как показано на рисунке. Имя интерфейса обычно начинает­ся с буквы «I». Интерфейс редко показывают самостоятельно. Обычно его при­соединяют к классу или компоненту, который реализует интерфейс.

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

4. Актер — набор согласованных ролей, которые могут играть пользователи при взаимодействии с системой (ее элементами Use Case). Каждая роль требует от системы определенного поведения. Как показано на рисунке, актер изобража­ется как проволочный человечек с именем.

5. Элемент Use Case (Прецедент) — описание последовательности действий (или нескольких последовательностей), выполняемых системой в интересах отдель­ного актера и производящих видимый для актера результат. В модели элемент Use Case применяется для структурирования предметов поведения. Элемент Use Case реализуется кооперацией. Как показано на рисунке, элемент Use Case изображается как эллипс, в который вписывается его имя.

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

7. Компонент — физическая и заменяемая часть системы, которая соответствует набору интерфейсов и обеспечивает реализацию этого набора интерфейсов. В систему включаются как компоненты, являющиеся результатами процесса разработки (файлы исходного кода), так и различные разновидности исполь­зуемых компонентов (СОМ+-компоненты, Java Beans). Обычно компонент — это физическая упаковка различных логических элементов (классов, интерфей­сов и коопераций). Как показано на рисунке, компонент изображается как пря­моугольник с вкладками, обычно включающий имя.

8. Узел — физический элемент, который существует в период работы системы и представляет ресурс, обычно имеющий память и возможности обработки. В узле размещается набор компонентов, который может перемещаться от узла к узлу. Как показано на рисунке, узел изображается как куб с именем.

Предметы поведения — динамические части UML-моделей. Они являются глаголами моделей, представлением поведения во времени и пространстве. Существу­ет две основные разновидности предметов поведения.

1. Взаимодействие — поведение, заключающее в себе набор сообщений, которыми обменивается набор объектов в конкретном контексте для достижения оп­ределенной цели. Взаимодействие может определять динамику как совокупно­сти объектов, так и отдельной операции. Элементами взаимодействия являются сообщения, последовательность действий (поведение, вызываемое сообщением) и связи (соединения между объектами). Как показано на рисунке, сообще­ние изображается в виде направленной линии с именем ее операции.

2. Конечный автомат — поведение, которое определяет последовательность состояний объекта или взаимодействия, выполняемые в ходе его существования в ответ на события (и с учетом обязанностей по этим событиям). С помощью конечного автомата может определяться поведение индивидуального класса или кооперации классов. Элементами конечного автомата являются состояния, пе­реходы (от состояния к состоянию), события (предметы, вызывающие перехо­ды) и действия (реакции на переход). Как показано на рисунке, состояние изображается как закругленный прямоугольник, обычно включающий его имя и его подсостояния (если они есть).

Эти два элемента — взаимодействия и конечные автоматы — являются базисными предметами поведения, которые могут включаться в UML-модели. Семантически эти элементы ассоциируются с различными структурными элементами (прежде всего с классами, кооперациями и объектами).

Группирующие предметы. — организационные части UML-моделей. Это ящики, по которым может быть разложена модель. Предусмотрена одна разновидность груп­пирующего предмета — пакет.

Пакет — общий механизм для распределения элементов по группам. В пакет мо­гут помещаться структурные предметы, предметы поведения и даже другие груп­пировки предметов. В отличие от компонента (который существует в период выполнения), пакет — чисто концептуальное понятие. Это означает, что пакет су­ществует только в период разработки. Как показано на рисунке, пакет изображает­ся как папка с закладкой, на которой обозначено его имя и, иногда, его содержание.

Поясняющие предметы — разъясняющие части UML-моделей. Они являются за­мечаниями, которые можно применить для описания, объяснения и комментиро­вания любого элемента модели. Предусмотрена одна разновидность поясняющего предмета — примечание.

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

Отношения в UML

В UML имеются четыре разновидности отношений:

• зависимость;
• ассоциация;
• обобщение;
• реализация.

Эти отношения являются базовыми строительными блоками отношений. Они ис­пользуются при написании моделей.

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

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

3. Обобщение — отношение специализации/обобщения, в котором объекты спе­циализированного элемента (потомка, ребенка) могут заменять объекты обоб­щенного элемента (предка, родителя). Иначе говоря, потомок разделяет структуру и поведение родителя. Как показано на рисунке, обобщение изображается в виде сплошной стрелки с полым наконечником, указывающим на родителя.

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

Диаграммы в UML

Диаграмма — графическое представление множества элементов, наиболее часто изображается как связный граф из вершин (предметов) и дуг (отношений). Диа­граммы рисуются для визуализации системы с разных точек зрения, затем они ото­бражаются в систему. Обычно диаграмма дает неполное представление элементов, которые составляют систему. Хотя один и тот же элемент может появляться во всех диаграммах, на практике он появляется только в некоторых диаграммах. Теоретически диаграмма может содержать любую комбинацию предметов и отно­шений, на практике ограничиваются малым количеством комбинаций, которые соответствуют пяти представлениям архитектуры ПС. По этой причине UML вклю­чает девять видов диаграмм:

1. диаграммы классов;
2. диаграммы объектов;
3. диаграммы Use Case (диаграммы прецедентов);
4. диаграммы последовательности;
5. диаграммы сотрудничества (кооперации);
6. диаграммы схем состояний;
7. диаграммы деятельности;
8. компонентные диаграммы;
9. диаграммы размещения (развертывания).

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

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

Диаграмма Use Case (диаграмма прецедентов) показывает набор элементов Use Case, актеров и их отношений. С помощью диаграмм Use Case для системы создается статическое представление Use Case. Эти диаграммы особенно важны при орга­низации и моделировании поведения системы, задании требований заказчика к системе.

Диаграммы последовательности и диаграммы сотрудничества — это разновиднос­ти диаграмм взаимодействия.

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

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

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

Диаграмма схем состояний показывает конечный автомат, представляет состоя­ния, переходы, события и действия. Диаграммы схем состояний обеспечивают ди­намическое представление системы. Они особенно важны при моделировании по­ведения интерфейса, класса или кооперации. Эти диаграммы выделяют такое поведение объекта, которое управляется событиями, что особенно полезно при мо­делировании реактивных систем.

Диаграмма деятельности — специальная разновидность диаграммы схем состоя­ний, которая показывает поток от действия к действию внутри системы. Диаграм­мы деятельности обеспечивают динамическое представление системы. Они осо­бенно важны при моделировании функциональности системы и выделяют поток управления между объектами.

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

Механизмы расширения в UML

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

• ограничения;
• теговые величины;
• стереотипы.

Ограничение (constraint) расширяет семантику строительного UML-блока, позво­ляя добавить новые правила или модифицировать существующие. Ограничение показывают как текстовую строку, заключенную в фигурные скобки {}.

Теговая величина (tagged value) расширяет характеристики строительного UML-блока, позволяя создать новую информацию в спецификации конкретного элемен­та. Теговую величину показывают как строку в фигурных скобках {}. Строка име­ет вид

имя теговой величины = значение.

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

Стереотип (stereotype) расширяет словарь языка, позволяет создавать новые виды строительных блоков, производные от существующих и учитывающие специфику новой проблемы. Элемент со стереотипом является вариацией существующего элемента, имеющей такую же форму, но отличающуюся по сути. У него могут быть дополнительные ограничения и теговые величины, а также другое визуальное пред­ставление. Он иначе обрабатывается при генерации программного кода. Отобра­жают стереотип как имя, указываемое в двойных угловых скобках (или в угловых кавычках). <<call>>

31. Формальное определение грамматики и языка.

Понятие языка. Формальное определение языка

В общем случае язык — это заданный набор символов и правил, устанавливаю­щих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого естественного пли искусственного языка является алфавит, определяющий набор допустимых символов языка. Алфавит — это счетное множество допустимых символов языка. Будем обозна­чать это множество символом V. Интересно, что согласно формальному опреде­лению, алфавит не обязательно должен быть конечным множеством, но реально все существующие языки строятся на основе конечных алфавитов. Цепочка символов α является цепочкой над алфавитом V: α(V), если в нее вхо­дят только символы, принадлежащие множеству символов V. Для любого алфа­вита V пустая цепочка λ может как являться, так и не являться цепочкой λ(V). Это условие оговаривается дополнительно. Если V — некоторый алфавит, то: V⁺ — множество всех цепочек над алфавитом V без λ; V* — множество всех цепочек над алфавитом V, включая λ. Справедливо равенство: .

Языком L над алфавитом V: L(V) называется некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. Из этого определения следует два вывода: во-первых, множество цепочек языка не обяза­но быть конечным; во-вторых, хотя каждая цепочка символов, входящая в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена.

Все существующие языки подпадают под это определение. Большинство ре­альных естественных и искусственных языков содержат бесконечное множество цепочек. Также в большинстве языков длина цепочки ничем не ограничена. Цепочку символов, принадлежащую заданному языку, часто называют предло­жением языка, а множество цепочек символов некоторого языка L(V) — множе­ством предложений этого языка. Для любого языка L(V) справедливо: .

Язык L(V) включает в себя язык L`(V): , если . Множество цепочек языка L'(V) является подмножеством множества цепочек языка L(V) (или эти множества совпадают). Очевидно, что оба языка должны строиться на основе одного и того же алфавита.

Два языка L(V) и L'(V) совпадают (эквивалентны): L'(V) = L(V), если и или, что то же самое: и . Множества допустимых цепочек символов для эквивалентных языков равны. Два языка L(V) и L'(V) почти эквивалентны: , если . Множества допустимых цепочек символов почти эквивалентных языков могут различаться только на пустую цепочку символов.

Кроме алфавита язык предусматривает также правила построения до­пустимых цепочек, поскольку обычно далеко не все цепочки над заданным алфа­витом принадлежат языку. Символы могут объединяться в слона или лексемы - элементарные конструкции языка, на их основе строятся предложении — более сложные конструкции. И те и другие в общем виде являются цепочками симво­лов, но предусматривают некоторые правила построения. Таким образом, необ­ходимо указать эти правила, или строго говоря, задать язык. В общем случае язык можно определить тремя способами:

• перечислением всех допустимых цепочек языка;
• указанием способа порождения цепочек языка (заданием грамматики языка);
• определением метода распознавания цепочек языка.

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

Например, запись задает язык над алфавитом V ={0,1}, содержащий все последовательности с чередующимися символами 0 и 1, начи­нающиеся с 0 и заканчивающиеся 1. Видно, что пустая цепочка символов в этот язык не входит.

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

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

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

Формальное определение грамматики. Форма Бэкуса—Наура

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

Грамматику языка можно описать различными способами. Например, грамматика русского языка описывается довольно сложным набором правил, которые изуча­ют в начальной школе. Для некоторых языков (в том числе для синтаксических конструкции языков программирования) можно использовать формальное опи­сание грамматики, построенное на основе системы правил (пли продукций). Правило (пли продукция) — это упорядоченная пара цепочек символов (α, β). В пра­вилах важен порядок цепочек, поэтому их чаще записывают в виде α → β (или α::=β). Такая запись читается как «α порождает β» или «β по определению есть α». Грамматика языка программирования содержит правила двух типов; первые (определяющие синтаксические конструкции языка) довольно легко поддаются фор­мальному описанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме. Поэтому любое описание (или стан­дарт) языка программирования обычно состоит из двух частей: вначале фор­мально излагаются правила построения синтаксических конструкции, а потом на естественном языке дается описание семантических правил.

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквива­лентными, если заданные ими языки различаются не более чем на пустую цепоч­ку символов:

Формально грамматика G определяется как четверка G(VT,VN, P, S), где: VT — множество терминальных символов или алфавит терминальных символов; VN — множество нетерминальных символов пли алфавит нетерминальных сим­волов;

P — множество правил (продукций) грамматики, вида α → β, где ;

S — целевой (начальный) символ грамматики .

Алфавиты терминальных и нетерминальных символов грамматики не пересека­ются: . Это значит, что каждый символ в грамматике может быть либо терминальным, либо нетерминальным, но не может быть терминальным и нетерминальным одновременно. Целевой символ грамматики — это всегда не­терминальный символ. Множество называют полным алфавитом грамматики G.

Во множестве правил грамматики может быть несколько правил, имеющих оди­наковые левые части, вида: α → β₁, α → β₂,.. α → β_n. Тогда эти правила объеди­няют вместе и записывают в виде: α → β₁| β₂|…| β_n. Одной строке в такой записи соответствует сразу n правил.

Такую форму записи правил грамматики называют формой Бэкуса—Наура. Форма Бэкуса—Наура предусматривает, как правило, также, что нетерминальные симво­лы берутся в угловые скобки: < >.

АСУЖТ

1. АРМы.

АРМ – совокуп. программ., методич. и языковых ПС, обеспечивающих работу польз. на пк в некот. предметн. обл. Структура АРМ - это совокупность его подсистем и элементов.

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

Техническое обеспеч предст. собой комплекс технических средств, основой которого служит ПЭВМ К комплекту техноло­гических средств следует отнести средства телефонной связи.

Инф. обеспеч- это мас­сивы информации, хранящиеся в локальных базах данных. Управление инф. осуществляется с помощью программной системы управления базами данных, которая производит запись информации, поиск, считывание, корректировку и решение информационных задач. ПО состоит из сис­темного программного обеспечения и прикладного. Основой системного обеспечения являются операционные системы (ОС) и системы программи­рования, например, алгоритмические языки Ассемблер, ПЛ/1, Бейсик и др. Системные программы обеспечивают рациональную технологию • обработки информации.

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

АРМ ДСП – дежурного по стан.

АРМ ДСЦ- маневрового диспетчера

АРМ ТКО – оператора техн. конторы по отправл.

АРМ ТКП – то же по прибытию

АРМ ТВК – товарного кассира

АРМ ПС- приемосдатчиков груза

АРМ КП –оператора контейнерной площадки

2. АСОУП, функциональный состав.

АСОУП предназнач. для созд. и поддержки в реальн. масшт. вр. инфор. модели ПП прогнозирования и текущего планирования ЭР всех предприятий дороги, отделения дороги и дороги. Функцион. состав АСОУП предназ.на информ. обеспеч. оперативных работников дороги и включ. в себя след. задачи:

УПВ(учет перехода поездов, вагонов, контейнеров через стыковые пункты, отделений и дорог) Здесь реш. аналитич. задачи связ. с переходом поездов через стыковые пункты, КПФ (контроль плана формирования поездов) Обеспечивает оперативн.выявления нарушений плана формирования допускаемых ст. формирования, КВД(контроль веса и длины состава) Включ. в себя оперативн. выявление неполновесность поездов, ППГ (прогноз прибытия груза на станцию), ВТД(выдача технологической документации) по запросу 213 можно получить любые сведения о поездах наход. на дороге, СЛЕЖ(пердусматривает пономерное слежение за специально выделенным составом)слежение за каждым локомотивом идущим в ремонт или из ремонта, ОКДЛ(оперативный контроль за дислокацией локомотивов)Этот комплекс ведет информацион. лок. модель дороги и подготавливает списки наличия действующих локомотивов.

3. АСУМР.

Одним из наиболее значимых проектов ОАО «РЖД» в области информатизации управления перевозками является Автоматизированная система управления местной работой (АСУ МР).

В соответствии с рисунком 4.1 местная работа в общем случае осуществляется в пределах нескольких районов (РМР), в рамках которых станции связаны единой технологией развоза местного груза и потоками местных поездов. Местный груз из-за пределов отделения доставляется сквозными и участковыми поездами до базовой технической станции (БС) отделения. БС является условным понятием, определяя особый статус станции в рамках системы организации местной работы. Именно с нее начинается развоз местного груза сборными, вывозными поездами или прицепными группами к сквозным и участковым поездам. Доставка местного вагона от междорожных стыков до БС находится в компетенции Дорожного центра управления (ДЦУ) и должна нормироваться как показатель работы его оперативного персонала. Таким образом, частично изменяются понятия развоза и передачи местного груза.

Сборными, вывозными поездами и прицепными группами вагонов местный груз доставляется со станций, имеющих маневровые локомотивы для последующего развоза вагонов на месте выгрузки как на «своей», так и на некотором числе рядом расположенных станций. Станции, где есть маневровые локомотивы, условно называются опорными (ОС), а где их нет – прикрепленными (ПС).

Управление местной работой на отделении железной дороги включает в себя 2 уровня. Первый – Центр управления местной работой (ЦУМР) в составе отдела перевозок. В него входит диспетчерский аппарат, обеспечивающий управление местной работой и взаимодействие с диспетчерским персоналом дорожного центра управления. Второй уровень – станции выполнения операций, включая диспетчерский аппарат базовых и опорных станций (ДСЦС, ДСЦ) и дежурных по прикрепленным станциям (ДСП).

Цель создания АСУ МР – оптимизация местной работы, обеспечивающая сокращение приведённых затрат на её выполнение.

В состав АСУ МР должны входить задачи следующих классов:

1 Автоматизированной разработки технологии местной работы.

2 Технического нормирования грузовой и местной работы.

3 Сменно-суточного планирования (местная работа, погрузка, выгрузка, регулировочные задания) (ССП МР).

4 Текущего планирования местной работы (ТП МР), детализирующее задания ССП МР и обеспечивающее перевыполнение этих заданий или компенсацию отставаний от их.

5 Диспетчерского контроля и регулирования местной работы (ДКР МР), обеспечивающие выполнение и перевыполнение текущих планов (за счёт оптимизации пооперационных заданий на маневровую работу и другие элементы МР).

6 Оперативного анализа местной и грузовой работы по итогам смены и суток (ОА МР), обеспечивающий выявление потерь и дополнительных резервов по итогам выполнения местной работы за каждую смену и сутки.

7 Целевого и расширенного периодического анализа выполненной работы.

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

Реализуется возможность

· формирования задания по обороту вагона на предстоящий период на основе прогнозной модели;

· получения прогноза выполнения установленных заданий в течение периода;

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

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

В прикладной части Единая АСУ МР существенно расширяет функциональный состав базовых версий системы
(с обеспечением адаптации требуемых элементов БВ АСУ МР
к единой БД).

Основная цель тиражирования базовых версий АСУ МР на сеть железных дорог в 2004-2005 годах – создание необходимой инфраструктуры (АРМы для всех диспетчеров и других работников, участвующих в управлении и организации МР, с включением этих АРМов в общую СПД) и подъём до уровня дороги необходимой дополнительной информации по операциям местной работы.

4. АСУСС.

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

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

В рамках сист. осущест. обработка инф. о подходе поездов и подготовке составов к расформированию, в том числе рас­чет и выдача размеченной телеграммы-катурного листа, По вводимым в ЭВМ запросам на основе динамической модели сор­тировочной ст. сост. справки о состоянии путей парков, имеющихся вагонам на путях, наличии на ст.транзитных с пере­работкой и местных вагонов, С помощью АС рассчитываются и выдаются отчеты форм Д0-I,2, справки для состав отчета Д0-42, справки об итогах работы станции за смену и сутки, о работе сортировочных горок и простое вагонов на ст.

5. Безбумажная технология в управлении перевозками.

Безбумажная технология[бт] (стандарт EDIFACT) Примен. бт позвол. за счет устранен.повторного ввода безошибочно передавать инф. от одного пк к другому, намного сокращая весь цикл работ. Совокуп. стандартизированных процедур способа обмена документами наз. электронным обменом данными (ЕDI).

Технология EDI обеспечив. целый ряд приемуществ: 1)упрощение поиска поставщиков товаров и подбора сервисных служб.2)увелич. производит. труда штатных сотрудников.3)улучшение контроля за сроками исполнения и прочими условиями поставок.Сущ. большое кол-во станд. связанных с технологией ЕDI. Напр., EDIFACT, кот. регламентирует эл. обмен докумен. в сферах административной и коммерч. деят. Он также позвол. одноврем. передавать неск. сообщений одной или различ. структур(неск. счетов, сопроводит. докумен. на грузы). Синтаксич. правила позволяют идентифицировать все эл-ты передаваемых сообщений, что дает возможность получателю информации полностью восстановить содержание передаваемых сообщений вплоть до отдельных эл-в даже в том случае, если структура докум. не была заранее известна. На жд введена разработка и началась опытная эксплуатация на выделен. полигоне безбумаж. технологии – АС электронной накладной. В основу новой технологии перевозки грузов повагонными отправками положены принципы оформления погрузки и выгрузки с помощью современных средств ВТ. Для полного функционир. сист. необх., чтобы начальная и конечная ст. были оборудованы средствами ВТ. После окончания формиров. документов в сист. АСОУП перед. сообщение 403 Сист. АСОУП обеспечив. слежение за повагонной отправкой от момента погрузки до момента выгрузки.

6. Виды транспортных перевозок.

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

Виды смеш. первозок: перев. грузов спец. груз. унифицированными модулями. Эти пер. относ. к категории перев. с исп. тран.-технол. систем.Такие технологии поз. отказаться от складов, либо сократить их емкость.

Контрейлерные перевозки –комбинирован. жд-авт. перевозки при кот. перевозится трейлер, кузов без водителя и тягача на жд платформе. Безвагонные технологии – организация комбинирован. жд перевозок без жд платформ.Двухярусные поезда- это перевозки контейнеров в 2 яруса на жд платформах. Паромные транспортно-технол. сист. предн. для перевозки пассажиров и подвижного состава, через водные преграды на спец. судах-паромах. Они делятся на 3 группы: 1)жд 2) автом. 3) комбинированные. перевозки сообщений река-море. Суда в кот. осущ. перевоз. грузов наз смешан. плаванием (3 междун. грузовые линии: 1)каспийск- волго-балтийск 2)среднеземн.-волгодон. линия 3)груз. лесная Череповец -Ейск).

7. Дискон.

В качестве составляющих данная система включает => сист.:1) АС контроля за использованием и продвижением контейнеров (АСОУК-2)

2) АС пономерного учета и передача контейнеров в межгосуд. сообщении 3) АС сбора инф. АСОУК-1(для составления отчета КЭО-1).

Назнач. сист.: предназ. для автоматизации ф. упр. контейнер. перевозками, основанной на создании достоверных инф-х номерных моделей дислокации и состоянии контейнеров на дорожном и сетевом уровнях. Учет производится по операциям погр./выгр. Контейнера на вагон и из вагона. Приема и сдачи конт. по междорожным, межгосударственным и международным стыками, а также в предприеме и сдаче контейнеров в портах. Сист. предн. для сбора, обработки, представл. данных по наличии и состоянии парка контейнера на жд, на сети в режиме реального времени, оперативного учета и контроля за передачей контейнеров РФ на тер-ю других гос-в, оперативного учета и контроля за нахождением контейнеров. Объектом автоматизации в сист. явл. пономерной учет парка контейнеров собств. и др. гос-в. Сист. ДИСКОН сост. из 3-х уровней сетевой, дорожный, линейный. Для контроля качества инф. на дор. уровне создан АРМ дисп. ДИСКОН, кот нах. в ИВЦ дороги. На дор. уровне для получ. работн. упр. конт. перевозками вых. форм и отчетов исп. АРМДЦФТО. Лин. уровень явл. основой формиров. исходн. инф. об операциях с конт. Формир. и передача инф. с лин. уровня осущ. по следующим АРМам: АРМ ПС, АРМ ТВК, АСУ КП.

8. Документооборот в портовых станциях.

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

9. Защита информации (контрольные знаки кодов станции, вагонов, локомотивов).

Начиная с 1984 года, на сети дорог МПС стала внедряться Единая 8-значная система нумерации перевозочных средств. Цель системы — улучшить обработку перевозочных документов грузового движения, а также свести в единую базу данных всю информацию о подвижном составе — в так называемую Картотеку ГВЦ МПС. До введения данной системы единой нумерации были подвержены только вагоны грузового парка для и не для перевозки грузов (вагон не для перевозки грузов — это, например, служебный вагон рефрижераторной секции). Номер грузового вагона имел семь знаков и записывался через тире между третьим и четвертым знаком, например, 232-2851. Новая система сохранила все принципы прежней нумерации, добавив к ним свои. Главным ее отличием стало введение восьмого, контрольного знака, или, как его еще называли, знака кодовой защиты. Связано это с массовым введением ЭВМ и автоматических считывателей номеров вагонов в парках прибытия крупных сортировочных станций. Поезд, прибывая на такую станцию, уже был «списан» — на него имелся фактический натурный лист. Это позволило экономить время на обработку состава, так как еще до прибытия и отцепки локомотива дежурный по станции и дежурный по горке знали, какие вагоны едут в этом поезде, и куда они пойдут далее. Для расчета контрольного знака применялся особый алгоритм, позволяющий выявить неточность при считывании номера. Если одна из цифр, в том числе и

контрольный знак, были считаны неверно, контрольной суммы не получалось, и информация требовала проверки. Сущность алгоритма проверки заключается в том, что при проведении определенных математических действий над цифрами номера должно получиться число, кратное 10. Для этого: каждую нечетную цифру номера необходимо умножить на 2, и, если получается двузначной число, то его цифры надо сложить; каждую четную цифру надо умножить на 1; потом сложить все полученные цифры. И получится число, кратное 10. Для номера вагона 23228513 этот пример выглядит так:

2 3 2 2 8 5 1 3

х2

4 4 1+6 2

х1

3 2 5 3

++

4 + 3 + 4 + 2 + 7 + 5 + 2 + 3 = 30

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

10. Классификация, кодирование, классификаторы.

Инфор-е обеспеч. АСУ жд есть совок.:

1) единой сист. классификации и кодирования технико-эконом-й инф.

2) унифициров. систем документации и файлов данных.

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

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

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

11. Концепция информатизации железнодорожного транспорта.