Вопрос. Порядок вычисления гистограмм.
Гистограмма позволяет оценить состояние качества. Гистограмма представляет собой столбчатый график, построенный по полученным за определенный период (час, неделю, месяц) данным, которые разбиваются на несколько интервалов. Число данных, попавших в каждый из интервалов (частота), выражается высотой столбика.
Гистограмма - это инструмент позволяющий зрительно оценить закон распределения величины разброса данных, а также принять решение о том, на чем следует сфокусировать внимание для целей улучшения процесса.
Порядок построения гистограммы
1. Собрать данные, выявить максимальное и минимальное значения и определить диапазон (размах) гистограммы.
2. Полученный диапазон разделить на интервалы, предварительно определив их число (обычно 5-20 в зависимости от числа показателей) и определить ширину интервала.
3. Все данные распределить по интервалам в порядке возрастания: левая граница первого интервала должна быть меньше наименьшего из имеющихся значений.
4. Подсчитать частоту каждого интервала.
5. Вычислить относительную частоту попадания данных в каждый из интервалов.
6. По полученным данным построить гистограмму - столбчатую диаграмму, высота столбиков которой соответствует частоте или относительной частоте попадания данных в каждый из интервалов:
-наносится горизонтальная ось, выбирается масштаб и откладываются соответствующие интервалы;
|
|
|
-затем строится вертикальная ось, на которой также выбирается масштаб в соответствии с максимальным значением частот.
Вопрос. Элементы компьютерного моделирования: клеточные автоматы и их применение.
(БРАЛА ИЗ ЛЕКЦИИ КУРАВСКОГО)
Из истории: Клеточные автоматы впервые были предложены фон Нейманом, исследовавшим с теоретической точки зрения вопрос о том, может ли машина эволюционировать и порождать себе подобных.
Клеточные автоматы представляют собой системы, состоящие из дискретных клеток, или ячеек.
- Клетки могут располагаться на одномерной прямой, плоскости или в многомерном пространстве.
- Каждая клетка имеет заданное количество «соседей» и может находиться в одном из нескольких состояний.
Пример: игра «Жизнь».
- Клеточные автоматы дают полезные модели для исследований в естесственных науках: моделирование роста снежинки..
Адаптация клеточных автоматов для исследования популяции:
Исследуемая величина:
- эмоциональное состояние
- информативность
- инфицированность
- вредная привычка
- мнение по какому-либо вопросу и т.д.
Состояние клеток:
- уровни эмоционального состояния
- степени информативности
- варианты мнений
- степени податливости влиянию
|
|
|
- степени усвоения вредных привычек и т.д.
Вопрос. Уточнения понятия алгоритма. Тезис Тьюринга.
Решение задачи точного определения понятия «алгоритм» было получено в 30-х гг. XX в. в двух формах:
1) решение основано на понятии рекурсивной функции;
2) решение основано на описании точно очерченного класса вычислительных процессов, реализуемых на машинах Тьюринга.
Отправляясь от аксиоматики Гильберта, Гёдель описал класс всех рекурсивных функций как класс всех арифметических функций, определимых в некоторой формальной системе. Исходя из других предпосылок, Чёрч пришёл в 1936 г. к тому же классу арифметических функций. Анализ идей, которые привели к этому классу функций, позволил Чёрчу выдвинуть гипотезу о том, что класс рекурсивных функций тождествен классу всюду определённых вычислимых функций (тезис Чёрча). Так как понятие “вычислимые функции” точно не определено, то тезис Чёрча доказать нельзя. Этот тезис является научной гипотезой, в пользу которой высказан ряд важных доводов и которую не удалось опровергнуть. Одним из таких доводов является то, что различные уточнения понятия “алгоритм”, сделанные разными авторами, оказались равносильными. Так, например, нормальный алгоритм Маркова оказался сводимым к ОРФ.
|
|
|
Для того, чтобы охватить бесконечно длящиеся процессы переработки исходных данных, Клини ввёл понятие частично рекурсивной функции и высказал гипотезу, что все частичные (т. е. не обязательно определённые для всех значений аргументов) функции, вычислимые посредством алгоритмов, являются частично рекурсивными. Более общая гипотеза Клини также недоказуема, как и гипотеза Чёрча. В дальнейшем под гипотезой Чёрча будет пониматься расширенная Клини формулировка.
Тезис Чёрча оказался достаточным, чтобы придать необходимую точность формулировкам алгоритмических проблем и в ряде случаев сделать возможным доказательство их неразрешимости. Отметим, что понятие рекурсивной функции строгое. Поэтому обычная математическая техника позволяет иногда непосредственно доказать, что решающая задачу функция не может быть рекурсивной. Именно этим путём Чёрчу удалось первому доказать неразрешимость основной алгоритмической проблемы логики предикатов - проблемы тождественной истинности формул исчисления высказываний.
Точное описание класса частичных рекурсивных функций вместе с тезисом Чёрча даёт одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Спрашивается, нельзя ли уточнить непосредственно само понятие алгоритма и уже затем при его помощи определить точно и класс вычислимых функций? Это было сделано Постом и Тьюрингом независимо друг от друга и почти одновременно с упомянутыми выше работами Чёрча и Клини.
|
|
|
Основная мысль Поста и Тьюринга заключалась в том, что алгорит-мические процессы - это процессы, которые может осуществлять подхо-дяще устроенная “машина”. В соответствии с этой мыслью ими были описаны в точных математических терминах довольно узкие классы машин, но на этих машинах оказалось возможным осуществлять или имитировать все алгоритмические процессы, которые фактически когда-либо описывались математически. Алгоритмы, осуществимые на данных машинах, было предложено рассматривать в качестве математических “представителей” вообще всех алгоритмов.
Несложные выкладки показали, что класс функций, вычислимых на этих машинах, в точности совпадает с классом всех частично рекурсивных функций. Тем самым было получено ещё одно фундаментальное подтверждение тезиса Чёрча. Машины Поста и Тьюринга отличались несущественно и в дальнейшем стали называться машинами Тьюринга.
Интуитивное определение как численных, так и логических алгоритмов похоже: в обоих случаях алгоритм определяется как система правил для решения определённого класса задач, которая обладает свойствами детерминированности, массовости и результативности.
Для уточнения понятия алгоритма в рассмотрение введен нормальный алгоритм Маркова; эта форма алгоритма удобна для специалиста по логике. Для тех же специалистов, которые имеют дело с численными алгоритмами, удобней иметь стандартный аппарат, более близкий к их естественной форме. Таким аппаратом является машина Тьюринга.
В процессе построения теории численных алгоритмов было выяснено, что любой логический алгоритм можно простыми методами свести к численному алгоритму. По мере усовершенствования этих методов стало ясно, что вообще любой алгоритм может быть всегда сведен к численному алгоритму.
Таким образом, теория численных алгоритмов (это понятие тождественно понятию “теория вычислимых функций”) стала универсальным аппаратом для исследования всех алгоритмических проблем.
Поскольку понятия “алгоритм” и “вычисление значений арифметической функции” тождественны, то в соответствии с тезисом Чёрча задача оказывается алгоритмически разрешимой лишь тогда, когда арифметическая функция, к вычислению которой сводится задача, оказывается общерекурсивной. Иначе: алгоритм существует лишь тогда, когда может быть построена общерекурсивная функция (просто рекурсивная функция).
Наоборот, в силу тезиса Чёрча алгоритмическая неразрешимость проблемы означает, что арифметическая функция, к вычислению которой сводится задача, не является рекурсивной.
Вопрос. Машина Тьюринга.
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
- Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
- Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
- Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
- Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Передвигаться на одну ячейку влево или вправо.
- Менять свое внутреннее состояние.
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Дата добавления: 2019-02-22; просмотров: 377; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!