НОУ « ВОЛГОГРАДСКИЙ ИНСТИТУТ БИЗНЕСА»
кафедра математики и естественных наук
КОНТРОЛЬНАЯ РАБОТА ПО ИНФОРМАТИКЕ
АРИФМЕТИЧЕСКИЕ ОСНОВЫ РАБОТЫ ЭВМ
Выполнил: студент группы 1- МТ71з
ШАЛИМОВ АЛЕКСЕЙ ЭДУАРДОВИЧ
Проверил:
МАКАРОВА МАРИЯ АЛЕКСАНДРОВНА
ВОЛГОГРАД 2008
Введение
1. Представление информации в компьютере
2. Системы счисления
3. Перевод числа из одной системы счисление в другую
4. Арифметические операции в позиционных системах счисления
Заключение
Список литературы
Введение
Качественно новое обслуживание информационных процессов, пронизывающих различные сферы человеческой деятельности тесным образом связано с использованием современной электронно-вычислительной техники.
Термин компьютер, так прочно вошедший в русский язык, в переводе означает «вычислитель», т.е. устройство для осуществления вычислений.
Потребность в автоматизации вычислений или, как сейчас говорят - обработки данных, возникла давно. Уже более полутора тысяч лет назад для облегчения вычислений стали использовать счеты.
Но только в 1642 году Блез Паскаль изобрел устройство для механического сложения чисел, а в 1673 году Г. В. Лейбниц сконструировал арифмометр, позволявший механическим способом выполнять четыре арифметических действия, И хотя, начиная с XIX века, арифмометры получили широкое распространение, у них был один существенный недостаток: расчеты производились очень медленно. Причина проста - выбор выполняемых действий и запись результатов при осуществлении расчетов производилась человеком, скорость работы которого весьма ограничена.
Для устранения этого недостатка английский математик Ч. Бэббидж попытался построить универсальное вычислительное устройство, выполняющее вычисления без участия человека. Для этого оно должно было уметь исполнять программы, вводимые с помощью перфокарт (прямоугольных пластин из плотной бумаги с информацией, наносимой при помощи отверстий). Бэббидж не смог довести до конца работу по созданию своей Аналитической машины: ее устройство оказалось слишком сложным для технического оснащения промышленности первой половины XIX века. Однако идеи, заложенные в основу этого устройства, позволили американцу Г. Эйкену в 1943 году построить на одном из предприятий фирмы IBM машину, функционирующую на электромеханических роле и получившую название «Марк-1».
К этому времени потребность в автоматизации обработки данных (в первую очередь, для военных нужд - баллистики, криптографии и т.д.) стала настолько ощутимой, что над созданием подобных машин одновременно работало несколько групп исследователей в разных странах мира. Начиная с 1943 года, группа специалистов под руководством Д. Мочли и П. Экерта в США занималась конструированием более современной вычислительной машины на основе электронных ламп, которая могла бы хранить выполняемую программу в своей памяти. Для ускорения работы в 1945 году к этому проекту был привлечен знаменитый математик Джон фон Нейман. В результате его участия был подготовлен доклад, содержавший целый ряд принципов, на основе которых и должна была функционировать разрабатываемая машина.
Первый компьютер, в котором в полной мере реализовались принципы фон Неймана был построен в 1949 году английским исследователем М. Уилксом. С той поры прошло более 50 лет, и тем не менее, большинство современных компьютеров в той или ином степени соответствуют принципам, изложенным фон Нейманом.
В своей работе Д. Фон Нейман описал, как должен быть устроен компьютер для того, чтобы он был универсальным и эффективным устройством обработки информации (рис.1). В состав такого компьютера должны входить:
♦ арифметико-логическое устройство, выполняющее арифметические и логические операции;
♦устройство управления, организующее процесс выполнения программ и синхронизирующее работу остальных устройств компьютера;
♦запоминающее устройство (память), предназначенное для хранения выполняемых программ и обрабатываемых данных;
♦внешние устройства, предназначенные для ввода и вывода информации.
1 Представление информации в компьютере
Компьютер может обрабатывать только информацию, представленную в числовой форме. Вся остальная информация (например, звук, видео, графические изображения и т.д.) перед обработкой на компьютере должна быть преобразована в числовую форму. Так, чтобы привести к цифровому виду (оцифровать) музыкальный звук, можно через небольшие промежутки времени измерять интенсивность звука на определенных частотах, представляя результаты каждого измерения в числовой форме. Затем, с помощью специальной компьютерной программы осуществляются необходимые преобразования полученных данных: наложение звуков от различных источников друг на друга (эффект оркестра), изменение тональности отдельных звуков и т.п. После чего, окончательный результат преобразуется обратно в звуковую форму.
2. Системы счисления
Система счисления - это способ записи чисел с помощью заданного набора специальных знаков (цифр).
Двоичная система счисления. В этой системе всего две цифры - 0 и 1. Особую роль здесь играет число 2 и его степени: 2, 4, 8 и т.д. Самая правая цифра числа показывает число единиц, следующая цифра - число двоек, следующая - число четверок и т.д. Двоичная система счисления позволяет закодировать любое натуральное число - представить его в виде последовательности нулей и единиц. В двоичном виде можно представлять не только числа, но и любую другую информацию: тексты, картинки, фильмы и аудиозаписи. Инженеров двоичное кодирование привлекает тем, что легко реализуется технически.
Десятичная система счисления. Пришла в Европу из Индии, где она появилась не позднее VI века н.э. В этой системе 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, но информацию несет не только цифра, но и место, на котором цифра стоит (то есть ее позиция). В десятичной системе счисления особую роль играют число 10 и его степени: 10, 100, 1000 и т.д. Самая правая цифра числа показывает число единиц, вторая справа - число десятков, следующая - число сотен и т.д.
Восьмеричная система счисления. В этой системе счисления 8 цифр: 0, 1, 2, 3, 4, 5, 6, 7. Цифра 1, указанная в самом младшем разряде, означает - как и в десятичном числе - просто единицу. Та же цифра 1 в следующем разряде означает 8, в следующем 64 и т.д. Число 100 (восьмеричное) есть не что иное, как 64 (десятичное). Чтобы перевести в двоичную систему, например, число 611 (восьмеричное), надо заменить каждую цифру эквивалентной ей двоичной триадой (тройкой цифр). Легко догадаться, что для перевода многозначного двоичного числа в восьмеричную систему нужно разбить его на триады справа налево и заменить каждую триаду соответствующей восьмеричной цифрой.
Шестнадцатеричная система счисления. Запись числа в восьмеричной системе счисления достаточно компактна, но еще компактнее она получается в шестнадцатеричной системе. В качестве первых 10 из 16 шестнадцатеричных цифр взяты привычные цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, а вот в качестве остальных 6 цифр используют первые буквы латинского алфавита: A, B, C, D, E, F. Цифра 1, записанная в самом младшем разряде, означат просто единицу. Та же цифра 1 в следующем - 16 (десятичное), в следующем - 256 (десятичное) и т.д. Цифра F, указанная в самом младшем разряде, означает 15 (десятичное). Перевод из шестнадцатеричной системы в двоичную и обратно производится аналогочно тому, как это делается для восьмеричной системы.
Существуют позиционные и непозиционные системы счисления. В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.
В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая – 7 единиц, а третья – 7 десятых долей единицы.
Сама же запись числа 757,7 означает сокращенную запись выражения
700 + 50 + 7 + 0,7 = 7 * 102 + 5 * 101 + 7 * 100+ 7 * 10-1 = 757,7.
Любая позиционная система счисления характеризуется своим основанием.
Основание позиционной системы счисления - это количество различных знаков или символов, используемых для изображения цифр в данной системе. За основание системы можно принять любое натуральное число - два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием q означает сокращенную запись выражения
an-1 qn-1 + an-2 qn-2 +… + a1 q1 + a0q0+ a-1 q-1 +… + a-m q-m ,
где ai – цифры системы счисления; n и m – число целых и дробных разрядов, соответственно.
В каждой системе счисления цифры упорядочены в соответствии с их значениями: 1 больше 0, 2 больше 1 и т.д.
В любой системе счисления для представления чисел выбираются некоторые символы (слова или знаки), называемые базисными числами, а все остальные числа получаются в результате каких-либо операций из базисных чисел данной системы счисления.
Системы счисления различаются выбором базисных чисел и правилами образования из них остальных чисел.
Единицей информации в компьютере является один бит (bit), т.е. двоичный разряд, который может принимать значение 0 или 1. Бит - это фундаментальная единица, определяющая количество информации, подвергаемое обработке или переносимое из одного места в другое. Поскольку биты записываются нулями и единицами, их последовательные совокупности позволяют кодировать двоичные числа (binarynumbers) - значение в двоичной системе счисления.
В более привычной для человека десятичной системе счисления (по основанию 10) для представления чисел используется десять символов: 0, 1, 2, 3, 4,5,6,7,8и 9. Чтобы составить число, значение которого в десятичной системе счисления больше 9 (например, 27), комбинируют две цифры: при этом позиции символов имеют определенный смысл. Прогрессия значений, связанная с позицией цифры, возрастает, как показано на рис. 2., пропорционально степени основания.
Рис. 2. Пример представления числа в десятичной системе счисления
Десятичное число, состоящее хотя бы из двух цифр, является суммой различных степеней основания, умноженных на соответствующую цифру. Так, число 10 представляет собой сумму из одного десятка (101) и нуля единиц (100), а число 423 - сумму из четырех сотен (102), двух десятков (101) и трех единиц (100).
Рассмотренный метод представления чисел достаточно универсален и используется в других системах счисления, в которых основание отлично от десяти. Например, в системе с основанием 8 задействовано восемь символов: 0, 1, 2, 3, 4, 5, 6 и 7, а значимость каждой позиции возрастает пропорционально степени числа 8, как показано на рис.3.
Рис. 3. Пример предоставления числа в восьмеричной системе счисления.
Как уже отмечалось, компьютер способен обрабатывать информацию в двоичной системе счисления. В ней используются только два символа 0 и 1, а смещение символа на одну позицию влево увеличивает значение числа пропорционально степени основания 2. На рис. 4 показано восьмибитовое (1 байт) представление числа 58 в двоичной системе счисления.
Рис. 4. Пример представления числа в двоичной системе счисления.
3. Перевод числа из одной системы счисление в другую
Из всех систем счисления особенно проста и поэтому интересна для технической реализации в компьютерах двоичная система счисления. Эта система имеет ряд преимуществ перед другими системами:
· для ее реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток - нет тока, намагничен - не намагничен и т.п.), а не, например, с десятью, - как в десятичной;
· представление информации посредством только двух состояний надежно и помехоустойчиво;
· возможно применение аппарата булевой алгебры для выполнения логических преобразований информации;
· двоичная арифметика намного проще десятичной.
Недостаток двоичной системы - быстрый рост числа разрядов, необходимых для записи чисел. Являясь удобной для компьютеров, для человека двоичная система неудобна из-за ее громоздкости и непривычной записи.
Перевод чисел из десятичной системы в двоичную и наоборот выполняет машина. Однако чтобы профессионально использовать компьютер, следует научиться понимать слово машины. Для этого и разработаны восьмеричная и шестнадцатеричная системы.
Числа в этих системах читаются почти так же легко, как десятичные, требуют соответственно в три (восьмеричная) и в четыре (шестнадцатеричная) раза меньше разрядов, чем в двоичной системе (ведь числа 8 и 16 – соответственно, третья и четвертая степени числа 2).
Перевод восьмеричных и шестнадцатеричных чисел в двоичную систему очень прост: достаточно каждую цифру заменить эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр).
То есть, чтобы перевести число из двоичной системы в восьмеричную или шестнадцатеричную, его нужно разбить влево и вправо от запятой на триады (для восьмеричной) или тетрады (для шестнадцатеричной) и каждую такую группу заменить соответствующей восьмеричной (шестнадцатеричной) цифрой.
Как перевести целое число из десятичной системы в любую другую позиционную систему счисления?
При переводе целого десятичного числа в систему с основанием q его необходимо последовательно делить на q до тех пор, пока не останется остаток, меньший или равный q–1. Число в системе с основанием q записывается как последовательность остатков от деления, записанных в обратном порядке, начиная с последнего.
Пример: Перевести число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
Ответ: 7510 = 1 001 0112 = 1138 = 4B16 .
Как пеpевести пpавильную десятичную дpобь в любую другую позиционную систему счисления?
Пpи переводе правильной десятичной дpоби в систему счисления с основанием q необходимо сначала саму дробь, а затем дробные части всех последующих произведений последовательно умножать на q, отделяя после каждого умножения целую часть произведения. Число в новой системе счисления записывается как последовательность полученных целых частей произведения. Умножение производится до тех поp, пока дробная часть произведения не станет равной нулю. Это значит, что сделан точный пеpевод. В противном случае перевод осуществляется до заданной точности. Достаточно того количества цифp в pезультате, котоpое поместится в ячейку.
Пример: Перевести число 0,35 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
Ответ: 0,3510 = 0,010112 = 0,2638 = 0,5916 .
Как перевести число из двоичной (восьмеричной, шестнадцатеричной) системы в десятичную?
При переводе числа из двоичной (восьмеричной, шестнадцатеричной) системы в десятичную надо это число представить в виде суммы степеней основания его системы счисления.
4. Арифметические операции в позиционных системах счисления
Рассмотрим основные арифметические операции: сложение, вычитание, умножение и деление. Правила выполнения этих операций в десятичной системе хорошо известны - это сложение, вычитание, умножение столбиком и деление углом. Эти правила применимы и ко всем другим позиционным системам счисления.
При сложении цифры суммируются по разрядам, и если при этом возникает избыток, то он переносится влево.
Пример: Сложим числа 15 и 6 в шестнадцатеричной системе счисления: F16 + 616 15 + 6 = 2110 = 101012 = 258 ;
Ответ: = 1516 .
Проверка. Преобразуем полученные суммы к десятичному виду:
101012 = 24 + 22 + 20= 16+4+1=21,
258 = 2*81 + 5*80= 16 + 5 = 21,
1516 = 1*161 + 5*160= 16+5 = 21.
Вычитание
Пример: Вычтем единицу из чисел 102, 108 и 1016
Вычтем единицу из чисел 1002, 1008 и 10016 .
Вычтем число 59,75 из числа 201,25.
Ответ: 201,2510 – 59,7510 = 141,510 = 10001101,12 = 215,48 = 8D,816 .
Проверка: Преобразуем полученные разности к десятичному виду:
10001101,12 = 27 + 23 + 22 + 20+ 2–1 = 141,5;
215,48 = 2*82 + 1*81 + 5*80+ 4*8–1 = 141,5;
8D,816 = 8*161 + D*160+ 8*16–1 = 141,5.
Умножение
Выполняя умножение многозначных чисел в различных позиционных системах счисления, можно использовать обычный алгоритм перемножения чисел в столбик, но при этом результаты перемножения и сложения однозначных чисел необходимо заимствовать из соответствующих рассматриваемой системе таблиц умножения и сложения.
Ввиду чрезвычайной простоты таблицы умножения в двоичной системе, умножение сводится лишь к сдвигам множимого и сложениям.
Пример: Перемножим числа 5 и 6.
Ответ: 5*6 = 3010 = 111102 = 368 .
111102 = 24 + 23 + 22 + 21 = 30; 368 = 3 81 + 6 80= 30.
Пример: Перемножим числа 115 и 51.
Ответ: 115*51 = 586510 = 10110111010012 = 133518 .
Проверка: Преобразуем полученные произведения к десятичному виду:
10110111010012 = 212 + 210 + 29 + 27 + 26 + 25 + 23 + 20= 5865;
133518 = 1*84 + 3*83 + 3*82 + 5*81 + 1*80= 5865.
Деление
Деление в любой позиционной системе счисления производится по тем же правилам, как и деление углом в десятичной системе. В двоичной системе деление выполняется особенно просто, ведь очередная цифра частного может быть только нулем или единицей.
Пример: Разделим число 30 на число 6.
Ответ: 30: 6 = 510 = 1012 = 58 .
Пример: Разделим число 5865 на число 115.
Восьмеричная: 133518:1638
Ответ: 5865: 115 = 5110 = 1100112 = 638 .
Проверка: Преобразуем полученные частные к десятичному виду:
1100112 = 25 + 24 + 21 + 20= 51; 638 = 6*81 + 3*80= 51.
Заключение
В структуру автоматизированной информационной системы входят несколько подсистем. Одной из таких подсистем является математическое и программное обеспечение, то есть совокупность математических методов, моделей, алгоритмов и программ для реализации целей и задач информационной системы, а также нормального функционирования комплекса технических средств.
Фундаментом науки о вычислительных машинах является конструктивная математика, в основе которой лежит математическая логика и теория алгоритмов с их однозначностью в оценке суждений и процедур вывода. Для описания элементов и узлов ЭВМ с самого начала использовалась математическая логика, а для описания компьютерных программ - теория алгоритмов.
Математическая логика - это дисциплина, изучающая технику математических доказательств. Отличие математических суждений от обычных разговорных высказываний состоит в том, что математические суждения всегда предполагают однозначную интерпретацию, в то время как наши обычные высказывания зачастую допускают многозначную трактовку.
Работа ЭВМ как автоматических устройств основана исключительно на математически строгих правилах выполнения команд, программ и интерпретации данных. Тем самым работа компьютеров допускает строгую однозначную проверку правильности своей работы в плане заложенных в них процедур и алгоритмов обработки информации.
С появлением самых первых компьютерных программ, имитирующих интеллектуальную деятельность людей, возникло понятие«искусственный интеллект» ивсе компьютерные программы, демонстрирующиеинтеллектуальное поведение, основаны на использовании определенного математического аппарата, опирающегося на законы математической логики и соответственно, имеющего арифметические основы. Без понимания этих законов и основ невозможно понимание принципов работы вычислительных машин вообще и систем искусственного интеллекта в частности.
Список литературы
1. Громов Ю. Ю., О. Г. Иванова, А. В. Лагутин. Информатика: Учебное пособие. Тамбов: Изд-во Тамб. гос. техн. ун-та, 2002.
2. Каймин В.А. Информатика: Учебник. - М.: ИНФРА-М,2000.
3. Сергеева И.И., Мазулевская А.А., Тарасова Н.В. Информатика: учебник. – М.: ИД «Форум»: ИНФРА – М, 2007.
В настоящее время в обыденной жизни для кодирования числовой информации используется десятичная система счисления с основанием 10, в которой используется 10 элементов обозначения: числа 0, 1, 2, … 8, 9. В первом (младшем) разряде указывается число единиц, во втором - десятков, в третьем - сотен и т.д.; иными словами, в каждом следующем разряде вес разрядного коэффициента увеличивается в 10 раз.
В цифровых устройствах обработки информации используется двоичная система счисления с основанием 2, в которой используется два элемента обозначения: 0 и 1. Веса разрядов слева направо от младших разрядов к старшим увеличиваются в 2 раза, то есть имеют такую последовательность: 8421. В общем виде эта последовательность имеет вид:
…2 5 2 4 2 3 2 2 2 1 2 0 ,2 -1 2 -2 2 -3 …
и используется для перевода двоичного числа в десятичное. Например, двоичное число 101011 эквивалентно десятичному числу 43:
2 5 ·1+2 4 ·0+2 3 ·1+2 2 ·0+2 1 ·1+2 0 ·1=43
В цифровых устройствах используются специальные термины для обозначения различных по объёму единиц информации: бит, байт, килобайт, мегабайт и т.д.
Бит или двоичный разряд определяет значение одного какого-либо знака в двоичном числе. Например, двоичное число 101 имеет три бита или три разряда. Крайний справа разряд, с наименьшим весом, называется младшим, а крайний слева, с наибольшим весом, - старшим .
Байт определяет 8-разрядную единицу информацию, 1 байт=23 бит, например, 10110011 или 01010111 и т.д., 1 кбайт = 2 10 байт, 1 Мбайт = 2 10 кбайт = 2 20 байт.
Для представления многоразрядных чисел в двоичной системе счисления требуется большое число двоичных разрядов. Запись облегчается, если использовать шестнадцатеричную систему счисления.
Основанием шестнадцатеричной системы счисления является число 16=2 4 , в которой используется 16 элементов обозначения: числа от 0 до 9 и буквы A, B, C, D, E, F. Для перевода двоичного числа в шестнадцатеричное достаточно двоичное число разделить на четырёхбитовые группы: целую часть справа налево, дробную - слева направо от запятой. Крайние группы могут быть неполными.
Каждая двоичная группа представляется соответствующим шестнадцатеричным символом (таблица 1). Например, двоичное число 0101110000111001 в шестнадцатеричной системе выражается числом 5C39.
Пользователю наиболее удобна десятичная система счисления. Поэтому многие цифровые устройства, работая с двоичными числами, осуществляют приём и выдачу пользователю десятичных чисел. При этом применяется двоично-десятичный код.
Двоично-десятичный код образуется заменой каждой десятичной цифры числа четырёхразрядным двоичным представлением этой цифры в двоичном коде (См. таблицу 1). Например, число 15 представляется как 00010101 BCD (Binary Coded Decimal). При этом в каждом байте располагаются две десятичные цифры. Заметим, что двоично-десятичный код при таком преобразовании не является двоичным числом, эквивалентным десятичному числу.
1.2 Логические основы ЭВМ
Раздел математической логики, изучающий связи между логическими переменными, имеющими только два значения, называется алгеброй логики. Алгебра логики разработана английским математиком Дж. Булем и часто называется булевой алгеброй. Алгебра логики является теоретической базой для построения систем цифровой обработки информации. Вначале на основе законов алгебры логики разрабатывается логическое уравнение устройства, которое позволяет соединить логические элементы таким образом, чтобы схема выполняла заданную логическую функцию.
Таблица 1 – Коды чисел от 0 до 15
| Десятичное число | Коды | ||
|---|---|---|---|
| Двоичный | 16-ричный | Двоично-десятичный | |
| 0 | 0000 | 0 | 000 |
| 1 | 0001 | 1 | 0001 |
| 2 | 0010 | 2 | 0010 |
| 3 | 0011 | 3 | 0011 |
| 4 | 0100 | 4 | 0100 |
| 5 | 0101 | 5 | 0101 |
| 6 | 0110 | 6 | 0110 |
| 7 | 0111 | 7 | 0111 |
| 8 | 1000 | 8 | 1000 |
| 9 | 1001 | 9 | 1001 |
| 10 | 1010 | A | 00010000 |
| 11 | 1011 | B | 00010001 |
| 12 | 1100 | C | 00010010 |
| 13 | 1101 | D | 00010011 |
| 14 | 1110 | E | 00010100 |
| 15 | 1111 | F | 00010101 |
1.2.1 Основные положения алгебры логики
Различные логические переменные могут быть связаны функциональными зависимостями. Функциональные зависимости между логическими переменными могут быть описаны логическими формулами или таблицами истинности.
В общем виде логическая формула функции двух переменных записывается в виде: y =f (X 1 , X 2), где X 1 , X 2 - входные переменные.
В таблице истинности отображаются все возможные сочетания (комбинации) входных переменных и соответствующие им значения функции y, получающиеся в результате выполнения какой-либо логической операции. При одной переменной полный набор состоит из четырёх функций, которые приведены в таблице 2.
Таблица 2 – Полный набор функций одной переменной
| X | Y1 | Y2 | Y3 | Y4 |
|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
Y1 - Инверсия, Y2 - Тождественная функция, Y3 - Абсолютно истинная функция и Y4 – Абсолютно ложная функция.
Инверсия (отрицание) является одной из основных логических функций, используемых в устройствах цифровой обработки информации.
При двух переменных полный набор состоит из 16 функций, однако в цифровых устройствах используются далеко не все.
Основными логическими функциями двух переменных, используемыми в устройствах цифровой обработки информации являются: дизъюнкция (логическое сложение), конъюнкция (логическое умножение), сумма по модулю 2 (неравнозначность), стрелка Пирса и штрих Шеффера. Условные обозначения логических операций, реализующих указанные выше логические функции одной и двух переменных, приведены в таблице 3.
Таблица 3 Названия и обозначения логических операций
Операцию инверсии можно выполнить чисто арифметически: 
и алгебраически: Из этих выражений следует, что инверсия x
, т.е. дополняет x
до 1. Отсюда и возникло ещё одно название этой операции - дополнение
. Отсюда же можно сделать вывод, что двойная инверсия приводит к исходному аргументу, т.е. и это называется законом двойного отрицания.
Таблица 4 – Таблицы истинности основных функций двух переменных
| Дизъюнкция | Конъюнкция | Исключающее ИЛИ | Стрелка Пирса | Штрих Шеффера | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| X1 | X2 | Y | X1 | X2 | Y | X1 | X2 | Y | X1 | X2 | Y | X1 | X2 | Y |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
Дизъюнкция. В отличие от обычного арифметического или алгебраического суммирования здесь наличие двух единиц даёт в результате единицу. Поэтому при обозначении логического суммирования предпочтение следует отдать знаку (∨) вместо знака (+) .
Первые две строчки таблицы истинности операции дизъюнкции (x 1 =0) определяют закон сложения с нулём : x ∨ 0 = x , а вторые две строчки (x 1 = 1) - закон сложения с единицей : x ∨ 1 = 1.
Конъюнкция. Таблица 4 убедительно показывает тождественность операций обычного и логическог умножений. Поэтому в качестве знака логического умножения возможно использование привычного знака обычного умножения в виде точки .
Первые две строчки таблицы истинности операции конъюнкции определяют закон умножения на ноль : x ·0 = 0, а вторые две - закон умножения на единицу: x ·1 = x.
Исключающее ИЛИ. Под функцией «Исключающее ИЛИ» понимают следующее: единица на выходе появляется тогда, когда только на одном входе присутствует единица. Если единиц на входах две или больше, или если на всех входах нули, то на выходе будет нуль.
Надпись на обозначении элемента ИСКЛЮЧАЮЩЕЕ ИЛИ «=1» (Рисунок 1, г) как раз и обозначает, что выделяется ситуация, когда на входах одна и только одна единица.
Эта операция аналогична операции арифметического суммирования, но, как и другие логические операции, без образования переноса. Поэтому она имеет другое название сумма по модулю 2 и обозначение ⊕, сходное с обозначением арифметического суммирования.
Стрелка Пирса и штрих Шеффера. Эти операции являются инверсиями операций дизъюнкции и конъюнкции и специального обозначения не имеют.
Рассмотренные логические функции являются простыми или элементарными, так как значение их истинности не зависит от истинности других каких либо функций, а зависит только от независимых переменных, называемых аргументами.
В цифровых вычислительных устройствах используются сложные логические функции, которые разрабатываются на основе элементарных функций.
Сложной является логическая функция, значение истинности которой зависит от истинности других функций. Эти функции являются аргументами данной сложной функции.
Например, в сложной логической функции 
аргументами являются X 1 ∨X 2 и .
1.2.2 Логические элементы
Для реализации логических функций в устройствах цифровой обработки информации используются логические элементы. Условные графические обозначения (УГО) логических элементов, реализующих рассмотренные выше функции, приведены на рисунке 1.
Рисунок 1 – УГО логических элементов: а) Инвертор, б) ИЛИ, в) И, г) Исключающее ИЛИ, д) ИЛИ-НЕ, е) И-НЕ.
Сложные логические функции реализуются на основе простых логических элементов, путём их соответствующего соединения для реализации конкретной аналитической функции. Функциональная схема логического устройства, реализующего сложную функцию, , приведённую в предыдущем параграфе, приведена на рисунке 2.
Рисунок 2 – Пример реализации сложной логической функции
Как видно из рисунка 2, логическое уравнение показывает, из каких ЛЭ и какими соединениями можно создать заданное логическое устройство.
Поскольку логическое уравнение и функциональная схема имеют однозначное соответствие, то целесообразно упростить логическую функцию, используя законы алгебры логики и, следовательно, сократить количество или изменить номенклатуру ЛЭ при её реализации.
1.2.3 Законы и тождества алгебры логики
Математический аппарат алгебры логики позволяет преобразовать логическое выражение, заменив его равносильным с целью упрощения, сокращения числа элементов или замены элементной базы.
1 Переместительный: X ∨ Y = Y ∨ X; X · Y = Y · X.
2 Cочетательный: X ∨ Y ∨ Z = (X ∨ Y) ∨ Z = X ∨(Y ∨ Z); X · Y · Z = (X · Y) · Z = X· (Y· Z).
3 Идемпотентности: X ∨ X = X; X · X = X.
4 Распределительный: (X ∨ Y)· Z = X· Z ∨ Y· Z.
5 Двойное отрицание: .
6 Закон двойственности (Правило де Моргана):
Для преобразования структурных формул применяется ряд тождеств:
X ∨ X · Y = X; X(X ∨ Y) = X - Правила поглощения.
X· Y ∨ X· = X, (X ∨ Y)·(X ∨ ) = X – Правила склеивания.
Правила старшинства логических операций.1 Отрицание - логическое действие первой ступени.
2 Конъюнкция - логическое действие второй ступени.
3 Дизъюнкция - логическое действие третьей ступени.
Если в логическом выражении встречаются действия различных ступеней, то сначала выполняются первой ступени, затем второй и только после этого третьей ступени. Всякое отклонение от этого порядка должно быть обозначено скобками.
Лекция 5. Арифметические и логические основы работы компьютера.
2.Правила создания блоксхем.
1. Алгоритмы и способы их описания.
Алгоритм - это точное предписание, которое определяет процесс, ведущий от исходных
данных к требуемому конечному результату.
Пример: правила сложения, умножения, решения алгебраических уравнений, умножения матриц и
т.п.
К сведению: Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией
арабского имени хорезмийского математика IX века альХорезми. Благодаря латинскому
переводу трактата альХорезми европейцы в XII веке познакомились с позиционной системой
счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система
счисления и правила счета в ней.
Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с обработки
некоторой совокупности возможных исходных данных и направленный на получение определенных
этими исходными данными результатов. Термин вычислительный процесс распространяется и на
обработку других видов информации, например, символьной, графической или звуковой.
Основные свойства алгоритмов:
1.Результативность означает возможность получения результата после выполнения
конечного количества операций.
2. Определенность состоит в совпадении получаемых результатов независимо от
пользователя и применяемых технических средств.
3. Массовость заключается в возможности применения алгоритма к целому классу
однотипных задач, различающихся конкретными значениями исходных данных.
4. Дискретность - возможность расчленения процесса вычислений, предписанных
алгоритмом, на отдельные этапы, возможность выделения участков программы с
определенной структурой.
Для задания алгоритма необходимо описать следующие его элементы:
набор объектов, составляющих совокупность возможных исходных данных,
промежуточных и конечных результатов;
правило начала;
правило непосредственной переработки информации (описание последовательности
действий);
правило окончания;
правило извлечения результатов.
Способы описания алгоритмов:
Словесно формульный;
структурный или блок схемный;
с помощью графов схем;
с помощью сетей Петри.
При словесноформульном способе алгоритм записывается в виде текста с формулами по
пунктам, определяющим последовательность действий.
Пример: необходимо найти значение следующего выражения: у = 2а – (х+6).
Словесноформульным способом алгоритм решения этой задачи может быть записан в
следующем виде:
1. Ввести значения а и х.
2. Сложить х и 6.
3. Умножить a на 2.
4. Вычесть из 2а сумму (х+6).
5. Вывести у как результат вычисления выражения.
При блок схемном описании алгоритм изображается геометрическими фигурами
(блоками), связанными по управлению линиями (направлениями потока) со стрелками. В
блоках записывается последовательность действий.
Преимущества:
1.наглядность: каждая операция вычислительного процесса изображается отдельной
геометрической фигурой.
2.графическое изображение алгоритма наглядно показывает разветвления путей решения
задачи в зависимости от различных условий, повторение отдельных этапов
вычислительного процесса и другие детали.
К сведению: Оформление программ должно соответствовать определенным требованиям. В
настоящее время действует единая система программной документации (ЕСПД), которая
устанавливает правила разработки, оформления программ и программной документации. В
ЕСПД определены и правила оформления блоксхем алгоритмов (ГОСТ 10.00280 ЕСПД, ГОСТ
10.00380 ЕСПД).
Операции обработки данных и носители информации изображаются на схеме
соответствующими блоками. Большая часть блоков по построению условно вписана в
прямоугольник со сторонами а и b. Минимальное значение а = 10 мм, увеличение а
производится на число, кратное 5 мм. Размер b=1,5a. Для от дельных блоков допускается
соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать
блоки одинаковых размеров. Все блоки нумеруются.
Виды блоков:
2.Правила создания блоксхем.
1.
Линии, соединяющие блоки и указывающие последовательность связей между ними,
2.
3.
4.
5.
6.
7.
должны проводится параллельно линиям рамки.
Стрелка в конце линии может не ставиться, если линия направлена слева направо или
сверху вниз.
В блок может входить несколько линий, то есть блок может являться преемником
любого числа блоков.
выходят две линии.
Из блока (кроме логического) может выходить только одна линия.
Логический блок может иметь в качестве продолжения один из двух блоков, и из него
Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В
случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не
ставить.
Схему алгоритма следует выполнять как единое целое, однако в случае
необходимости допускается обрывать линии, соединяющие блоки.
Структурные схемы алгоритмов:
Последовательность двух или более операций;
выбор направления;
повторение.
Любой вычислительный процесс может быть представлен как комбинация этих
элементарных алгоритмических структур.
Виды алгоритмов:
линейные;
ветвящиеся;
циклические.
В линейном алгоритме операции выполняются последовательно, в порядке их записи.
Каждая операция является самостоятельной, независимой от какихлибо условий. На схеме
блоки, отображающие эти операции, располагаются в линейной последовательности.
Линейные алгоритмы имеют место, например, при вычислении арифметических выражений,
когда имеются конкретные числовые данные и над ними выполняются соответствующие
условию задачи действия.
Пример линейного алгоритма:
Составить блок – схему алгоритма вычисления арифметического выражения
у=(b2ас):(а+с)
Алгоритм называется ветвящимся, если для его реализации предусмотрено несколько
направлений (ветвей). Каждое отдельное направление алгоритма обработки данных
является отдельной ветвью вычислений.
Ветвление в программе - это выбор одной из нескольких последовательностей команд при
выполнении программы. Выбор направления зависит от заранее определенного признака,
который может относиться к исходным данным, к
промежуточным или конечным результатам. Признак
характеризует свойство данных и имеет два или более
значений.
Ветвящийся процесс, включающий в себя две ветви,
называется простым, более двух ветвей - сложным.
Сложный ветвящийся процесс можно представить с помощью
простых ветвящихся процессов.
Направление ветвления выбирается логической проверкой, в
результате которой возможны два ответа:
1.«да» - условие выполнено
2.«нет» - условие не выполнено.
Следует иметь в виду, что, хотя на схеме алгоритма должны
быть показаны все возможные направления вычислений в
зависимости от выполнения определенного условия (или
условий), при однократном прохождении программы процесс реализуется только по одной
ветви, а остальные исключаются.
Важно! Любая ветвь, по которой осуществляются вычисления, должна приводить к
завершению вычислительного процесса.
Пример алгоритма с ветвлением:
Составить блоксхему алгоритма с ветвлением для вычисления следующего выражения:
Y = (а+b), если Х <0;
с/b, если Х>0.
Циклическими называются алгоритмы, содержащие циклы.
Цикл - это многократно повторяемый участок алгоритма.
Этапы организации цикла:
подготовка (инициализация) цикла (И);
выполнение вычислений цикла (тело цикла) (Т);
модификация параметров (М);
проверка условия окончания цикла (У).
Порядок выполнения этих этапов, например, Т и М, может изменяться.
Типы циклов:
В зависимости от расположения проверки условия окончания цикла различают циклы с
нижним и верхним окончаниями.
Для цикла с нижним окончанием (рис. а) тело цикла выполняется как минимум один раз, так
как сначала производятся вычисления, а затем проверяется условие выхода из цикла.
В случае цикла с верхним окончанием (рис. б) тело цикла может не выполниться ни разу в
случае, если сразу соблюдается условие выхода.
а б
Рис.Примеры циклических алгоритмов
Виды циклов:
Цикл называется детерминированным, если число повторений тела цикла заранее известно или
определено.
Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а
зависит от значений параметров (некоторых переменных), участвующих в вычислениях.
Пример циклического алгоритма:
Алгоритм нахождения суммы 10ти чисел
На ЭВМ могут решаться задачи различного характера, например:
научноинженерные; разработки системного программного обеспечения; обучения; управления
производственными процессами и т. д.
В процессе подготовки и решения на ЭВМ научно инженерных задач можно выделить следующие
этапы:
1.постановка задачи;
2.математическое описание задачи;
3.выбор и обоснование метода решения;
4.алгоритмизация вычислительного процесса;
5.составление программы;
6.отладка программы;
7.решение задачи на ЭВМ и анализ результатов.
В задачах другого класса некоторые этапы могут отсутствовать, например, в задачах разработки
системного программного обеспечения отсутствует математическое описание.
На данном этапе формулируется цель решения задачи и подробно описывается ее содержание.
Анализируются характер и сущность всех величин, используемых в задаче, и определяются
условия, при которых она решается.
Корректность постановки задачи является важным моментом, так как от нее в значительной
степени зависят другие этапы.
Настоящий этап характеризуется математической формализацией задачи, при которой
существующие соотношения между величинами, определяющими результат, выражаются
посредством математических формул.
Так формируется математическая модель явления с определенной точностью, допущениями и
ограничениями. При этом в зависимости от специфики решаемой задачи могут быть использованы
различные разделы математики и других дисциплин.
Математическая модель должна удовлетворять по крайней мере двум требованиям:
реалистичности и реализуемости. Под реалистичностью понимается правильное отражение
моделью наиболее существенных черт исследуемого явления.
Реализуемость достигается разумной абстракцией, отвлечением от второстепенных деталей,
чтобы свести задачу к проблеме с известным решением. Условием реализуемости является
возможность практического выполнения необходимых вычислений за отведенное время при
доступных затратах требуемых ресурсов.
Модель решения задачи с учетом ее особенностей должна быть доведена до решения при помощи
конкретных методов решения. Само по себе математическое описание задачи в большинстве
случаев трудно перевести на язык машины. Выбор и использование метода решения задачи
позволяет привести решение задачи к конкретным машинным операциям. При обосновании выбора
метода необходимо учитывать различные факторы и условия, в том числе точность вычислений,
время решения задачи на ЭВМ, требуемый объем памяти и другие.
Одну и ту же задачу можно решить различными методами, при этом в рамках каждого метода
можно составить различные алгоритмы.
На данном этапе составляется алгоритм решения задачи согласно действиям, задаваемым
выбранным методом решения. Процесс обработки данных разбивается на отдельные относительно
самостоятельные блоки, и устанавливается последовательность выполнения блоков.
Разрабатывается блоксхема алгоритма.
Контрольные вопросы:
1.Поясните понятие «алгоритм».
2.В чем состоит особенность описания алгоритмов с помощью структурной схемы и конструкций
алгоритмического языка?
3.Перечислите типовые алгоритмические конструкции и объясните их назначение.
4.Что такое исполнитель алгоритма? Что или кто может являться исполнителем алгоритма?
5.Поясните алгоритм работы исполнителя на примере роботаманипулятора или автомата
(например, автомата продажи газет).
Изучение систем счисления, арифметических и логических операций очень важно для понимания того, как происходит обработка данных в вычислительных машинах.
Любой компьютер может быть представлен как арифметическая машина, реализующая алгоритмы путем выполнения арифметических действий. Эти арифметические действия производятся над числами, представленными в принятой для них системе счисления, в заданных форматах и с использованием специальных машинных кодов.
Изучение различных систем счисления, которые используются в компьютерах, и арифметических операций в них очень важно для понимания того, каким образом производится обработка числовых данных в вычислительных машинах.
Системой счисления (СС) называется способ изображения чисел с помощью ограниченного набора символов, имеющих определенные количественные значения. Система счисления образует совокупность правил и приемов представления чисел с помощью набора знаков (цифр).
Все системы счисления можно разделить на два класса: позиционные и непозиционные. Для записи чисел в различных системах счисления используется некоторое количество отличных друг от друга знаков, называемых алфавитом системы счисления.
Системы счисления, в которых значение знака не зависит от того места, которое он занимает в числе, называются непозиционными. Наиболее известным примером непозиционной системы счисления является римская. В этой системе используется 7 знаков (I, V, X, L, С, D, М), которые соответствуют следующим величинам:
I(1) V(5) X(10) L(50) C(100) D(500) M(IOOO)
Примеры: III(три), LIХ(пятьдесят девять), DLV(пятьсот пятьдесят пять).
Недостатками непозиционных систем, из-за которых они представляют лишь исторический интерес, являются сложный способ записи чисел и громоздкие правила выполнения арифметических операций, хотя по традиции римскими числами часто пользуются при нумерации глав в книгах, веков в истории и т. п.
Во всех вычислительных машинах применяется позиционная система счисления. В позиционных СС каждая цифра числа имеет определенный вес, зависящий от позиции цифры в последовательности, изображающей число. Позиция цифры называется ее разрядом. Число знаков в позиционной системе счисления называется основанием системы счисления.
В позиционной системе счисления любое число можно представить в виде:
Основание системы счисления N показывает, во сколько раз “вес” i- го разряда больше (i – 1) разряда. Целая часть числа отделяется от дробной части точкой (запятой).
Пример 1. А 10 = 37,25. В соответствии с формулой (1) это число формируется из цифр с весами разрядов
Теоретически наиболее экономичной системой счисления является система счисления с основанием е = 2,71828…, находящимися между числами 2 и 3.
Во всех современных ЭВМ для представления числовой информации используется двоичная система счисления. Это обусловлено:
· более простой реализацией алгоритмов выполнения арифметических и логических операций;
· более надежной физической реализацией основных функций, так как они имеют всего два состояния (0 и 1);
· экономичностью аппаратурной реализации всех схем ЭВМ.
При N =2 число различных цифр, используемых для записи чисел, ограниченно множеством из двух цифр (нуль и единица). Кроме двоичной системы счисления широкое распространение получили и производные системы:
· двоичная - {0,1};
· десятичная, точнее двоично-десятичное представление десятичных чисел, - {0,1,2,…,9};
· шестнадцатеричная - {0,1,…,9,A,B,C,D,E,F}. Здесь шестнадцатеричная цифра А обозначает число 10, В – число 11,…, F – число 15;
· восьмеричная (от слова «восьмерик») - {0,1,2,3,4,5,6,7}. Она широко используется для специализированных ЭВМ.
Таблица 1 – Представление чисел в различных системах счисления
Для автоматизации работы с данными, которые относятся к разным типам, унифицируют их форму представления. Это можно сделать с помощью кодирования данных на единой основе. В быту используют такие системы кодировки, как азбука Морзе, Брайля, коды морских сигналов. Основное понятие арифметики это число.Число– абстрактное выражение количества. Компьютер обрабатывает информацию, представленную только в числовой форме. Он оперирует с кодами и числами, представленными в некоторойсистеме счисления.
Система счисления– способ представления чисел(правило записи и получения чисел), с помощью фиксированного набора символов, обозначающих цифры. По способу представления чисел системы счисления разделяются на позиционные и непозиционные.
Непозиционныесистемы для записи числа используют множество символов. Значение символа не зависит от местоположения его в числе(римская СС).
Позиционная система счисления– когда от позиции цифры в числе зависит ее вес(555 –единицы, десятки, сотни). Всякая позиционная СС характеризуетсяоснованием,т.е. количеством цифр, используемых для записи числа. За основание СС можно принять любое натуральное число.
10ая– использует 10 цифр → 0, 1… 9
2ая– 2 цифры → 0, 1
Люди предпочитают 10ую(это удобно, видимо потому, что с древних времен считали по пальцам).
В вычислительной технике система кодирования основана на представлении данных в двоичной системе счисления. Компьютеры используют 2уюсистему, т.к. имеется ряд преимуществ:
Для ее реализации нужны устройства всего с двумя устойчивыми состояниями (есть ток, нет тока). Это надежнее, чем, например, 10ая;
возможно применение аппарата булевой алгебры;
двоичная арифметика проще десятичной;
представление информации с помощью 2-х состояний более надежно.
Недостаток: - быстрый рост разрядов.
В компьютере используются также 8аяи 16аясистемы.
Перевод чисел из 10ойв 2уюи наоборот выполняет машина.
При вводе информация кодируется, при выводе декодируется.
Обозначение цифр в 2ой системе:0, 1, 10, 11(3), 100(4), 101(5), 110(6), 111(7), 1000(8), 1001(9), 1010(10)и т.д.
Обозначение цифр в 8-ой системе: 0, 1, 2 … 7, 10(8), 11(9), 12(10)……17(15), 20(16), 21(17)и т.д.
Обозначение цифр в 16ой системе: 0, 1, 2 … 9, A(10), B(11),C(12) ... F(15), 10(16), 11(17) и т. д.
Целое число в позиционной СС может быть представлено в виде:
Aq=an-1qn-1+an-2qn-2+…+a0q0 , где
A– само число;
q– основание системы счисления;
ai– цифры, принадлежащие алфавиту данной системы счисления;
n– число целых разрядов числа.
Пусть в десятичной системе задано число37510.
Каждая позиция, занимаемая цифрами, называется разрядом числа.Разряды имеют названия иномера:разряд единиц (0), разряд десятков (1), разряд сотен (2). Названия определяютвес (012). Число в позиционной системе счисления представляет собой сумму степеней основания, умноженную на соответствующий коэффициент, который должен быть одной из цифр данной системы счисления. Достаточно просуммировать веса единичных разрядов.
37510=5*100+7*101+3*102 = 5+70+300=375
Это называется разложением числа по степеням основания.
Номера разрядов совпадают с показателем степени.
1011012=1*20+0*21+1*22+1*23+0*24+1*25=1+0+4+8+0+32=4510
101102=0*20+1*21+1*22+0*23+1*24=0+2+4+0+16=2210
1000012=1*20+0*21+0*22+0*23+0*24+1*25=1+32=3310
178=1*81+7*80= 8+1=1510
77648= 7*83+7*82+6*81+4*80 = 3584+448+48+4 =408410
1716= 1*161+7*160= 16+7 = 2310
3AF16=3*162+10*161+15*160=768+160+15=94310
1A16= 1*161+10*160= 16+10 = 2610
От того, какая система счисления будет использована в компьютере, зависят: скорость вычислений, емкость памяти, сложность алгоритмов выполнения арифметических и логических операций
Алгоритм перевода чисел делением на основание системы счисления: исходное число делим на основание новой СС. Затем получившееся частное опять делим на основание и т. д. , до тех пор, пока частное не станет меньше основания СС. Последнее частное и остатки записываем в порядке, обратном получению