Информатика и информационные технологии: конспект лекций

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

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

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

Числа с фиксированной точкой в ЭВМ представляются как целые двоичные числа, и занимаемый ими объем может составлять 1, 2 или 4 байта.

32-разрядные процессоры могут работать с оперативной памятью емкостью до 232-1, а адреса могут записываться в диапазоне 00000000 – FFFFFFFF. Однако в реальном режиме процессор работает с памятью до 220-1, а адреса попадают в диапазон 00000 – FFFFF. Байты памяти могут объединяться в поля как фиксированной, так и переменной длины. Словом называется поле фиксированной длины, состоящее из 2 байтов, двойным словом – поле из 4 байтов. Адреса полей бывают четныеи нечетные,при этом для четных адресов операции выполняются быстрее.

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

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

Величина, которая может быть представлена символом двоичного алфавита, называется минимальной единицей информации или битом. Последовательность из 8 бит – байт. Алфавит, содержащий 256 различных 8-битных последовательностей, называется байтовым.

Дискретную информацию обычно отождествляют с цифровойинформацией, которая является частным случаем символьной информации алфавитного представления. Алфавит – конечный набор символов любой природы. Очень часто в информатике возникает ситуация, когда символы одного алфавита надо представить символами другого, т. е. провести операцию кодирования.Если количество символов кодируемого алфавита меньше количества символов кодирующего алфавита, то сама операция кодирования не является сложной, в противном случае необходимо использовать фиксированный набор символов кодирующего алфавита для однозначного правильного кодирования.
Как показала практика, наиболее простым алфавитом, позволяющим кодировать другие алфавиты, является двоичный, состоящий из двух символов, которые обозначаются, как правило, через О и 1. С помощью n символов двоичного алфавита можно закодировать 2п символов, а этого достаточно, чтобы закодировать любой алфавит.

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