Языки программирования

1. История развития средств вычислительной техники Этапы развития

— Ранний (домеханический) (до 1642 г.)

— Механический (1642 — середина 19 века)

1642 — машина Блеза Паскаля, первая попытка механизировать вычисления

1654 — логарифмическая линейка, первое устройство, сделавшее вычисления быстрыми

1801 — появление перфокарт

1820-е годы — арифмометр Томаса, первое механическое вычислительное устройство

1822−1838 — Разностная машина Чарльза Бэббиджа, первая попытка создать программируемое вычислительное устройство

— Электромеханический (середина 19 века — 2000 г.)

1888 — Первая счетная машина, использующая электрическое реле

1906 — Г. Бэббидж построил действующую модель аналитической машины 1940;1948 — разработка теории информации Клода Шеннона

1938 г. создание Z1 — компьютера c механическими модулями памяти середина 1940;х — разработка архитектуры фон Неймана

1946 г. — создание первой универсальной цифровой вычислительной машины ЭНИАК

1947 г. — создание точечного транзисторного усилителя

1958 г — создание первой электронной микросхемы

1954 — первый язык программирования высокого уровня — Fortran

1963 г — первая компьютерная мышь

1966 г. — основание компании Intel

1969 — создание прообраза интернета (APARnet)

1975, 1976 — создание Microsoft и Apple

— Электронный (2000 г. — …)

2. Принцип программного управления Это один из принципов фон Неймана. Все вычисления, предусмотренные алгоритмом решения задачи, должны быть представлены в виде программы, состоящей из последовательности управляющих слов — команд. Каждая команда предписывает некоторую операцию из набора операций, реализуемых вычислительной машиной. Команды программы хранятся в последовательных ячейках памяти вычислительной машины и выполняются в естественной последовательности, то есть в порядке их положения в программе. При необходимости, с помощью специальных команд, эта последовательность может быть изменена.

3, 4, 5. Машина Тьюринга. Понятие, свойства. Детерминированная машина Тьюринга. Недетерминированная машина Тьюринга Машина Тьюринга (МТ) — математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением модели конечного автомата и способна имитировать любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

Свойства машины Тьюринга как алгоритма:

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

Понятность. На каждом шаге в ячейку пишется символ из алфавита, автомат делает одно движение (Л, П, Н), и машина Тьюринга переходит в одно из описанных состояний.

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

Результативность. Правильно написанная машина Тьюринга за конечное число шагов даст окончательный ответ на вопрос задачи.

Массовость. Каждая машина Тьюринга определена над всеми допустимыми символами из алфавита.

Детерминированная машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три вещи: символ, который будет записан на ленте, направление смещения головки по ленте и новое состояние конечного автомата. Например, X на ленте в состоянии 3 однозначно определяет переход в состояние 4, запись на ленту символа Y и перемещение головки на одну позицию влево.

В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов. Например, X на ленте и состояние 3 допускает как состояние 4 с записью на ленту символа Y и смещением головки вправо, так и состояние 5 с записью на ленту символа Z и смещением головки влево.

6. История развития ПК В 1969 году компания Honeywell выпускает «Кухонный Компьютер» H316 — первый домашний компьютер (стоимость 10 600 $).

В 1974 году фирма MITS начало производство компьютера Altair 8800, который, как считается, положил начало всем любительским персональным компьютерам.

В 1976 году начался кустарный выпуск Apple I — компьютера, который послужил предтечей развития одного из современных производителей персональных компьютеров, Apple Computer.

В июне 1977 года первый серийно выпускавшийся Apple II предложил пользователям интегрированную клавиатуру, цветную графику, звук, пластиковый корпус и восемь слотов расширения. «Apple II» положил начало революции в области персональных компьютеров: это была машина для масс, а не только для любителей, учёных или инженеров.

В июне 1981 года был выпущен Texas Instruments TI-99/4A — первый домашний компьютер с 16-разрядным процессором Texas Instruments TMS9900.

12 августа 1981 года фирма IBM представила широкой публике первую модель персонального компьютера IBM PC 5150, ставшую фактическим родоначальником современных персональных компьютеров на архитектуре Intel x86.

В январе 1984 года — первый успешный серийно выпускаемый персональный компьютер с манипулятором типа «мышь» и полностью графическим интерфейсом, названный Apple Macintosh.

