1; циклический Линейный алгоритм ~ все операции выполняются последовательно
Работа добавлена на сайт samzan.net:
Типы алгоритмов
- линейный
- разветвляющийся
а) полная форма (если условие, то серия действий 1, иначе серия действий 2);
б) сокращённая (если условие, то серия действий 1);
- циклический
Линейный алгоритм – все операции выполняются последовательно. Большинство алгоритмов не сводится к последовательному выполнению команд. В них присутствует разветвление.
Форма организации действий, при которой в зависимости от некоторого условия совершается одна или другая последовательность действий называется ветвлением.
Разветвляющийся – это такой алгоритм, который содержит команду ветвления.
Команда ветвления – это составная команда, которой та или иная серия команд выполняется после проверки условия.
Линейный Разветвляющийся
Сокращённый
Если условие ложно, исполнитель ничего
не делает
Циклические алгоритмы применяются в тех случаях, когда требуется реализовать многократно повторяющиеся однотипные действия. Циклы могут иметь фиксированное или неопределённое число повторений. Могут включать несколько других вложенных циклов. Охватывающие циклы называются внешними, вложенные – внутренними. Циклический – алгоритм, который содержит команду повторения. Команда повторения – это составная команда, в котором тело цикла повторяется несколько раз.
Циклический (для) Циклический(пока) Циклический(до)
нет
Начало
Тело цикла
Конец
нет
да
да
Друг от друга отличаются способом проверки окончания цикла. Цикл «пока» выполняется, пока условие истинно. Цикл «до» выполняется до тех пор, пока условие не станет истинным. Для этих циклов обязательные блоки – это установка начального значения параметров, проверка условия достижения конечного значения параметра, изменение параметра. Цикл «для» (цикл с параметром) – все три необходимых блока собираются в один, в котором указывается начальное и конечно значения и шаг.
While
Int mt, n, p;
do {
x*=2
}while (x<n);
_____________
Double
Int n,p;
….
p=1;
while(2<=p<=h|{
p*=2;}
Машина Тьюринга
Это абстрактный исполнитель. Была предложена Тьюрингом для формализации понятия алгоритма. Машина Тьюринга – строгое математическое построение, или математический аппарат. Создана для решения определённых задач. Все вычисления сведены к небольшому набору простых однообразных операций. Принципиальное отличие МТ от вычислительных машин в том, что запоминающее устройство представляет собой бесконечную ленту. У реально вычислительных машин ЗУ может быть больших размеров, но всегда конечно. Когда МТ изготавливают, то её обычно рисуют или распечатывают на бумаге. Иногда программируют на компьютере (аккумуляция МТ). В каждой МТ есть две части:
- Неограниченная в обе стороны лента, разделённая на ячейки;
- Автомат (головка для считывания записи, управляемая программой).
С каждой МТ связано два конечных алфавита. Первый алфавит – алфавит входных символов (А = {a1,a2,an}), алфавит состояния (Q = {p1,pn}). Состояние Q0 называется пассивным. Если машина попала в это состояние, то она закончила свою работу. Q1 называется начальным. Находясь в этом состоянии, машина начинает эту работу. Входное слово размещается на ленте по одной букве, расположенных подряд в ячейке. Слева и справа от слова находятся входные ячейки (А0 – признак того, что ячейка пуста). Автомат может двигаться вдоль ленты влево или вправо, читать содержимое ячеек и записывать в ячейки буквы. Автомат каждый раз видит только одну ячейку. В зависимости от буквы А и P и в зависимости от своего состояния Qj автомат может выполнять следующие действия:
1) Поставить новую букву в определённую ячейку
2) Выполнить сдвиг на одну ячейку по ленте вправо или влево или остаться неподвижным.
3) Перейти в новое состояние.
Т.е. у МТ есть три вида операций, каждый раз для очередной пары (Qg, Ai) МТ выполняет команду, состоящую из 3 операций с определёнными параметрами.
С л о ж и т ь: 5+ 3 =?
Q1
Входное слово на ленте для сложения чисел 5 и 3
Последовательность символом будем называть словом, под лентой размещаем автомат. Автомат способен считать определённые символы в ячейке, или записать новый. Также может переместиться влево или вправо на одну позицию. Кроме того, МТ должна иметь ещё одно принципиально важное устройство – устройство управления. Задать машине правило записи, правило стирания символов на месте, правило движения автомата, правило изменения состояния машины. Создать или запрограммировать фактически означает создать её устройство управления.
|
a0 |
a1 |
anj |
… |
an |
||
|
q1 |
||||||
|
q2 |
||||||
|
… |
||||||
|
qp |
aj{ Л P Н]am |
|||||
Ветка определяется символом алфавита и состоянием машины. Команда представляет собой указание куда передвинуть головку записи, какой символ записать в текущую ячейку, в какое состояние привести машину. Для передвижения Л - влево, Р – вправо, Н – неподвижен. После выполнения автомат переходит в состояние qn, следующую команду надо искать в m-строке в таблице на пересечении со столбцом aL. Букву aL автомат видит после сдвига.
|
с |
л |
о |
ж |
и |
т |
ь |
: |
5 |
+ |
3 |
= |
? |
? |
8 |
|
|
q1 |
qRq1 |
уРq1 |
MRq1 |
mRq1 |
m |
m |
|||||||||
|
q2 |
Автомат стоит под буквой S. Машина в начальном состоянии q1
Автомат ничего не изменяя на ленте будет двигаться влево. До тех пор пока не окажется под ячейкой в двоеточием, сама перейдет в состояние q3, не изменяя дойдет до слова с символом “С”. Остановится и машина перейдет в конечное состояние q0. Зачем нужно было после получения ответа, двигать аппарат влево. Можно было бы без этого обойтись, но для более строгой в мат. Смысле трактовки работы машины Тьюринга, автомат в конце помещать относительно ленты там где он был в начале. Слово на ленте после окончания вычислений.
Задача: усовершенствовать машину так, чтобы в середине строки не было пустых ячеек. Машина записала заранее известный результат, она его не вычислила, он был записан человеком. В машине Тьюринга все задачи оказались сведенными в сколько угодно длинной череде одних и тех же простых операций. А именно: считать/записать символ, записать автомат, перевести машину из одного состояния в другое, это есть общее единой для любых самых разных вычислений. Таким образом задача вычислима(существует алгоритм решения задачи, если существует машина Тьюринга, решающая эту задачу.) Тьюринг нашел единый способ определения вычислимости. Если в начале работы считывающая записывающая головка занимает определенное положение, если в процессе работы машина прочитала входное слово полностью(обошла все символы входного слова), если останов машины произошел в исходном положении головки, то говорят – задача решена. Существует алгоритм ее решения и проблема вычислима. Если вышеуказанные требования не могут быть выполнены(головка например никогда не останавливается, уходит за левую/правую границу ленты). Несмотря на свое условие, машина Тьюринга может выполнять все возможные преобразования слов, реализуя тем самым все возможные алгоритмы. Свойства машины Тьюринга как алгоритм. Дискретность, может перейти к1, который может быть перейти в +1 шагу только после выполнения К шага.
На каждом шаге пишется символ из алфавита, автомат делает одно движение, машина Тьюринга переход в … состояние.
Детерменированость : в каждой клетке машины таблицы Тьюринга записан лишь один вариант действий. На каждом шаге результат определен однозначно.
Результативность : правильно написанное машиной Тьюринга за конечное число шагов перейдет в состояние q1.
Массовость : каждая машина Тьюринга определена над всеми словами из алфавита.
Реализация машины Тьюринга на языке высокого уровня
Т-а: для любой машины Тьюринга существует эквивалентная ей машина Тьюринга, работающая на бесконечно работающей линии. В этом случае полубесконечную ленту моделирует одномерный массив и любую программу машины Тьюринга можно реализовать с помощью следующих конструкций:
1)Последовательность операторов
2)if then else в условии
3)while
4)go to
Необходимые операторы языка:
1)Чтение очередного символа из обозреваемой ячейки ленты. На языка высокого уровня массива – это чтение ….
2)Запись символа в обозреваемую ячейку на языке высокого уровня – это присваивание значения текущему элементу массива.
3)Имитация сдвига автомата. Изменение символа читаемого индекса.
Вывод: любую машину Тьюринга и след. Любой алгоритм можно организовать на языке высокого уровня с использование только трех управляющих конструкций.
Типы данных. Структуры данных. Абстрактные типы данных(АТД). Механизмы агрегирования ячеек памяти в ЯВУ(язык высокого уровня)
Хотя термины темы звучат похоже, но они имеют различный смысл. В языках программирования тип данных переменной обозначает множество значений, которые может принимать эта переменная. Переменная булевого типа может принимать только два значения True и False. Набор базового типа данных отличается в различных языках. Правила конструирования составных типов данных на основе базовых типов тоже различаются в разных языках. АТД – это математическая модель и различные операторы определенные в рамках этой модели. Алгоритм может разрабатываться в терминах АТД, но для реализации алгоритма в конкретном языке программирования, необходимо найти способ представления АТД в терминах типов данных и операторов, поддерживаемых данным языком программирования. Для представления АТД используются структуры данных, которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Базовым строителем блоком структуры данных является ячейка, которая предназначена для хранения значения определенного базового или составного типа данных. Структуры данных создаются путем задания имен совокупностям(агрегата ячеек) ячеек. В качестве простейшего механизма агрегирования ячеек в большинстве языков программирования можно применять одномерный массив. Массив так же можно рассматривать как отображения множества индексов во множества ячеек. Ссылка на ячейку обычно состоит из имени массива и значения из множества индекса данного массива. Значения всех ячеек массива должны иметь одинаковый тип данных. Общий механизм агрегирования ячеек является структура. Структуру можно рассматривать как ячейку, состоящую из нескольких других ячеек(называемых полями), значения в которых могут быть разных типов. Структуры часто группируются в массивы. Задает имя reclist, список записи 4-х элементного массива, значениями которого являются записи с двумя полями data и next.
Файл как и одномерный массив является последовательностью значений опреленного типа. Однако файл не имеет индеса
2. Кич
3. Девочка моя Сейчас ночь
4. Облік грошових коштів
5. вариантам 25 ~ 28 Были ли у человеческого искусства два пути с самого начала или оно раздвоилось гораздо позж
6. Зависимость жизнедеятельности живых существ от их биоритмов
7. Сокеты, используемые для установки процессоров Intel
8. НА ТЕМУ- ldquo;Атомна Енергетика Україниrdquo; Виконав учень 10Б класу
9. Организационные аспекты деятельности судов
10. Оствальд Фридрих Вильгельм
11. Реферат- Договор на оказание услуг по рекламе
12. Реферат на тему- Теорія ldquo;інфляційного Всесвітуrdquo; У принципі мабуть можна побудувати ск
13. Попурри 2003. 336 с.html
14. реферат дисертації на здобуття наукового ступеня доктора економічних наук Харків
15. тема общеобязательных юридических норм установленных и охраняемых государством а понятие субъективное п
16. Получение спирта сырца
17. .Предмет функции и задачи дидактики как науки
18. методические рекомендации по производственной практике составлены на основании методических рекомендаций
19. Объекты гражданских прав
20. Введение Антропогенное воздействие на среду обитания и здоровье человека И стала мачехой Земля Сам