Вычисление машинного порядка

Вопросы к экзамену по дисциплине

«Основы алгоритмизации и программирования»

Триместр

1. Алгоритм. Неформальное определение. Свойства алгоритма.

 

АЛГОРИТМ – точное предписание, которое задает вычислительный процесс, начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным данным результата.

 

АЛГОРИТМ – это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент времени задается исходная система величин, а в каждый следующий момент система величин получается по определенному закону из системы величин, имевшейся в предыдущий момент времени.

 

1. Понятность - Алгоритм должен быть записан на языке, понятном исполнителю.
2. Дискретность - Алгоритм состоит из конечного числа инструкций и все инструкции выполняются в дискретном времени.
3. Элементарность шагов - Объем работы, выполняемый на всяком шаге ограничен сверху некоторой константой, не зависящей от объема данных.
4. Детерминированность (определенность, точность) - Для каждого шага по набору исходных данных результат выполнения шага определяется однозначно и не зависит ни от каких случайных факторов.
5. Конечность (финитность) - Выполнение алгоритма должно завершиться за конечное число шагов.
6. Массовость - Алгоритм должен быть применим к разным наборам допустимых исходных данных.

 

2. Системы счисления. Внутреннее машинное представление целых чисел. Примеры из С++, связанные с внутренним машинным представлением целых чисел.

 

Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков.

 

Позиционные системы счисления — это системы счисления, в которых значение цифры напрямую зависит от её положения в числе. Количество цифр, используемых в системе счисления, называется её «основанием».

 

В непозиционных системах счисления величина числа не зависит от положения цифр в записи. Если к каждой цифре приписать знак номинала, то такие составные знаки (цифра + номинал) уже можно перемешивать, то есть такая запись является непозиционной.

 

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

Множество целых чисел, представимых в памяти ЭВМ ограничено и зависит от размера ячеек памяти (машинного слова), используемых для их хранения. В k-разрядной ячейке может храниться 2^k (655636) различных значений целых чисел.

 

Чтобы записать внутреннее машинное представление целого числа со знаком, необходимо найти его дополнительный код.

 

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

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

1. Перевести число N в двоичную систему счисления.

2. Полученный результат дополнить слева незначащими нулями до k разрядов.

3. При необходимости перевести число в сжатую шестнадцатеричную форму.

 

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

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

Алгоритм получения внутреннего представления целого отрицательного числа N, хранящегося в k-разрядном машинном слове:

1. Получить внутреннее представление положительного числа N.

2. Получить обратный код этого числа заменой 0 на 1 и 1 на 0, т.е значения всех бит инвертировать.

3. К полученному числу прибавить 1 (получить дополнительный код).

4. При необходимости записать сжатое внутренне машинное представление.

 

3. Внутреннее машинное представление вещественных чисел.

 

Вещественные числа в памяти компьютера представляются в формате с плавающей десятичной запятой (экспоненциальной форме).

 

Так как вариантов представления одного и того же числа в экспоненциальной форме бесконечное множество, то для внутреннего машинного представления условились представлять числа в нормализованной или денормализованной форме.

В денормализованной форме мантисса должна отвечать следующему условию: она должна быть правильной дробью и иметь после запятой цифру, отличную от нуля, то есть 1/n ≤ |m| < 1

 

Нормализованная мантисса содержит свой старший бит слева от точки. В общем случае мантисса должна удовлетворять условию 1<=|m|<10. Так как числа представлены в двоичном виде, то этот бит всегда равен 1. Иными словами нормализованная мантисса принадлежит интервалу 1 <= |m| < 2. В памяти машины этот бит не хранится, т.е. является "скрытым”.

Для положительных и отрицательных чисел мантисса в памяти представлена в прямом коде.

 

Вычисление машинного порядка

Для хранения вещественных чисел в памяти компьютера выделяются следующие разряды:

- знак числа (старший бит),

- машинный порядок числа

- мантисса.

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

Связь между машинным порядком (М_р) и математическим (р) в рассматриваемом случае выражается формулой: М_р = (2^n-1-1) + p, где n – это количество бит, отводимых на порядок.

 

4. Понятие языка программирования. Виды языков программирования.

Понятие транслятора. Виды трансляторов. Этапы создания исполняемой программы на языке С++.

 