3 апреля 1986 года — первый ноутбук IBM PC Convertible от фирмы IBM.

1990 год — фирма Microsoft выпустила Windows 3.0.

1992 год — появилась первая бесплатная операционная система с большими возможностями — Linux.

1993 год — фирма Intel выпустила 32-разрядный микропроцессор Pentium, который состоял из 3,1 млн транзисторов и мог выполнять 112 млн операций в секунду.

1995 год — появилась операционная система Windows 95.

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

Свойства алгоритма: дискретность, детерминированность (определённость), понятность, конечность, результативность.

8. Операторы выражений Это любые выражения, которые заканчиваются точкой с запятой.

i++;

a=cos (b * 5);

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

Пример:

int rus (unsigned char r)

{ if (r>='А' && c<=' ')

return 1;

else

return 0;

}

Выполнение вызова функции:

1. Выражения вычисляются и подвергаются обычным арифметическим преобразованиям. Затем тип полученного аргумента сравнивается с типом соответствующего параметра. Если они не совпадают, то либо производится преобразование типов, либо формируется сообщение об ошибке.

2. Происходит присваивание значений фактических параметров соответствующим формальным параметрам.

3. Управление передается на первый оператор функции.

4. Выполнение оператора return в теле функции возвращает управление и возможно, значение в вызывающую функцию. При отсутствии оператора return управление возвращается после выполнения последнего оператора тела функции, а возвращаемое значение не определено.

10. Пустой оператор Простейший оператор — пустой оператор (;). Он не делает ничего. Но он используется тогда, когда синтаксис требует присутствия оператора, а данный оператор не нужен.

11. Оператор if.

If — оператор условия.

if (условие)

{операторы₁}

else

{операторы₂}

В качестве условия может выступать любое выражение, результат которого является булевским (т.е. «да» или «нет», «правда» или «ложь», true или false).

Полная форма — с else, сокращенная — без else.

12. Оператор switch.

Switch — оператор многозначного выбора (переключатель). Переключатель выполняет один заданный блок операторов в зависимости от значения вычисляемого ключевого выражения. Принципиальным отличием от if является то, что switch возвращает не логическое, а целое значение. Кроме того есть специальная секция default («по умолчанию»), операторы которой выполняются в том случае, если значение ключевого выражения отличается от всех приведенных.

int a;

scanf («%d», &a);

switch (a)

{

case 1:

printf («Apple»);

break;

case 2:

printf («Banana»);

break;

default:

printf («Orange»);

break;

}

13. Оператор break.

Оператор break завершает выполнение ближайшего внешнего оператора do, for, switch или while, в котором он находится. Управление передается оператору, который расположен после завершенного оператора.

14. Оператор for.

Выполнение оператора for происходит следующим образом:

1. Вычисляется начальное выражение.

2. Вычисляется условное выражение. Возможны три результата:

— Если значение условного выражения «истина», то выполняется оператор. Процесс начинается снова с вычисления условного выражения.

— Если условное выражение опущено, то считается, что его значение «истина» и процесс выполнения протекает так, как это описано в первом случае.

— Если значение условного выражения «ложь», то выполнение оператора

for прекращается и управление передается к следующему оператору программы.

#include

int main (void)

{

int i;

for (i = 0; i < 10; i++)

printf («%dn», i);

return 0;

}

15. Оператор цикла while.

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

1. Вычисляется значение выражения.

2. Если значение выражения есть «ложь», то тело оператора while не выполняется, и управление передается на следующий за оператором while оператор программы.

3. Если значение выражения есть «истина», то выполняется тело оператора и процесс повторяется с шага 1.

float x, a;

scanf_s («%f», &x); scanf_s («%f», &a);

while (x < a)

{

x += 0.5;

printf («%fn», x);

}

16. Оператор цикла do while.

Выполнение происходит следующим образом:

1. Выполняется тело оператора.

2. Вычисляется выражение. Если его значение «ложь», то выполнение оператора do заканчивается и управление передается следующему оператору программы. Если его значение «истина» (ненулевое значение), то процесс повторяется, начиная с шага 1. Выполнение оператора do может быть прервано выполнением оператора break, goto или return в теле оператора do.

int i, j;

float x, a;

scanf_s («%f», &x); scanf_s («%f», &a);

do

{

printf («%f %fn», x, a);

x += 0.5;

}

