Title: ТИ (база порно)

Q: 1. Определение информатики
A: Информатика — это наука, предметом изучения которой являются процессы машинного сбора, преобразования, хранения, защиты, поиска и передачи всех видов информации, а также средства их автоматизированной обработки.

Q: 2. Информатика как наука и вид практической деятельности
A: Как наука, информатика изучает общие закономерности, свойственные информационным процессам (в самом широком смысле этого понятия). Когда разрабатываются новые носители информации, каналы связи, приёмы кодирования, визуального отображения информации и многое другое, то конкретная природа этой информации почти не имеет значения. Для разработчика системы управления базами данных (СУБД) важны общие принципы организации и эффективность поиска данных, а не то, какие конкретно данные будут затем заложены в базу многочисленными пользователями. Эти общие закономерности есть предмет информатики как науки.
Как вид практической деятельности, информатика используется в различных областях, где она является непрерывным источником современных технологий. Многообразные информационные технологии, функционирующие в различных видах человеческой деятельности (управлении производственным процессом, проектировании, финансовых операциях, образовании и т. п.) имеют общие черты, в то же время существенно различаются между собой

Q: 3. Место информатики в системе наук
A: По Ершову, информатика – фундаментальная естественная наука.
Фундаментальная наука – наука, основные понятия которой носят общенаучный характер и используются во многих других науках и видах деятельности. Пример: математика и философия. Информатика в этом ряду, т. к. понятия «информация» и «процессы обработки информации» носят общенаучную значимость.
Естественная наука – наука, имеющая дело с объективными сущностями мира, существующими независимо от нашего сознания. Пример: физика, химия, биология. Отнесение к ним информатики отражает единство законов обработки информации в системах разной природы – искусственных, биологических, общественных.
Также информатика имеет черты технических и гуманитарных.
Черты технической науки информатика получает из аспектов, связанных с функционированием и созданием машинных систем обработки информации.
Черты гуманитарной науки обусловлены вкладом информатики в развитие и совершенствование социальной сферы.
Таким образом информатика – комплексная, междисциплинарная отрасль научного знания.

Q: Часть 3 вопроса. 3.1.Составные части современной информатики
A: (Информация, которая может быть в тесте, но которой нет в списке билетов)
В структуре информатики выделяют шесть основных научно-технических направлений:
1. Программирование.
2. Вычислительная техника – раздел, в котором разрабатываются общие принципы построения вычислительных систем.
3. Прикладная информатика – раздел, изучающий конкретные разновидности систем и технологий, формирующихся с помощью специальных информационных систем (управленческих, медицинских, обучающих, военных и др.).
4. Кибернетика – раздел, изучающий вопросы управления с помощью различного рода информационных сигналов. Включает в себя техническую кибернетику, распознавание образов, нейрокибернетику, математическую лингвистику.
5. Искусственный интеллект – направление информатики, цель которого – разработка аппаратно-программных средств, позволяющих пользователю-непрограммисту ставить и решать свои задачи, традиционно считающиеся интеллектуальными, общаясь с ЭВМ на ограниченном подмножестве естественного языка. Включает в себя робототехнику и экспертную систему.
6. Теоретическая информатика – раздел информатики, использующий математические методы для общего изучения процессов обработки информации. Включает в себя теорию алгоритмов, теорию автоматов, теорию информации, теорию формальных языков, системный анализ и др.

Q: 4. Роль информации в современном обществе
A: Информационная революция – преобразование общественных отношений из-за кардинальных изменений в сфере обработке информации.
1-я – изобретение письменности
2-я – изобретение книгопечатания
3-я – изобретение электричества, вызвавшая появление телеграфа, телефона, радио.
4-я – изобретение микропроцессоров и персонального компьютера.

Q: 5. Свойства информации
A: Основные свойства информации:
• Запоминаемость
• Передаваемость – способность к копированию
• Преобразуемость – способность менять способ и форму существования
• Воспроизводимость - характеристика неиссякаемости. При копировании остаётся тождественной самой себе
• Стираемость

Q: 6. Основные понятия информатики (информация, представление, интерпретация)
A: Информация – абстрактное содержание какого-либо высказывания, описания, указания, сообщения или известия.
Информационная технология – процесс, использующий совокупность средств и методов сбора, обработки и передачи данных для получения информации нового качества о состоянии объекта, процесса или явления.
Телекоммуникации – дистанционная передача данных на базе компьютерных сетей и современных технических средств связи.
Информационный процесс – процесс, в результате которого осуществляется приём, передача (обмен), преобразование и использование информации.
Представление – внешняя форма изображения информации
Интерпретация – переход от представления к абстрактной информации, т. е. к значению представления.

