1. Общее представление об информации. Кодирование информации. Код ASCII.

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

Можно привести немало разнообразных свойств информации. Каждая научная дис­циплина рассматривает те свойства, которые ей наиболее важны. С точки зрения информатики наиболее важными представляются следующие свойства: объективность, полнота, достоверность, адекватность, доступность и актуальность информации.

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

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

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

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

В технических устройствах хранения, передачи и обработки информации для её кодирования часто используют алфавиты, содержащие лишь два различных символа. Наличие всего двух символов значительно упрощает электрические схемы с электронными переключателями, которые принимают только два состояния - они либо проводят ток, либо нет. Алфавит из двух символов 1 и 0 называют двоичным и говорят о двоичном представлении информации (кодировании информации в двоичном коде). При таком представлении буквы, цифры и любые другие символы изображаются двоичными словами - последовательностями из нулей и единиц.

Комбинируя восемь нулей и единиц различными способами, можно получить 256 различных комбинаций. Этого количества достаточно, чтобы каждому символу поставить в соответствие свою неповторимую комбинацию из восьми нулей и единиц. Эти комбинации определяются кодовой таблицей ASCII (американский стандартный код для обмена информацией).

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

В кодовой таблице ASCII первые 128 символов (с номерами от 0 до 127) являются стандартными: буквы латинского алфавита, цифры, знаки препинания и другие (специальные) символы. Остальные (128 кодов) используются для кодировки букв национальных алфавитов.

2. Измерение информации.

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

В качестве единицы измерения количества информации принят 1 бит — один символ двоичного алфавита: 0 или 1. Наряду с битом существует укрупнённая единица - байт, равный 8 битам.

Одним байтом кодируется любой печатный знак (буква, цифра, любой другой символ). Байт — один символ, который представляет комбинацию из 8 бит.

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

Широко используются более крупные единицы информации:

• 1 Килобайт (Кбайт) = 1024 байт = 2¹⁰ байт,

• 1 Мегабайт (Мбайт) = 1024 Кбайт = 2²⁰ байт,

• 1 Гигабайт (Гбайт) = 1024 Мбайт = 2³⁰ байт.

• 1 Терабайт (Тбайт) = 1024 Гбайт = 2⁴⁰ байт

3. Вероятностный подход к измерению информации.

Определить понятие “количество информации” довольно сложно. В решении этой проблемы существуют два основных подхода: символьный и вероятностный. Один из основателей кибернетики, американский математик Клод Шеннон, предложил вероятностный подход к измерению количества информации.

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

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

Например, сообщение о результате бросания монеты (количество равновероятных исходов равно 2) содержит х=1 бит информации (2^х = 2).

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

где p_i — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений

Легко заметить, что если вероятности p_i равны, то каждая из них равна 1/N, и формула Шеннона превращается в формулу Хартли.

4. Основные функциональные части компьютера. Взаимодействие процессора и памяти при выполнении команд и программ.

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

Назначение процессора:

1) управлять работой ПК по заданной программе;

2) выполнять операции обработки информации.

Память компьютера делится на внутреннюю и внешнюю. Внутренняя память ПК включает в себя оперативное запоминающее устройство (ОЗУ) и постоянное запоминающее устройство (ПЗУ).

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

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

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

Возможности компьютера как универсального исполнителя по работе с информацией определяются системой команд процессора. Эта система команд представляет собой язык машинных команд (ЯМК). Из команд ЯМК составляются программы управления работой компьютера. Отдельная команда определяет отдельную операцию (действие) компьютера. В ЯМК существуют команды, по которым выполняются арифметические и логические операции, операции управления последовательностью выполнения команд, операции передачи данных из одних устройств памяти в другие и пр.

5. Общие сведения о системах счисления. Двоичная система счисления.

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

Существуют позиционные и непозиционные системы счисления.

В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII вес цифры Х в любой позиции равен просто десяти.

В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая – 7 единиц, а третья – 7 десятых долей единицы. Сама же запись числа 757,7 означает сокращенную запись выражения

700 + 50 + 7 + 0,7 = 710² + 510¹ + 710⁰ + 710^-1 = 757,7.

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

В компьютере информация представляется в двоичном виде (в битовой форме). Она имеет ряд преимуществ перед другими системами:

• для ее реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток — нет тока), а не с десятью, — как в десятичной;

• представление информации посредством только двух состояний надежно и помехоустойчиво;

