2 Билет.
Системы счисления. Переводы чисел из одной СС в другую.
СС может быть позиционной/непозиционной если значение цифры числа зависит/не зависит от местоположения цифры в числе.
Общепризнанной ПСС является десятичная СС.
В любой ПСС число разбивается на разряды слева направо, таким образом что единица соседнего старшего разряда в определенное число раз старше соседней единицы младшего разряда и основания. ПСС называет количество единиц какого либо разряда, объединяемых в единицу соседнего старшего разряда.
Основание СС в любой ПСС записывается как 10. Любое число в ПСС с основанием P>1 может быть представлено в сокращеной форме или в виде многочлена.
P - основание СС.
0<
<
P-1 называется базисными
цифрами. Количество базисных цифр равно
основанию СС.
Правила перевода
При рассмотрении правил перевода необходимо помнить правила арифметики какой СС вы пользуетесь.
"Своя СС" с осн. P
"Чужая СС" с осн. Q
Для перевода необходимо:
1) Записать число в виде многочлена.
2) базисные цифры и основание Q-ичной СС записать с помощью P-ичных чисел.
3) Выполнить арифметические действия.
Схема Горнера
= ((1*8+3)*8+2*8+1
Перевод из P в Q.
Перевод целых чисел.
1)Представим число в виде многочлена.
2)Разделим число на основание СС в которую переводим .
3)Предлагается делить целую часть на Q.
Переводы дробных чисел
1) Запишем
число в виде многочлена и умножим на q.
2) Продолжая
умножать дробную часть на Q
получим
-цифры
числа X в новом представлении.
3) Умножаем пока дробная часть не станет равной нулю.
3 Билет.
Смешанные
СС, переводы чисел для CC,связанных
соотношением P=
.
Cмешанные СС - это СС в которой каждая цифра P-ичного числа записывается с помощью n Q-ичных разрядов. где n- кол-во Q-ичных разрядов достаточных для записи старшей цифры P-ичной СС.
Переводы из P в Q
Достаточно каждую цифру P записать с помощью n Q-ичных разрядов.
Чтобы перевести число из Q в P нужно:
1) Разбить данное число влево и в право от запятой на группы по n-разрядов.
2) Неполные крайние группы дописать 0
3) Каждую группу записать с помощью одной P-ичной цифры.
1BF9,
-> 0001.1011.1111.1001,0011.0
->
4 Билет.
Понятия Алгоритма, Рекурсивные функции.
Алгоритм - этап для автоматизированного решения задач.
Алгоритм-способ описания сложных процессов любой природы
Алгоритм - Форма изложения научных результатов
Алгоритм - Способ обоснования математики
Алгоритмы могут строиться на основе наблюдений и экспериментов и называться имитационными.
Алгоритмы могут конструироваться из уже известных, но как бы не был создан алгоритм, он должен быть обоснован. Эти доказательства могут обосноваться математическими методами или экспериментами.
Алгоритм - это правило на каком либо языке и определяющее последовательность действий, преобразовывающих исходные данные в результаты.
Последовательность действий состоящих из четких, понятных шагов называется алгоритмическим процессом.
Основные свойства - Массовость, результативность и детерминированность.
Массовость -Алгоритм может использовать домножество для набора из множества допустимых исходных данных.
Результативность - потенциальная выполнимость алгоритма без ограничения по времени.
Детерминированность - однозначность шагов.
Благодаря математикам-конструктивистам существуют формы понятия алгоритма. Они связаны с понятиями рекурсивных функций, машин Тьюринга, норм. алгоритмов Маркова.
Рекурсивные функции.
Ограниченный объект или явление, внутри которого содержится подобный ему объект или явление.
В математике существует рекурсивное определение, а в информатике - рекурсивные функции.
В программе функцию называют рекурсивной если она обращается к самой себе на прямую или через серию других подпрограмм ( такие функции называются косвенно рекурсивными).
Если функция вызывает саму себя то в стеке сохраняется копия значений её параметров как при вызове обычной функции, и управление передается первому оператору тела функции.
При следующем обращении к самой себе параметры снова сохраняются в стеке, и так до тех пор, пока значение параметров не станет таким, что вычисление алгоритма пойдет не по рекурсивной ветви.