Q: 6.1 Информационные процессы
A: Основных информационных процессов 3: хранение информации (на внутренней памяти человека («оперативной памяти») или на внешней памяти), передача информации (распространение между людьми, которые являются источниками и приёмниками информации), обработка информации.

Q: 7. Информационная система в информатике
A: В информатике рассматриваются информационные система вида (A, R, I), где R – множество представлений с интерпретацией I во множестве A элементов (информаций).

Q: 8. Семантически эквивалентные изображения
A: информационной системе (A, R, I) два изображения r1, r2 ∈R называются семантически эквивалентными, если они несут одинаковую информацию I[r1] = I[r2].

Q: 9. Условия существования отображений на множестве информаций
9.1 Системы нормальных форм
A: Не все эквивалентные способы изображения информации одинаково легко интерпретируются (Пример: 0.(9), 0!, 1. Все эти термы имеют значение «один»). Подмножество S (изображений простой внешней формы) множества изображений R выделяется как множество нормальных форм, тогда S – система нормальных форм.
Если в такой системе для каждого изображения существует хотя бы одна семантически эквивалентная нормальная форма, то СНФ называется полной. Если любое множество изображений с одинаковой интерпретацией имеет единственную НФ, то СНФ называется однозначной.

Q: 10. Измерение информации. Вероятностный и объёмный подходы к измерению информации.
10.1 Непрерывная и дискретная информация
A: Носитель информации – некоторая материальная субстанция, необходимая для переноса сообщения от источника к получателю.
Сигнал – сообщение, передаваемое с помощью носителя.
Параметр сигнала – использующаяся для представления сообщения характеристика процесса передачи.
Модуляция – изменение одного или нескольких параметров выбранного сигнала в соответствии с передаваемой информацией.
Канал связи – совокупность средств, предназначенных для передачи сообщений.
Верность передачи – мера соответствия принятого сообщения посланному сообщению.
Помехи – возмущения, как внешние, так и внутренние, вызывающие отклонение принятых сигналов от переданных сигналов.
Линия связи – среда, обеспечивающая поступление сигналов от передающего устройства к приёмному устройству.
Кодирование – преобразование сообщения в сигнал, удобный для передачи по данному каналу связи.
Сигнал делится на:
• Дискретный, когда параметр сигнала принимает последовательное во времени конечное число значений (и все они могут быть пронумерованы). Сообщение, передаваемое с помощью таких сигналов, называется дискретным сообщением.
• Непрерывный, когда параметр сигнала есть непрерывная функция от времени. Сообщение, соответственно, называется непрерывным сообщением.

Q: 10.2 Измерение информации. Вероятностный и объёмный подходы к измерению информации.
A: Определить понятие количества информации довольно сложно, но в решении этой проблемы существуют два подхода.
Вероятностный подход (Разработан Клодом Шенноном)
(P.S. вывод формул Хартли и Шеннона не будет представлен в этом конспекте, так как сам вывод не несёт непосредственной важности для экзамена. Более подробно описано в Теоретическом материале №2 на course.sgu.ru)
Вероятностный подход основан на понятиях количества информации и энтропии. Рассмотрим опыт, связанный с бросанием игральной кости с N гранями (самый популярный случай N = 6). Результатом опыта может быть выпадения грани со знаком 1, 2, …, N.
Энтропия – численная величина, измеряющая неопределённость.
Процедуру бросания кости можно описать следующим образом:
Готовимся бросить кость. Исход опыта неизвестен, т. е. имеется некоторая определённость, которую обозначим за H1.
Кость брошена. Информация об исходе опыта получена. Количество этой информации обозначим за I.
Неопределённость данного опыта после его осуществления обозначим за H2.
Количество информации – разность неопределённостей, имевшихся «до» и «после» опыта. I = H1 + H2.
Формула Хартли – формула, позволяющая вычислить количество информации, требующееся для однозначного выбора одного исхода, исходя из количества исходов опыта:
Единицей измерения принимается количество информации, требующееся для однозначного выбора одного из двух исходов, которое называется бит.
Если же все события не равновероятно, то применяем Формулу Шеннона
Где I – количество информации, H – количество энтропии, Pi – вероятность i-го события, n – количество исходов, m – количество событий
Объёмный подход
В двоичной системе счисления знаки 0 и 1 будет называть битами.
Объём информации – количество требуемых для записи двоичных символов.

