Автоматные грамматики и конечные автоматы.

Пусть G=(N, )автоматная грамматика. Тогда сущ-ет такой конечный автомат К=(Q, ), что L(K)=L(G). Конечный автомат строится след образом: 1. Входные алфавиты КА и автоматной грамматики совпадают. 2. Q=N (E), где Е-заключительное состояние КА. 3. . 4. Если , то F={S,E}, в противном случае F={E}. 5. Функция переходов КА опр-ся след образом: а) Е ; б) если ; в) . Пусть К=(Q, ) – КА. Тогда сущ-ет такая автоматная грамматика L(K)=L(G). Автоматная грамматика опр-ся след образом: 1. Входные алфавиты автоматной грамматики и конечного автомата совпадают. 2. N = Q. 3. S=q0. 4. Правила вывода автоматной грамматики опр-ся след образом: а) ; б)

Алгоритм (решение проблемы принадлежности):

Вход: конечный автомат К=(Q, ) и цепочка w . Выход: ответ «да»,если w ; ответ «нет», если w .

Описание алгоритма: пусть w=a₁a₂…a_n. Найти посл-ть состояний . Если то выдать ответ да, в противном случае – ответ нет.

Алгоритм (решение проблем пустоты):

Вход: конечный автомат К=(Q, ). Выход: ответ «да»,если ; ответ «нет», если .

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

Проблема эквивалентности для конечных автоматов разрешима. Пусть К=(Q, ) – конечный автомат, a q1, q2 – его различные состояния. Говорят, что цепочка х различает состояния q1 и q2, если (q1, х)+(q3, ), (q2, х)+(q4, ) и одно из состояний q3, q4 принадлежит F, a другое нет.

Алгоритм (решение проблемы эквивалентности для конечных автоматов):

вход: два детерминированных полностью определенных конечных автомата К1=(Q1, ) и К2=(Q2, ), таких, что Q1 Q2= . Выход: ответ да, если ; нет в противном случае. Описание алгоритма: построить конечный автомат К=(Q1 ).

Состав программного обеспечения ПЭВМ. Общие принципы классификации операционных систем. Понятие процессов и потоков. Дисциплины диспетчеризации.

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

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

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

Виды и классификация ОС: 1) Кол-во одновременно обслуживаемых системой пользов-лей (одно-, многопользовательские). 2)По числу процессов, одновременно выполняемых (одно-, многозадачные). 3)По типу доступа пользов-лей к ПЭВМ: -сист.с пакетной обработкой; -сист.разделения времени; -сист.реального времени; 4)По типу средств вычислит.техники для управления ресурсами которой система предназначена: -одно/многопроцессорные; -сетевые; -распределенные («облачные»); 5) Разрядность: 16-разрядная - 32-разрядная - 64-разрядная; 6) По ур. безопасности (-низкий, -высокий); 7) открытые (с возможностью редактировать исходный код) - закрытые (без возможности редактировать исходный код); 8) графические - текстовые (только командная строка);

Ресурс – это всякий объект, кот. может распределяться внутри системы.

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

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

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

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

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

Планирование вып-ся раз в неск. мин., диспетчеризация может запускаться каждые 30 или 100 мс.

Дисциплины диспетчеризации:

· Бесприоритетные:1) линейные (в порядке очереди, или случайный выбор процесса). 2)циклические (циклический алгоритм, или многоприоритетный циклический алгоритм).

· Приоритетные: 1)с фиксированным приоритетом (с относительным; с абсолютным; или адаптивное обслуживание). 2) с динамическим приоритетом (адаптивное обслуживание; приоритет зависит от времени ожидания; приоритет зависит от времени обслуживания)

Дисциплины:

· FCFS – первый пришел – первый обслужен («+»: простота реализации;«­­–»: рост времени простоя при решении объемных задач).

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

· SRT – следующее задание, то – которое требует меньше времени для завершения.

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

Эти дисциплины делятся на:

· Не вытесняющую многозадачность. (без перераспределения процессорного времени).FCFS, SJN, SRT.

· Вытесняющая многозадачность. (с перераспределением процессорного времени). RR. Реализована в большинстве современных ОС (WindowsNT, Linux, OS/2).