• двоичная арифметика намного проще десятичной.

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

Для перевода десятичного числа в двоичную систему счисления необходимо представить его в виде суммы степеней числа 2. Например, (76)₁₀ = 64 + 8 + 4 = 2⁶ + 2³ + 2² = (1001100)₂.

Для перевода дроби в двоичную систему счисления преобразуют отдельно ее целую и дробную части. Применяют алгоритм умножения на 2. Например, для перевода 0,375 в двоичную систему счисления, имеем:

20,375 = 0,75 (целая часть равна 0)

20,75 = 1,5 (целая часть равна 1)

20,5 = 1,0 (целая часть равна 1)

Этот процесс продолжается до тех пор, пока дробная часть не окажется равной нулю. Тогда имеем (0,375)₁₀= (0,011)₂.

6. Восьмеричная и шестнадцатеричная системы счисления.

Современные компьютеры производят вычисления в двоичной системе счисления. Однако для представления компьютерной информации нередко используют восьмеричную и шестнадцатеричную системы счисления.

В следующей таблице представлено соответствие между восьмеричными цифрами (OCT) и трехзначными двоичными (BIN) числами (двоичными триадами), равными по значению этим цифрам.

OCT	0	1	2	3	4	5	6	7
BIN	000	001	010	011	100	101	110	111

Записать восьмеричное число в двоичной системе счисления – это значит заменить каждую восьмеричную цифру на соответствующую двоичную триаду. Например: 3517,2₈→11 101 001 111,010 ₂.

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

В следующей таблице представлено соответствие между шестнадцатеричными (HEX) цифрами и четырехзначными двоичными числами (двоичными тетрадами), равными по значению этим цифрам.

DEC	0	1	...	8	9	10	11	12	13	14	15
HEX	0	1	...	8	9	A	B	C	D	E	F
BIN	0000	0001	...	1000	1001	1010	1011	1100	1101	1110	1111

Записать шестнадцатеричное число в двоичной системе – это значит заменить каждую шестнадцатеричную цифру на соответствующую двоичную тетраду. Например: С81F,1D₁₆ → 1100 1000 0001 1111,0001 1101_2-16

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

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

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

Числа в памяти компьютера располагаются в байтах – минимальных по размеру ячейках памяти. Целые числа могут представляться в компьютере со знаком или без знака. Целые числа без знака обычно занимают в памяти один байт (8-разрядная ячейка) или два байта (16-разрядная ячейка). Диапазон значений в первом случае от 00000000₂ до 11111111₂ (от 0₁₀ до 255₁₀). Разряды нумеруются справа налево, начиная с нуля. Например, число 72₁₀ = 1001000₂ в однобайтовом формате:

Номера разрядов	7	6	5	4	3	2	1	0
Биты числа	0	1	0	0	1	0	0	0

Знак “плюс” кодируется нулем, а “минус” — единицей.

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

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

1. Прямой код. В знаковый разряд помещается цифра 1, а в разряды цифровой части числа — двоичный код его абсолютной величины. Например, прямой код числа -1 

Номера разрядов	7	6	5	4	3	2	1	0
Биты числа	1	0	0	0	0	0	0	1

 знак числа

2. Обратный код. Получается инвертированием всех цифр двоичного кода абсолютной величины числа, включая разряд знака: нули заменяются единицами, а единицы — нулями. Например, обратный код числа -1 

Номера разрядов	7	6	5	4	3	2	1	0
Биты числа	1	1	1	1	1	1	1	0

 знак числа

3. Дополнительный код. Получается образованием обратного кода с последующим прибавлением единицы к его младшему разряду. Например, дополнительный код числа -1

Номера разрядов	7	6	5	4	3	2	1	0
Биты числа	1	1	1	1	1	1	1	1

8. Выполнение арифметических действий с целыми числами.

При сложении чисел А и В имеют место четыре основных случая:

1. А и В положительные. При суммировании складываются все разряды, включая разряд знака. Так как знаковые разряды положительных слагаемых равны нулю, разряд знака суммы тоже равен нулю. Например: 0 0000011 (А=3) + 0 0000111 (В=7) = 0 0001010 (10)₁₀ Получен правильный результат

