Курс лекций по дисциплине «Информатика»

Вид материала

Курс лекций

Содержание Дополнительный код Пример. Выполним вычитание напрямую и через сложение (через дополнительный код Конрадом Цузе Пример. Вычислить наибольшее и наименьшее 5-разрядное целое число в системе счисления Пример. В факториальной системе счисления Лекция 5: Высказывания и предикаты Пример. Не является высказыванием Пример. Построим из ниже заданных простых высказываний Пример. Выражение "х = у" – предикат Пример. Заданы предикаты Пример. Заполним таблицу истинности трехместной логической функции Пример. Изобразим графически множество истинности двухместного предиката Логические функции Пример. Докажем равенство логических выражений Пример. Операции конъюнкции Аксиома тождества : всякое высказывание 6. Лекция: Логические вентили, схемы, структуры Логические схемы 7. Лекция: Базовые алгоритмические структуры Обычная запись ... Полное содержание

Подобный материал:

• Курс лекций по дисциплине история экономических учений москва 2008, 5434.7kb.
• Курс лекций по дисциплине "Компьютерные науки", 19.41kb.
• Н. И. Вавилова утверждаю ректор фгоу впо сгау /Н. И. Кузнецов/ 2008 г. Рекламно-техническое, 59.06kb.
• С. Н. Постовалов Программирование в системе 1С: Предприятие 7 (компонента "Бухгалтерский, 899.42kb.
• Курс лекций по дисциплине история экономики москва 2008, 991.98kb.
• Курс лекций по дисциплине "Стратегический менеджмент организации" 35 Курс лекций построен, 1161.6kb.
• Курс лекций по дисциплине " основы компьютерных технологий" Часть I. Microsoft Word, 432.92kb.
• Учебно методический комплекс по дисциплине «Менеджмент», 1078.42kb.
• Курс лекций по дисциплине «Компьютерные сети и телекоммуникации» для студентов факультета, 1959.57kb.
• Курс лекций по основам программирования Учебно-методическое пособие, 726.7kb.

При переводе в 8-ную систему или из нее необходимо группировать в тройки биты, а при переводе в 16-ную или из нее – группировать их в четверки битов. Можно добавлять, если нужно, незначащие нули (слева от целой части и справа от мантиссы) или отбрасывать их.

Пример. Рассмотрим переводы в смешанных системах.

1. 
   Из 2-ной системы в 8-ную (двоично-восьмеричное изображение):
   

2. из 8-ной системы в 2–ную (восьмерично-двоичное изображение):
   

3. из 2-ной системы в 16-ную (двоично-шестнадцатеричное изображение):
   

4. из 16-ной системы в 2-ную (шестнадцатерично-двоичное изображение):
   

Сложение в двоичной системе счисления осуществляется по правилам

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 2₁₀ = 10₂ (единица идет в старший разряд).

Таблица вычитания в двоичной системе счисления имеет вид

0 – 0 = 0, 1 – 0 = 1, 1 – 1 = 0, 0 – 1 = 10 – 1 = 1 (единицу забираем у старшего разряда).

Таблица умножения в двоичной системе счисления имеет вид

0 x 0 = 0, 0 x 1 = 0, 1 x 0 = 0, 1 x 1 = 1.

Таблица деления в двоичной системе счисления имеет вид

0 : 0 = не определено, 1 : 0 = не определено, 0 : 1 = 0, 1 : 1 = 1.

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

^ Дополнительный код = обратный код + единица в младшем разряде.

Пример.

1. 
   10011 двоичное число,
   

01100 обратный код этого двоичного числа,

01101 дополнительный код этого двоичного числа;

2. 457 восьмеричное число,
   

321 дополнительный код;

3. А9 шестнадцатеричное число,
   

57 дополнительный код.

Вычитание с помощью дополнительного кода: найти дополнительный код вычитаемого такой же разрядности, как и уменьшаемое, и сложить этот код с уменьшаемым. Результатом вычитания будет полученная сумма без учета старшего разряда (отбрасывается).

^ Пример. Выполним вычитание напрямую и через сложение (через дополнительный код):




Целые числа в математике и их аналоги в n-разрядных арифметиках тождественны (по количеству) в рамках их представления с этой разрядностью. При этом можно отметить основные отличия представления чисел в поле памяти человека и в поле памяти n-разрядной арифметики:

1. 
   бесконечное и счетное множество целых чисел представляется отрезком [–N; +N], где N – максимальное число, представимое в этой арифметике (многоточие – общее число единиц, равное n): N = (111 . . . 1)₂ ;
   
2. бесконечное и несчетное множество действительных чисел , располагающееся на числовой оси равномерно и плотно, представляется в n-разрядной арифметике множеством с неравномерной плотностью (сгущение у нуля и сжатость со стороны меньших чисел);
   
3. нуль во множестве действительных чисел в любой своей окрестности имеет множество чисел, а нуль в n-разрядной арифметике представлен изолированно.
   

С точки зрения обычной арифметики, например, в интервале (–1; 1) имеется бесконечное множество "плотно" расположенных точек, причем в любой окрестности каждой такой точки имеется хотя бы одна точка из этого множества. Такую арифметику называют часто регулярной арифметикой. Машинная же арифметика имеет следующие особенности. Она нерегулярна – точки интервала сгущаются около нуля; кроме того, в этом интервале точка х "изолирована" – если взять любую ее окрестность (х – а; х + а), где а – число, которое не превосходит машинного нуля (наименьшего представимого в машине числа), то в этом интервале нет других точек (отличных от х). Говоря языком теории вероятности, плотности распределения чисел в регулярной и нерегулярной арифметике – различны, как, впрочем, плотности распределения целых и вещественных чисел в одной и той же арифметике. Множество вещественных чисел в машинной арифметике представляется как подмножество (определяемое разрядностью арифметики) множества рациональных чисел. Есть и другие особенности этих множеств (связанные, например, с выполнением операций), но указанные выше особенности – основные.

Различия в представлении чисел в обычной и в машинной (n-разрядной) арифметике ограничивают как "математические" возможности компьютера, так и "компьютерные" возможности математики, использование математических методов, алгоритмов в компьютерах.

Нужно всегда иметь в виду, что точность в теоретической математике – понятие абстрактное и в практической математике может возникать иллюзия точности там, где ее на самом деле нет, – если нет корректной договоренности о пределах возможных значений неизбежных погрешностей в рамках рассматриваемых вычислительных ресурсов, например, трудоемкости и времени, а также не оговорена стратегия управления этой погрешностью.

Так как диапазон n-разрядных чисел системы счисления с основанием p находится в пределах , то для представления дробных чисел этот диапазон еще снижается, поскольку часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые "зоны нечувствительности" форм представления чисел в n-разрядных арифметиках.

В 1937 году ^ Конрадом Цузе для увеличения диапазона чисел, представимых в арифметике двоичных чисел, а также для повышения точности этого представления чисел было предложено представление чисел в плавающей, нормализованной форме – число x представляется в виде: , где m – мантисса числа, k – целый порядок числа, .

Пусть даны два числа: и (). Тогда можно проверить, что результаты выполнения операций будут равны:



Если из n разрядов, отводимых под изображение чисел, m двоичных разрядов отвести под мантиссу, k – под порядок, один разряд – под знак числа и один разряд – под знак порядка (например, 0 – плюс, 1 – минус), то диапазон представимых в форме с плавающей запятой чисел резко увеличивается (m + k + 2 = n):



(многоточие соответствует k единицам).

Числа, меньшие нижней границы положительных чисел и большие верхней границы отрицательных чисел, считаются равными нулю, не различаются между собой. Числа, большие верхней границы положительных чисел, полагаются равными положительной бесконечности (меньшие нижней границы отрицательных – отрицательной бесконечности). Сравнение двух разных по величине чисел в арифметике с ограниченной разрядностью может поэтому приводить к неверному результату, как и сравнение двух равных в таких системах чисел с точки зрения математической.

Такое представление очень удобно для хранения в ЭВМ, так как на самом деле необходимо хранить не само число, а его знак, мантиссу, порядок и знак порядка, и все операции с числами сводятся к операциям с этими объектами. Операции же с этими объектами просты: сравнение знаков, увеличение, уменьшение порядка, сложение мантисс, нормализация, то есть в конечном итоге сводятся к достаточно просто реализуемым операциям сдвига, выравнивания, сравнения разрядов.

^ Пример. Вычислить наибольшее и наименьшее 5-разрядное целое число в системе счисления с основанием 3. Наибольшее целое n-разрядное число, которое возможно записать в системе счисления с основанием р, равно:



Наименьшее целое n-разрядное число в этой системе равно



Таким образом, в системе счисления с основанием 3 и числом разрядов 5 представим диапазон следующих чисел:



Формулам можно придать более компактный вид. Например, для двоичной системы



а в восьмеричной системе счисления эти числа



К "неудобствам" этой формы представления чисел можно отнести возможность возникновения следующих "особо опасных" ситуаций:

1. 
   если число достаточно мало, например, а = 0.12Е + 00, то оно может быть представлено любым числом из наименьшего интервала включающего а, в частности числом 0.120000001 или 0.199999999 и в этом случае сравнивать на равенство "в лоб" нельзя (вещественные числа в форме с плавающей запятой опасно сравнивать на совпадение);
   
2. порядок выполнения операций может влиять на результат, например, в 4-разрядной арифметике с фиксированной запятой 20.0000 + 0.0001 = 20.0001, но при этом 0.2000Е + 02 + 0.1000Е – 05 = 0.2000Е + 02;
   
3. может возникнуть так называемая ситуация "переполнения порядка" при сложении (умножении) очень больших чисел или "исчезновения порядка" при сложении (умножении) "очень малых чисел", в частности, 0.6000Е + 39 ×0.1200Е + 64 = 0.9999Е + 99 (или же не определено), а также 0.6000Е – 35 × 0.0200Е – 65 = 0.9999Е – 99 (или же не определено), при соответствующим образом определенной разрядности десятичной арифметики;
   
4. при сложении чисел с плавающей запятой (а, в конечном счете, все операции выполняются через сложение) происходит выравнивание порядков для последующего сложения мантисс, а при выравнивании степеней может происходить потеря (усечение) младших разрядов, например, такая ситуация может возникнуть при сложении одного "очень большого числа" с одним "очень малым числом"
   

Есть много различных способов (часто искусственных) формирования систем чисел.

^ Пример. В факториальной системе счисления целые числа записывают линейной комбинацией факториалов, например, . Эта система (условно) позиционна. Так как 0! = 1! = 1, то два младших разряда n-разрядного числа в разложении этого числа по факториалам представимы как и поэтому веса этих разрядов не зависят от позиции (поэтому при это число можно считать непозиционным лишь условно). Формула перевода из факториальной системы счисления в десятичную систему:



История развития систем счисления достаточно интересна. Приведем лишь некоторые факты. Счет вначале велся с помощью пальцев рук (пятерками и затем – десятками). В некоторых странах сохранился счет с основанием 12 (например, Великобритания – 12 шиллингов) и 20 (например, Франция – "quatre–vingts" или "четыре-двадцать" то есть 80; у древних адыгов счет велся аналогично: "тощIищ", то есть "двадцать-три" – 60) и др. 

^ Лекция 5: Высказывания и предикаты Рассматриваются основные понятия и сведения алгебры высказываний и предикатов – высказывания, предикаты, аксиомы, логические выражения и функции, эквивалентные выражения и приведение к эквивалентному выражению, другие сопутствующие понятия и факты логики, а также инфологические задачи. Информатика, как было рассмотрено выше, изучает знаковые (алфавитные) системы. Алгебра – наиболее адекватный математический аппарат описания действий в них, поэтому алгебраический аппарат наилучшим образом подходит для описания информационных систем общей природы, отвлеченно от их предметной направленности. Информационные процессы хорошо формализуются с помощью различных алгебраических структур. Алгеброй A называется некоторая совокупность определенных элементов X, с заданными над ними определенными операциями f (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры . Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции). Совокупность операций алгебры A называется ее сигнатурой , а совокупность элементов алгебры – носителем алгебры. Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения отражения смысла информации (семантики). Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0". Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной. Пример. Рассмотрим словосочетания: Москва – столица США. Житель города Москва. 5 – 7 + 8. 5 – 9 + 28 = 4. В пятую неделю зимы было очень холодно. В Антарктиде живут тигры. Высказывание должно быть однозначно истинным или однозначно ложным, поэтому высказываниями являются только утверждения 1), 4), 6). ^ Пример. Не является высказыванием и "парадокс лжеца" (Эвбулид, учитель Демосфена, около 350 лет до н.э.): "То, что я сейчас утверждаю, – ложно", ибо если оно истинно – то оно ложно, а если допустить, что оно ложно, то оно истинно. Это неопределенная высказывательная форма. Аналогичный пример принадлежит известному математику, логику Гёделю (1931 г.): "То, что утверждается в этом предложении, не может быть доказано". Если его можно опровергнуть, то его нельзя доказать, а если его можно опровергнуть, то его можно доказать. Предложения такого рода не могут быть доказаны или опровергнуты в пределах того языка (той теории, алгебры), с помощью которой они сформулированы. Известны многие подобные парадоксы. Рассматривая высказывания, мы не обращаем внимания на их внутреннюю структуру и можем разлагать их на структурные части, равно как и объединять их. ^ Пример. Построим из ниже заданных простых высказываний составные, сложные высказывания, принимающие значение "истина", "ложь": "Зима – холодное время года". "Пальто – теплая одежда". "Камин – источник тепла". Истинным будет, например, сложное высказывание: "Зима – холодное время года и зимой носят пальто", а ложным будет, например, высказывание: "Некоторые ходят в пальто, поэтому на улице зима". Придумайте другие примеры. Предикат – высказывательная форма с логическими переменными (множество значений этих переменных вполне определено), имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется его местностью. Простые высказывания или предикаты не зависят от других высказываний или предикатов ("не разбиваемы на более простые"), а сложные – зависит хотя бы от двух простых. ^ Пример. Выражение "х = у" – предикат, "х > 5" – предикат, а "7 > 5" – высказывание. Утверждение "Хорошо" не является высказыванием, утверждение "Оценка студента А по информатике – хорошая" – простое высказывание, утверждение "Вчера была ясная погода, я был вчера на рыбалке" – сложное высказывание, состоящее из двух простых. Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}. ^ Пример. Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели". Найдем множество истинности предикатов р и q, если , Получаем, что , . Множество логических переменных с определенными над ним операциями: – отрицания или инверсии, – логического сложения или дизъюнкции , – логического умножения или конъюнкции называется алгеброй предикатов (и высказываний) , если эти операции удовлетворяют следующим аксиомам: Аксиома двойного отрицания: Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции): Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов): Аксиомы одинаковых операндов: Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения): Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот): Аксиомы де Моргана (перенесения бинарной операции на операнды): Аксиомы нейтральности (взаимноинверсных множителей или слагаемых): Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем, Из этих аксиом следует ряд полезных соотношений, например, Три базовые операции алгебры предикатов определяются таблицей их значений, так как в алгебре предикатов из-за дискретности значений логических функций часто используется табличная форма задания функции. Булеву функцию n переменных можно полностью определить таблицей из 2n строк. Итак, эти операции определяются совмещенной таблицей значений вида 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 Такая таблица всех значений некоторой логической функции называется таблицей истинности этой функции. Пример. Составим таблицу истинности функции . Эта таблица имеет вид 0 0 1 0 0 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 1 Следовательно, функция тождественно-истинна. Это можно было доказать (проверить) и с помощью аксиом: ^ Пример. Заполним таблицу истинности трехместной логической функции . Эта таблица имеет вид 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 ^ Пример. Изобразим графически множество истинности двухместного предиката вида р(х,у) = "модуль числа х равен модулю числа у", если задана область изменения аргументов: . Имеем соотношение Смысл предикатов р1(х,у) и р2(х,у) очевиден. Множество изображается графиком функции y=|x|, который дан на рис. 5.1: Рис. 5.1.  График функции y = |x| Кроме указанных трех базовых операций можно с их помощью ввести еще следующие важные операции алгебры предикатов (можно их назвать небазовыми операциями): импликации: ; эквиваленции: . Операции импликации и эквиваленции, хотя и являются часто используемыми, но не базовые, ибо они определяемы через три введенные выше базовые операции. Нетрудно определить их таблицы истинности (проделайте это самостоятельно с помощью правых частей приведенных равенств). При выполнении логических операций в компьютере они сводятся к поразрядному сравнению битовых комбинаций. Эти операции достаточно быстро (аппаратно) выполняемы, так как сводятся к выяснению совпадения или несовпадения битов. В логических формулах определено старшинство операций, например: скобки, отрицание, конъюнкция, дизъюнкция (остальные, небазовые операции пока не учитываем). Всегда истинные формулы называют тавтологиями . ^ Логические функции эквивалентны, если совпадают их таблицы истинности, то есть совпадают области определения и значения, а также сами значения функции при одних и тех же наборах переменных из числа всех допустимых значений. Если это совпадение происходит на части множества допустимых значений, то формулы называются эквивалентными лишь на этой части (на этом подмножестве). Задача упрощения логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов) эквивалентному выражению. Наиболее простой вид получается при сведении функции к постоянной – 1 (истина) или 0 (ложь). Пример. Упростим: Задача доказательства равенства двух логических выражений (функций) состоит в установлении эквивалентности этих функций на некотором множестве значений всех переменных, входящих в данную функцию. ^ Пример. Докажем равенство логических выражений: Используя аксиомы алгебры предикатов, получаем равенства Левая часть равенства приведена к правой части, то есть данное равенство доказано полностью. Такие задачи решаются с помощью аксиом алгебры предикатов одним из следующих способов: правая часть равенства приводится к левой части; левая часть равенства приводится к правой части; обе части равенства приводятся к третьему выражению. Логические функции позволяет эффективно решать так называемые инфологические (информационно-логические) задачи, доказывать утверждения. Информационно-логическая (инфологическая) задача – это задача, в которой необходимо установить некоторые информационные или логические связи и сделать необходимые причинно-следственные логические выводы. Эти задачи возникают в различных областях и часто являются плохо формализованными и структурированными. Их нужно хорошо формализовать и структурировать. Насколько хорошо будет возможно это сделать – настолько хорошо и полно будет решена рассматриваемая проблема или задача. Рассмотрим пример информационно-логической задачи (например, решаемой следователем, знакомым с алгеброй предикатов). Пример. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определим истинный цвет и истинную марку автомобиля. Рассмотрим простые высказывания вида: х = "машина – синяя", у = "машина – Бьюик", z = "машина – черная", u = "машина – Крайслер", v = "машина – Форд". На их основе высказывание Брауна можно записать в виде сложного логического выражения вида , высказывание Джонса – в виде , а высказывание Смита – в виде . Так как в каждом из этих выражений одна из переменных принимает значение "истина", то истинны и дизъюнкции вида: . По определению конъюнкции, . Это выражение мы взяли из-за однозначности равенства 1 конъюнкции и неоднозначности (многовариантности) его равенства нулю. Упростим выражение: Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда , то заключаем, что автомобиль был черным "Бьюиком". Законы алгебры высказываний и предикатов сходны с правилами, по которым человек делает умозаключения, доказывает, мыслит. ^ Пример. Операции конъюнкции, дизъюнкции, отрицания алгебры высказываний – аналоги союзов "и", "или", приставки "не", используемых (возможно, интуитивно) при выражении мысли человеком. Чтобы переложить на ЭВМ работы мыслительного характера, эти правила необходимо строго сформулировать, формализовать. Это позволяет осуществить алгебра логики. Приведем некоторые аксиомы логики – науки, изучающей методы доказательства и опровержения утверждений. Аксиома исключения третьего : либо имеет место высказывание, либо его отрицание. Аксиома противоречия : высказывания и его отрицание не могут иметь места одновременно. Аксиома двойного отрицания : двукратное отрицание какого-либо утверждения равносильно исходному утверждению. ^ Аксиома тождества : всякое высказывание тождественно самому себе. Если высказывания x и y связаны друг с другом отношением , то говорят, что высказывание y следует из высказывания x (или y – следствие x); если множество истинности Х высказывания х содержит множество истинности Y высказывания y, то высказывание x – условие, высказывание y – заключение, а само соотношение – вывод. Доказательство формальных математических утверждений (теорем) – последовательность корректных выводов, ведущих от условия к заключению. Алгебра логики помогает доказывать теоремы (дает общие подходы и методы доказательства). Общий подход к доказательству теорем методом от противного, обратных и противоположных теорем можно формализовать с помощью алгебры логики.

