Представление целых чисел в дополнительном коде

Другой способ представления целых чисел — дополнительный код. Диапазон значений величин зависит от количества бит памяти, отведенных для их хранения. Например, величины типа Integer (все названия типов данных здесь и ниже представлены в том виде, в каком они приняты в языке программирования Turbo Pascal. В других языках такие типы данных тоже есть, но могут иметь другие названия) лежат в диапазоне от -32768 (-2¹⁵) до 32767 (2¹⁵ - 1) и для их хранения отводится 2 байта (16 бит); типа LongInt — в диапазоне от -2³¹ до 2³¹ - 1 и размещаются в 4 байтах (32 бита); типа Word — в диапазоне от 0 до 65535 (2¹⁶ - 1) (используется 2 байта) и т.д.

Как видно из примеров, данные могут быть интерпретированы как числа со знаком, так и без знака. В случае представления величины со знаком самый левый (старший) разряд указывает на положительное число, если содержит нуль, и на отрицательное, если — единицу.

Дополнительный код положительного числа совпадает с его прямым кодом. Прямой код целого числа может быть получен следующим образом: число переводится в двоичную систему счисления, а затем его двоичную запись слева дополняют таким количеством незначащих нулей, сколько требует тип данных, к которому принадлежит число.

Например, если число 37₍₁₀₎ = 100101₍₂₎ объявлено величиной типа Integer (шестнадцатибитовое со знаком), то его прямым кодом будет 0000000000100101, а если величиной типа LongInt (тридцатидвухбитовое со знаком), то его прямой код будет 00000000000000000000000000100101. Для более компактной записи чаще используют шестнадцатеричное представление кода. Полученные коды можно переписать соответственно как 0025₍₁₆₎ и 00000025₍₁₆₎.

Дополнительный код целого отрицательного числа может быть получен по следующему алгоритму:

записать прямой код модуля числа;

инвертировать его (заменить единицы нулями, нули — единицами);

прибавить к инверсному коду единицу.

Например, запишем дополнительный код числа -37, интерпретируя его как величину типа LongInt (тридцатидвухбитовое со знаком):

прямой код числа 37 есть 00000000000000000000000000100101;

инверсный код 11111111111111111111111111011010;

дополнительный код 11111111111111111111111111011011 или FFFFFFDB₍₁₆₎.

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

вычесть из кода числа 1;

инвертировать код;

перевести в десятичную систему счисления. Полученное число записать со знаком минус.

Примеры. Запишем числа, соответствующие дополнительным кодам:

0000000000010111. Поскольку в старшем разряде записан нуль, то результат будет положительным. Это код числа 23.

1111111111000000. Здесь записан код отрицательного числа. Исполняем алгоритм: 1) 1111111111000000₍₂₎ - 1₍₂₎ = 1111111110111111₍₂₎; 2) 0000000001000000; 3) 1000000₍₂₎ = 64₍₁₀₎.
Ответ: -64.

1+8)фон нейман

А рхитектура фон Неймана — широко известный принцип совместного хранения программ и данных в памяти компьютера. Вычислительные системы такого рода часто обозначают термином «Машина фон Неймана», однако, соответствие этих понятий не всегда однозначно. В общем случае, когда говорят об архитектуре фон Неймана (нем. von Neumann), подразумевают физическое отделение процессорного модуля от устройств хранения программ и данных.

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

АЛГОРИТМЫ И МАШИНА ТЬЮРИНГА
Понятие «алгоритм» берет свое начало из работы персидского математика IX в. Абу Джафара Муххамеда ибн Мусы аль-Хорезми. Современное написание слова «алгоритм», пришедшее на смену более раннему «алгорифм», своим происхождением обязано, скорее всего, слову «арифметика». От происхождения понятия «алгоритм» следуют и его главное свойство — дискретность.
Примеры применения алгоритмов были известны задолго до появления книги аль-Хорезми. Один из них — процедура нахождения наибольшего общего делителя двух чисел — восходит к работам Евклида (III в. до н. э.). Алгоритм Евклида является систематической процедурой, которая содержит в себе: 1) исходные данные (два известных числа), 2) математическую инструкцию и 3) результат — число НОД.
Алгоритм Евклида — одна из огромного множества вычислительных процедур, встречающихся в дискретной математике, но, несмотря на это, логического определения понятия «алгоритм» не существует. В XX в. начались интенсивные поиски описания (объяснения) этого понятия и первыми это удалось сделать Алану Тьюрингу и Эмилю Посту (1937).

Тьюринг рассматривал проблему алгоритмической разрешимости, поставленную в начале ХХ в. Д. Гильбертом, которая заключается в отыскании такой универсальной вычислительной процедуры, которая была бы применима для решения некоторого широкого класса математических задач. Эта проблема не зависела от аксиоматического построения математики и формулировалась Тьюрингом примерно так: существует ли некая универсальная механическая процедура, позволяющая, в принципе, решить все математические задачи (из некоторого определенного класса задач) последовательно одну за другой? Обратим внимание на термин, впервые введенный Тьюрингом, а именно: механическая процедура.

