4. Запишите систему уравнений характеризующих автомат Мили
Автомат Мили (англ. Mealy machine) — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы.
Автомат Мили — совокупность
a(t + 1) = δ(a(t), z(t)) (переходов)
ω(t) = λ(a(t), z(t)) (выходов)
Таким образом, в автомате Мили выходной сигнал (буква выходного алфавита) и момент автоматного времени t зависит как от внутреннего состояния автомата в момент t, так и от входного сигнала (буквы входного алфавита) в момент t.
Управлять компьютером нужно по определенному алгоритму. Алгоритм — это точно определенное описание способа решения задачи в виде конечной (по времени) последовательности действий. Такое описание еще называется формальным. Для представления алгоритма в виде, понятном компьютеру, служат языки программирования. Сначала всегда разрабатывается алгоритм действий, а потом он записывается на одном из таких языков. В итоге получается текст программы — полное, законченное и детальное описание алгоритма на языке программирования. Затем этот текст программы специальными служебными приложениями, которые называются трансляторами, либо переводится в машинный код, либо исполняется.
Что такое язык программирования
Самому написать программу в машинном коде весьма сложно, причем эта сложность резко возрастает с увеличением размера программы и трудоемкости решения нужной задачи. Условно можно считать, что машинный код приемлем, если размер программы не превышает нескольких десятков байтов и нет потребности в операциях ручного ввода/вывода данных.
Поэтому сегодня практически все программы создаются с помощью языков программирования. Теоретически программу можно написать и средствами обычного человеческого (естественного) языка — это называется программированием на метаязыке (подобный подход обычно используется на этапе составления алгоритма), но автоматически перевести такую программу в машинный код пока невозможно из-за высокой неоднозначности естественного языка.
Языки программирования — искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов). Совокупность подобных требований образует синтаксис языка программирования, а смысл каждой команды и других конструкций языка — его семантику. Нарушение формы записи программы приводит к тому, что транслятор не может понять назначение оператора и выдает сообщение о синтаксической ошибке, а правильно написанное, но не отвечающее алгоритму использование команд языка приводит к семантическим ошибкам (называемые еще логическими ошибками или ошибками времени выполнения).
Процесс поиска ошибок в программе называется тестированием, процесс устранения ошибок — отладкой.
Общие сведения об алгоритмических языках и программировании. Простейшие команды языка. Интерпретатор и компилятор.
Управлять компьютером нужно по определенному алгоритму. Алгоритм — это точно определенное описание способа решения задачи в виде конечной (по времени) последовательности действий. Такое описание еще называется формальным. Для представления алгоритма в виде, понятном компьютеру, служат языки программирования сегодня практически все программы создаются с помощью языков программирования. Теоретически программу можно написать и средствами обычного человеческого (естественного) языка — это называется программированием на метаязыке (подобный подход обычно используется на этапе составления алгоритма), но автоматически перевести такую программу в машинный код пока невозможно из-за высокой неоднозначности естественного языка. Языки программирования — искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов). Совокупность подобных требований образует синтаксис языка программирования, а смысл каждой команды и других конструкций языка — его семантику. Нарушение формы записи программы приводит к тому, что транслятор не может понять назначение оператора и выдает сообщение о синтаксической ошибке, а правильно написанное, но не отвечающее алгоритму использование команд языка приводит к семантическим ошибкам (называемые еще логическими ошибками или ошибками времени выполнения). Процесс поиска ошибок в программе называется тестированием, процесс устранения ошибок — отладкой. С помощью языка программирования создается не готовая программа, а только ее текст, описывающий ранее разработанный алгоритм. Чтобы получить работающую программу, надо этот текст либо автоматически перевести в машинный код (для этого служат программы-компиляторы) и затем использовать отдельно от исходного текста, либо сразу выполнять команды языка, указанные в тексте программы (этим занимаются программы-интерпретаторы). Интерпретатор берет очередной оператор языка из текста программы, анализирует его структуру и затем сразу исполняет (обычно после анализа оператор транслируется в некоторое промежуточное представление или даже машинный код для более эффективного дальнейшего исполнения). Только после того как текущий оператор успешно выполнен, интерпретатор перейдет к следующему. При этом, если один и тот же оператор должен выполняться в программе многократно, интерпретатор всякий раз будет выполнять его так, как будто встретил впервые. Вследствие этого, программы, в которых требуется осуществить большой объем повторяющихся вычислений, могут работать медленно. Кроме того, для выполнения такой программы на другом компьютере там также должен быть установлен интерпретатор — ведь без него текст программы является просто набором символов. По-другому, можно сказать, что интерпретатор моделирует некую виртуальную вычислительную машину, для которой базовыми инструкциями служат не элементарные команды процессора, а операторы языка программирования. Компиляторы полностью обрабатывают весь текст программы (он иногда называется исходный код). Они просматривают его в поисках синтаксических ошибок (иногда несколько раз), выполняют определенный смысловой анализ и затем автоматически переводят (транслируют) на машинный язык — генерируют машинный код. Нередко при этом выполняется оптимизация с помощью набора методов, позволяющих повысить быстродействие программы (например, с помощью инструкций, ориентированных на конкретный процессор, путем исключения ненужных команд, промежуточных вычислений и т. д.). В результате законченная программа получается компактной и эффективной, работает в сотни раз быстрее программы, выполняемой с помощью интерпретатора, и может быть перенесена на другие компьютеры с процессором, поддерживающим соответствующий машинный код. Основной недостаток компиляторов — трудоемкость трансляции языков программирования, ориентированных на обработку данных сложной структуры, часто заранее неизвестной или динамически меняющейся во время работы программы. Тогда в машинный код приходится вставлять множество дополнительных проверок, анализировать наличие ресурсов операционной системы, динамически их захватывать и освобождать, формировать и обрабатывать в памяти компьютера сложные объекты, что на уровне жестко заданных машинных инструкций осуществить довольно трудно, а для ряда задач практически невозможно. С помощью интерпретатора, наоборот, допустимо в любой момент остановить работу программы, исследовать содержимое памяти, организовать диалог с пользователем, выполнить сколь угодно сложные преобразования данных и при этом постоянно контролировать состояние окружающей программно-аппаратной среды, благодаря чему достигается высокая надежность работы. Интерпретатор при выполнении каждого оператора проверяет множество характеристик операционной системы и при необходимости максимально подробно информирует разработчика о возникающих проблемах. Кроме того, интерпретатор очень удобен для использования в качестве инструмента изучения программирования, так как позволяет понять принципы работы любого отдельного оператора языка. В реальных системах программирования перемешаны технологии и компиляции, и интерпретации. В процессе отладки программа может выполняться по шагам, а результирующий код не обязательно будет машинным — он даже может быть исходным кодом, написанным на другом языке программирования (это существенно упрощает процесс трансляции, но требует компилятора для конечного языка), или промежуточным машиннонезависимым кодом абстрактного процессора, который в различных компьютерных архитектурах станет выполняться с помощью интерпретатора или компилироваться в соответствующий машинный код. Разные типы процессоров имеют разные наборы команд. Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности, то он называется языком программирования низкого уровня. В данном случае «низкий уровень» не значит «плохой». Имеется в виду, что операторы языка близки к машинному коду и ориентированы на конкретные команды процессора. Языком самого низкого уровня является язык ассемблера, который просто представляет каждую команду машинного кода, но не в виде чисел, а с помощью символьных условных обозначений, называемых мнемониками. Однозначное преобразование одной машинной инструкции в одну команду ассемблера называется транслитерацией. Так как наборы инструкций для каждого модели процессора отличаются, конкретной компьютерной архитектуре соответствует свой язык ассемблера, и написанная на нем программа может быть использована только в этой среде. С помощью языков низкого уровня создаются очень эффективные и компактные программы, так как разработчик получает доступ ко всем возможностям процессора. С другой стороны, при этом требуется очень хорошо понимать устройство компьютера, затрудняется отладка больших приложений, а результирующая программа не может быть перенесена на компьютер с другим типом процессора. Подобные языки обычно применяют для написания небольших системных приложений, драйверов устройств, модулей стыковки с нестандартным оборудованием, когда важнейшими требованиями становятся компактность, быстродействие и возможность прямого доступа к аппаратным ресурсам. В некоторых областях, например в машинной графике, на языке ассемблера пишутся библиотеки, эффективно реализующие требующие интенсивных вычислений алгоритмы обработки изображений.
Не сдавайте скачаную работу преподавателю!
С помощью нашего сервиса Вы можете собрать свою коллекцию шпаргалок по нужному предмету, и распечатать готовые ответы в удобном для вырезания виде. Для этого начните собирать ответы, добавляя в «Мои шпаргалки».
последовательность преобразований над данными заданного типа, приводящая к изменению их типа
●формально описанная процедура преобразования входных данных в выходные данные, представляющие собой искомый результат
последовательность итерационных шагов, приводящих к получению результата
описанный перечень предписаний по увеличению значения результата вычислений
(1)Алгоритмы решения задач относятся к моделям.
(1)Наиболее наглядным способом записи алгоритма является
описание действий с помощью условных обозначений
●изображение в виде последовательно блоков, каждый из которых предписывает выполнение определенных действий
описание функциональных зависимостей между данными, предписывающих выполнение определенных действий
описание последовательности шагов
(1)Решение задачи нахождения пути в лабиринте, это —
●перебор возможных решений с возвратом
минимальный поиск с отсечением
применение эвристического алгоритма
●алгоритмы, использующие опыт экспертов
реализующие методы статистической обработки
алгоритмы «разделяй и властвуй»
(1)Оптимизация посредством применения «жадных» алгоритмов основана на том. что
процесс принятия решения можно разбить на элементарные шаги, на каждом ил которых принимается отдельное решение
процесс решения осуществляется перебором
процесс решения производится в разделенных пространствах поиска
процесс решения может осуществляться параллельно
законченное минимальное смысловое выражение на языке программирования
протокол взаимодействия компонентов компьютерной сети
●алгоритм, записанный на языке программирования
набор команд операционной системы компьютера
(1)Процесс написания программы никогда НЕ ВКЛЮЧАЕТ
редактирование текста программы
запись операторов в соответствующей языку программирования форме
●изменение физических параметров компьютера
(1)Система программирования предоставляет программисту возможность
●автоматической сборки разработанных модулей в единый проект;
планирования рабочего дня;
анализа существующих программных продуктов по соответствующей тематике;
автоматического построения математической модели, исходя из постановки задачи;
выбора языка программирования
(1)Способ записи программ, допускающий их непосредственное выполнение на ЭВМ. называется
функциональным языком программирования
логическим языком программирования
●машинным языком программирования
процедурным языком программирования
(1)На этапе отладки программы
строится математическая модель решаемой задачи
определяется состав входных данных
выполняется анализ физических характеристик
●проверяется корректность работы программы
тестирования и отладки
(1)Если задан тип данных, то известной является информация о
●диапазоне возможных значений
количестве обращений к данным
(1)Какая информация известна, если задан тип данных?
●диапазон возможных значений
количество обращений к данным
количество записей данных
связи между данными
вложенность структур данных
●тип соответствующего поля данных
устойчивость структур данных
(1)Целочисленный тип является типом данных
(1)Обнаруженное при тестировании нарушение формы записи программы приводит к сообщению об ошибке
тестированием «черного ящика»
определением белого шума
тестированием «белого ящика»
●организация программного обеспечения с минимальными взаимосвязями между его модулями
организация программного обеспечения с максимальными взаимосвязями между его модулями
решение задач, для которых нет явного алгоритма решения
исключение использования подпрограмм
а) использование композиции двух базовых элементов — ветвления и циклической структур
б) использование большого количества подпрограмм
в) принцип модульности разработки сложных программ
д) использование композиции трех базовых элементов — линейной, ветвления и циклической структур
(1)Укажите структуры, которые не допускается использовать в программе при структурном программировании
Последовательное выполнение двух и более операций
(1)Стиль, вычисление в котором представляет собой вывод некоторого целевого утверждения называется программированием
Объектно — ориентированным
(1)Уменьшение объема кода программ связано с использованием программирования.
●объектно — ориентированного
(1)Методика анализа, проектирования и написания приложений с помощью структуры классов, каждый из которых является целостным фрагментом кода и обладает свойствами и методами, называется программированием.
(1)К концепции объектно-ориентированного программирования НЕ относится
е) метод обработки
з) класс объектов
а, д, з
д. е. ж,
●з г. е
ж, з. д
(1)Объект связан с классом в терминах ОБЪЕКТНО-ориентированного программирования в следующей нотации
объект не является наследником класса
объект и класс связаны через общие функции
совокупность классов образует объект
●класс является описанием объекта
●С и C++
удаление подпрограммой самой себя
заражение подпрограммой самой себя
●обращение подпрограммы к самой себе
размножение подпрограммой самой себя
(1)Какая структура данных больше подходит для реализации рекурсии
(1)Какой алгоритм сортировки массива относится к рекурсивным:
сортировка методом пузырька
сортировка простыми вставками
На рис. в виде дерева рекурсии представлен фрагмент алгоритма F(5)
F(1) F(D) 1
поиска простых чисел
●вычисления чисел Фибоначчи
задачи о ближайших точках
f(xl xn.0) = a(xl xn). f(xl xn.y+1) = h(xl xn,y, f(xl xn0)) определяет
набор переменных, начинающихся с одной буквы
ограниченная апострофами последовательность любых символов
●последовательность фиксированного числа однотипных переменных, имеющих общее имя
самый простой оператор языка программирования
(1)Массив относится к типам данных
●составным (конструируемым) типам
по возрастанию значений элементов
по частотным характеристикам
●по возрастанию индексов элементов
(1)Задан одномерный массив X1. Х2 XN. Фрагмент алгоритма
количество нулевых элементов
количество положительных элементов
номер последнего нулевого элемента
номер первого нулевого элемента
оператор, выполняемый в случае истинности условия и оператор, выполняемый в случае ложности условия
●условие и оператор, выполняемый в случае истинности условия
б) переход по условию
(1)Оператор ветвления на блок схеме отображается в виде
(1)В блок схеме, внутри данного символа можно написать:
обращением к подпрограмме
(1)На рисунке представлен фрагмент алгоритма, имеющий структуру.
циклическую с постусловием
циклическую с предусловием
(1)При выполнении подпрограммы
Aлг пpl (арг цел X. рез цел F) Нач
to F:= 2 иначе F:= F (X — 2) + 3 все кон
с параметрами (2. А) значение переменной А будет равно
Air пpl (арг цел X. рез цел F) Нач
toF:= 2 иначе F:= F (X — 1) + 3 все кон
(1)В результате работы алгоритма
:= X + 5 Х:= Y
:= X + Y вывод Y
переменная Y приняла значение 14. Укажите число, которое являлось значением переменной X до начала работы алгоритма.
:= X -1 X:= Y +2
переменная Y приняла значение 10. Укажите число, которое являлось значением переменной X до начала работы алгоритма.
(1)В результате работы фрагмента блок-схемы алгоритма
(1)При каких начальных значениях а и b алгоритм на блок-схеме закончит работу (a mod 2 — операция взятия числа а по модулю 2).
(1)При каких начальных значениях переменных алгоритм на блок-схеме закончит работу (a mod 2 = остаток от деления а на 2).
(1)В результате работы фрагмента алгоритма
2. 8.16. 32
2. 4. 8, 12
●4. 6. 8. 10
(1)Блок-схема на рисунке соответствует алгоритму
где кв — конец ветвления кц — конец цикла нц — начало цикла
●Ol; Если I1 то 02; кв; ОЗ; Пока не I2 выполнять нц ОЗ; кц;
Ol; Если I1 то 02; кв; ОЗ; Пока I2 выполнять нц ОЗ; кц;
Ol; Если I1 то 02; иначе ОЗ; кв; Пока не I2 выполнять нц ОЗ; кц;
Ol; Если I1 то 02; кв; Пока не I2 выполнять нц ОЗ; кц;
ПРОЦЕДУРА KLMN; НАЧАТЬ ПРОЦЕДУРУ
(1)Укажите сколько раз выполнится цикл в программе
wliile (а / 2) < (b / 3)
●бесконечное число раз
(1)Задан фрагмент алгоритма:
1. если а<b, то с=b-а, иначе с=2*(а-b)
В результате выполнения данного алгоритма с начальными значениями
а=8, b=3, переменные c u d примут значения
(1)Тектстуры являются объектами.