while (x > a);

return 0;

17. Оператор continue.

Оператор continue тоже предназначен для прерывания цикла, организуемого операторами for, while, do… while. Но в отличие от оператора break, он не прекращает дальнейшее выполнение цикла, а только немедленно переходит к следующей интерации того цикла, в теле которого он оказался. Он как бы имитирует переход на конечный оператор цикла, но не за пределы самого цикла.

int a, b;

for (a=1,b=0; a<100; b+=a, a++)

{ if (b%2) continue;

/* обработка четных сумм */

return 0;

18. Оператор return. Оператор goto.

Return завершает выполнение функции и возвращает элемент управления вызывающей функции, возобновляет выполнение в вызывающей функции в точке сразу после вызова.

int sum (int a, int b)

{renurn (a+b);}

Goto — оператор безусловного перехода к определённой точке программы, обозначенной номером строки либо меткой.

for (){

goto exit;

}

exit: printf («Быстрый выход из вложенных циклов»);

19. Операнды и операции Операнд — это константа, переменная, выражение или вызов какой-либо определённой в программе функции. Любой операнд, который имеет константное выражение и тип. Целая константа может быть типа int, long, unsigned int, unsigned long, в зависимости от ее значения и от формы записи. Символьная константа имеет тип int. Константа с плавающей точкой всегда имеет тип double. Строковый литерал состоит из последовательности символов, заключенных в кавычки, и представляется в памяти как массив элементов типа char.

Операция — это некоторая функция, которая выполняется над операндами и которая возвращает вычисленное значение — результат выполнения операции. Каждой операции в Си соответствует свой знак операции.

унарные операции — операции вида [знак операции] [операнд]

бинарные операции — [операнд] [знак операции] [операнд]

и тернарные операции — [условие]? [выражение1]: [выражение2].

20. Преобразование типов Преобразования типов могут быть неявными, при выполнении операций и вызовов функций, или явными, при выполнении операций приведения типов.

Для преобразования числа в строку альтернативой, совместимой со стандартом, является использование стандартной библиотечной функции sprintf.

Функция itoa принимает передаваемое целое число и конвертирует его в число в основании корня. Полученное число записывается в буфер вывода buffer.

Функция atoi используется для конвертации строки в числовой вид.

21. Операция sizeof

Sizeof — это унарный оператор, возвращающий длину в байтах переменной или типа и помещенный в скобки. Использование sizeof помогает создавать переносимый код для тех случаев, когда код зависит от размера стандартных типов данных С.

float f;

printf («%f «, sizeof f);

printf («%d», sizeof (int));

22. Мультипликативные операции. Аддитивные операции Мультипликативные операции *, / и % группируются слева направо. Выполняются обычные арифметические преобразования.

выражение * выражение выражение / выражение выражение % выражение Аддитивные операции + и — группируются слева направо. Выполняются обычные арифметические преобразования.

выражение + выражение выражение — выражение

23. Операции сдвига Операции сдвига << и >> группируются слева направо. Проводятся обычные арифметические преобразования операндов, каждый из которых должен быть целочисленного типа. Затем правый операнд преобразуется к типу int; результат имеет тип левого операнда. Результат не определен, если правый операнд отрицателен или больше, чем длина объекта в битах.

выражение << выражение выражение >> выражение Значением выражения е1<<�е2 является е1, сдвинутое влево на е2 битов; освобождающиеся биты заполняются нулем. Значением выражения е1>>е2 является е1, сдвинутое вправо на е2 битовых позиций.

24. Поразрядные операции Поразрядные (побитовые) операции можно производить с любыми целочисленными переменными и константами. Эти действия не применимы к переменным типа float, double или long double. Результаты побитовых операций будут иметь целочисленное значение. К поразрядным операциям относятся следующие операции:

& (или and),

| (или OR),

^ (или XOR),

— (или NOT),

сдвиг влево, сдвиг вправо.

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

25. Логические операции выражение || выражение Операция || группируется слева направо. Она возвращает 1, если один из операндов отличен от нуля, и 0 в противном случае. В отличие от операции | операция || гарантирует вычисление слева направо; более того, если первый операнд отличен от нуля, то значение второго операнда вообще не вычисляется. Операнды не обязаны быть одинакового типа, но каждый из них должен быть либо одного из основных типов, либо указателем. Результат всегда имеет тип int.

26. Условная операция выражение? выражение: выражение Условные выражения группируются слева направо. Вычисляется значение первого выражения, и если оно отлично от нуля, то результатом будет значение второго выражения; в противном случае результатом будет значение третьего выражения. Если это возможно, проводятся обычные арифметические преобразования, с тем, чтобы привести второе и третье выражения к общему типу; в противном случае, если оба выражения являются указателями одинакового типа, то результат имеет тот же тип.

27. Операции увеличения и уменьшения Объект, на который ссылается операнд 1-го значения префиксной операции ++, увеличивается. Значением является новое значение операнда. Выражение ++х эквивалентно х+=1.

При применении постфиксной операции — к l-му значению результатом является значение объекта, на который ссылается l-е значение. После того, как результат принят к сведению, объект уменьшается точно таким же образом, как и в случае префиксной операции. Результат имеет тот же тип, что и выражение l-го значения.

28. Простое присваивание

l-е значение = выражение Когда производится простое присваивание с '=', значение выражения заменяет значение объекта, на которое ссылается l-е значение. Если оба операнда имеют арифметический тип, то перед присваиванием правый операнд преобразуется к типу левого операнда.

29. Теория типов. Хранение информации в памяти компьютера Теория типов — какая-либо формальная система, являющаяся альтернативой наивной теории множеств, сопровождаемая классификацией элементов такой системы с помощью типов, образующих некоторую иерархию.

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

Внутренняя память предназначена для хранения относительно небольших объемов информации при ее обработке микропроцессором. Внешняя память предназначена для длительного хранения больших объемов информации независимо от того включен или выключен компьютер.

Энергозависимой называется память, которая стирается при выключении компьютера. Энергонезависимой называется память, которая не стирается при выключении компьютера.

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

30. Теория переменных и типов данных в ANSI C

Переменная в языке C — это именованная область памяти, в которой содержится определенное значение.

Элементы переменной: тип: размер выделяемой памяти (целочисленные — int, char, long и вещественные — float, double, long double); имя переменной: любое английское название; значение: (необязательный параметр) можно сразу присвоить определенное значение для нашей переменной.

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

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

31, 32, 33. Классическая и гарвардская архитектуры. Понятия, свойства. Модифицированная архитектура Гарварда.

Гарвардская архитектура — архитектура ЭВМ, отличительными признаками которой являются:

1. Хранилище инструкций и хранилище данных представляют собой разные физические устройства.

2. Канал инструкций и канал данных также физически разделены.

Архитектура была разработана Говардом Эйкеном в конце 1930;х годов в Гарвардском университете.

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

Архитектура Гарварда имеет один очевидный недостаток — высокую стоимость. При разделении каналов передачи команд и данных на кристалле процессора последний должен иметь почти вдвое больше выводов, так как шина адреса и шина данных составляют основную часть выводов микропроцессора. Способом решения этой проблемы стала идея использовать общие шину данных и шину адреса для всех внешних данных, а внутри процессора использовать шину данных, шину команд и две шины адреса. Такую концепцию стали называть модифицированной гарвардской архитектурой. Разделение шин в модифицированной гарвардской структуре осуществляется при помощи раздельных управляющих сигналов: чтения, записи или выбора области памяти. Такой подход применяется в современных сигнальных процессорах.

34. Архитектура Фон Неймана.

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

Принципы фон Неймана

1) Принцип однородности памяти Команды и данные хранятся в одной и той же памяти и внешне в памяти неразличимы. Распознать их можно только по способу использования (одно и то же значение в ячейке памяти может использоваться и как данные, и как команда, и как адрес в зависимости лишь от способа обращения к нему).

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

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