ПРОГРАММА – это алгоритм, записанный на определенном языке программирования.

 

ЯЗЫК ПРОГРАММИРОВАНИЯ – это формальная знаковая система, предназначенная для записи компьютерных программ.

 

Аппаратная платформа.

Машинные коды

Языки низкого уровня (Ассемблер)

Языки высокого уровня

 

ТРАНСЛЯТОР – это программа, которая переводит программу с языка высокого уровня на язык машинных команд.

По способу трансляции различают:

- компиляторы;

- интерпретаторы.

 

5. Лексика, синтаксис, семантика и прагматика языка программирования. Состав языка программирования на примере С++.

 

Описание ЛЕКСИКИ – задание алфавита языка.

Описание СИНТАКСИСА – задание правил построения конструкций ЯП.

Описание СЕМАНТИКИ – придание смысла конструкциям языка.

Описание ПРАГМАТИКИ – отвечает на вопрос: «Как писать программы на этом языке?»

 

Состав языка программирования:

1. Символы языка — это основные неделимые знаки, в терминах которых пишутся все тексты на языке.
2. Элементарные конструкции — это минимальные единицы языка, имеющие самостоятельный смысл. Они образуются из основных символов языка.
3. Выражение в языке программирования состоит из элементарных конструкций и символов, оно задает правило вычисления некоторого значения.
4. Оператор задает полное описание некоторого действия, которое необходимо выполнить. Для описания сложного действия может потребоваться группа операторов. В этом случае операторы объединяются в составной оператор, или блок.
5. Действия, заданные операторами, выполняются над данными. Предложения языка программирования, в которых даются сведения о типах данных, называются описаниями или неисполняемыми операторами.
6. Объединенная единым алгоритмом совокупность описаний и операторов образует программу на языке программирования.

 

 

6. Способы описания языка программирования: БНФ и диаграммы Вирта. Основные алгоритмические конструкции С++ в нотации БНФ и диаграмм Вирта.

 

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

1. Формы Бэкуса – Наура

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

1. Символ «::=» отделяет левую часть правила от правой (читается: «определяется как»);
2. Нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки «<» и «>»;

терминалы - это символы, используемые в описываемом языке

1. Правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или»).

Для повышения удобства и компактности описаний, в расширенных БНФ вводятся следующие дополнительные конструкции (метасимволы):

1. квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;
2. фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;
3. сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;
4. круглые скобки «(» и «)» используются для ограничения альтернативных конструкций;
5. кавычки используются в тех случаях, когда один из метасимволов нужно включить в цепочку обычным образом.

Пример:

<двоичная цифра>::= 0 | 1 <двоичный код>::= <двоичная цифра>{<двоичная цифра>} <условный оператор>::= if (<условие>) <оператор> [ else <оператор> ]

1. Диаграммы Вирта

В метаязыке диаграмм Вирта используются графические примитивы:

При построении диаграмм учитывают следующие правила:

1. Каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно изображаются на противоположных сторонах;
2. Каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;
3. Альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;
4. Должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа или снизу);
5. Стрелки на дугах диаграмм обычно не ставятся, а направления связей отслеживаются движением от начальной дуги в соответствии с плавными изгибами промежуточных дуг и ветвлений.

7. Алфавит языка. Лексемы языка С++. Понятие идентификатора. Ключевые слова С++. Константы. Их виды в С++. Примеры.

 

Алфавит языка:

1. Прописные и строчные латинские буквы, знак подчеркивания;
2. Арабские цифры от 0 до 9;
3. Специальные знаки:

“ { } , | [ ] ( ) + - / % * . \ ‘ : ? < = > ! & # ~ ; ^

1. Пробельные символы: пробел, символы табуляции, символы перехода на новую строку.

Лексемы языка С++:

1. идентификаторы;
2. ключевые (зарезервированные) слова;
3. знаки операций;
4. константы;
5. разделители (скобки, точка, запятая, пробельные символы)

Идентификатор:

ИДЕНТИФИКАТОР – это имя программного объекта.

Свойства идентификаторов:

1. При записи идентификатора допустимы: латинские буквы, цифры, знак подчёркивания «_»
2. Первым символом идентификатора цифра быть не может.
3. Идентификатор не может совпадать с зарезервированным словом.

