реберные графы
Реберный граф графа (line graph) G=(X, U) - граф U(G)=(U, Е) называются реберным, если каждой вершине uОU(G) сопоставлено ребро uОU и две вершины в U(G) смежны тогда и только тогда, когда соответствующие ребра смежны в графе G.
Сильносвязный орграф
(сильный орграф) (strongly connected graph) - орграф, у которого любые две вершины взаимодостижимы.
Изоморфизм графов.
Два графа G=(X, U) и L=(X', U') изоморфны, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.
Хроматическое число
(chromatic number) c(G) - наименьшее число n, для которого граф G имеет n-раскраску.
Цикломатическое число
n(G) неориентированного графа G=(X, U) - n(G)=|U| - |X| + k(G), где k(G) - число компонент связности графа G.
Раскраска точная
раскраска с использованием минимального числа красок, т. е. число красок равно хроматическому числу графа G или хроматическому классу графа G.
Полная раскраска
раскраска вершин графа, такая, что для любых двух цветов найдутся две смежные вершины, окрашенные в эти цвета.
Раскраска
(вершинная) - приписывание цветов (натуральных чисел) вершинам графа, такое, что никакие две смежные вершины не получают одинаковые цвета (числа).
Объединение графов
(помеченных графов) G1=(X1, U1) и G2=(X2, U2) - граф G1ИG2, множеством вершин которого является Х=X1ИX2, а множеством ребер U=U1ИU2.
Соединение графов
G1=(X1, U1) и G2=(X2, U2) таких, что X1ЗX2=Ж, U1ЗU2=Ж - граф G1+G2, который состоит из G1ИG2ИK(X1, X2), где K(X1, X2) - полный двудольный граф с множеством вершин X1 и X2 в долях.
Пересечение графов
(помеченных графов) G1=(X1, U1) и G2=(X2, U2) - граф G1ЗG2, множеством вершин которого является Х=X1ЗX2, а множеством ребер U=U1ЗU2, где U1 и U2 - множество неупорядоченных пар вершин.
Симметрическая разность графов
G1 и G2 - граф G1ЕG2=G1ИG2 - G1ЗG2.
Сумма графов
G1=(X1, U1) и G2=(X2, U2) - граф G1?G2, состоящий из множества вершин Х=X1?X2 и две вершины s=(x1, x2) и t=(y1, y2) (s, t О X, x1, y1 О X1, x2, y2 О X2) смежны в G1?G2 тогда и только тогда, когда x1=y1 и x2 смежна с y2 или x2=y2 и x2 смежна с y1.
Композиция графов
(лексикографическое произведение графов) G1=(X1, U1) и G2=(X2, U2) - граф G=G1[G2], состоящий из множества вершин Х=X1?X2, и две вершины s=(x1, x2) и t=(y1, y2) смежны в G тогда и только тогда, когда x1 смежна с y1 или x1=y1 и x2 смежна с y2.
Разность графов
(помеченных графов) - граф G1-G2, который получается из G1 удалением элементов, соответствующих графу G2.
Перечисление графов
подсчет числа неизоморфных графов в заданном классе (с заданными характеристиками).
Пустой подграф
внутренне-устойчивое множество вершин) - подграф графа G, в котором любая пара вершин несмежна.
Полный подграф
(complete subgraph) - подграф, в котором каждая пара вершин смежна.
k-компонента
(максимальная по включению) - часть графа, в котором любая пара вершин k-соединима.
Сильная компонента
орграфа G - максимальный подграф орграфа G, в котором любая пара вершин сильно связн
Компонента связности
графа (connected component) - максимальный подграф [возможно, не единственный - А.Ч.] графа G, в котором все вершины попарно достижимы.
Подграф
(часть) графа (subgraph, section graph) G=(X, R) - граф G'=(X', R'), для которого X'НX, R'НR и две несмежные вершины в G не смежны в G'.
Типы частей графов
Подграф (часть) графа (subgraph, section graph) G=(X, R) - граф G'=(X', R'), для которого X'НX, R'НR и две несмежные вершины в G не смежны в G'.
ЫВсувмсвафмамфывмафвмвфвымвамфвЧСяЧСм счя с ВВССВСССС
пыаипямиямссми
аяиаяиаиаси
иясми амичсми
ичм имчимсии
Равносильность ф-мул лог. высказ. Основные и дополнит. равносильности
1.2.2 Равносильность формул
Пусть А и В - формулы, зависящие от одного и того же списка переменных. А и В называются равносильными, если на любой оценке списка они принимают одинаковые значения. Алгебраический аналог равносильности - тождественное равенство алгебраических выражений. Обозначение А=В.
Основные равносильности
Для любых формул А,В,С справедливы следующие равносильности:
1. Коммутативность
А^В=В^А
2. Идемпотентность
А^А=А
3. Ассоциативность
А^(В^С)=(А^В)^С
4. Коммутативность
АvВ=ВvА
5. Идемпотентность
АvА=А
6. Ассоциативность
Аv(ВvС)=(АvВ)vС
7. Дистрибутивность v относительно ^
Аv(В^С)=(АvВ)^(АvС)
8. Дистрибутивность ^ относительно v
А^(ВvС)=(А^В)v(А^С)
9. 1-ый закон поглощения
А^(АvВ)=А
10. 2-ой закон поглощения
Аv(А^В)=А
11. Снятие двойного отрицания
?? А=А
12. 1-ый закон де Моргана
?(А^В)=?Аv?В
13. 2-ой закон де Моргана
?(АvВ)=?А^?В
Выражение одних логических связок через другие:
16. А~В=(АэВ)^(ВэА)=(А^В)v( ?А^?В)
17. АВАВ(АВ)
18. АВАВ(АВ)
19. АВ(АВ)(АВ)
Разделительное ?или?.
20. А+В(АВ) (АВ)(АВ)
Штрих Шеффера.
21. АВ(АВ)АВ
Стрелка Пирса
22. АВ(АВ)(АВ)
Любая равносильность может быть доказана с помощью таблиц истинности.
Основ. положения об алгоритмах
2 Теория алгоритмов
2.1 Основные требования к алгоритмам.
Каждый алгоритм работает с данными: входными, промежуточными, выходными.
При этом, объекты должны быть четко определены и отличны как друг от друга, так и от ?необъектов?. Например, к алгоритмическим объектам относятся числа, векторы, матрица смежности графа, формулы. Дело даже не в том, что рисунок графа менее ясно представляет граф, чем матрица, а в том, что матрицу можно разбить на элементы (0 и 1). Не является алгоритмическими объектами ? ?хорошая книга?, ?осмысленное утверждение?.
Набор элементарных объектов образуют конечный алфавит исходных символов ( букв, цифр и т.д.) из которых строятся другие объекты. Средством построения являются индуктивные определения, указывающие, как строить новые объекты из уже построенных. Например: идентификатор - это буква, либо идентификатор, к которому приписана справа буква или цифра. Слова конечной длины в конечных алфавитах (в частности числа) ? наиболее обычный тип алгоритмических данных, а число символов в слове (длина слова) ? единица измерения объема обрабатываемой информации. Более сложный случай ? формулы. Здесь основным алгоритмам предшествуют вспомогательные, которые проверяют, удовлетворяют ли исходные данные нужным требованиям (синтаксический анализ).
Перечислим основные требования к алгоритмам.
1. Данные для размещения требуют памяти. Память обычно считается однородной и дискретной, т.е. состоит из одинаковых ячеек, каждая ячейка может содержать один символ алфавита. При этом память может быть бесконечной.
2. Алгоритм состоит из отдельных элементарных шагов (действий), причем количество их конечно. Например, множество элементарных действий ? система команд ЭВМ. Обычно элементарный шаг имеет дело с фиксированным числом символов, однако это требование не всегда выполняется. Например: динамическая память, используемая в программировании.
3. Последовательность шагов детерминирована, т.е. после каждого шага указывается, что делать дальше.
4. Результативность или сходимость алгоритма, т.е. остановка после конечного числа шагов.
5. Следует различать:
а) описание алгоритма (инструкция, программа)
б) механизм реализации (ЭВМ)
в) процесс реализации (последовательность шагов, которая будет порождена при применении алгоритма к конкретным данным).
6. Массовость алгоритма ? служит для решения не какой-либо конкретной задачи, а целого класса задач. Например: формулы для решения системы двух уравнений определяют решение при любом значении коэффициента, арифметические правила применимы к любым числам и т.д.
Процедуру для решения индивидуальной задачи не называют алгоритмом. Например: xn+yn=zn ? не известен алгоритм, позволяющий определить для n= 1,2,3,4,.. решение. Но для конкретных n существует решение. Например: n=2, x=3, y=4, z=5.
Ниже рассматриваемые алгоритмические модели можно считать формализацией понятия ?алгоритм?, то есть, они универсальны ? допускают описание любых алгоритмов. При этом будет показано, что каждая модель сводится к другой.
Выделяют три основных типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями о том, что такое алгоритм.
? Рекурсивные функции. Модель основана на функциональном подходе и рассматривает понятие алгоритма с точки зрения того, что можно вычислить с помощью алгоритма. Исторически это первая формализация алгоритма, которая связывает определение алгоритма с вычислениями и числовыми функциями.
? Машина Тьюринга. Алгоритм представляется как детерминированное устройство, выполняющее примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Эвристика этой модели близка к ЭВМ
? Канонические системы Поста, нормальный алгоритм Маркова ? преобразование слов в произвольных алфавитах, в которых элементарной операцией являются подстановки, т.е. замены подслова ? другим словом. Другими словами, в этих моделях формализован процесс преобразования записей исходных данных в запись результатов. Преимуществами можно считать: максимальную абстрактность и возможность применить понятие алгоритма к объектам произвольной природы (не обязательно числовой).
Пример
1) Алгоритм Евклида ( НОД двух заданных целых положительных чисел a и b).
1. Обозревай данные числа a и b. Переходи к следующему указанию.
2. Сравни обозреваемые числа (a=b или a<b или a>b). Переходи к следующему указанию.
3. Если обозреваемые числа равны, то каждое дает искомый результат. Процесс вычисления остановить. Если нет, переходи к следующему указанию.
4. Если первое обозреваемое число меньше второго, то переставь их местами. Переходи к следующему указанию.
5. Вычитай второе число из первого и обозревай остаток. Переходи к указанию 2.
Элементарные шаги в алгоритме Евклида ? арифметические действия (вычитание, сравнение). Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям называются численными алгоритмами.
Блок-схемы алгоритмов
Связи между шагами можно изобразить в виде графа. Например для алгоритма Евклида это:
нет
да
Вершины ? шаги, ребра ? переходы между шагами. Вершины, из которых выходит одно ребро ? оператор, вершины, из которых выходит два ребра ? логическое условие или предикат. Важная особенность блок-схемы ? каждый шаг может не быть элементарным ?значит можно алгоритм ?разблочивать? (разбивать на отдельные задания, и раздавать для программирования разным лицам). Необходимо программисту блока знать: где лежит информация, форму ее представления, что должен делать блок, куда записать результат.
Можно также из нескольких алгоритмов, рассматриваемых как блоки, связать один большой алгоритм. Например: A1?вычисляет f1(x), A2 - вычисляет f2(x), блок-схема, представляющая композицию A1 и A2 представлена на рисунке
2.2 Машины Тьюринга
Машина Тьюринга состоит из
? управляющего устройства, которое может находиться в одном из состояний, образующих множество Q={q1, ?, qn}
? ленты, разбитой на ячейки, в каждой из которых может быть записан символ из конечного алфавита A={a1,?, am}
? устройства обращения к ленте ? считывающей или пишущей головки, которая в любой момент времени обозревает ячейку ленты и в зависимости от символа в ячейке и состояния управляющего устройства записывает в ячейку символ ( может быть совпадающий с прежним или пустой (т.е. стирает)), сдвигается на ячейку влево или вправо или остается на месте. При этом управляющее устройство переходит в новое состояние ( или остается в старом ).
Среди состояний управляющего устройства выделены начальное q1 и конечное qz(q0) ( z,0 ? не числовые переменные, а знак конца).
Таким образом память машины Тьюринга ? это внутренняя память (множество состояний) и внешняя память (лента).
Лента бесконечна в обе стороны, но в начальный момент времени только конкретное число ячеек заполнено непустыми символами, остальные пустые, т.е. содержат λ (пустой символ обозначает пробел).
Данные машины Тьюринга ? слова, как исходные, так и окончательные результаты.
Элементарные шаги ? считывание, запись символов, сдвиг головки, переход управляющего устройства в следующее состояние.
Детерминированность машины Тьюринга (последовательность шагов) определяется таким образом: для каждого внутреннего состояния qi и символа aj однозначно заданы:
а) следующее состояние qi′ ,
б) символ aj′, который нужно записать вместо aj в ту же ячейку,
в) направление сдвига головки ? dk :( L ? влево, R ? вправо, E (с) ? на месте)
Следовательно, Машина Тьюринга может описываться системой правил (команд), имеющих вид:
1) qiaj → qi′ aj′ dk (1)
2) aj
qi qi′ aj′ dk
3)
qi aj → aj′ dk qi′
Однозначно требуется, чтобы для любого j и любого i ≠z в системе команд имелась одна команда аналогичная (1) (с левой частью qiaj ); qz в левой части не встречается.
Полное состояние машины Тьюринга (внутреннее состояние + состояние ленты + положение головки ) называется конфигурацией или машинным словом и обозначается α1qiα2, где qi - текущее внутреннее состояние, α1 ? слово слева от головки, α2 ? слово = (символ обозревателя головки + символы справа от него ), причем слева от α1 и справа от α2 нет непустых символов. Например, конфигурация с внутренним состоянием qi , в котором на ленте записано abcde и головка обозревает d запишется abcqide.
Стандартная начальная конфигурация q1α (головка обозревает крайний левый символ слова на ленте). Стандартная заключительная конфигурация qzα.
Пример:
Алфавит А={1, λ}, состояния { q1 , qz },
Команды q1 1 q11R, q1λ q1 1 R
Для любой начальной конфигурации такая Машина Тьюринга работает бесконечно, заполняя 1 ленту вправо.
Если α1 q1 α2 => β 1 qz β2 , то машина Тьюринга Т перерабатывает слово α1 α2 в β 1 β2 , обозначим это Т(α1 α2) = β 1 β2 .
Исходными данными машины Тьюринга будем считать слова, записанные на ленте и векторы из таких слов.
Запись на ленте словарного вектора правильная, если она имеет вид α1 λ α2 λ ? αk-1 λ αk (λ Аисх), либо α1*α2 * ? αk-1 * αk (*-символ?разделитель, * Аисх).
Обозначим Арез ? алфавит результатов (совокупность слов, разделенных пробелами). Может быть что Аисх= Араз, также выделим Апр ? промежуточный алфавит, который может быть ≠ Аисх и Арез (в частности это разделитель). Таким образом алфавит ленты А=Аисх U Апр U Арез. В простейшем случае Аисх = Арез, А = АисхU{λ}
Пусть f ? функция, отображающая множество векторов над Аисх в множество векторов над Арез . f: Vисх → Wрез
Машина Тьюринга правильно вычисляет функцию f, если
1)Для любого V? Vисх и W ? Wрез , таких, что f(V)=W, следует q1V* qz W* (V*, W* - правильные записи V и W)
2)Для любого V, такого что f (V) ? не определена, машина Т, с начальной конфигурацией q1V* работает бесконечно.
Если для f существует машина Тьюринга, которая правильно ее вычисляет, то f называется правильно вычислимой по Тьюрингу.
Две машины Тьюринга с одним алфавитом Аисх эквивалентны , если они вычисляют одну и туже функцию.
Далее будем рассматривать числовые функции, т.е. f : N →N. Натуральные числа будем представлять в единичном (унарном) коде, т.е. Аисх = {1} либо Аисх = {1, *}, число x представляется словом 1?1=1x. Таким образом, числовая функция f(x1,?,xn) правильно вычислима по Тьюрингу, если существует машина Тьюринга q11x1 * 1x2 * ?* 1xn qz1y, когда f(x1,?,xn) = y и Т работает бесконечно, начиная с q11x1 *?1xn, когда f(x1,?,xn) не определена.
Пример (Сложение, машина Т+)
Сложить a и b означает следующее: слово 1a*1b переработать в 1a+b , т.е. удалить разделитель * и сдвинуть, например первое слагаемое, ко второму.
Обозначим машину Тьюринга - Т+, введем 4 состояния (q1,?,q4) и систему команд.
q11→ q2λR
q21→ q21R
q2*→ q31L
q31→ q31L
q3λ→ q4λR
Диаграмма переходов
1→R 1→ L
1→ λ R * →1 L λ→ λ R
Пример (Копирование машина Ткоп)
Переработка слова α → α * α; α = 1α
Система команд приведена в таблице
1 λ * 0
q1
q2
q3
q4 q20R
q21R
q31R
q41L qzλR
q3*R
q41R q1* L
q3*R
q4*L q11L
q10R
Диаграмма переходов
0 →1L 1→ R 1→ R *, 1→L
1 3 4
*→L 1→0R *, λ→ *R λ→ 1L
8 6
0→ R
λ→R 10
Ткоп при каждом проходе исходного числа 1α заменяет левую из его единиц 0 (q1) и пишет ( в состояние q3 ) одну единицу справа от 1α в ближайшую пустую клетку (q3 ). При первом проходе, кроме того ( состояние q2 ) ставится маркер. Таким образом копия 1α строится за α проходов. После записи очередной 1 машина переходит в состояние q4 , которое передвигает головку влево от ближайшего нуля, после чего машина переходит в состояние q1 и цикл повторяется. Он прерывается когда q1 обнаруживает на ленте не 1, а маркер. Это значит, что все 1 в 1α исчерпаны, т.е. сделано α проходов. Тогда головка возвращается влево в исходное положение, заменяя по дороге все 0 единицами.
Некоторые операции над машинами Тьюринга
Напомним, что композицией 2-х функций f1(x) и f2(g) называется g(x)=f2(f1(x)) .
Теорема
Если f1(x) и f2(x) вычислимы по Тьюрингу, то f2(f1(x)) также вычислима по Тьюрингу.
Пример
Рассмотрим машину, вычисляющую f(x) = 2x(x≠0). Ее можно представить как композицию Т+ (Ткоп). Ткоп строит двухкомпонентный вектор, Т+ вычисляет функцию от 2-х переменных (складывает их).
Диаграмма переходов
0 →1L 1→ R 1→ R *, 1→L
*→L 1→0R *, λ→ *R λ→ 1L Ткоп
0→ R
λ→ q21R
1→R 1→ L
1→ λ R * →1 L λ→ λ R
Т+
* →λ R
Пример (предикат):
Машина с нижеприведенной диаграммой вычисляет предикат ?α ? четное число?
λ→И
1→ λ L
1→R λ→ L
λ→Л
1→R 1→R 1→ λ L
λ→ L λ→И
Считывающая головка достигает конца числа α в состоянии q2, если число единиц четно; в состоянии q3, если число единиц нечетно. После чего она перемещается в исходное положение в состояние q4 или q5 (в каждом из них есть петля) и печатает И или Л. Чтобы предикат вычислялся с восстановлением, достаточно чтобы в петлях заменить 1→ λ L на 1→ L .
Машина Тьюринга Т++ - для сложения n чисел ( n=1,2,?)
1→ 1R 1→ 1R 1→1L
1→ λR *→ 1R λ→ λ L λ→ λ R
*→ λ R
*→*L
λ→ λ R
1→1L
q41→ q41 R ? проход 2-го (очередного) слагаемого
q4λ→ q5 λ L - проверка на 3-е (следующее ) слагаемое
Цикл из состояний q1, q2 , q3 ? ?зацикленная? Т+ , в которой заключены состояния совмещенные с начальной суммой, полученной на очередном цикле ? 1-е слагаемое следующего цикла. q4 ? разветвление. В нем проверяется условие, есть ли 2-е слагаемое, если да (* присутствует), то переход к новому циклу, если нет (λ после единиц), то машина выходит из цикла.
Заключение
1) Для вычислений на машине Тьюринга достаточно, чтобы лента была бесконечна в одну сторону, например вправо. Такая лента называется полулентой.
Теорема
Любая функция, вычислимая по Тьюрингу, вычислима на машине Тьюринга с правой полулентой.
Другими словами, для любой машины Тьюринга существует эквивалентная ей машина Тьюринга с правой полулентой. Аналогичная теорема формулируется для левой полуленты.
Такую эквивалентную машину можно построить например так: каждый раз, когда головке прежней машины нужно зайти за левый край ленты, новая машина предварительно сдвинет все написанное вместе с головкой на клетку вправо.
2)Тезис Тьюринга
Любой алгоритм может быть реализован машиной Тьюринга.
Тезис Тьюринга не является теоремой, это гипотеза, как например гипотезы об адекватности математических моделей физическим явлениям.
Подтверждением тезиса Тьюринга является математическая практика, а также то, что описание алгоритмов в терминах другой известной алгоритмической модели может быть сведено к его описанию в виде машины Тьюринга.
Примитивно-рекурсивные ф-ции
2.3 Рекурсивные функции
Каждый алгоритм однозначно ставит в соответствие исходным данным результат. Следовательно, с каждым алгоритмом однозначно связана некая функция, которую он вычисляет. На выяснении вопроса для каких функций алгоритмы существуют, а для каких нет основана теория рекурсивных функций.
Основным в ней является то, что все множество исследуемых функций строится из конечного числа исходных функций (базиса) с помощью простых операций, эффективная выполнимость которых достаточно очевидна. Операции над функциями будем называть операторами.
2.3.1 Примитивно ? рекурсивные функции
К вычислимым функциям можно отнести все константы, т.е. 0 и все натуральные числа 1,2,?. Но можно обойтись 0 и функцией следования f(x)=x+1(x'). Кроме того в базис включим функции тождества, обозначим семейство таких функций {Inm}: Inm(x1,x2,..,xn)=xm(m≤n). Иначе ее можно назвать функцией введения фиктивных переменных. Определим семейство операторов суперпозиции {Snm} : для h(x1,?,xm), gi(x1,?,xn), i=1,?,m.
Snm (h,g1,?gm)=h(g1(x1,?,xn),?, gm (x1,?,xn))=f(x1,?,xn).
Оператор примитивной рекурсии Rn
определяет (n+1)-местную функцию f через n-местную функцию g и (n+2)-местную функцию h таким образом:
f(x1,?,xn,0)= g(x1,?,xn)
f(x1,?,xn,y+1)= h(x1,?,xn,y, f(x1,?,xn,y))
Эти формулы называются схемой примитивной рекурсии.
В случае, когда f одноместна, получаем следующее представление схемы
f(0)=c
f(y+1)=h(y,f(y))
Для вычисления f(x1,?,xn,k) понадобится (k+1) вычислений по схеме при y=0,1,2,..,k.
Функция называется примитивно-рекурсивной, если она может быть получена из константы 0, функции x? и функций Inm с помощью применения конечного числа операторов суперпозиций и схем примитивной рекурсии.
Примеры
1. Сложение f+(x,y)=x+y - примитивно рекурсивно
f+(x,0)=x=I11(x)
f+(x,y+1)=f+(x,y)+1=(f+(x,y))'
2. Умножение f×(x,y)=xy - примитивно рекурсивно,
f×(x,0)=0
f×( x,y+1)= f×( x,y)+ x= f×( x, f×( x,y))
3. Возведение в степень fexp(x, y)=xy - примитивно рекурсивно
fexp(x, 0)=1
fexp(x, y+1)= xy x= f×( x, fexp(x, y))
Определим функцию x 0 y (арифметическое вычитание)
Покажем примитивную рекурсию следующих функций
4а) f(x)= x 1 определяется схемой:
f(0)=0 1=0
f(y+1)=y
4б) f(x,y)= x y
f(x,0)=x
f( x,y+1)=x (y+1)=(x y) 1= f(x,y) 1
4в) f(x,y) = |x-y|= (x y)+(y x)
4г)
sg(0)=0
sg(x+1)= 1
4д) min (x,y)=x (x y)
4е) max (x,y)= y+(x y)
5а). r(x,y) ? остаток от деления y на x
например, r(3,5)=2), r(3,8)=2, r(x,0)=0
т.е. r(x,y+1)=(r(x,y)+1) sg(|x (r(x,y)+1)|)
если y+1 не делится на x, то sg(|x (r(x,y)+1)|)=1 и r(x,y+1)= r(x,y)+1
если y+1 делится на x, то r(x,y)+1= sg(|x (r(x,y)+1)|)=0
5б). q(x,y)=[y/x] ? частное от деления y на x, т.е. целая часть дроби.
q(x,0)=0 (sg(x)=1 sg(x))
т.е. q( x,y+1)=q(x,y)+sq(|x(r(x,y)+1)|)
если y+1 делится на x , то q( x,y+1) на 1 больше, чем q(x,y).
если нет, то q( x,y+1)= q(x,y).
a mod b ? целый остаток
a div b ? целая часть b/a
Из этих примеров следует примитивная рекурсия ?арифметизированных? логических функций, т.е. функций числовых, которые на множестве {0,1} ведут себя как логические. Действительно, если х,у{0,1}, то
х = 1 х
x y = max (x,y)
x y = min (x,y)
т.к? {,,} полная система логических функций и суперпозиция ? примитивно-рекурсивный оператор, то все логические функции примитивно - рекурсивны.
Отношение R(x1,?,xn) называется примитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция R :
Предикат называется примитивно?рекурсивным, если его характеристическая функция примитивно?рекурсивна. В силу выражения логических функций через арифметические, если предикаты P1,?,Pn - примитивно?рекурсивны, то полученный из них с помощью логических операторов любой другой предикат - примитивно?рекурсивен.
Пример
1. P(n,x) : x делится на n
P(n,x) примитивно?рекурсивен, т.к. его характеристическая функция
2. P(n,m,x): x делится на m и на n
P(n,m,x): - примитивно?рекурсивен для любого m и n, т.к.
Pn,m(x)=Pm(x) Pn(x)
2.3.2 Примитивно ? рекурсивные операторы
Примитивно?рекурсивный оператор сохраняет примитивно-рекурсивные функции , то есть результат его применения к примитивно?рекурсивным функциям дает снова примитивно?рекурсивную функцию. Операторы Snm , Rn ? примитивно?рекурсивные операторы по определению. Рассмотрим другие примитивно?рекурсивные операторы. Их использование позволяет существенно сократить примитивно ? рекурсивное описание функций.
и ? примитивно?рекурсивные операторы (т.к. используют только и , примитивная рекурсия, котораых доказана). Такими операторами являются суммирование и умножение от k до z:
и
- оператором или ограниченным оператором наименьшего числа (или ограниченным оператором минимизации) называется
Из предиката P(x1,?,xn,y) с помощью оператора y≤z получается функция . Второй случай в определении добавлен для того, чтобы была всюду определена.
Пример
Рассмотрим предикат предыдущего примера
тогда
Ограниченный - оператор примитивно?рекурсивен, так как его характеристическая функция имеет вид
Ограничение z в ограниченном - операторе дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката P.
Далее будет показано, что неограниченный - оператор не является примитивно ? рекурсивным.
2.3.3 Частично ? рекурсивные функции
Не все функции примитивно?рекурсивные, так как каждая примитивно?рекурсивная функция имеет конечное описание, т.е. задается конечным словом в некотором алфавите. Множество конечных слов счетно, следовательно примитивно?рекурсивные функции образуют счетное подмножество несчетного множества функций типа . ( Например функция Аккермана - вычислима, но растет быстрее, чем любая примитивно?рекурсивная функция поэтому не является примитивно?рекурсивной).
Следовательно вычисляемые функции не обязательно примитивно?рекурсивные. Введем новое понятие рекурсивности функций:
Частично-рекурсивная функция ? это функция, которая может быть построена из простейших функций 0, x+1, Inm с помощью конечного числа применения суперпозиций, примитивной рекурсии и неограниченного оператора.
При этом - оператору можно придать стандартную форму:
f(x1,?,xn) = y(g(x1,?,xn-1,y)= xn) или
f(x1,?,xn) = y(g(x1,?,xn-1,y)= 0)
Таким образом, среди рекурсивных функций появляются не полностью определенные, т.е. частичные функции (когда g(x1,?,xn-1,y)=0 не имеет решения).
Общерекурсивная функция ? частично- рекурсивная функция, если она всюду определена. (Например, функция Аккермана).
Тезис Черча
Всякая функции, вычислимая некоторым оператором, частично?рекурсивна.
Теорема
Всякая функция вычислимая на машине Тьюринга ? частично ?рекурсивна.
Вычислит сложность алоритма
2.4 Вычислительная сложность алгоритма
2.4.1 Понятие сложности алгоритма
Пусть А ? алгоритм решения некоторого класса задач.
Назовем размерностью задачи (n) совокупность параметров (их количество), характеризующих объем обрабатываемых исходных данных и определяющих необходимые для выполнения расчетов ресурсы (время, память).
Например : Машина Тьюринга ? n ? длина цепочки, граф ? n ? количество вершин.
С понятием размерности задач связано понятие вычислительной сложности. Различают временную и емкостную сложность алгоритма.
Временная сложность - Т(n) ? функция , зависящая от размерности задачи время выполнения А.
Емкостная сложность ? С(n) ? функция, зависящая от размерности задачи ? необходимая память.
Технические характеристики ЭВМ при таком подходе не учитываются.
Оценивая вычислительную сложность ориентируются на количество основных операций (сложение, сравнение и т.д.), которые должен выполнить алгоритм для решения каждой задачи размерности n.
Можно рассмотреть 3 варианта оценки вычислительной сложности :
1) в ?худшем случае? - в процессе расчетов учитывается самая длинная последовательность основных операций.
2) В ?лучшем случае? - как правило это вырожденные ситуации.
3) В ?среднем? - для расчета которых необходимо иметь статистические данные о том как часто реализованы ?лучшие? и ?худшие? варианты.
Будем говорить , что f(n) и g(n) одного порядка для больших n: f(n)=О(g(n)), если
Например : f(n) = 2n5 + 6 n4 + 6 n2 +18 = O (n5), g(n)= n5.
Будем говорить, что f(n) имеет меньший порядок для больших чем g(n), если
Например : f(n) = 2n5 + 6 n4 + 6 n2 +18 = 0 (n6).
Причина использования оценок в форме О и 0 связана с тем, что точные зависимости при расчете сложности алгоритма зависят от особенностей реализации алгоритма и требуют вычислений лишних для поставленной задачи.
При достаточно больших n константы в формулах не оказывают влияния на порядок возрастания, но если константы сравнимы по порядку с n, то в каком-либо диапазоне данных это может привести к изменению эффективности алгоритма.
С точки зрения эффективности все алгоритмы делят на 2 класса: полиномиальные и экспоненциальные.
А ? полиномиальный, если f(n) растет не быстрее, чем полином k степени от n ТА(n) = О(Р k(n)), иначе А ? экспоненциальный.
Пример
полиномиальные: линейные О(n)
полулинейные О(n log n)
квадратичные О(n2)
экспоненциальные: О(n!) = О(n n)
Большинство экспоненциальных алгоритмов ? это варианты полного перебора, полиномиальные алгоритмы можно построить лишь тогда, когда удается найти решение без перебора всех допустимых вариантов данных.
Назовем классом Р-задач, задачи, для которых существует детерминированный алгоритм, реализующий эту задачу за полиномиальное время.
Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.
Класс задач, для решения которых существует недетерминированный алгоритм, решающий эту задачу за полиномиальное время , называется классом NP задач.
Модель недетерминированного алгоритма
Варианты исчерпаны
вариант решения решение
Класс Р ? задач входит в класс NP задач: Р NP (алгоритм А ? пустой). NPР являются труднорешаемыми.
В классе NP содержатся NP- полные задачи, для которых не существует детерминированного алгоритма, работающего за полиномиальное время.
Так как алгоритм решения NP задач состоит из алгоритма угадывания и алгоритма проверки, NP- полные задачи требуют полного перебора и решаются рекурсивно так, что алгоритм поиска решения на каждом шаге рассматривает все возможные варианты решений на глубине 1 и решает оставшуюся задачу меньшего размера.
Примеры NP- полных задач
1) генерация всех k-элементных подмножеств какого-либо n-элементного множества
2) построение разбиений множества из n?элементов на k1, k2, ? km?элементные подмножества
3) задача коммивояжера: коммивояжер должен посетить n городов так, чтобы максимально снизить расходы на поездку TA(n) = О (n!)
4) построение таблиц значений логарифмических функций TA(n) = О( 2n )
2.4.2 . Методы оценивания вычислительной сложности.
Оценивая вычислительную сложность алгоритма, будем руководствоваться равномерным весовым критерием: всякая основная операция алгоритмического языка занимает единицу времени, а каждая переменная единицу памяти, независимо от величины этой переменной. При этом не учитываем величину числа, длину машинного слова, различия в количестве поразрядных операций, т.е. не учитываем особенности машинной реализации алгоритма.
Однако, если такие требования к оценке не устраивают, то используют другие критерии, например, логарифмический весовой критерий, в котором время выполнения основной операции и память, требуемая для размещения одной переменной, пропорциональны величине этой переменной. Пропорциональность выражается с помощью логарифмической зависимости, которая определяется количеством двоичных символов, необходимых для представления числа.
Весовые функции арифметических действий выражаются через базовые операции над двоичными переменными.
Оценка сложности на уровне блок-схем
Блок - схема - направленный граф, содержащий вершины 3-х типов :
1) Функциональная
2) Предикатная P
3) Объединяющая
Структурная блок-схема представляется в виде композиции четырех элементарных, называемых структурами управления:
1) композиция К
2) альтернатива А
3) итерация с постусловием I
4) итерация с предусловием
Использование 1) ? 4) достаточно для любого представления алгоритма, однако это будет не всегда просто и естественно, так как существует большее разнообразие структур.
Применяя вышесказанное, можно записать временную сложность в таком виде:
1) Т(К) = Т (F 1) + Т (F 2)
2) Тх(А) = Тх(Р) + max { Тх (F 1) , Тх (F 2) }
Тср(А) = Тср(Р) + Р1 Тср (F 1) + Р2 Тср (F 2)
Р1 и Р2 ? вероятности перехода по каждой дуге от Р
3) , 4) для каждого повторения: Тх(РF)= Тх(Р) + Тх(F), учитывая m повторений: Тх(I)= m Тх(РF)
Пусть f(n) ? зависимость чисел повторяющегося цикла от размерности задачи, если число операций в цикле оценивается константой с, то Тц1 = О(f(n)). В простейшем случае, когда просто просматривается путь длины n Тц = О(n).
Если имеется двойной цикл, причем число повторений внешнего f1(n), а внутреннего f2(n), то Тц2 = О(f1(n)*f2(n)).
Если параметр внутреннего цикла зависит от внешнего, например
for i := 1 to n do
for j:= j +1 to n do ?
Тогда:
i = 1 - внутренний цикл выполняется (n ? 1) раз
i = 2 - внутренний цикл выполняется (n ? 2) раз
. . .
i = n - внутренний цикл выполняется 0 раз
общее число повторов (n ? 1) + (n ? 2) + ? 1 + 0 = О(n2)
Оценка сложности на уровне моделей.
Такой вид оценок применяется в случае сложных программ, когда подробная блок?схема затрудняет вычисление оценок из-за громоздкости, тогда удобней оценить алгоритм глядя как бы сверху, т.е. на модель алгоритма.
Рассмотрим в качестве примера рекурсивный алгоритм.
Задача 1
Разместить слова длины h, использующие k букв в словаре. Модель ? дерево Число выходящих ребер из каждой вершины ? число способов выбора очередной буквы слов (т.е. число букв в алфавите). Каждый кольцевой вершине соответствует одно слово. Высота дерева ? h. Поиск слова ? обход дерева в прямом порядке.
Алгоритм WORD (h)
1. Найти множества слов, у которых совпадают первые буквы.
2. Исключить первую букву в каждом подмножестве слов.
3. Выполнить WORD (h-1) для укороченного слова
ТWORD(h)=(Т1+Т2)Т3=(k + const)·Т(h - 1)
Начальное условие: Т(1) = 1, решая уравнение получаем ТWORD(h) = О (k h)
Задача 2
Составить всевозможные неупорядоченные пары из n-элементов последовательности {а1,?а n }
1. i = 2 до n сформировать пары вида {а1,а. i }
2. исключить а1 из последовательности
3. выполнить алгоритм для последовательности {а2,?а n }
Т1 = n ? 1, Т2 = const Т3 = Т (n ? 1)
Т(n) = n + const + Т(n ? 1) , Т(1) = 0 ==>
Т(n) = n + c + ( n + c + Т(n ? 2)) = 2 n + const + Т(n ? 2)
Т(n) = (k + 1) n + с + Т(n ? (k + 1))
Т(n) = (n ? 1) · n + с + Т(n ? (n ? 1)) = О(n2)
Итак, количество операций вычислялось без использования блок?схем. Важно было только определить, как представить задачу размерности n через подзадачи меньшей размерности.
Алгоритмы, основанные на таком принципе (разбиение на задачи меньшей размерности) моделируются с помощью деревьев.
Сформулируем теорему, определяющую один из возможных путей построения эффективного алгоритма, использующего этот принцип:
Теорема
Пусть имеется алгоритм для решения задачи размерности n, причем это решение конструируется из решений a подзадач размерности n/c алгоритмом перехода, оценивающимся сложностью O(n), тогда Т(n) = а · Т (n/c) + О(n), при начальном условии Т(1) = b.
Решение этого уравнения определяется в зависимости от а и с.
Законы логики
1. Идемпотентность: х v x - x(дизъюнкция); х ^ x - x(конъюнкция);
2. Коммутативность: x v y - x v x; x ^ y - y ^ x;
3. Ассоциативность: x v(y v z) - (x v y)v z; x ^(y ^ z) - (x ^ y)^ z;
4. Дистрибутивность: x v(y v z) - (x v y)^(x v z); x ^(y v z) - (x v y)v(x ^ z);
......................
Формулы логики
Формула называется тождественно-истинной или тафтологией, если она истина при всех значениях переменных, входящих в неё.
Формула называется тождественно-ложной, если она принимает значения "ложно" при всех значениях переменных входящих в неё.
Понятие высказывания
Суждение, утверждающее что-либо о чем либо, назывется высказыванием, если можно сказать истинно оно или ложно, в данный момент места и времени.
Предмет дискретной М
Дискретная математика – самостоятельный раздел современной математики, изучающий св-ва различных структур, имеющих конечный характер, т.е. такие понятия как: непрерывность, бесконечность, предел – не являются предметом изучения дискретной метематики.
Экология как биологическая наука
Термин "Экология" был введён в 1866 г. немецким ученым зоологом Геккелем..... и тд.
Обмен веществ клетки
Совокупность химических реакций биосинтеза и распада...
Биосинтез белка - одно из наиболее важных свойств живой клетки
Водоросли
Водоросли - это низшие растения, живущие приемущественно в водной среде
Известно около 30000 видов...
Проведення вступного і первинного інструктажів по ОП.
46.1- ВСТУПНИЙ
- при прийняті на роботу
- з студентами які проходять виробничу практику
- у разі екскурсії на підприємстві
- при вступі у навчальні заклади
2- ПЕРВИННИЙ
- з новоприйнятими на роботу та відрядженими
- при переводі з одного підрозділу в інший
- з студентами учнями при початку проведення лабораторно-практичних робіт , які несуть небезпеку
Первинний інструктаж; проводиться до початку роботи
безпосередньо на робочому місці з працівником: — новоприйнятим (постійно чи тимчасово) на підприємство; — який переводиться з одного цеху виробництва до іншого; — який буде виконувати нову для нього роботу; — з відрядженим працівником, який бере безпосередню участь у виробничому процесі на підприємстві.
Вступний інструктаж проводиться в кабінеті охорони праці або
в приміщенні, що спеціально для цього обладнано, з використанням
сучасних технічних засобів навчання, навчальних та наочних посібників
за програмою, розробленою службою охорони праці з урахуванням
особливостей виробництва.
Первинний інструктаж провод. індивідуально чи з групою
осіб одного фаху за діючими на підприємстві інструкціями з охорони
праці відповідної до виконуваних робіт, а також з урахуванням вимог
орієнтовного переліку питань первинного інструктажу .
Вступний інструктаж проводиться на початку занять працівником
служби охорони праці, а за відсутності такого — особою, на яку наказом
керівника закладу освіти покладено ці обов'язки. Запис про проведення вступного
інструктажу робиться в журналі реєстрації вступного інструктажу, який
зберігається в службі охорони праці або в працівника, що відповідає за
проведення вступного інструктажу.
Санітарна класифікація виробництв.
47Промислові підприємства, що виділяють газ, дим, пил, кіпоть, неприємні запахи, що створюють шум, не можна розташовувати до найближчого житлового району з підвітряної сторони; ці підприємства треба відокремлювати від житлових районів санітарно-захисними зонами (розривами).
Територія санітарно-захисної зони призначена для:
- забезпечення зниження рівня впливу до необхідних гігієнічних нормативів по усіх факторах впливу за її межами;
- створення санітарно-захисного барєра між територією підприємства (групи підприємств) і територією житлової забудови;
- організації додаткових озеленених площ, що забезпечують екранування, асиміляцію і фільтрацію забруднювачів атмосферного повітря і підвищення комфортності мікроклімату.
Рівень вмісту шкідливих домішок в атмосферному повітрі за межами санітарно-захисної, зони не повинен перевищувати гігієнічних нормативів, встановлених для атмосферного повітря населених місць.Санітарна характеристика виробничих процесів
І група. Виробничі процеси, які протікають при нормальних метеорологічних умовах і при відсутності шкідливих газів і пиловиділень:
ІІ група. Виробничі процеси, які протікають при несприятливих метеорологічних умовах чи пов’язані з виділенням пилу чи напруженою фізичною роботою
ІІІ група. Виробничі процеси з різко визначеними факторами шкідливостей і з забрудненням ними робочого одягу:
ІV група. Виробничі процеси які вимагають особливого режиму для забезпечення якості продукції:
Надання долікарської допомоги при утепленнях.
48.Утоплення – смерть від гіпоксії, що виникає в результаті закриття дихальних шляхів рідиною, найчастіше водою.
Доставивши потопаючого на берег, приступають до надання першої допомоги, характер якої залежить від його стану. Якщо потерпілий знаходиться у свідомості, у нього задовільний пульс і дихання збережено, то достатньо укласти його на суху тверду поверхню таким чином, щоб голова була опущена низько, потім роздягнути, розтерти руками або сухим рушником. Бажано дати гаряче пиття (чай, кава, дорослим можна трохи алкоголю, наприклад 1-2 столові ложки горілки), закутати теплою ковдрою і дати відпочити.
Якщо потерпілий при вилученні з води знаходиться без свідомості, але у нього збережені задовільний пульс і дихання, то слід закинути його голову і висунути нижню щелепу, після чого укласти таким чином, щоб голова була опущена низько, потім своїм пальцем (краще обгорненим носовою хусткою) звільнити його ротову порожнину від мулу, тини і блювотних мас, насухо обтерти і зігріти.
Вплив електроструму на організм людини.
50. Особливості впливу електричного струму на організм людини.
Електричний струм, проходячи через тіло людини, зумовлює перетворення поглинутої організмом електричної енергії в інші види і спричиняє термічну, електролітичну, механічну і біологічну дію.
Найбільш складною є біологічна дія, яка притаманна тільки живим організмам.
Термічний вплив електричного струму характеризується нагріванням тканин аж до опіків.Більше половини всіх електротравм становлять опіки. Вони важко піддаються лікуванню, тому що глибоко проникають у тканини організму. При проходженні через тіло людини електричного струму в тканинах виділяється тепло.
Електролітична дія струму виявляється у розкладанні органічної рідини, в тому числі крові, яка є електролітом, та в порушенні її фізико-хімічного складу.
Механічна дія струму призводить до розриву тканин організму внаслідок електродинамічного ефекту, а також миттєвого вибухоподібного утворення пари з тканинної рідини і крові.
Електротравми умовно поділяють на загальні і місцеві. До місцевих травм належать опіки, електричні знаки, електрометалізація шкіри, механічні пошкодження, а також електрофтальмія (запалення очей внаслідок впливу ультрафіолетових променів електричної дуги).
Електричний удар є порушення живих тканин організму проходить через нього електричним струмом, що супроводжується мимовільним скороченням м'язів. Поразка людини електричним струмом може відбутися при дотиках: до струмоведучих частин, що знаходяться під напругою; відключеним струмоведучих частин, на яких залишився заряд або з'явилося напруження у результаті випадкового включення; до металевих неструмоведучих частин електроустановок після переходу на них напруги зі струмовідних частин.
Поняття про шум і вібрацію, їх вплив на організм.
51.Шум – хаотичний склад різних по рівню і частоті звуків, які негативно впливають на організм людини.
Людина сприймає звукові коливання від 16-20000Гц.
Шум характеризується такими показниками:
- частотою коливань
- інтенсивністю
- звуковим тиском
Являється біологічним подразником на нервову систему, викликає головні болі, підвищення тиску, зниження гостроти зору, концентрації уваги ….
Викликає порушення діяльності шлунка серцевинної системи , призводить до захворювання слухового апарату.
Вібрація – механічні коливання пружних тіл з низькими частотами при великих амплітудах.
Негативно впливає на організм людини викликаючи віброхворобу. Основними проявами є порушення нервової та серцево-судинної системи, поява головного болю. Заморочення та зниження працездатності, порушення сну… місцеві вібрації малої інтенсивності поліпшують функціональний стан , прискорюють загоєння ран.
Перевезення людей автомобілями.
52.Дозволяється перевозити пасажирів у транспортному засобі обладнаному місцями для сидіння в кількості, що передбачена технічною х-кою так, щоб вони не заважали водієві керувати транспортним засобом і не обмежували оглядовість, відповідно до правил перевезення.
Водіям маршрутних транспортних засобів забороняється під час перевезення пасажирів розмовляти з ними, їсти, пити, палити, а також перевозити пасажирів і вантаж у кабіні, якщо вона відокремлена від салону.
Під час перевезення в автобусі, мікроавтобусі організованої групи дітей повинно бути не менше одного дорослого супровідника. При цьому спереду і ззаду обов'язково встановлюється згідно з вимогами підпункту "в" пункту 30.3 цих Правил розпізнавальний знак "Діти" .
Водію забороняється починати рух до повного зачинення дверей та відчиняти їх до зупинки транспортного засобу.
Забороняється перевозити:
а) пасажирів поза кабіною автомобіля (крім передбачених цими Правилами випадків перевезення пасажирів у кузові вантажного автомобіля з бортовою платформою або в кузові-фургоні, призначених для перевезення пасажирів), у кузові автомобіля-самоскида, трактора, інших самохідних машин, на вантажному причепі, напівпричепі, в причепі-дачі, в кузові вантажного мотоцикла;
б) дітей, зріст яких менше 145 см або тих, що не досягли 12-річного віку, - на передньому сидінні легкового автомобіля, мікроавтобуса (за відсутності спеціального дитячого сидіння) і на задньому сидінні мотоцикла;
в) дітей до 16-річного віку в кузові будь-якого вантажного автомобіля;
г) організовані групи дітей у темну пору доби.
Предмет
53. Основи охорони праці» як наука виникла й сформувалася на стику наук про працю і людину.
Наука про охорону праці тісно пов’язана з іншими науками. Вона широко використовує найновіші досягнення науки і техніки, базується на теоретичних розробках з фізики, хімії, математики, електроніки, медицини, економіки тощо. Важливе місце в розробці питань охорони праці займають такі наукові дисципліни, як ергономіка, інженерна психологія і фізіологія праці, технічна естетика.
Завданнями охорони праці є також: знаходження оптимальних співвідношень між різними факторами виробничого середовища;впровадження норм гранично допустимих рівнів виробничих факторів, визначення ступеня шкідливості і небезпеки праці; розробка та планування заходів щодо поліпшення умов праці; забезпечення безпеки виконання робіт працівниками;
впровадження технічних засобів і заходів щодо боротьби з травматизмом і профзахворюваннями;розробка методів оцінки соціальної та економічної ефективності заходів з удосконалення умов і охорони праці.
Складається з 5 розділів
1- правові та організаційні питання з охорони праці
2- основи гігієни та виробничої санітарії
3- основи техніки безпеки
4- основи пожежної безпеки
54.Автоматичне гасіння пожеж.
55.Системи освітлення і їх характеристика.
56.Джерела шуму і вібрації.
57.Прилади і апарати для гасіння пожеж водою.
58.Захисне заземлення, занулення і автоматичне вимкнення.
59.Устаткування по забезпеченню безпечної роботи котлів посудин під тиском.
60.Вимірювання рівня освітленості. Принцип роботи і загальна будова приладу.
54. Системи автоматичного пожежогасіння приводяться в дію пожежною автоматикою за об'єктивними показниками й забезпечують оперативне гасіння вогнища загоряння без участі людини.
Конструктивно автоматичні установки пожежогасіння складаються з резервуарів наповнених необхідною кількістю вогнегасної речовини, пристроїв керування й контролю, системи трубопроводів і насадок-розпилювачів. Кількість розпилювачів, довжини трубопроводів й обсяг ємностей для вогнегасної речовини визначаються ретельними розрахунками.Використовують спринклерні та дрен черні установки автоматичного гасіння. Автоматична установка складається
- джерела водопостачання, гідрант, пожежна водойма
- мережа труб для транспортування
- джерело подачі води
- зрошувачі.
Використовують також модульні установки, автоматичні установки малогабаритні одна з них є ПУМА – 12п. може загасити пожежу 50куб.м. а також модуль буран – 18куб.м.
55. Освітлення виробничих приміщень може бути природним, штучним і суміщеним. Освітлення суміщене, коли в світлий час доби недостатнє за нормами природне освітлення доповнюють штучним.
Природне освітлення має велике гігієнічне значення, яке полягає в сильній тонізуючій дії на організм людини.
Тривала відсутність природного (сонячного) світла гнітючого діє на психіку людини, сприяє розвитку почуття тривоги, знижує інтенсивність обміну речовин в організмі, послаблює реактивність організму, сприяє розвиткові короткозорості та втомлюваності. Тому санітарні норми передбачають обов’язкове природне освітлення усіх виробничих, адміністративних, підсобних і побутових приміщень, без якого можна обійтись тільки у виняткових випадках. Наприклад, у приміщеннях, де обслуговуючий персонал виробничим процесом (на складах, які розміщуються в підвалах тощо). У цих випадках влаштовують електричне освітлення.
Природне освітлення може бути боковим - крізь світлові прорізи в зовнішніх стінах; верхнім - крізь світлові ліхтарі в покрівлях, а також прорізи в місцях перепадів висот суміжних прильотів будівлі; комбінованим - крізь прорізи для бокового і верхнього освітлення.
Для створення раціонального освітлення необхідно нормувати рівень освітленості на робочих поверхнях. Однак таке нормування природного світла викликало б великі труднощі, тому що освітленість коливається в дуже широких межах і залежить від пори року, дня, хмарності, відбиваючих властивостей поверхні землі (сніг, трав’яний покрив, асфальт тощо).
Штучне освітлення виробничих ділянок і будівель може бути загальним, місцевим і комбінованим.
56.ДЖЕРЕЛА ШУМУ ТА ВІБРАЦІЇ
*Джерела виникнення шуму поділяють 4 види
1- аеродинамічні – виникає при русі повітряних мас
2- гідравлічний – виникає при русі води, рідинних мас.
3- механічний – виникає при роботі певних вузлів та деталей
4- електромагнітний - при роботі електромагнітних пристроїв
* за впливом на організм вибірці поділяють
1- загальні – впливає на весь організм
2- місцева – тільки на окремі органи
За джерелом виникнення поділяють на 3 види
1- транспортна – виникає при русі транспорту
2- транспортно-технічна – виникає пр. роботі механізмів, які виконують технологічні операції (бульдозер)
3- технологічна – виникають при роботі стаціонарних машин і механізмів
58.Захисне заземлення – це зумисне електричне з’єднання з землею металевих не струмопровідних частин, які можуть опинитись під напругою внаслідок пошкодження електричної ізоляції
Занулення – це зумисне з’єднання металевих частин електроустановки, які зазвичай не перебувають під напругою з нульовим захисним провідником
Заземлення і занулення не завжди гарантує безпеку людей від ураження струмом. Для захисту використовують захисне відключення.
Захисне відключення – це швидкодіючий захист, який забезпечує автоматичне відключення електроустановки при виникненні в ній небезпеки ураження людини струмом. Цей вид захисту спрацьовує за 0,1 – 0,05с, а занулення 0,2с і більше.
При такому нетривалому проходженні струму через тіло людини безпечним є навіть струм 500 – 650мА.
Захисне вимикання окремо чи сукупно з іншими засобами захисту виконує такі функції:
- захист при замиканні на землю або корпус обладнання;
- захист при появі небезпечних струмів витікання;
- захист при переході вищої напруги на сторону нижчої;
- автоматичний контроль кола захисного заземлення і занулення
59. Для управління роботою котлів і посудин що працюють під тиском вони мають мати: Прилади що запобігають підвищенню тиску, манометри, термометри, показники рівня води, запірно і регулювальну арматуру. Запобіжні клапани встановлюють на патрубках що приєднані до котла. Вони поділ.: важільно вантажні клапани- пристрій що працює, якщо котли підвищую тиск понад допустимий, пружинний запобіжнй клапан для випуску рідкого чи газоподібного палива в атмосферу при різкому підвищенні тиску. Випобухові запобіжні клапани розм.. в місцях які виключалиб можливість травмування персоналу. Манометри встан. На котлах для постійного слідкування за режимом їх роботи. Не допускаються користування манометрами, якщо вийшов його перевірки, якшо на манометрі відсутня пломба чи клеймо про здійсню перевірки, якщо розбите скло чи інше пошк. Що може вплинути на результат показів. Термометри встановлюють для забезп. Надійної роботи котлів при вході чи виході з котла. Допустима температура гарячої води позначається на шкалі термометра червоною рискою. Показчики рівня води встан. На котлах для постійного контролю за її рівнем. Шкала може бути проградуйована, на ній має бути вказано мінімально і максимальні рівні рідини в будь якій установці. Запірна арматура має мати маркування має вказуватися діаметр умовного проходу, матеріал з якого виготовленого вентель, умовний чи робочий тиск, температура середовища, напрям потоку середовища.