4) Принцип двоичного кодирования Вся информация, как данные, так и команды, кодируются двоичными цифрами 0 и 1. Каждый тип информации представляется двоичной последовательностью и имеет свой формат. Последовательность битов в формате, имеющая определенный смысл, называется полем.

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

Так как динамическая переменная создаётся во время выполнения программы, у неё нет собственного идентификатора. Работа с динамической переменной ведётся косвенно, через указатель. Создание такой переменной заключается в выделении участка памяти с помощью специальной функции malloc. Эта функция возвращает адрес в памяти, который назначается указателю. После окончания работы с динамической переменной выделенную под неё память необходимо освободить — для этого тоже есть специальная функция free.

void *malloc (int size);

// выделить область памяти размером в size байтов и возвратить адрес

void free (void *p);

// освободить область памяти, выделенную по адресу p

void *realloc (void *p, int size);

// расширить выделенную область памяти до размера size, при изменении адреса переписать старое содержимое блока

36. Понятие указателя Указатель — переменная, диапазон значений которой состоит из адресов ячеек памяти или нулевого адреса. Последнее используется для указания того, что в данный момент там ничего не записано. Тип указателя определяет тип объекта, на который указатель будет ссылаться.

int i; // целая переменная

const int ci = 1; // целая константа

int* pi; // указатель на целую переменную

