Схема И: эта схема реализует конъюнкцию двух или более логических элементов.
F(x1,x2) = x1^x2
| X1 | X2 | Y |
Схема ИЛИ: реализует дизъюнкцию двух или более логических значений.
F(x1,x2) = x1Vx2
| X1 | X2 | Y |
Схема НЕ: (инвертор) реализует операцию отрицания.
| X | Y |
Схема И-НЕ: состоит из элемента И и инвертора и осуществляет отрицание результата схемы И.
| X1 | X2 | Y |
Схема ИЛИ-НЕ: состоит из элемента ИЛИ и инвертора и осуществляет отрицание схемы ИЛИ.
| X1 | X2 | Y |
Триггер (триггерная система) — класс электронных устройств, обладающих способностью длительно находиться в одном из двух устойчивых состояний и чередовать их под воздействием внешних сигналов. Каждое состояние триггера легко распознаётся по значению выходного напряжения. По характеру действия триггеры относятся к импульсным устройствам — их активные элементы (транзисторы, лампы) работают в ключевом режиме, а смена состояний длится очень короткое время.
19.Понятие алгоритма и алгоритмической системы. Свойства интуитивного понятия алгоритма. Язык алгоритма.
Алгоритм – конечная совокупность точно сформулированных правил, которые позволяют решать те или иные классы задач.
Основные свойства «интуитивного» понятия алгоритма:
- Массовость алгоритма. Подразумевается, что алгоритм позволяет решать не одну конкретную задачу, а некоторый класс задач данного типа. Обеспечивает возможность изменения исходных данных в определенных пределах.
- Детерминированность алгоритма. Процесс применения правил к исходным данным однозначно определен.
- Результативность алгоритма. На каждом шаге процесса применения правил известно, что считать результатом этого процесса, а сам процесс должен прекратиться за конечное количество шагов.
Язык – знаковая система (множество символов и правил) любой физической природы, выполняющая познавательную и коммуникативную функции в процессе человеческой деятельности.
Язык может быть естественным и искусственным:
Естественный язык – форма выражения мыслей и средство общения между людьми.
Искусственный язык – вспомогательный, созданный на базе естественного языка людьми для каких-либо частных целей.
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.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.
Графический способ
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма, или блок-схемой. В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. В таблице приведены наиболее часто употребляемые символы.
| Название | Блок-схема | Пояснение |
| Пуск-останов | | Начало, конец алгоритма, вход и выход в подпрограмму |
| Процесс | | Вычислительное действие или последовательность действий |
| Решение | | Проверка условий |
| Модификация | | Начало цикла |
| Предопределённый процесс | | Вычисления по подпрограмме |
| Ввод-вывод | | Ввод-вывод в общем виде |
Псевдокод
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам. В псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых однозначно определён.
алгназвание алгоритма (аргументы и результаты)
даноусловия применимости алгоритма
надоцель выполнения алгоритма
начописание промежуточных величин
последовательность команд (тело алгоритма)
Кон.
Часть алгоритма от слова алгдо слова начназывается заголовком, а часть, заключённая между словами начи кон— телом алгоритма.
Программный способ записи алгоритмов
Алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. В этом случае язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой.