Ключевые слова:

Ключевые слова — это предварительно определенные зарезервированные идентификаторы, имеющие специальные значения для компилятора. Их нельзя использовать в программе в качестве идентификаторов, если только они не содержат префикс @. Например, @if является допустимым идентификатором, но if таковым не является, поскольку if — это ключевое слово.

 

КОНСТАНТА – способ адресации данных, изменение которых рассматриваемой программой не предполагается или запрещается.

ВИДЫ КОНСТАНТ В С++:

1. Неименованные константы (цифры и числа, символы и строки, множества);

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

§ любая последовательность цифр (возможно, предваряемая знаком "-" или "+" или разбиваемая одной точкой) воспринимается компилятором как неименованная константа - число (целое или вещественное);

§ любая последовательность символов, заключенная в апострофы, воспринимается как неименованная константа - строка;

§ любая последовательность целых чисел, либо символов через запятую, обрамленная квадратными скобками, воспринимается как неименованная константа - множество.

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

a = -10;

b = 12.075 + х;

c = 'z';

d = "abc" + string44;

1. Именованные константы

Именованные константы, как следует из их названия, должны иметь имя. Стало быть, эти имена необходимо сообщить компилятору, то есть описать в специальном разделе const.

Если не указывать тип константы, то по ее внешнему виду компилятор сам определит, к какому (базовому) типу ее отнести. Любую уже описанную константу можно использовать при объявлении других констант, переменных и типов данных.

Вот несколько примеров описания нетипизированных именованных констант:

const int speedLimit = 55;

const double pi = 3.14;

 

8. Переменные. Описание переменных. Инициализация переменных. Основные типы данных С++.

 

ПЕРЕМЕННАЯ — это «ячейка» оперативной памяти компьютера, в которой может храниться какая-либо информация.

ОПИСАНИЕ ПЕРЕМЕННЫХ:

[класс памяти] [const] тип имя

ИНИЦИАЛИЗАЦИЯ ПЕРЕМЕННЫХ:

[класс памяти] [const] [тип] имя инициализатор

short x,t;

int y=0; int y(0);

bool flag=true;

const float pi=3.1415926;

double z(2.17),r(.5),p(1E7);

char ch, a='0',s(67);

 

1. int – целый
2. char – символьный
3. wchar_t – расширенный символьный
4. bool – логический
5. float – вещественный
6. double – вещественный двойной точности

 

 

9. Ввод-вывод данных. Функции scanf, printf. Спецификации преобразования.

Стандартная библиотека C/C++ включает ряд функций для чтения и записи на консоли (клавиатура и монитор). Эти функции читают и пишут данные как простой поток символов.

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

· Функция printf() имеет прототип в файле stdio.h:
int printf(char *управляющая строка, ...);

· В случае успеха функция printf() возвращает число выведенных символов.

Управляющая строка содержит два типа информации: символы, которые непосредственно выводятся на экран, и спецификаторы формата, определяющие, как выводить аргументы.

Функция printf() это функция форматированного вывода. Это означает, что в параметрах функции необходимо указать формат данных, которые будут выводиться. Формат данных указывается спецификаторами формата. Спецификатор формата начинается с символа % за которым следует код формата.

Кроме того, к командам формата могут быть применены модификаторы l и h.

В спецификаторе формата, после символа % может быть указана точность (число цифр после запятой). Точность задаётся следующим образом: %.n<код формата>. Где n - число цифр после запятой, а <код формата> - один из кодов приведённых выше.

Функция scanf () - функция форматированного ввода. С её помощью можно вводить данные со стандартного устройства ввода (клавиатуры). Вводимыми данными могут быть целые числа, числа с плавающей запятой, символы, строки и указатели.

· Функция scanf () имеет следующий прототип в файле stdio . h:

int scanf(char *управляющая строка);

· Функция возвращает число переменных, которым было присвоено значение.

Управляющая строка содержит три вида символов: спецификаторы формата, пробелы и другие символы. Спецификаторы формата начинаются с символа %.

· Для ввода данных с помощью функции scanf () ей в качестве параметров нужно передавать адреса переменных, а не сами переменные.

Чтобы получить адрес переменной, нужно поставить перед именем переменной знак &(амперсанд). Знак & означает взятие адреса.

 