^ 6. Лекция: Логические вентили, схемы, структуры Рассматриваются основные теоретические (математические, логические) понятия и сведения, касающиеся базовых логических элементов и структур – логических вентилей, логических (переключательных) схем, логической базы аппаратуры ЭВМ и их оптимальной структуры, оптимизации их структур. Любой, самый примитивный компьютер – сложнейшее техническое устройство. Но даже такое сложное устройство, как и все в природе и в технике, состоит их простейших элементов. Любой компьютер, точнее, любой его электронный логический блок состоит из десятков и сотен тысяч так называемых вентилей (логических устройств, базовых логических схем), объединяемых по правилам и законам (аксиомам) алгебры вентилей в схемы, модули. Логический вентиль (далее – просто вентиль) – это своего рода атом, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана (отсюда и название), открывая или закрывая путь сигналам. ^ Логические схемы предназначены для реализации различных функций алгебры логики и реализуются с помощью трех базовых логических элементов (вентилей, логических схем или так называемых переключательных схем). Они воспроизводят функции полупроводниковых схем. Работу вентильных, логических схем мы, как и принято, будем рассматривать в двоичной системе и на математическом, логическом уровне, не затрагивая технические аспекты (аспекты микроэлектроники, системотехники, хотя они и очень важны в технической информатике). Логические функции отрицания, дизъюнкции и конъюнкции реализуют, соответственно, логические схемы, называемые инвертором, дизъюнктором и конъюнктором. Логическая функция "инверсия", или отрицание, реализуется логической схемой (вентилем), называемой инвертор. Принцип его работы можно условно описать следующим образом: если, например, "0" или "ложь" отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или "истина", которую можно также отождествить с тем, что на выходе снимается напряжение в 1 вольт. Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт ("истина"), то на выходе инвертора будет сниматься 0 вольт, то есть "ложь" (схемы на рисунках 6.1 а, б). Рис. 6.1.  Принцип работы инвертора Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рис. 6.2), в которой замкнутая цепь соответствует 1 ("истина") или х = 1, а размыкание цепи соответствует 0 ("ложь") или х = 0. Из указанных простейших базовых логических элементов собирают, конструируют сложные логические схемы ЭВМ, например, сумматоры, шифраторы, дешифраторы и др. Большие (БИС) и сверхбольшие (СБИС) интегральные схемы содержат в своем составе (на кристалле кремния площадью в несколько квадратных сантиметров) десятки тысяч вентилей. Это возможно еще и потому, что базовый набор логических схем (инвертор, конъюнктор, дизъюнктор) является функционально полным (любую логическую функцию можно представить через эти базовые вентили), представление логических констант в них одинаково (одинаковы электрические сигналы, представляющие 1 и 0) и различные схемы можно "соединять" и "вкладывать" друг в друга (осуществлять композицию и суперпозицию схем). Таким способом конструируются более сложные узлы ЭВМ – ячейки памяти, регистры, шифраторы, дешифраторы, а также сложнейшие интегральные схемы. Пример. В двоичной системе таблицу суммирования цифры x и цифры y и получения цифры z с учетом переноса p в некотором разряде чисел x и y можно изобразить таблицей вида x y z p 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Эту таблицу можно интерпретировать как совместно изображаемую таблицу логических функций (предикатов) вида Логический элемент, соответствующий этим функциям, называется одноразрядным сумматором и имеет следующую схему (обозначим ее как или – если мы хотим акцентировать именно выбранный, текущий i-й разряд) Пример. "Черным ящиком" называется некоторое закрытое устройство (логическая, электрическая или иная схема), содержимое которого неизвестно и может быть определено (идентифицировано) только по отдельным проявлениям входа/выхода ящика (значениям входных и выходных сигналов). В "черном ящике" находится некоторая логическая схема, которая в ответ на некоторую последовательность входных (для ящика) логических констант выдает последовательность логических констант, получаемых после выполнения логической схемы внутри "черного ящика". Определим логическую функцию внутри "черного ящика" (рис. 6.10), если операции выполняются с логическими константами для входных последовательностей (поразрядно). Например, х = 00011101 соответствует последовательности поступающих значений: "ложь", "ложь", "ложь", "истина", "истина", "истина", "ложь", "истина". Из анализа входных значений (входных сигналов) х, у и поразрядного сравнения логических констант в этих сообщениях с константами в значении z – результате выполнения функции в "черном ящике", видно, что подходит, например, функция вида Действительно, в результате "поразрядного" сравнения сигналов (последовательностей значений "истина", "ложь") получаем следующие выражения (последовательности логических констант): Важной задачей (технической информатики) является минимизация числа вентилей для реализации той или иной схемы (устройства), что необходимо для более рационального, эффективного воплощения этих схем, для большей производительности и меньшей стоимости ЭВМ. Эту задачу решают с помощью методов теоретической информатики (методов булевой алгебры). Пример. Построим схему для логической функции Пример. Определим логическую функцию , реализуемую логической схемой вида (рис. 6.13) Искомая логическая функция, если выписать ее последовательно, заполняя "верх" каждой стрелки, будет иметь следующий вид:

^ 7. Лекция: Базовые алгоритмические структуры Рассматриваются основные понятия об алгоритме в программах и алгоритмизации решения задач. "Алгоритм" является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса информатики (ядром курса). Понятие алгоритма, как и понятие информации, точно определить невозможно. Поэтому встречаются самые разнообразные определения – от "наивно-интуитивных" ("алгоритм – это план решения задачи") до "строго формализованных" (нормальные алгоритмы Маркова). В качестве рабочего определения алгоритма возьмем следующее определение. Алгоритм – это упорядоченная совокупность точных (формализованных) и полных команд исполнителю алгоритма (человек, ЭВМ), задающих порядок и содержание действий, которые он должен выполнить для нахождения решения любой задачи из рассматриваемого класса задач. Алгоритм удовлетворяет следующим основным свойствам: Конечность (дискретность) команд и выполняемых по ним действий алгоритма. Выполнимость в определенной операционной среде (в определенном классе исполнителей). Результативность отдельных команд и всего алгоритма. Применимость алгоритма ко всем возможным входным данным конкретного класса задач. Определенность (детерминированность) команд и всего алгоритма для всех входных данных. Формализованное, конструктивное описание (представление) команд алгоритма. Минимальная полнота системы команд алгоритм. Непротиворечивость любых команд алгоритма на любом наборе входных данных. Любой алгоритм ориентирован на некоторый общий метод решения класса задач и представляет собой формализованную запись метода, процедуры. Алгоритм, записанный на некотором алгоритмическом, формальном языке, состоит из заголовка алгоритма (описания параметров, спецификаций класса задач) и тела алгоритма (последовательности команд исполнителя, преобразующих входные параметры в выходные). Для записи, исполнения, обмена и хранения алгоритмов существуют различные средства, языки, псевдокоды – блок-схемы, структурограммы (схемы Нэсси-Шнайдермана), Р-схемы, школьный алгоритмический язык (ШАЯ), различные языки программирования. В качестве языка описания алгоритмов нами используется далее язык программирования Паскаль, так как он наиболее подходит для целей обучения и часто (обоснованно) используется в обучении. На алгоритмическом языке Паскаль любой алгоритм простой (не модульной, не составной) структуры имеет следующий стандартный вид: Program <имя (заголовок) алгоритма>; Uses <список подключаемых библиотек, если они нужны>; { комментарии, если нужны } Label <список меток (имен участков программ), если они нужны>; { комментарии } Const <список констант (не изменяемых величин), если они нужны>; { комментарии } Type <список имен и типов структур данных, если они нужны>; { комментарии } Var <список имен и типов переменных, если они нужны>; { комментарии } { < условия задачи и применимости алгоритма > } { < цель составления и выполнения алгоритма > } Begin <команды ввода входных данных, если они нужны>; { комментарии } <тело алгоритма (команды управления и преобразования алгоритма)>; { комментарии } <команды вывода результатов (выходных данных), если они нужны>; { комментарии } End. Пример. Программа вычисления объема v правильного цилиндра с радиусом основания r и высотой h. Program VСil; Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете" } Const pi = 3.14; Var r, h, v: real; { для правильного цилиндра с радиусом основания r и высотой h } { вычислить и выдать на экран значение его объема v } Begin ClrScr; { команда очистки экрана (от данных предыдущей задачи) } ReadLn (r, h); { ввод входных параметров } v:=pi*r*r*h; { вычисление объема по формуле для цилиндра } WriteLn (‘Вычисленный объем цилиндра равен ’, v) { вывод результата } End. Приведем таблицу наиболее часто используемых в языке Паскаль функций и процедур. ^ Обычная запись Паскаль Квадрат числа х sqr(x) Корень квадратный из x sqrt (x) Модуль |х| abs (x) sin x sin(x) cos x cos(x) tg x tg(x) ctg x ctg(x) arcsin x arcsin (x) arccos x arccos(x) arctg x arctg(x) Натуральный логарифм ln x ln(x) Степень числа е = 2, 7... или еx exp(x) Остаток от деления целого х на целое у x mod y Частное от деления целого х на целое y x div y Целая часть числа х (вещественного) int(x) Случайное число от 0 до х rnd(x) Длина текста х в символах length (x) Пример. Результаты применения этих функций: sqrt(9) = 3, abs(–5) = 5, sin(0) = 0, cos(0) = 1, ln(1) = 0, exp(1 ) =e, 23 mod 5 = 3, 20 mod 5 = 0, 23 div 5 = 4, 20 div 5 = 4, int(2.7) = 2, int(2) = 2, rnd(0) = 0.231356, length(‘информ’) = 6. Порядок выполнения операций (старшинство операций – по убыванию) в языке Паскаль: вычисление выражений в скобках; вычисление стандартных функций; умножение и деление (обозначаются "*" и "/"); сложение и вычитание (обозначаются "+" и "–"). Пример. Выражение b*c + (d/t*(v/n/m))*sin(x) вычисляется в следующем порядке (слева направо): v/n, (v/n)/m, d/t, (d/t)*(v/n/m), sin(x), b*c, (d/t*(v/n/m))*sin(x), b*c+(d/t*(v/n/m))*sin(x) и эквивалентно математическому выражению: . Рассмотрим базовые простые команды языка Паскаль. Команда описания (заголовка) алгоритма (программы) : Program <имя алгоритма>;, где <имя алгоритма> – имя, задаваемое составителем программы (краткое, полное, грамотное отражение сути алгоритма). Ввод – команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров: Read (<список вводимых параметров>); или ReadLn (<список вводимых параметров>);. Первая команда вводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана. Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма: Write (<список выводимых параметров>); или WriteLn (<список выводимых параметров>);. Первая команда выводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана. Присваивание – команда изменения текущего значения переменной вида: <идентификатор> := <выражение>;, где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак ":=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>. Команда начала алгоритма (блока) – команда Begin. Команда завершения алгоритма (блока) – команда End. Команда вставки комментариев в текст алгоритма имеет вид: <комментируемое в программе> <текст комментария>. Комментировать можно любой объект в программе. Обычно комментируют переменную, структуру данных, команду, группу команд. Различают три базовые алгоритмические структуры: следование, ветвление, повторение. Структура следование состоит из двух команд с указанной очередностью их выполнения и имеет вид: <команда – предшественник>; <команда – преемник>. Структура типа ветвления в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия. Структура имеет вид if <условие> then <команда, выполняемая при выполнении условия> else <команда, выполняемая при невыполнении условия>;. Ключевые (служебные) слова Паскаля – if (если), then (то), else (иначе). Ключевые слова нельзя изменять, заменять, так как их эталоны закреплены в переводчике с языка Паскаль (о нем подробнее – ниже). Пример. Команда вида if (х>y) { если текущее значение х больше текущего значения y, } then у := х { то текущее значение у полагаем равным текущему значению х, } else x:= y; { иначе (при х <= y) текущее значение x заменяем на текущее значение y }. Структура типа ветвления в неполной форме – частный случай ветвления в полной форме, в которой, при невыполнении условия, управление просто передается следующей команде и больше никаких действий команда ветвления не осуществляет. Эта структура имеет вид if <условие> then <команда, выполняемая при исполнении условия>; . Структура повторения (цикл) служит для компактной записи одного и того же набора команд, повторяемых для различных значений параметров команд. Структура повторения типа "пока (while)" записывается в виде: while <условие продолжения повторения> do <повторяемая команда>; или while <условие продолжения повторения> do begin <повторяемая команда номер 1>; <повторяемая команда номер 2>; . . . <повторяемая команда номер N> end;. Ключевые слова Паскаля – while (пока), do (выполнять), begin (начало), end (конец). Телом цикла называется последовательность повторяемых команд, которая может быть и пустой (редко встречаемый случай).