const int * pci; // указатель на целую константу

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

int *mas = malloc (sizeof (int) * 10);

38. Обменные сортировки: сортировка пузырьком Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма). Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

39. Обменные сортировки: быстрая сортировка Быстрая сортировка — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Алгоритм:

Выбираем в массиве некоторый элемент, который будем называть опорным элементом.

Реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:

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

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

41. Сортировка Шелла Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (например, в пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

42. Алгоритм BogoSort

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

Колода в 32 карты будет сортироваться компьютером, в среднем, лет.

43. Понятие оценки сложности алгоритма Существует несколько способов измерения сложности алгоритма. Обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели — требования к объёму памяти, свободному месту на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Основной оценкой функции сложности алгоритма f (n) является оценка. Здесь n — величина объёма данных или длина входа. Мы говорим, что оценка сложности алгоритма.

если при g > 0 при n > 0 существуют положительные с1, с2, n0, такие, что:

при n > n0, иначе говоря, можно найти такие с1 и c2, что при достаточно больших n f (n) будет заключена между

и .

В таком случае говорят ещё, что функция g (n) является асимптотически точной оценкой функции f (n), так как по определению функция f (n) не отличается от функции g (n) с точностью до постоянного множителя.

44. Понятие конечного автомата Конечный автомат — абстрактный автомат, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

Конечный автомат начинает работу в состоянии q0, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x. Конечные автоматы широко используются на практике, например, в синтаксических и лексических анализаторах, тестировании программного обеспечения на основе моделей.

45. Исходный, объектный и машинный код Машинный код — система команд конкретной вычислительной машины, которая интерпретируется непосредственно процессором или микропрограммами этой вычислительной машины. Каждая инструкция выполняет определённое действие, такое как операция с данными или переход к другому участку кода. Каждая исполнимая программа состоит из последовательности таких инструкций. Машинный код можно рассматривать как примитивный язык программирования или как самый низкий уровень представления скомпилированных или ассемблированных компьютерных программ. Хотя вполне возможно создавать программы прямо в машинном коде, сейчас это делается редко в силу громоздкости кода и трудоёмкости управления ресурсами процессора, за исключением ситуаций, когда требуется экстремальная оптимизация.

Объектный код — некий текст программы, написанный без специфических для какого-либо языка программирования команд, но в котором оставлены названия функций и операций, названия переменных и другое. Объектный код, в отличие от исходного кода, позволяет формально подключится к нему из любого языка программирования. Сборка (компиляция) сложных программ происходит в два этапа — сначала идет подготовительный этап (написание объектного кода), а затем уже идет компиляция, чтобы получить исполняемый файл программы. У объектного кода есть еще одно преимущество — например вы имеете сто файлов, которые подлежат компиляции. При запуске компиляции вы вдруг замечаете, что в одном из файлов происходит ошибка. В этом случае вы можете исправить только этот файл, пишите только для него объектный код заново и затем пересобираете программу, не нужно компилировать все сто файлов заново.

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

46. Функции компилятора и линковщика Компилятор выполняет трансляцию (перевод) программы, составленной на исходном языке высокого уровня, в эквивалентную программу на низкоуровневом языке, близком машинному коду (абсолютный код, объектный код, иногда на язык ассемблера). Входной информацией для компилятора (исходный код) является описание алгоритма или программа на проблемно-ориентированном языке, а на выходе компилятора — эквивалентное описание алгоритма на машинно-ориентированном языке (объектный код).

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

47. Понятие стека Стек (англ. стопка) — структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Значением переменной стека является указатель на вершину стека. Если стек пуст, то значение указателя равно NULL.

struct stack

{

char *data;

struct stack *next;

};

Возможны три операции со стеком: добавление элемента (push), удаление элемента (pop) и чтение головного элемента (peek). При добавлении (push) указывается новый элемент, указывающий на элемент бывший до этого самым верхним. Новый элемент теперь становится головным. При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).