Q: 11. Алгоритмы. Свойства алгоритмов.
A: (Интуитивное понятие алгоритма) Алгоритм – способ с точным (т. е. выраженным в точно определённом языке) конечным описанием применения практически выполнимых элементарных шагов переработки информации.
Для алгоритмов важно различать постановку задачи, которая должна быть решена с его помощью, и специфичный способ, которым решается задача, при этом для алгоритма различают элементарные шаги обработки, которые имеются в распоряжении, и описание выбора отдельных, подлежащих выполнению шагов.
К свойствам алгоритма относят:
• Массовость – алгоритм разрабатывается для целого класса задач
• Дискретность – алгоритм представляется в виде конечной последовательности шагов
• Определённость – каждый шаг определён точно и недвусмысленно. Перед началом каждого шага определены все необходимые ему данные.
• Эффективность – из нескольких вариантов решения выбирается тот, что потребует меньше ресурсов.
Терминистический алгоритм – тот, что завершается за конечное число шагов.
Детерминированный алгоритм – тот, в котором нет свободы в выборе очередного шага.

Q: 12. Рекурсивные функции и сопутствующие им алгоритмы.
A: (P.S. Более подробно про все РФ и сопутствующие алгоритмы с примерами можно ознакомиться в Теоретическом материале №3 на course.sgu.ru)
Рекурсивные функции (РФ) строятся на множестве целых неотрицательных чисел посредством определения 3 базовых РФ, для которых сопутствующие алгоритмы одношаговые. Затем используются 3 приёма, называемые операторами подстановки, рекурсии и минимизации, с помощью которых на основе базовых функций строятся более сложные РФ. По существу, приведённые операторы – алгоритмы, с помощью которых получают более сложные алгоритмы.
Простейшие базовые функции:
Функция произвольного количества аргументов, тождественно равная нулю. φn , где n – количество аргументов. (φ3(4, 56, 789) = 0)
Тождественная функция. ψn, i , где n – количество аргументов, i – номер аргумента, которому функция тождественно равна. (ψ4, 3(56, 754, 42, 8) = 42)
Функция получения последователя. λ. (λ(99) = 100)
Приёмы построения сложных функций:
Оператор подстановки F(f1,…, f¬n). Вычисляются значения функций f1,…, f¬n и используются как аргументы при вычислении F.
Оператор рекурсии R. f ::= R[f1, f2, x(y)]. Функция f принимает n аргументов, функция f1 содержит (n-1) аргумент, а функция f2 (n+1) аргумент. x – главный дополнительный аргумент (ГДА), y – вспомогательный дополнительный аргумент (ВДА). Значением искомой функции при нулевом ГДА считать значение функции f1, а при каждом последующем ГДА – значение функции f2 для предыдущего значения ГДА и для значения ВДА, совпадающего со значением искомой функции на предыдущем этапе. (P.S. простыми словами, при ненулевом значении ГДА, ГДА – это аргумент функции f на предыдущем этапе, а ВДА – это значение функции на предыдущем этапе).
Оператор минимизации. f ::= μ[f1, (x)]. Строит новую функцию f с помощью функции f1 имеющей (n+1) аргументов и дополнительного исчезающего аргумента. Алгоритм: придаём последнему аргументу значения, начиная с нуля, вычисляя при этом значение функции f1, как только значение функции f1 станет равным нулю, значение дополнительного аргумента принимаем за значение искомой функции для тех главных аргументов, для которых вычислялось значение функции f1

Q: 13. Применение правил текстовых замен
A: Пусть V запас знаков. V ∗ множество всех конечных цепочек симво-
лов из V . Пустая цепочка, т.е. цепочка, не содержащая ни одного символа,
обозначается ε. Пара (v, w) ∈ V ∗ × V ∗ называется заменой над V . Замена
часто записывается в виде v → w.
Конечное множество R замен будем в дальнейшем называть системой тек-
стовых замен (СТЗ) над V . Элементы системы будем называть правилами
текстовых замен (ПТЗ). СТЗ служат для представления алгоритмов, отдель-
ные шаги которых состоят в применении правил замен.
Замена s → t называется применением правила v → w, если имеются
слова a, v, w, z ∈ V ∗ такие, что справедливо s = a · v · z, t = a · w · z.
Слово s ∈ V ∗ называется терминальным (или терминалом) в R, если не
существует слова t ∈ V ∗ такого, что справедливо следующее: замена s → t
является применением какого-либо правила из R. Таким образом, к терми-
нальному слову s нельзя больше применить никакого правила замены.