2. А положительное, B отрицательное и по абсолютной величине больше, чем А. Например: 3+(-10)=-7  0 0000011 (прямой код) + 1 1110101 (обратный код числа -10) = 1 1111000 (обратный код числа -7) Получен правильный результат в обратном коде. При переводе в прямой код биты цифровой части результата инвертируются: 1 0000111 = –7₁₀.

3. А положительное, B отрицательное и по абсолютной величине меньше, чем А. Например: 10+(-3)=7  0 0001010 (прямой код) + 1 1111100 (обратный код числа-3) = 1 0000110. Компьютер исправляет полученный первоначально неправильный результат (6 вместо 7). Переносом единицы из знакового разряда в младший разряд суммы и выдает правильный результат 7.

4. А и В отрицательные. Например: (-3)+(-7)=-10  1 1111100 (обратный код -3) + 1 1111000 (обратный код числа -7) = 1 1110100. Полученный первоначально неправильный результат (обратный код числа –11₁₀ вместо обратного кода числа –10₁₀) компьютер исправляет переносом единицы из знакового разряда в младший разряд суммы. При переводе результата в прямой код биты цифровой части числа инвертируются: 1 0001010 = –10₁₀.

Сложение целых чисел может быть организовано с использованием дополнительных кодов.

• на преобразование отрицательного числа в обратный код компьютер затрачивает меньше времени, чем на преобразование в дополнительный код, так как последнее состоит из двух шагов — образования обратного кода и прибавления единицы к его младшему разряду;

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

9. Представление вещественных чисел в компьютере.

В ПК числа могут быть представлены в одной из двух форм:

1) с фиксированной точкой – в естественной форме (0.00345 – правильная дробь, 1.23456 – неправильная дробь)

2) с плавающей точкой (запятой) (555,55 = 55555•10^-2 = 0,55555•10³)

Для отображения вещественных чисел, которые могут быть как очень маленькими, так и очень большими, используется форма записи чисел с порядком основания системы счисления. Любое число А может быть представлено в экспоненциальной форме: А = m • qⁿ, где m – мантисса числа, q – основание системы счисления.,n – порядок числа.

Например, 0,55555•103 Чтобы привести к какому-то стандарту в представлении чисел с плавающей запятой условились представлять числа в нормализованной форме. При этом мантисса отвечает условию:

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

Например, 555,55 – естественная форма;

0,55555•10^{3 -} нормализованная форма . Это касается и отрицательных чисел, т.к. мантисса в условии взята по модулю. Дробные числа занимают в памяти 4 байта (обычная точность) или 8 байтов (двойная точность).

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

• знака мантиссы,

• знака порядка,

• порядка числа

• мантиссы.

1-й байт	2-й байт	3-й байт	4-й байт
± порядок	знак и мантисса

• в старшем бите 1-го байта хранится знак порядка числа ( 0 – плюc, 1 – минус);

• 7 бит 1-го байта содержат порядок;

• в следующих трех байтах, хранятся значащие цифры мантиссы и её знака (24 разряда).

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

± маш. порядок	М АН	Т И С	С А
1-й байт	2-й байт	3-й байт	4-й байт

В старшем бите 1-го байта хранится знак числа: 0 обозначает плюс, 1 — минус. Оставшиеся 7 бит первого байта содержат машинный порядок. В следующих трех байтах хранятся зна­чащие цифры мантиссы (24 разряда).

Машинный порядок изменяется в диапазоне от 0 до 127 (в десятичной системе счисления). Порядок (в математическом понимании), очевидно, может быть как положительным так и отрицательным. Разумно эти 128 значений разделить поровну между положительными и отрицательными значениями порядка: от -64 до 63.

Машинный порядок смещен относительно математичес­кого и имеет только положительные значения. Смещение вы­бирается так, чтобы минимальному математическому зна­чению порядка соответствовал нуль. Связь между машинным порядком (Мр) и математическим (р) в рассматриваемом случае выражается формулой: Мр = р + 64.

Полученная формула записана в десятичной системе. В дво­ичной системе формула имеет вид: Мр₂ = р₂ + 100 0000₂.

• Внутреннее представление вещественного числа.

Алгоритм записи внутреннего представления вещественного числа:

1) перевести модуль данного числа в двоичную систему счис­ления с 24 значащими цифрами;

2) нормализовать двоичное число; 3) найти машинный порядок в двоичной системе счисления;

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

10 Выполнение арифметических действий с вещественными числами.

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

Алгоритм сложения и вычитания чисел в формате с плавающей запятой:

