Основные логические элементы современных вычислительных устройств: назначение, описание, условные обозначения. Триггеры.

Схема И: эта схема реализует конъюнкцию двух или более логических элементов.

F(x₁,x₂) = x₁^x₂

Схема ИЛИ: реализует дизъюнкцию двух или более логических значений.

F(x₁,x₂) = x₁Vx₂

Схема НЕ: (инвертор) реализует операцию отрицания.

Схема И-НЕ: состоит из элемента И и инвертора и осуществляет отрицание результата схемы И.

Схема ИЛИ-НЕ: состоит из элемента ИЛИ и инвертора и осуществляет отрицание схемы ИЛИ.

Триггер (триггерная система) — класс электронных устройств, обладающих способностью длительно находиться в одном из двух устойчивых состояний и чередовать их под воздействием внешних сигналов. Каждое состояние триггера легко распознаётся по значению выходного напряжения. По характеру действия триггеры относятся к импульсным устройствам — их активные элементы (транзисторы, лампы) работают в ключевом режиме, а смена состояний длится очень короткое время.

19.Понятие алгоритма и алгоритмической системы. Свойства "интуитивного" понятия алгоритма. Язык алгоритма.

Алгоритм – конечная совокупность точно сформулированных правил, которые позволяют решать те или иные классы задач.

Основные свойства «интуитивного» понятия алгоритма:

1. Массовость алгоритма. Подразумевается, что алгоритм позволяет решать не одну конкретную задачу, а некоторый класс задач данного типа. Обеспечивает возможность изменения исходных данных в определенных пределах.
2. Детерминированность алгоритма. Процесс применения правил к исходным данным однозначно определен.
3. Результативность алгоритма. На каждом шаге процесса применения правил известно, что считать результатом этого процесса, а сам процесс должен прекратиться за конечное количество шагов.

Язык – знаковая система (множество символов и правил) любой физической природы, выполняющая познавательную и коммуникативную функции в процессе человеческой деятельности.

Язык может быть естественным и искусственным:

Естественный язык – форма выражения мыслей и средство общения между людьми.

Искусственный язык – вспомогательный, созданный на базе естественного языка людьми для каких-либо частных целей.

20. МАТЕМАТИЧЕСКОЕ ОПРЕДЕЛЕНИЕ АЛГОРИТМА ЧЕРЕЗ ПОНЯТИЕ "АЛФАВИТНЫЙ ОПЕРАТОР". ВЗАИМОСВЯЗЬ И СВОЙСТВА АЛФАВИТНЫХ ОПЕРАТОРОВ И АЛГОРИТМОВ.

Алфавитным оператором или алфавитным отображением называется всякое соответствие между словами некоторого алфавита и словами в том же самом или в каком-либо другом фиксированном алфавите. Первый называется входным, а второй – выходным алфавитом данного оператора. В случае совпадения входного и выходного алфавитов говорят, что алфавитный оператор задан в соответствующем алфавите.

Абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или символами данного алфавита. Иными словами алфавит - это конечное множество различимых символов (слово "абстрактный" для краткости здесь и далее опускается). Алфавит, как и любое другое множество, может быть задан перечислением его элементов. Например, алфавит A есть A={ a, b, c }, алфавит B есть B={ x, y }.

Под словом или строкой в алфавите понимают любую конечную последовательность символов. В последовательности (цепочке) между символами стоит операция сцепки или конкатенации, т.е. менять местами символы в последовательности нельзя. Например, в алфавите А словами являются любые последовательности: a, ac, cb, acb, bb, а в алфавите B: x, y, yx, xx и т. п.

Число символов в слове называется длиной этого слова. Так слова в алфавите А, приведенные в примере, имеют длину соответственно 1, 2, 2, 3, 2. Различают также пустые слова, не содержащие ни одного символа. Слово р называется подсловом слова q, если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое. Очевидно, что такое понятие слова будет отличаться от аналогичного в разговорных языках. Здесь под словом можно понимать любую последовательность символов, даже бессмысленную.

При расширении алфавита понятие слова может существенно меняться. Так, например, в алфавите A={0,1,2,3,4,5,6,7,8,9} цепочка символов 69+73 представляет собой два слова, соединенные знаком суммы, а в алфавите В={+,0,1,2,3,4,5,6,7,8,9} это будет одно слово.

21.ОБЩИЕ (УНИВЕРСАЛЬНЫЕ) СПОСОБЫЗАДАНИЯ АЛГОРИТМОВ. "АЛГЕБРАИЧЕСКИЕ" СРЕДСТВА ЗАДАНИЯ АЛГОРИТМОВ: МАШИНА ТЬЮРИНГА.

22. ОБЩИЕ (УНИВЕРСАЛЬНЫЕ) СПОСОБЫЗАДАНИЯ АЛГОРИТМОВ. "ГЕОМЕТРИЧЕСКИЕ" СРЕДСТВА ЗАДАНИЯ АЛГОРИТМОВ: БЛОК-СХЕМНЫЙ МЕТОД АЛГОРИТМИЗАЦИИ.

На практике наиболее распространены следующие способы задания алгоритмов:

— словесная (запись на естественном языке);

— графическая (изображения из графических символов);

— псевдокоды (полуформализованные описания алгоритмов на ус­ловном алгоритмическом языке, включающие в себя как элементы язы­ка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

— программная (тексты на языках программирования). Словесный способ записи алгоритмов представляет собой описание последователь­ных этапов обработки данных.

Словесный способ

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задаётся в про­извольном изложении на естественном языке.

Пример. Записать алгоритм нахождения наибольшего общего дели­теля (НОД) двух натуральных чисел (алгоритм Евклида).

Алгоритм может быть следующим:

1) Задать два числа.

2) Если числа равны, то взять любое из них в качестве ответа и остано­виться, в противном случае продолжить выполнение алгоритма.

3) Определить большее из чисел.

4) Заменить большее из чисел разностью большего и меньшего из чисел.

5) Повторить алгоритм с шага 2.

Описанный алгоритм применим к любым натуральным числам и дол­жен приводить к решению поставленной задачи.

Графический способ

При графическом представлении алгоритм изображается в виде по­следовательности связанных между собой функциональных блоков, каж­дый из которых соответствует выполнению одного или нескольких дей­ствий. Такое графическое представление называется схемой алгоритма, или блок-схемой. В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. В таб­лице приведены наиболее часто употребляемые символы.

Название	Блок-схема	Пояснение
Пуск-останов		Начало, конец алгоритма, вход и выход в подпрограмму
Процесс		Вычислительное действие или последовательность действий
Решение		Проверка условий
Модификация		Начало цикла
Предопределён­ный процесс		Вычисления по подпрограмме
Ввод-вывод		Ввод-вывод в общем виде

Псевдокод

Псевдокод представляет собой систему обозначений и правил, пред­назначенную для единообразной записи алгоритмов.

В псевдокоде не приняты строгие синтаксические правила для запи­си команд, присущие формальным языкам, что облегчает запись алгорит­ма на стадии его проектирования. Однако в псевдокоде обычно имеют­ся некоторые конструкции, присущие формальным языкам. В псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл ко­торых однозначно определён.

Общий вид алгоритма:

алг название алгоритма (аргументы и результаты)

дано условия применимости алгоритма

надо цель выполнения алгоритма

нач описание промежуточных величин

последовательность команд (тело алгоритма)

Кон.

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключённая между словами нач и кон — телом алгоритма.

Программный способ записи алгоритмов

Алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. В этом случае язык для записи ал­горитмов должен быть формализован. Такой язык принято называть язы­ком программирования, а запись алгоритма на этом языке — програм­мой.