Q: 14. Системы текстовых замен.
A: Пусть V – запас знаков. V* - множество всех конечных цепочек символов из V. Пустая цепочка, т.е. цепочка, не содержащая ни одного символа, обозначается ε. Пара (υ,ω) ∈ V* × V* называется заменой над V. Замена часто записывается в виде υ→ω.
Конечное множество R замен будем в дальнейшем называть системой текстовых замен (СТЗ) над V. Элементы системы будем называть правилами текстовых замен (ПТЗ). СТЗ служат для представления алгоритмов, отдельные шаги которых состоят в применении правил замен.
Замена s→t называется применением правила υ→ω, если имеются слова a,v,ω,z ∈V* такие, что справедливо s = a∙v ∙z, t = a ∙w ∙z.
Слово s∈V* называется терминальным (или терминалом), в R, если не существует слова t ∈V* такого, что справедливо следующее: замена s→t является применением какого-либо правила из R.

Q: 15. Вычисления
A: Вычисления – последовательность применения ПТЗ.
Если t0, t1, …, tn принадлежат V* и ti → ti+1 есть применение некоторого правила из R для всех i 0 ≤ i < n, то последовательность (ti) 0 ≤ i ≤ n называют (конечным) вычислением над R для t0. Часто вычисление записывается следующим образом: t0 → t1 → … → tn.
Слово t0 называется входом для вычисления. Если tn – терминал, то вычисление называется завершающимся (конечным) с результатом tn (выходом). Бесконечная последовательность (ti) i ∈ N из слов ti ∈ V*, для которых ti → ti+1 есть применение некоторого ПТЗ из R для всех i ∈ N, называется не завершающимся (бесконечным) вычислением.

Q: 16. Алгоритмы текстовых замен.
A: Система текстовых замен R в силу следующего предписания определяет алгоритм текстовых замен (АТЗ), который использует слова над V в качестве входа и выхода. Для входного слова t ∈V* алгоритм работает следующим образом: «Если одно из правил множества R применимо к слову t (т. е. существует слово s∈V*, для которого имеет место: t → s есть применение правила из R), то примени правило к t и затем примени снова этот же алгоритм к s. В противном случае прекрати выполнение алгоритма.
Алгоритмы в виде текстовых замен в общем случае являются недетерминистическими и недетерминированными. Для входного слова t существуют, как правило, разные вычисления, с различными результатами. При этом для одной и той же задачи могут существовать как завершающиеся, так и не завершающиеся вычисления.

Q: 17. Марковская стратегия в алгоритмах текстовых замен.
A: Алгоритмы Маркова являются детерминированными.
Алгоритм Маркова: «Если к слову применимо несколько правил, то фактически применяется то из этих правил, которое в описании алгоритма встречается первым. Если правило применимо в нескольких местах обрабатываемого слова, то выбирается самое левое из этих мест».
Таким образом, благодаря детерминированности марковских алгоритмов справедливо следующее:
• Каждое вычисление по марковской стратегии является также общим вычислением в СТЗ
• Для каждого входного слова существует точно одно конечное или же бесконечное марковское вычисление.

Q: 18. Понятие вычислительной структуры
A: Алгоритмы работают над элементами данных, которые могут быть объединены в так называемый носитель. Для формулирования алгоритмов наряду с используемыми элементами данных весьма существенны имеющиеся в распоряжении эффективные функции над этими элементами.
Вычислительные структуры – совокупность фигурирующих в алгоритмах носителей и операций.

Q: 19. Сигнатуры
A: Сигнатура Σ — есть пара (S, F) множеств S и F обозначений, причем S обозначает множество типов, т. е. имен для носителей, F — множество символов (имен) функций; для каждого символа функции f ∈ F пусть задана ее функциональность f ct f ∈ S+.
Для улучшения читаемости при задании функциональности для f будем писать: f ct f = (s1, . . ., sn)sn+1
Пример: Вычислительная структура: BOOL, тогда
SBOOL = (bool)
FBOOL = true, f alse, ¬, ∨, ∧
f ct true = bool
f ct false = bool
f ct¬ = (bool)bool
f ct∨ = (bool, bool)bool
f ct∧ = (bool, bool)bool
Сигнатуры допускают наглядное графическое представление в виде диаграммы, которая для каждого типа содержит узел и для каждого n-местного символа операции — дугу с n входными узлами и одним выходным узлом. Для вычислительной структуры bool, дополненной работой с натуральными числами, мы получаем диаграмму сигнатуру, показанную слева.

