системы счисления. 1 Лабораторные работы по дисциплине Теоретические основы информатики Оглавление
 Скачать 2 Mb.
|
|
эквиваленцией или двойной импликацией и обозначается знакомили. Высказывание А↔В истинно тогда и только тогда, когда значения Аи В совпадают. Пример. Высказывание Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» - ложно. 32 ЛИБО … ЛИБО Операция, выражаемая связками Либо … либо, называется исключающее ИЛИ или сложением по модулю 2 и обозначается XOR или Высказывание А В истинно тогда и только тогда, когда значения Аи Вне совпадают. Пример. Высказывание Число 6 либо нечетно либо делится без остатка на 2» является истинным, а высказывание Либо число 6 четно либо число 6 делится на – ложно, так как истинны оба высказывания входящие в него. Замечание Импликацию можно выразить через дизъюнкцию и отрицание B ¬A = B A Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию Вывод Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания. Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания (не, затем конъюнкция (и, после конъюнкции – дизъюнкция (или) и исключающего или ив последнюю очередь – импликация и эквиваленция. С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой логическим выражением. Логическая формула - это символическая запись высказывания, состоящая из логических величин (констант или переменных, объединенных логическими операциями (связками. Логическая функция - это функция логических переменных, которая может принимать только два значения 0 или 1. В свою очередь, сама логическая переменная аргумент логической функции) тоже может принимать только два значения 0 или 1. Пример. A = ) F( B & A B A, – логическая функция двух переменных A и B. Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности. Приведем таблицу истинности основных логических операций (табл. 2) Таблица 2. A B ¬A B & A B A B A B A ↔ B A XOR 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 Опираясь на данные таблицы истинности основных логических операций можно составлять таблицы истинности для более сложных формул. Алгоритм построения таблиц истинности для сложных выражений 1. Определить количество строк – количество строк = 2 n + строка для заголовка, – n - количество простых высказываний. 2. Определить количество столбцов количество столбцов = количество переменных + количество логических операций определить количество переменных (простых выражений 33 – определить количество логических операций и последовательность их выполнения. 3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций. Пример Составить таблицу истинности для формулы И–НЕ, которую можно записать так ) ¬( B & A 1. Определить количество строк На входе два простых высказывания Аи В, поэтому n=2 и количество строк =2 2 +1=5. 2. Определить количество столбцов Выражение состоит из двух простых выражений (A и B) и двух логических операций (1 инверсия, 1 конъюнкция, те. количество столбцов таблицы истинности = 4. 3. Заполнить столбцы с учетом таблиц истинности логических операций табл. 3). Таблица 3. Таблица истинности для логической операции ) ¬( B & A A B B & A ) ¬( B & A 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 Подобным образом можно составить таблицу истинности для формулы ИЛИ–НЕ, которую можно записать так Таблица 4. Таблица истинности для логической операции B) ¬(A A B B A B) ¬(A 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 Примечание И–НЕ называют также штрих Шеффера» (обозначают | ) или «антиконъюнкция»; ИЛИ–НЕ называют также стрелка Пирса (обозначают ↓) или «антидизъюнкция». Пример Составить таблицу истинности логического выражения Решение 1. Определить количество строк На входе два простых высказывания Аи В, поэтому n=2 и количество строк 2 +1= 5. 2. Определить количество столбцов Выражение состоит из двух простых выражений (A и B) и пяти логических операций (2 инверсии, 2 конъюнкции, 1 дизъюнкция, те. количество столбцов таблицы истинности = 7. Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции. 3. Заполнить столбцы с учетом таблиц истинности логических операций табл. 5). Таблица 5. Таблица истинности для логической операции ¬B ¬ = C & A B & A A B ¬A ¬B B & A ¬ ¬B & A C 34 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 Логические формулы можно также представлять с помощью языка логических схем. Существует три базовых логических элемента, которые реализуют три основные логические операции логический элемент И – логическое умножение – конъюнктор; логический элемент ИЛИ – логическое сложение – дизъюнктор; логический элемент НЕ – инверсию – инвертор. конъюнктор дизъюнктор инвертор Поскольку любая логическая операция может быть представлена в виде комбинации трех основных, любые устройства компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов, как из кирпичиков. Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают сигналы-значения аргументов, на выходе появляется сигнал-значение функции. Преобразование сигнала логическим элементом задается таблицей состояний, которая фактически является таблицей истинности, соответствующей логической функции, только представлена в форме логических схем. В такой форме удобно изображать цепочки логических операций и производить их вычисления. Алгоритм построения логических схем. 1. Определить число логических переменных. 2. Определить количество логических операций и их порядок. 3. Изобразить для каждой логической операции соответствующий ей логический элемент. 4. Соединить логические элементы в порядке выполнения логических операций. Пример. По заданной логической функции ¬B ¬ = ) F( & A B & A B A, построить логическую схему. Решение. 1. Число логических переменных = 2 (A и B). 2. Количество операций = 5 (2 инверсии, 2 конъюнкции, 1 дизъюнкция. Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции. 3. Схема будет содержать 2 инвертора, 2 конъюнктора и 1 дизъюнктор. 4. Построение надо начинать с логической операции, которая должна выполняться последней. В данном случае такой операцией является логическое сложение, следовательно, на выходе должен быть дизъюнктор. На него сигналы подаются с двух конъюнкторов, на которые, в свою очередь, подаются один входной сигнал нормальный и один инвертированный (с инверторов. B & A A & B B A A 1 B A A 35 Задания для самостоятельной работы 1. Составить таблицу истинности логического выражения C. Варианты задания № варианта C 1 A ¬B) (A )) (¬( XOR ↔ B & A 2 B ) (¬ ) ( XOR B & A ↔ B & A 3 A ¬A) (¬B ) ( XOR ↔ B & A 4 B ¬B) (¬ B) ¬(A XOR & A ↔ 5 B XOR & A ↔ ¬B) ¬( B) (A 6 A XOR ↔ B & A B) (¬A ) ¬( 7 A B) (¬A B) ¬(A XOR ↔ 8 B A) (¬B ) (¬ XOR ↔ B & A 9 A ) ¬( ¬B) (A XOR A & B ↔ 10 B XOR ↔ A & B ¬B) (A ) (¬ 11 A ) (¬ ¬B) (¬A XOR A & B ↔ 12 B XOR ↔ B) (A ¬A) (¬B 13 A B) (¬A A) ¬(B XOR ↔ 14 B B) (¬A )) (¬( XOR ↔ B & A 15 B ) ( ¬B) (¬A XOR A & B ↔ 16 A ¬A) (B ¬B) (¬A XOR ↔ 2. Построить логическую схему функции F(A,B). Варианты задания № варианта F(A,B) 1 2 3 4 5 6 A)) (¬(B ) ¬( B & A ¬B) ( B) ¬(A & A ¬B) (A B) ¬(A A)) (¬B B) ¬((¬A ¬A) (¬B B) (¬A ¬B) ¬(A B) (¬A 36 7 8 9 10 11 12 13 14 15 16 Содержание отчета 1. Текст задания (сданными своего варианта. 2. Представление по каждому пункту задания подробного решения. 5. Алгоритм. Способы записи, основные типы алгоритмов. Краткие теоретические сведения Алгоритмом называется точное предписание, определяющее последовательность действий исполнителя, направленных на решение поставленной задачи. В роли исполнителей алгоритмов могут выступать люди, роботы, компьютеры. Понятие алгоритма в программировании является фундаментальным. Для алгоритма важен не только набор определенных действий, но и то, как они организованы, те. в каком порядке они выполняются. Свойства алгоритма: понятность – все действия должны входить в систему команд исполнителя, те. быть понятны ему; дискретность - алгоритм делится на отдельные элементарные шаги определенность - каждая команда однозначно определяет действие исполнителя конечность(результативность) - алгоритм должен завершаться за конечное число шагов. массовость – алгоритм позволяет решать целый класс похожих задач. Способы записи алгоритма 1. Словесно-формульный Пример. Алгоритм деления обыкновенных дробей 1. Числитель первой дроби умножить на знаменатель второй 2. Знаменатель второй дроби умножить на числитель второй 3. Записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель - результат выполнения пункта 2. 2. Графический способ (в виде блок-схемы Блок схема – это графическое представление алгоритма при помощи стандартных обозначений. Блок схемы составляются в соответствии с ГОСТами. ГОСТы алгоритмов ГОСТ 19.002-80, ГОСТ 19.003-80. На схемах алгоритмов выполняемые действия изображаются в виде отдельных блоков, которые соединяются между собой линиями связи в порядке выполнения действий. На линиях связи могут ставиться стрелки, причем, если направление связи слева направо или сверху вниз, то стрелки не ставятся. Блоки нумеруются. Внутри блока дается информация о выполняемых действиях. Таблица 1 – Основные блоки, используемые при составлении алгоритмов Название Обозначение Назначение Пуск, Останов Начало-конец алгоритма Процесс Любое вычислительное действие Решение Проверка условия Модификатор Цикл Ввод-вывод Ввод-вывод данных Документ Вывод на печатающее устройство Соединитель Используется на линиях разрыва Комментарий Комментарий 3. Запись алгоритма в виде последовательности команд для ЭВМ Алгоритм, записанный на одном из языков программирования называется программой. Типы вычислительных процессов Вычислительные процессы могут быть линейные, разветвляющиеся и циклические. Линейные алгоритмы Линейный алгоритм – алгоритм, в котором все команды выполняются последовательно друг за другом. 38 Пример 1: составить алгоритм обмена значений переменных a и b. Пример 2: Составить алгоритм обмена значений переменных a и b без использования дополнительной переменной. Команды a b c a=5, b=12 5 12 - c=a 5 12 5 a=b 12 12 5 b=c 12 5 5 Команды a b a=3, b=7 3 7 a=a+b 10 7 b=a-b 10 3 a=a-b 7 3 5 12 5 a b c 1) c=a 2) a=b 3) b=c 39 Пример 2: составить алгоритм вычисления a 8 , используя не более х действий умножения (возведение в степень не использовать Пример 3: Составить алгоритм вычисления a 6 , используя не более трех команд умножения. Алгоритмы с ветвлением Часто при выполнении алгоритма должны предлагаться различные действия в зависимости от выполнения или невыполнения некоторого условия. Такие алгоритмические структуры называют ветвлением. Команды a a=2 2 a=a*a 4 a=a*a 16 a=a*a 256 Команды a b a=2 2 - a=a*a 2 2 - b=a 2 2 2 2 a=a*a 2 4 2 2 a=b*a 2 6 2 2 40 Полное ветвление Неполное ветвление Пример 4. Вычислить выражение x y для введенного x. Исходные данные x. Результат y, или функция не определена проверяемый случай x>=0 y результат x=9 9>=0 да y= 3 9 y= 3 x=-9 -9>=0 нет - функция не определена 41 Пример 5. Вычислить выражение x y для введенного x. Пример 6. Выбрать максимальное из х чисел a и b. 1 вариант 2 вариант проверяемый случай x>=0 y результат x=9 9>=0 да y= 3 9 y= 3 x=-9 -9>=0 нет - функция не определена проверяемый случай x y результат a=9 b=15 9>15 нет 15>9 да 15 a=18 b=3 18>3 да - 18 a=7 b=7 7>7 нет 7>7 нет числа равны 42 Алгоритмы с циклами Цикл – многократное повторение одних и тех же действий. 1. Цикл с предусловием Такой цикл называют пока. Механизм его работы пока условие истинно, повторять Пример 7. Вывести все отрицательные члены арифметической прогрессии -11; - 7… Пусть a – очередной член прогрессии. a=a 1 +4 – следующий член прогрессии. Пока a<0, повторять a=a 1 +4. Цикл с предусловием может не выполниться ни разу, если условие сразу оказалось ложным. Пример 9. Найти сумму первых десяти натуральных чисел S=1+2+…+10 S – сумма а – очередное слагаемое. S:=S+a a:=a+1 Выполнять, пока a<=10 43 2. Цикл с постусловием. Механизм работы повторять, пока условие не станет истинным. Этот цикл всегда выполняется хотя бы 1 раз. Пример 9. Найти сумму положительных членов арифметической прогрессии 17; 11 … S=a+S a:=a-6 тело цикла повторять до тех пор, пока не выполнится условие a<=0 44 Пример 10. Вычислить n! F=F*k k=k+1 тело цикла повторять до тех пор, пока не выполнится условие k>N Задания для самостоятельной работы Вариант Номера заданий 1 аж, н, 2a 2 б, зоб в, и, п, в г, кр, г д, л, с, де, м, те аир, ж б, к, с, з в, л, т, б гм, н, в д, ж, о, г е, з, п, да, и, ре б, к, с, ж. Составить блок-схему алгоритма решения задачи а) По длине ребра куба найти площадь грани, площадь полной поверхности и объем куба. б) Найти площадь кольца с радиусами r1 ив) Вычислить площадь треугольника потрем сторонам(по формуле Герона). г) Вычислить площадь параллелограмма по двум сторонами углу между ними, заданному в градусах. д) Вычисление суммы цифр введенного натурального двухзначного числа. 45 е) По координатам трёх вершин некоторого треугольника найти его площадь и периметр. ж) Вводятся Хи. Если Х больше Y, то произвести их обмен. з) Из чисел A, B, C, D выбрать максимальное. и) Введено четырехзначное число. Найти количество четных цифр. К) Введено трехзначное число. Найти сумму четных цифр. Л) Введено четырехзначное число. Найти среднее арифметическое нечетных цифр. м) Определить, существует ли треугольник с заданными сторонами a, b, c. Н) Найти сумму делителей числа n. О) Найти сумму 1 + 1/3 + 1/5 +...(N слагаемых. П) Подсчитать сумму двухзначных чисел, сумма цифр которых не превышает 7. Р) Задана арифметическая прогрессия 2; 5; … . Определите наименьшее количество членов прогрессии, начиная с первого, сумма которых превышает 50. С) Вывести таблицу значений функции y= sin 2 x – cos x на интервале [- , ] с шагом /10. Т) Найти сумму S = х+2х+3х... (n слагаемых) 2. Выполнить ручную трассировку и определить результат выполнения алгоритма а) б) начало S = 0 I = 1 I<=5 S =S+I I = I+1 S кода нет начало S = 0 I = 2 I<=10 S =S+I I = I+2 S кода нет 46 ) г) Е) Для массива X = (-8, 9, 10, -2, 4, -5, 3, 2) найти значение переменной, которая является результатом работы алгоритма Ж) Для массива X = (8, 0, -10, -8, 4, -9, -3, 7) найти значение переменной, которая является результатом работы алгоритма начало S = 0 I = 1 I<7 S =S+2*I I = I+2 S конец да нет начало S = 0 I = 12 I>0 S =S+I I = I-2 S конец да нет 47 З) определить значение y при x=105, z=8 48 6. Машина Поста. Машина Тьюринга Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы. В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является лита или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста. Машина Поста состоит из бесконечной ленты, поделенной на одинаковые ячейки (секции. Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак, головки (каретки, способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку. Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис i K j, где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка. Всего для машины Поста существует шесть типов команд V j - поставить метку, перейти к й строке программы. X j - стереть метку, перейти к й строке программы. <- j - сдвинуться влево, перейти к й строке программы. -> j - сдвинуться вправо, перейти к й строке программы. ? j1; j2 - если в ячейке нет метки, то перейти к й строке программы, иначе перейти к й строке программы. ! – конец программы (стоп. У команды стоп отсылки нет. Варианты окончания выполнения программы на машине Поста Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми. Уход в бесконечность, зацикливание. Машина Постав результате работы алгоритма может вообще не остановиться (никогда не дойти до команды стоп и никогда не завершиться аварийной ситуацией. Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга. Почему достаточно лишь два различных символа (есть метка, нет метки Дело в том, что любой алфавит может быть закодирован двумя знаками в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита. 49 Пример работы машины Поста увеличить число 3 на единицу (изменить значение в памяти сна Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано стем, что одна метка обозначает ноль, а уже две – единицу, и т.д. Допустим, точно известно, что каретка стоит где-то слева отметок и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так 1 -> 2 2 ? 1;3 3 <- 4 4 V 5 5 ! Задания для самостоятельного выполнения Задача 1. Машина Поста состоит из ленты, разбитой на ячейки, и каретки, которая может считывать содержимое обозреваемой ячейки, стирать метки и ставить метки. Создайте компьютерную модель машины Поста, вычитающей два числа. Задача 2. Напишите компьютерную программу, моделирующую машину Поста, которая увеличивает целое число на 2. Задача 3. Напишите компьютерную программу, моделирующую машину Поста, которая уменьшает целое число на 2. Задача 4. Напишите компьютерную программу, моделирующую машину Поста, которая складывает два целых числа. Задача 5. Напишите компьютерную программу, моделирующую машину Поста, которая умножает целое число на 2. Задача 6. Напишите программу для МП, складывающую два целых числа, заданных набором единиц. |