Каким могло быть такое устройство? Оно должно принимать множество дискретных состояний, число которых должно быть потенциально бесконечно. Дискретные состояния устройства Тьюринг назвал внутренними состояниями. Несмотря на конечность числа внутренних состояний, механическое устройство Тьюринга приспособлено для работы с входными, промежуточными и выходными данными неограниченного объема. Более того, устройство может иметь и накопитель внешней памяти неограниченного объема («черновики» для хранения промежуточных результатов), а также иметь возможность выдавать окончательное решение, состоящее из символов (например, цифр) любого, но только конечного числа.
Тьюринг представлял внешние данные и объем для хранения информации в виде «ленты» с последовательно выделенными на ней ячейками. Машина по мере необходимости могла обращаться к этой «ленте», считывать с нее данные (информацию) и перемещать ее вперед или назад в ходе выполнения операций по заданной и заложенной в ее внутреннюю память программе. Помимо этого, устройство могло вносить новые данные на ленту и стирать с нее старые, что позволяло использовать одну и ту же ленту и как внешнюю память, и как источник данных.

Лента движется через считывающее и стирающее устройство («головку») туда-сюда до тех пор, пока выполняются вычисления. Когда, наконец, вычисления закончены, «головка» останавливается, а результат вычислений отображается на части все той же ленты, лежащей по одну сторону от устройства. Т. о., МТ в принципе способна выполнить любой алгоритм, но данный алгоритм для нее должен составить кто-то внешний, не принадлежащий к этому вычислительному устройству. Назовем его программистом.

Поскольку лента разбита на совершенно одинаковые ячейки, которые моделируют собою единичную систему счисления, то возникает задача эффективного размещения в них необходимых данных. Для этого принята двоичная система счисления: пустая ячейка (отсутствие данного) обозначается символом «0», а помеченная (наличие информации) — символом «1». При этом не утрачивается общность рассуждения по считыванию любого количества информации: «головка», которая считывает n ячеек, перемещаясь при этом на k внутренних состояний, моделирует какой-либо «текст», состоящий из комбинаций символов «0» и «1». Чтобы явно определить операции, совершаемые «головкой», их можно пронумеровать порядковой последовательностью натуральных чисел: 1, 2, 3, 4, …, n. Тогда действия МТ полностью определятся программой, которая представляет собою список из из замен одних символов другими.

Расширением этой идеи является понятие универсальной машины, которое состоит в том, чтобы не просто соединить в одну несколько машин, а в том, чтобы можно было закодировать команды для произвольной машины Т в виде последовательностей нулей и единиц, которую может записать на своей ленте одна из машин. Эта запись используется как начальная часть входных данных для некоторой особой машины U, которая затем обрабатывает остальную часть ленты в точности так, как это сделала бы машина Т. Универсальная машина Тьюринга — это машина-имитатор, так как начальная часть ленты дает универсальной машине U всю необходимую информацию для повторения исходной машины Т.

Вопросы для проведения 1 рубежного контроля

Информатика как единство науки и технологии

Цели и задачи курса «Информатика»

Структура современной информатики

Информация, ее виды и свойства

Уровни представлений об информации

Носители данных. Операции с данными

Функции, отношения, множества

Булева алгебра и логические схемы компьютера. Логические машины.

Основы логики: логика высказываний, логические языки, таблица истинности

Графы и деревья

Обзор и история архитектуры компьютеров

Логические элементы компьютера (вентили, триггеры, счетчики, регистры)

Представление данных в памяти ПК

Представление числовых данных

Системы счисления. Правила перевода чисел из одной системы счисления в другую

Знаковые представления и представления в дополнительном коде

Представление нечисловых данных

Организация машины (принципы Фон-Неймана, управляющее устройство, системы команд и типы команд)

Ввод/вывод и прерывания. Устройство ввода и вывода

Устройство памяти компьютера

Иерархия памяти

Организация основной памяти и операции

Виртуальная память

Обзор современного программного обеспечения

Стратегия решения задач

Алгоритмы и поиск решений

Концепции и свойства алгоритмов

Структура данных (типы, массивы, строки)

Стратегии реализации алгоритмов

Блок-схема. Виды блок-схем

Способы представления алгоритмов

Алгоритмические структуры

Основные вычислительные алгоритмы: конечные автоматы, машина тьюринга, легко и трудно разрешаемые задачи

Анализ алгоритмов

Архитектура организации процессора

Организация системы адресации и команд

Фон-Неймановская структурная схема ЭВМ

Основные поняти курса «Информатика»

Основы дискретной математики

Этапы решения задач на ЭВМ