Q: 20. Основные термы.
A: При заданной сигнатуре существует множество основных термов, которые могут быть образованы с помощью символов функций сигнатур.
Определение множества основных термов – Пусть Σ = (S, F) есть сигнатура.
• каждый нульместный символ функции f ∈ F с f ct f = s образует основной терм типа s;
• каждая последовательность символов f(t1, . . ., tn) с f ∈ F и функциональностью f ct f = (s1, . . . , sn)s есть основной терм типа s, если для всех i, 1 ≤ i ≤ n, ti есть основной терм типа si.
Обозначение множества основных термов: WΣ.
Обозначение множества основных термов типа s: Wσs.
Не существует нульместных символов функций ⇒ множество WΣ пусто.
Интерпретация - Переход от основного терма (представления) t типа s к соответствующему элементу a из множества A называют интерпретацией t в A.
Если имеется вычислительная структура A с сигнатурой Σ, то основные термы в A допускают интерпретацию.
Для каждого основного терма t запись IA[t] обозначает интерпретацию I в A. Пишут также tA вместо IA[t].
Интерпретация получается заменой в основном терме символов функций на соответствующие функции: IA[f(t1, . . . , tn)] = fA(IA[t1], . . . , IA[tn]).
Структура А называется термопроизводимой ⇔Если для каждого элемента a (!= ⊥) носителей из A имеется представление терма, т. е. для каждого s и каждого a ∈ sA (!= ⊥) существует основной терм типа s с tA = a.

Q: 21. Термы с идентификаторами.
A: Идентификатор («обозначатель», «переменная», «неизвестное») – держатель места («имя») для терма (или элемента), который может быть подставлен на это место. Идентификаторы могут пониматься как имена термов или элементов, которые позднее будут конкретизированы.
Примеры (термы с идентификаторами). 1. Уравнения с «неизвестными» в математике — это уравнения между термами с идентификаторами, например ах2 + bx + c = 0.
Термы со свободными идентификаторами называются также полиномами.
Вместо идентификаторов в термы могут подставляться другие термы:
Пусть t — терм с идентификаторами, x — идентификатор типа s и r —терм типа s; через t[r/x] обозначается терм, который получается, когда идентификатор x заменяется на r. Этот процесс называется подстановкой.
Соответствующее отображение называется подстановкой в термы с (свободными) идентификаторами.
Пусть t — терм с (свободными) идентификаторами.
Терм r называется экземпляром t ⇔ r получается из t путем замены (подстановки) в нем определенных (свободных) идентификаторов.

Q: 22.Алгоритмы, как системы подстановки термов.
A: Наиболее наглядный метод описания алгоритмов как системы текстовых замен предлагают системы подстановки термов. Ранее было показано, что термы могут строиться над заданной сигнатурой по определенным, четким правилам. Правила преобразования термов могут быть определены так, что термы всегда будут переводиться в семантически эквивалентные термы.
Вспом. Опр.: Для заданной сигнатуры Σ и заданного семейства X множеств идентификаторов пара (t, r) термов t, r одинакового типа с (свободными) идентификаторами из X называется подстановкой термов, правилом подстановки термов (ППТ), а также схемой подстановки термов.
Правило записывается в виде t → r.
В большинстве случаев для ППТ требуется, чтобы все идентификаторы, встречающиеся в r, также входили в t.
Вспом. Опр.: Множество (в общем случае конечное) R правил подстановки термов на сигнатуре Σ называется системой подстановки термов (СПТ) над Σ.
Терм t называется терминальным для системы R, если не существует терма r такого, что t → r есть применение правила из R.
Система R называется терминированной, если не существует не завершающихся вычислений.
Пример (СПТ для вычислительной структуры BOOL). Ниже символы функций ¬, ∨ будут использоваться в скобочной префиксной и инфиксной формах записи. Правила подстановок термов гласят:
(¬true) → false и (¬false) → true
(false ∨ x) → x и (x ∨ false) → x
(true ∨ true) → true
Алгоритмы подстановки термов
Пусть задана система подстановок R. R определяет алгоритм в силу следующего предписания (алгоритм получает в качестве входного слова основной терм t).
1. Если R содержит правило подстановки с применением t → r, то далее алгоритм продолжается с использованием r вместо t.
2. Если R не содержит правила подстановки с применением t → r, то алгоритм заканчивается с t в качестве результата.
Алгоритм подстановки термов (АПТ) тем самым выполняет вычисление в R для каждого основного терма t. Часто вычисление состоит в решении задачи преобразования заданного основного терма в определенную заранее заданную нормальную форму.
Если АПТ начинает работать с заданным основным термом t, то t называют также входом для алгоритма;
если алгоритм завершается основным термом r, то r называется также выходом или результатом.