48. Понятие дека Дек (двухсторонняя очередь) — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO.

push_front (Добавить в начало дека новый элемент)

push_back (Добавить в конец дека новый элемент)

pop_front (Извлечь из дека первый элемент)

pop_back (Извлечь из дека последний элемент)

front (Узнать значение первого элемента (не удаляя сам элемент))

back (Узнать значение последнего элемента (не удаляя сам элемент))

size (Узнать количество элементов в деке)

clear (Очистить дек полностью)

49. Понятие очереди Омчередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (enqueue) возможно лишь в конец очереди, выборка — только из начала очереди (dequeue), при этом выбранный элемент из очереди удаляется.

Существует несколько способов реализации очереди в языках программирования. Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end. Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1.

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

Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов. Преимущества данного метода: размер очереди ограничен лишь объёмом памяти. Недостатки: сложнее в разработке; требуется больше памяти; работа с очередью несколько медленнее.

50. Понятие дерева и таблицы Дерево — структура данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы.

Корневой узел — самый верхний узел дерева (узел 2 на примере).

Корень — одна из вершин.

Лист — узел, не имеющий дочерних элементов (узлы 2, 4, 5, 11).

Внутренний узел — любой узел дерева, не имеющий потомков (7, 5, 6, 9).

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

Таблица — вектор, элементами которого являются записи. Характерной логической особенностью таблиц является то, что доступ к элементам таблицы производится не по номеру (индексу), а по ключу. Ключ — это свойство, идентифицирующее данную запись во множестве однотипных записей. Как правило, к ключу предъявляется требование уникальности в данной таблице. Ключ может включаться в состав записи и быть одним из ее полей, но может и не включаться в запись, а вычисляться по положению записи. Таблица может иметь один или несколько ключей.

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

51. Понятие структуры и объединения в языке ANSI C

Структура — это совокупность переменных, объединенных под одним именем. С помощью структур удобно размещать в смежных полях связанные между собой элементы информации. Объявление структуры создает шаблон, который можно использовать для создания ее объектов. Переменные, из которых состоит структура, называются членами. Как правило, члены структуры связаны друг с другом по смыслу. Ключевое слово struct сообщает компилятору, что объявляется структура.

Одновременно с объявлением структуры можно объявить одну или несколько переменных.

struct str_name

{

int member₁;

float member₂;

char member₃[256];

}

Объединение — структура данных, члены которой расположены по одному и тому же адресу. Поэтому размер объединения равен размеру его наибольшего члена. В любой момент времени объединение хранит значение только одного из членов. Объединения часто используются при необходимости преобразования типов, поскольку можно обращаться к данным, хранящимся в объединении, совершенно различными способами.

union union_type {

int i; char ch;

};

52. Понятие и механизм указателей Указатель — переменная, диапазон значений которой состоит из адресов ячеек памяти или нулевого адреса. Последнее используется для указания того, что в данный момент там ничего не записано. Тип указателя определяет тип объекта, на который указатель будет ссылаться.

int i; // целая переменная

const int ci = 1; // целая константа

int* pi; // указатель на целую переменную

const int * pci; // указатель на целую константу

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

54. Динамическое выделение памяти. Утечки памяти Часто возникают ситуации, когда заранее не известно, сколько данных будет хранить программа. В этом случае используется динамическое выделение памяти, когда память занимается и освобождается в процессе исполнения программы. При использовании динамической памяти (ДП) отпадает необходимость заранее распределять память для хранения данных, используемых программой. Управление динамической памятью — это способность определять размер объекта и выделять для его хранения в соответствующую область памяти в процессе исполнения программы. При динамическом выделении памяти для хранения данных используется специальная область памяти — «куча» (heap). Объем «кучи» и ее местоположение зависят от модели памяти, которая определяет логическую структуру памяти программы.

float*a = (float *)malloc (n*sizeof (float));

printf («введите элементы массива»);