10. Ввод-вывод данных. Стандартные потоки ввода и вывода. Манипуляторы.

 

Частью стандартной библиотеки C++ является библиотека iostream. В ней реализована поддержка для файлового ввода/вывода данных встроенных типов. Для использования библиотеки iostream в программе необходимо включить заголовочный файл:

#include <iostream>

Операции ввода/вывода выполняются с помощью классов istream (потоковый ввод) и ostream (потоковый вывод). Третий класс, iostream, является производным от них и поддерживает двунаправленный ввод/вывод. Для удобства в библиотеке определены три стандартных объекта-потока:

• cin – объект класса istream, соответствующий стандартному вводу. В общем случае он позволяет читать данные с терминала пользователя;
• cout – объект класса ostream, соответствующий стандартному выводу. В общем случае он позволяет выводить данные на терминал пользователя;
• cerr – объект класса ostream, соответствующий стандартному выводу для ошибок. В этот поток мы направляем сообщения об ошибках программы.

Вывод осуществляется, как правило, с помощью перегруженного оператора сдвига влево (<<), а ввод – с помощью оператора сдвига вправо (>>).

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

• ifstream, производный от istream, связывает ввод программы с файлом;
• ofstream, производный от ostream, связывает вывод программы с файлом;
• fstream, производный от iostream, связывает как ввод, так и вывод программы с файлом.

Чтобы использовать часть библиотеки iostream, связанную с файловым вводом/выводом, необходимо включить в программу заголовочный файл:

#include <fstream>

Один из способов форматирования текста — форматирование с помощью манипуляторов

МАНИПУЛЯТОР — объект особого типа, который управляет потоками ввода/вывода, для форматирования передаваемой в потоки информации.

Примеры манипуляторов: endl (переход на новую строку при выводе), fixed (вывод чисел с плавающей точкой в фиксированной форме), setprecision (задаёт количество знаков после запятой).

 

11. Операции С++. Группы операций. Приоритет выполнения операций. Правила выполнения операций одинакового приоритета.

 

ПРИОРИТЕТ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ:

n Унарные операции (++, --, ~, !, -, +, &, * – разадресация, new, delete…)

n Бинарные и тернарная операции

n Арифметические операции (*, /, %, +, -)

n Операции сравнения (>, <, >=…)

n Побитовые операции (&, ^, |)

n Логические операции (&&, ||)

n Условная операция (?)

n Операции присваивания (=, +=, /=…)

n Последовательное вычисление (int a = 3, b = a + 4, c = a + b)

В большинстве своём приоритет выполнения операций происходит слева направо. Однако, сперва компилятор обращает внимание на скобки, затем – на * и /, && и ||…, а лишь потом на +, - и др.

Справа налево выполняются унарные и тернарная операции, а также операции присваивания. 

 

12. Унарные операции. Примеры. Операции присваивания. Операция последовательного вычисления. Порядок выполнения.

 

Унарные операции — это операции, содержащие единственный операнд

Знаки операций обеспечивают формирование выражений.  

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

&	Получение адреса операнда
*	Обращение по адресу (разыменование)
-	Унарный минус, меняет знак арифметического операнда
~	Поразрядное инвертирование внутреннего двоичного кода целочисленного операнда (побитовое отрицание)
!	Логическое отрицание (НЕ). В качестве логических значений используется 0 - ложь и не 0 - истина, отрицанием 0 будет 1, отрицанием любого ненулевого числа будет 0.
++	Увеличение на единицу: префиксная операция - увеличивает операнд до его использования, постфиксная операция увеличивает операнд после его использования.  int m=1,n=2;  int a=(m++)+n; // a=4,m=2,n=2  int b=m+(++n); //a=3,m=1,n=3
- -	Уменьшение на единицу: префиксная операция - уменьшает операнд до его использования, постфиксная операция уменьшает операнд после его использования.
sizeof	Вычисление размера (в байтах) для объекта того типа, который имеет операнд имеет две формы ---sizeof выражение и sizeof (тип) Примеры: sizeof(float)//4 sizeof(1.0)//8, т. к. вещественные константы по умолчанию имеют тип double

 

13. Арифметические операции. Операции сравнения. Примеры. Порядок выполнения.