Q: 23. Различные представления числовой информации. (С фиксированной и плавающей точкой.)
A: В ЭВМ применяются две основные формы представления чисел: полулогарифмическая с плавающей запятой и естественная с фиксированным положением запятой.
При представлении чисел с фиксированной запятой её положение закрепляется в определенном месте, относительно разрядов числа (обычно перед старшим разрядом или после младшего) и сохраняется неизменным для всех чисел, изображаемых в данной разрядной сетке.
Для кодирования знака числа используется старший («знаковый») разряд.
Переполнение разрядной сетки – получение в результате арифметических операций над правильными дробями двоичных чисел, по абсолютной величине больших или равных единице.
Диапазон представления правильных двоичных дробей:
2-(n-1) ≤|A| ≤1 – 2-(n-1)
Машинный нуль - числа, меньшие по абсолютной величине единицы младшего разряда разрядной сетки.
Диапазон представления целых двоичных чисел со знаком в n-разрядной сетке:
0 ≤|A| ≤2n-1 – 1
Представление чисел с плавающей запятой в общем случае имеет вид:
A = m * Np, где N – основание системы счисления, p – целое число, называемое порядком числа A, m – мантисса числа A (m < 1)
Т. к. в ЭВМ применяется двоичная система счисления, то представление чисел с плавающей запятой в ней имеет вид:
A = m * 2p. Порядок и мантисса представлены в двоичной форме.
Нормализованное двоичное число – число, у которого мантисса удовлетворяет неравенству 1/2≤m<1.
Триггер – техническое устройство, которым в ЭВМ представляется разряд двоичного числа и двум различным состояниям которого приписываются значения 0 и 1.
Регистр – группа триггеров, предназначенная для представления в ЭВМ многоразрядного числа.

Q: 24. Системы счисления. Правила перевода.
A: Система счисления – система приёмов и правил, позволяющих устанавливать взаимно-однозначное соответствие между любым числом и его представлением в виде совокупности конечного числа символов.
Цифры – множество символов, используемых для такого представления
Непозиционная система счисления – значение цифры не зависит от её положения в числе
Позиционная система счисления – значение цифры зависит от её положения в числе.
В позиционной системе счисления любое число записывается в виде последовательности цифр:
A = am-1am-2…ak…a0, a-1…a-L
Позиции, пронумерованные индексами k (-L ≤ k ≤ m-1) называются разрядами числа.
Количество различных цифр N, используемых для изображения чисел в позиционной системе счисления называется основанием системы счисления. Оно указывает на то, во сколько раз единица (k+1)-го разряда больше единицы k-го разряда. Тогда любое число может быть представлено в виде суммы:
Перевод числа из одной системы в другую выполняется по универсальному алгоритму, заключающемуся в последовательном делении целой части числа и образующихся целых частных на основание новой системы счисления, записанное в исходной системе счисления, и в последующем умножении дробной части и дробных частей получающихся произведений на то же основание, записанное в исходной системе счисления. При переводе целой части получающиеся в процессе последовательного деления остатки представляют цифры целой части числа в новой системе счисления, записанные цифрами исходной системы счисления. Последний остаток является старшей цифрой переведённого числа.