1. Провести выравнивание порядков 2. Сложить или вычесть мантиссы.

3. Привести полученное число к стандартному формату с плавающей запятой путем нормализации.

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

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

Алгоритм умножения чисел в формате с плавающей запятой:

1. Сложить порядки 2. Перемножить мантиссы

Алгоритм деления чисел в формате с плавающей запятой:

1. Из порядка делимого вычесть порядок делителя 2. Мантиссу делимого делить на мантиссу делителя.

11. Логические функции, их применение для записи условий.

Наука, в которой с помощью формальных правил определяет истинность или ложность высказыкания нలзываб⑂ся логᐹкⒾᐹ. А 0лгебре логи␻Ѹ вӃе вՋсказыванй摏 䐾боؿначذът⑁я буквᐰ䐼и 萰l b, с и т℮ дီ, что пжҷ␲оляеي манипу;м䑀Ծвать ими подాбно т␾Լу, как в математసке мвнизѓлҸీчют обы葇ЭыоиȠؿнрЕмవнныЬи, принимающие гишь дка значениᑏ јСҢИ萝␐ (true) или ЛОЖЬ 䀨false).䀍ҟеременныЕ䀠и䀨ౄунвтии. принимరющѸе ␷начение 0 (falre( సлШ 1 
ôrõe
 нѾӁят ౽а7вҰние логИхеՁки౅

НадȠвысказываఽия؜и могутࠠвыполняться слеشуюсИе п␾лغчѵские`жпеՀаци蒸:

• ␞трицаѽие. Об萾ҷн0чепие: частИцᐶ НЕ (NoT9;

• Кжн䑨ᑌнкцИя (лог8Շеское ум蘽о␶ение).!Пбозначеѽие: со⑎ѷоԾ И 8AND)䀮ДизъЎнкѦ䐸я (萻оֳичеుкое&сложениԵ). О␱означнᐽие: союзом ИЛИ (OR).

Результذты вуполнХния логиїеских" о?ерациѹ приࠠ соответствуюљих!значениях пе䑀еменныч tru⁥ ,1) или falSe (0) даны В таблице истинности

Х	y	NOT x	x AND y	x OR y
1	1	0	1	1
1	0	0	0	1
0	1	1	0	1
0	0	1	0	0

‍

Примситет выполненич о䐿ешаций в логических Тсраж␵ниях без скобок$следующий: отрицание (LOT), конъюнкция 䀨AND), дизъюнкция (၏R!.

При вы萿олнении логическ䔸х кПерациЩ пр萾из␲одят сһедующие ؾпеᑀации сравнения: равно (=), больш䐵 耨>)$ м␵ньше (<)< ѱолюше илиȠравԽо (), $мень䱀е `или равно (), ҽе равн萾 ().

Еᑑли в оشном вырѰжении встречаюц䑁я ᐰриєнѵтѸᑇеские оперРцй䐸 иРؾЯصрации cраᐲнения, то они выполняются в порядке их ؿеречислен8я.ȠНапример, лоళическؾе выражение x² + y^r < 1 AND q>0 буѴет истинно, если точка (x,y) принаఴлежит полу:ругу.

12. Понят8е алгоритҼа. Хормы представления алгоритмов.

Алг␾ритм – систеда форҼаЛӌныE ПѐТвил,ࠠ葇етко и ాднозначнѾ опредеᐻяющаяȠؿроцесс выполнения заданной работы в ѲШде конЕчной последؾватбль落ости действᐸй.

Длгоритм – ؂очЭый пాсядок действий, онӀеделяющий процесс перехода оу Լсходных да落ных к Ըскомому рееуЫѬтату.

Алгоритм долж萵е обладатф0следу⑎щимк свойుтвамик

• Деӂерминированностٌю - однозначностью получаемого ѐезультата при одних и тех же исходных даннЋх;ࠠ

• ДҰссов萾стью m возможностью получения иёкомого резуѻьтата прᐼ различных 䀠исходных䀠 данНых ␔ля некотороళо класса зРдач;

• результативностью - дл䑏 ␻юбых допусти䐼ых ဠисходных данных алгоритм должен череЧࠠконечное число ша蒳ов завершить свою раСоту, либо подать с萸гнал о тҾм, что дан␽ый రлгоӀито непـиᐼеним для решения† поставленной зАдач萸;

• дискретносBью - возᐼожнощтьюĠ0разбиения определ␵нного алгорит䐼ического процесса` на отдельные элеменూарныеࠠэтапы, вЋполнХние которӋх человеком или䀠 ЭВМ не耠 вызывает сᘾмнения, а результат выполнения 蔺аждого эле␼ентарного этапа опӀеделен и понятен.

1. Основнᑋми ظжобразительными средствами алгоритмов являются сй5дующ8е 䑁пособы Шх записи: словесная, 䕄Ормульмо`– словесная,Р графическая, на языкРх программҸрования.

萡ловесны␹ – содержание этапов вًчислений задается нА естественном языке в произвؾльной фжрме. Достоиᐽствд ⑝тоУо способа: общедЮступн萾ст䑌, возможнాсть описывать алгоритм с любой степенью детализАции.

萑ѻок-схемный – это графическое изобрРжение логической структуры Алгоритма, в котором кажҴый этап ᐿроцесса переработки данных представляеЂся в ви萴е геометрическИх фигуш (блоков), име䑎щᐸх строгую конфигурацию Т смотвеూсقвии с характ␵ром выполняемых дейстаиЩ. 耍

13. Линнйные, развеувленн葋␵ и цикличные а␻гори䑂мы.

Алгоритмы бываюق чрежвычайно сложными, многостуненчатыми по с2оей стрCктуце(и состоят из тысяч отдельных о␿ерацийn При всем многాобразии7алгор8тؽов решения задач в нШх можно выделить три основны䑅 (канонических) вида алгоритмических структур: йинейнуюl ветв⑏щуюс౏, циклическую.䀠С помощью этих треٍ видов стـуктур!можео построить алгоритҼ гюбой сложности.

Доказано, чтоဠлюбую програнмృ можно написать, используя коѼԱинацииĠэтих трех базовых каноничехкиѕ структур алгоритмов.

Линейным"называется алгоՀитмическиЩ"процесс, н@и котором в䑁е этапы решения задачи(выполняются в䀠порядке следованظя записи этих этбпов. Порядок Ѳыполнения этапмв не закисит ни от 8схоѵных данных,Ƞни от7результатов выпоЛнения предًдущ蕸х этапов.

Вычиѡлительный прԾцесс, который в зависимости от выполнения определенных условийРреализубтся по одному иж нҵскольких заранее преФусмотренᐽых (возможных) напраᐲлени9, нРзывбԴтся разгетвляющимся. аждое напрАвг5ние вычиспени␹ называется ветزьюီ Вًбор†ветвиࠠосуще䑁твляется в рХзулэтатవ провбрки неѺоторогп$логичеслого условия.

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

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

Различают циклы арифметические (с заранее известным числом повторений) и итерационные (число повторений которых заранее не известно и выход из которых осуществляется по выполнению некоторого условия).

13. Логические элементы и базовые управляющие структуры визуального структурного программирования.

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

Схемы, реализующие эти операции, называют логическими элементами, и обозначаются на схемах:

Отрицание (дополнение или инверсия) обозначают NOT_х или

Л огическое И

(конъюнкция или логическое умножение) Обозначают х AND y или x y или x  y

Логическое ИЛИ

(дизъюнкция или логическое сложение)

Обозначают х OR y или x + y или x  y

Операции И, ИЛИ, НЕ образуют полную систему логических операций, из которой можно построить сколь угодно сложное логическое выражение.

13. Программа как изображение алгоритма в терминах команд, управляющих работой компьютера.

Описание алгоритмов с помощью программ - алгоритм, записанный на языке программирования, называется программой.    Словесная и графическая формы записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнения на компьютере, записывается на языке программирования (языке, понятном ЭВМ). Сейчас известно несколько сот языков программирования. Наиболее популярные: Си, Паскаль, Бейсик и т. д.     Пример. Составить алгоритм нахождения наибольшего числа из трех заданных чисел a, b, c. program Max; var   a, b, c, result: Real; begin   Write  ('Введите a, b, c');   ReadLn (a, b, c);   if a>b then result := a else result := b;   if c>result then result := c;   WriteLn ( ' Максимальное из трех чисел равно:', result :9:2) end.

13. Языки высокого уровня. Трансляция и компоновка. Исходный и объектный модули, исполняемая программа. Компиляция и интерпретация.

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

Ядро системы программирования составляет язык Существующие языки программирования можно разделить на две группы: процедурные и непроцедурные.

Процедурные (или алгоритмические) программы представляют из себя систему предписаний для решения конкретной задачи. Роль компьютера сводится к механическому выполнению этих предписаний.

Процедурные языки разделяют на языки низкого и высокого уровня.

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

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

1. Фортран 2. Бейсик 3. Си 4. Паскаль На его базе созданы несколько более мощных языков (Модула, Ада, Дельфи). 5. Дельфи (Delphy) - язык объектно-ориентированного "визуального" программирования; в данный момент чрезвычайно популярен.

В самом общем случае для создания программы на выбранном языке программирования (языке системного программирования) нужно иметь следующие компоненты: 1. Текстовый редактор для создания файла с исходным текстом программы. 2. Компилятор или интерпретатор. Исходный текст с помощью программы-компилятора переводится в промежуточный объектный код. Исходный текст большой программы состоит из нескольких модулей (файлов с исходными текстами). Каждый модуль компилируется в отдельный файл с объектным кодом, которые затем надо объединить в одно целое. 3. Редактор связей или сборщик, который выполняет связывание объектных модулей и формирует на выходе работоспособное приложение – исполнимый код. Исполнимый код – это законченная программа, которую можно запустить на любом компьютере, где установлена операционная система, для которой эта программа создавалась. Как правило, итоговый файл имеет расширение .ЕХЕ или .СОМ.

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

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

17. Реализация базовых алгоритмов на языке высокого уровня.

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

1. Базовая структура  "следование". Образуется последовательностью действий, следующих одно за другим:

2. Базовая структура  "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:

• если—то;

• если—то—иначе;

• выбор;

• выбор—иначе.

если x > 0 если a > b выбор

  то y := sin(x)   то a := 2*a; b := 1 при n = 1: y := sin(x)

все   иначе b := 2*b при n = 2: y := cos(x)

все при n = 3: y := 0

все

3. Базовая структура  "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

нц для i от 1 до 5 нц пока i <= 5

  X[i] := i*i*I   S := S+A[i]

  Y[i] := X[i]/2   i := i+1

кц кц

18. Операции с массивами. Ввод и вывод массивов. Алгоритмы поиска и упорядочения массива.

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

Обычно ввод элементов массивов осуществляется в цикле:

DIM A(6) DIM A(9)

FOR i=0 TO 5 FOR i=0 TO 9

READ A(i) INPUT A(i)

NEXT NEXT

DATA 1,2,3,4,5,6

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

Вывод массивов может осуществляться такими же последовательностями операторов, что и ввод, но вместо оператора READ или INPUT записывается оператор печати PRINT. Например, вывод на печать (по строкам) двумерного массива имеет вид

FOR i=1 TO n

FOR j=1 TO k

PRINT A(i,j);

NEXT j

PRINT

NEXT i

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Имеется три способа сортировки массивов:

• сортировка обменом; сортировка выбором; сортировка вставкой.

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

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

• сравнение, определяющее упорядоченность пары элементов;

• перестановку, меняющую местами пару элементов;

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

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

19. Программы и подпрограммы. Подпрограммы, их назначение и классификация.

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

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

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

Примеры процедур и функций в Pascal: стандартные процедуры READ, WRITE, VAL, функции ORD, CHR, математические функции и др. Наличие в Паскале богатой библиотеки таких программных заготовок существенно облегчает разработку прикладных программ. Однако в большинстве случаев приходится разрабатывать свои, нестандартные процедуры и функции.

Структура подпрограммы почти буквально повторяет структуру всей Pascal-программы, что имеет глубокий смысл - часть подобна целому.

20. Классификация программного обеспечения. Виды программного обеспечения.

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

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

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

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

К прикладному ПО относятся: Комплект офисных приложений MS OFFICE , Бухгалтерские системы

Интегрированные пакеты делопроизводства, CAD – системы (системы автоматизированного проектирования)

Редакторы HTML или Web – редакторы , Браузеры – средства просмотра Web – страниц, Графические редакторы

Экспертные системы, и так далее.

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

- общего назначения (текстовые процессоры, табличные редакторы, системы управления базами данных, графические процессоры, издательские системы, системы автоматизации проектирования и т. д.);

- проблемно-ориентированные — направлены на решение определенной задачи (проблемы) в конкретной предметной области (банковские пакеты, пакеты бухгалтерского учета, финансового менеджмента, правовых справочных систем и т. д.).