for (i=0;i

printf («массив»);

for (i=0;i

free (a);

return 0;}

Утемчка паммяти — процесс неконтролируемого уменьшения объёма свободной оперативной или виртуальной памяти компьютера, связанный с ошибками в работающих программах, вовремя не освобождающих ненужные участки памяти, или с ошибками системных служб контроля памяти. Утечки памяти приводят к тому, что потребление памяти программой неконтролируемо возрастает, в результате рано или поздно вступают в действие архитектурные ограничения ЭВМ, и тогда новое выделение памяти становится невозможным. В этой ситуации в программе, которая запрашивает память, обычно происходит аварийная остановка. Это может по стечению обстоятельств произойти и совсем с другой программой после того, как программа, подверженная утечкам, потребит всю память ЭВМ.

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

Отказ от динамической памяти.

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

Сборка мусора (средства, позволяющие автоматически освобождать неиспользуемую память).

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

55. Динамические списки Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

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

56. Модульность. Области видимости переменных Модульность — принцип, согласно которому программное средство (библиотека, веб-приложение и др.) разделяется на отдельные именованные сущности, называемые модулями. Модульность часто является средством упрощения задачи проектирования ИС и распределения процесса разработки ИС между группами разработчиков. При разбиении ИС на модули для каждого модуля указывается реализуемая им функциональность, а также связи с другими модулями.

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

Область видимости — область программы, в пределах которой идентификатор некоторой переменной продолжает быть связанным с этой переменной и возвращать её значение. За пределами области видимости тот же самый идентификатор может быть связан с другой переменной, либо быть свободным. Область видимости переменной определяется местом её объявления.

Переменные обычно разделяются на два типа по области видимости:

локальные — объявляются внутри функции и недоступны снаружи неё;

глобальные — объявляются вне всех функций и доступны отовсюду.

#include

int a = 0; // глобальная переменная

int main ()

{

printf («%d», a); // будет выведено число 0

{

int a = 1; // объявлена локальная переменная а, глобальная переменная a не видна

printf («%d», a); // будет выведено число 1

{

int a = 2; // еще локальная переменная в блоке, глобальная переменная a не видна, не видна и предыдущая локальная переменная

printf («%d», a); // будет выведено число 2 }}}

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

#include <…>

Директива препроцессора — строка в исходном коде, которая начинается с символа # и следующего за ним ключевого слова препроцессора. Список ключевых слов:

· define — задаёт макроопределение (макрос) или символическую константу

· undef — отменяет предыдущее определение

· include — вставляет текст из указанного файла

· if — осуществляет условную компиляцию при истинности константного выражения

· ifdef — осуществляет условную компиляцию при определённости символической константы

· ifndef — осуществляет условную компиляцию при неопределённости символической константы

· else — ветка условной компиляции при ложности выражения

· elif — ветка условной компиляции, образуемая слиянием else и if

· endif — конец ветки условной компиляции

· line — препроцессор изменяет номер текущей строки и имя компилируемого файла

· error — выдача диагностического сообщения

· pragma — действие, зависящее от конкретной реализации компилятора

· пустое слово — пустое действие.

58. Кроссплатформенное программное обеспечение вычислительный тьюринг код алгоритм Кроссплатформенное ПО — программное обеспечение, работающее более чем на одной аппаратной платформе или операционной системе.

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

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

На разных ОС стандартные элементы интерфейса имеют разные размеры. Поэтому простое позиционирование элементов интерфейса невозможно — под другой ОС они могут налезать друг на друга. Существует несколько подходов:

· единый стиль, общий для всех ОС (программы выглядят одинаково под всеми ОС).

· самоадаптирующийся интерфейс, подстраивающий сетку под реальные размеры элементов управления.

59. Основы ООП Объектно-ориентированное программирование (ООП) — это способ организации кода в программе путем его группировки в виде объектов, то есть отдельных элементов, которые включают информацию и функции. ООП позволяет группировать определенные фрагменты информации вместе с часто используемыми функциями или действиями, связанными с этой информацией. Эти элементы объединяются в один элемент, так называемый объект. Возможность связать вместе эти значения и функции дает несколько преимуществ. Например, нужно отслеживать только одну переменную, а не несколько; можно сгруппировать вместе связанные между собой функции; можно организовать структуру программы так, чтобы она больше соответствовала реальным потребностям.

На практике объектно-ориентированное программирование делится на две части. Одна часть включает стратегии и приемы для разработки программ. Вторая часть ООП — это собственно структуры программирования, доступные в данном языке программирования для создания программы с использованием объектно-ориентированного подхода.