Q: 25. Представление отрицательных чисел в ЭВМ.
A: Прямой код – запись двоичного числа с использованием старшего («знакового») разряда.
Формула для образования прямого кода правильной дроби:
[A] = A, если A ≥0
[A] = 1 – A, если A < 0
Формула для образования прямого кода целого числа:
[A] = A, если A ≥0
[A] = 10n-1 – A, если A < 0. (n – количество позиций в разрядной сетке)
Прямой код в ЭВМ применяется только для представления положительных двоичных чисел. Для отрицательных чисел применяется либо дополнительный, либо обратный код.
Формула для образования дополнительного кода дроби:
[A] = 10 + A
Формула для образования дополнительного кода целого числа:
[A] = 10n + A. (n – количество позиций в разрядной сетке)
Формула для образования обратного кода дроби:
[A] = 10 – 10-(n-1) + A. (n – количество позиций в разрядной сетке)
Формула для образования обратного кода целого числа:
[A] = 10n – 1 + A. (n – количество позиций в разрядной сетке)

Q: 26. Методы контроля передаваемой информации.
A: Контроль чётности/нечётности – к сообщению добавляется один контрольный бит, значение которого устанавливается так, чтобы общее число единиц в сообщении было чётным/нечётным. При проверке подсчитывается количество единиц и, если чётность сохранилась, то делается вывод о правильности передачи.
CRC-код - над сообщением проводится ряд математических преобразований и результат дописывается. При проверке преобразования выполняются снова и сравнивается результат. Если CRC-код не совпадает, то делается вывод о наличии ошибок.

Q: 27. Дистанция Хэмминга и её применение.
A: Дистанция Хэмминга – количество попарно различных бит между двумя сообщениями одинаковой длины в соответствующих разрядах.
Если каждая пара сообщений имеет дистанцию Хэмминга не менее 3, то можно определить до 2 ошибок, а исправить одну. Действительно, изменение одного бита в одном из двух сообщений изменит дистанцию Хэмминга между ними на 1 (увеличит/уменьшит). Тогда сообщение с одной ошибкой будет иметь с истинным сообщением дистанцию 1, а со всеми остальными не менее 2. Пример работы на рисунке:

Q: 28. Коды Хэмминга, исправляющие единичную ошибку.
A: Определим количество контрольных разрядов из соотношения:
2¬k > m + k,
Где m – длина кодируемого сообщения, а k минимально возможное целое число.
Контрольные биты располагаем в позициях, номера которых представляют собой степень двойки (1, 2, 4, 8…). Каждый из контрольных разрядов отвечает за свою группу (см. рис. 1). Так, 1-й контрольный бит отвечает за 1, 3, 5, 7, 9 и т.д. разряды, 2-й за 2, 3, 6, 7, 10, 11 и т.д., 3-й за 4, 5, 6, 7, 12, 13, 14, 15 и т.д.
Значение контрольного бита устанавливаем таким образом, чтобы после установки количество единиц в его группе стало чётным.
При проверке сообщения на ошибки определяется чётность каждой из k групп. Если все группы дали значение 0, т. е. в каждой из них чётное количество единиц, то ошибки нет. Если же хотя бы одна группа дала значение 1, то контрольные биты, записанные справа налево дадут двоичное представление номера разряда, в котором допущена ошибка.

Q: 29. Спецификация программ и правила вывода
A: Каждый алгоритм имеет как статическую, так и динамическую структуру. Статическая структура представляется текстом, описывающим действия и проверки, которые должны быть выполнены при решении данной задачи. Текст не зависит от исходных данных. Динамическая структура, наоборот, во многом определяется набором входных данных. Динамическая структура отражает процесс вычислений и состоит из последовательности состояний вычислений.
Методы композиции в языках программирования позволяют формировать структурные операторы из других простых или составных операторов. Фундаментальное свойство всех рассматриваемых видов композиции заключается в том, что они дают возможность объединить в одну сложную структурную схему с одним входом и одним выходом. Каждая такая структурная схема имеет вид, показанный на рис. 2, где S – отдельное действие ЭВМ, или сложная схема. В более краткой форме такая схема изображается следующим образом:
{P}S{Q}
Это соотношение – спецификация программы, которая означает, что если соотношение P истинно перед выполнением S, то Q будет истинно после завершения выполнения S.
Если S – программа, корректность которой требуется установить, то соотношение выше – то, что требуется доказать, причём P – соотношение, которому должны удовлетворять начальные значения переменных, а Q – соотношение, которому должны удовлетворять конечные значения переменных, соответственно.
Исходя из того, что если P истинно на входе, то Q – истинно на выходе, получается, что {P}S{Q} тождественно истинно, если S не завершается. Таким образом, это соотношение определяет только частичную корректность программы. Частично корректной считается та программа, которая гарантирует получение требуемого результата при её завершении.
Этапы проектирования программ:
• Начинается со спецификации {P}S{Q}, которой должна удовлетворять проектируемая программа.
• Процесс проектирования сверху вниз определяет спецификации {Pi}Si{Qi}, для компонентов Si из которых строится программа.
• Проектирование программы осуществляется одновременно с доказательством корректности указанных спецификаций.

Q: 30. Правила консеквенции.
A: P.S. судя по заданиям с экзамена, то сам процесс вывода правил не нужен, важно только знание итогового правила. Поэтому сам процесс вывода правил лучше прочитать, но учить не обязательно)
Правила вывода – схемы рассуждений, которые позволяют доказывать свойства программ. Имеют вид: (H1,...,Hn)/H. Если H1, …, Hn – истинные утверждения, то H – также истинное утверждение.
Правила консеквенции являются простейшими правилами вывода.
Первое правило консеквенции
Если выполнение программы S обеспечивает истинность утверждения R, то оно также обеспечивает истинность каждого утверждения, которое следует из R, т. е.
({P}S{R},R→Q)/({P}S{Q})
Второе правило консеквенции
Если R – известное предусловие программы S, приводящей к результату Q после завершения своего выполнения, то это же относится к любому другому утверждению, из которого следует R. Т. е.
(P→R,{R}S{Q})/({P}S{Q})

Q: 31. Правило вывода для простых операторов C++.
A: Eсли рассматривать случай, когда S – простой оператор (простейшей формой которого является пустой оператор), то получим правило для любого P:
{P}{P}
Также рассмотрим оператор присваивания. Пусть x = e – оператор присваивания, который устанавливает x равным значению выражения e. Тогда можем сделать вывод, что для любого P
{PeX}x = e{P}
Это означает, что если P истинно для подстановки e вместо x перед выполнением присваивания, то P должно быть истинным, когда переменной x присвоили её новое значение.

Q: 32. Правила вывода составных и условных операторов.
A: Простейшей формой структурирования является создание составных операторов, путём последовательной композиции, состоящей из действия S1, за которым следует действие S2. Такой оператор имеет вид
{S1; S2; …; Sn¬;}
И называется составным оператором.
Правило вывода для последовательной композиции гласит: если S есть {S1; S2;} и если имеют место {P}S1{R} и {R}S2{Q}, то истинно и {P}{S1;S2;}{Q}. Формально это выражено так:
Или в общем виде:
Теперь поговорим про условные операторы. Если S1 и S2 – операторы, а B – логическое выражение, то
If(B)S1; else S2
Есть оператор, обозначающий следующее действие: вычисляется B. Если его значение – истина, то должно быть выполнено действие, описываемое S1, в противном случае, действие описываемое S2.
Выработаем правило для условного оператора. Если требуется установить истинность {P}if(B)S1; else S2; {Q}, то необходимо доказать:
Если B истинно, то выполняется S1. Т. к. P истинно перед выполнением, то P∧B также истинно перед S1. Значит требуется доказать, что {P∧B}S1{Q}
Если B ложно, то выполняется S2. Т. к. P истинно перед выполнением, то P∧¬B справедливо перед выполнением S2. Тогда требуется доказать, что { P∧¬B}S2{Q}
Тогда сформулируем правило вывода:
Теперь рассмотрим вариант неполного условного оператора, который получается в случае, если S2 – пустой оператор. Дабы доказать {P}if(B)S; {Q} требуется обеспечить два условия:
Если S выполняется, то Q справедливо после завершения. Т. к. при условии истинности B выбирается для выполнения S, то выводим, что P∧B истинно перед выполнением S. А значит, надо доказать {P∧B}S{Q}
Если S не выполняется, то после вычисления B получается ложь. Для этого истинно P∧¬B, и если Q справедливо после выполнения условного оператора, то необходимо доказать, что P∧¬B →Q
Правило вывода формулируется следующим образом:

Q: 33. Правило вывода для циклов
A: Цикл с предусловием имеет вид:
while(B)S;
Где B – логическое выражение, а S – оператор. Обозначает итерационное выполнение оператора S, пока B истинно.
Цикл с постусловием имеет вид:
do S while(B)
Оператор итерации (цикл) определяет, что S выполняется перед вычислением B. Затем, если B истинно, процесс итерационного выполнения S продолжается, в противном случае заканчивается.
Рассмотрим, что требуется для вывода правила цикла с постусловием.