Всё для Учёбы — студенческий файлообменник
2 монеты
zip

Шпаргалка «Экзаменационная» по Информатике (Федоренко Н. М.)

9. Позиционные системы счисления. Примеры.

Определение 1: Система счисления или нумерация – это способ записи чисел.

Определение 2: Символы, при помощи которых записывают числа, называются цифрами, а их совокупность – алфавитом системы счисления. Количество цифр, составляющих алфавит, называются его размерностью.

Определение 3: Система счисления называется позиционной, если количественный эквивалент цифры зависит от её положения в записи числа. В привычном нам десятичной системе значение числа образуется следующим образом: значение цифр умножаются на «веса» соответствующих разрядов и все полученные значения складываются. Например, 5047=5*1000+0*100+4*10+7*1. Такой способ называется аддитивно-мультипликативным.

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

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

Определение 5: Позиционную систему счисления называют традиционной, если её базис образует члены геометрической прогрессии, а значение цифр есть целые неотрицательные числа. Так, базисы десятичной, двоичной и восьмеричной систем счисления образует геометрические прогрессии со знаменателями 10, 2 и 8 соответственно. В общем виде базис можно записать так: …Р^-3, P^-2, P^-1, 1, P, P^2, P^3,…, P^n,….

Определение 6: Знаменатель Р геометрической прогрессии, члены которой образуют базис традиционной системы счисления, называется основанием этой системы счисления. Традиционные системы счисления с основанием Р называются Р-ичными. В таких системах размерность алфавита равна основанию системы счисления. Так, алфавит десятичной системы счисления составляют цифры 0,1,….9. Алфавитом произвольной системы счисления с основанием Р составляют цифры 0,1….,Р-1 .

В класс позиционных систем счисления входят также системы, в которых либо базис не является геометрической прогрессией, а цифры есть целые неотрицательные числа, либо базис является геометрической прогрессией, но цифры не являются целыми неотрицательными числами. К первым можно отнести факториальную и фибоначчиеву системы счисления, ко вторым – уравновешенные системы счисления. Такие системы будут называться нетрадиционными. Алфавитом фибоначчиевой системы счисления являются цифры 0 и 1, а её базисом – последовательность цифр Фибоначчи 1,2,3,5,8,13,21,34,55,89…. Базисом факториальной системы счисления является последовательность 1!, 2!,…,n!,… В отношение алфавита этой системы можно сделать замечание: количество цифр, используемых в разряде, увеличивается с ростом разряда.

Примеры сами полюбому!)))

26. Алгоритм Евклида

Алгори́тм Евкли́да — алгоритм для нахождения наибольшего общего делителя двух целых чисел. Этот алгоритм применим также для нахождения наибольшего общего делителя многочленов. Кольца, в которых применим алгоритм Евклида, получили название Евклидовы кольца.

Евклид описал его в VII книге и в X книге «Начал». В обоих случаях он дал геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков. Алгоритм Евклида был известен в древнегреческой математике по крайней мере за век до Евклида под названием «антифайресис» — «последовательное взаимное вычитание».

a:b -> частное q и остаток b

a = bq0 + r1 b = r1q1 + r2

r1 = r2q2 + r3

rk является делителем предыдущего остатка

Последний ненулевой остаток (rk) – является НОД чисел a и b.

Пример:

НОД(1547,560)

1547=2*560+427 a q1 b r1

560=1*427+133 b q2 r1 r2

133=4*28+21

28=21*1+7 7/21

Нод(1547,560)=7

Теорема 1: алгоритм Евклида всегда даёт НОД за конечное число шагов.

Теорема 2: пусть d является НОД(а,б), а>b. Тогда сущ. такие целые числа u и v –

такие что d=u*a+v*b . Другими словами НоД двух чисел можно представить в виде линейной комбинации этих чисел с целыми коэффициентами

НОД(1547,560)=7

7(d)=21(u)*1547+58(v)*560

Определение: 2 числа взаимно простые, если НоД = 1

Классы языков программирования.

• Функциональные

• Императивные

• Стековые

• Процедурные

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

• Аспектно–ориентированные

• Декларированные

• Динамические языки программирования

• Учебные

• Описания интерфейсов

• Прототипные

• Объектно-ориентированные

• Рефлексивные

• Языки логического программирования

• Языки параллельного программирования

• Сценарные или скриптовые

• Эзотерические

Стековый язык программирования – это язык программирования, в котором для передачи параметров используется машинная модель стока. Этому описанию соответствует несколько языков, в первую очередь Forth и PostScript, а также многие ассемблерные языки (использующие эту модель на низком уровне – Java, C#). При использовании стека, в качестве основного канала передачи параметров между словами, элементы языка, естественным образом, образуют фразы ( последовательное сцепление). Это свойство сближает данные языки с естественными языками.

В языках функционального программирования основным конструктивным элементом является математическое понятие функции

К динамическим языкам относятся: Python, PHP, Ruby, JavaScript.

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

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

Скриптовый язык (язык сценариев) – язык программирования, разработанный для записи «сценариев», последовательностей операций, которые пользователь может выполнять на компьютере. Простые скриптовые языки раньше часто называли языками пакетной обработки (batch languages или job control languages). Сценарии обычно интерпретируются, а не компилируются. Пример РНР

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

Каноническим примером прототип-ориентированного языка является язык Self.

Язык Си был придуман в 1972 г. сотрудником Bell Laboratories (отделение известной телефонной компании AT&T) Денисом Ритчи, одним из первых пользователей операционной системы Unix. Задумывался он не как универсальный алгоритмический язык, а, скорее всего, как инструмент для развития операционной смстемы и создания новых обслуживающих программ.

В 1978 г. Появилась первая книга, посвященная описанию Си и технике Программирования на этом языке, которая с большим запозданием была переведена на русский язык (Б.Керниган, Д.Ритчи, Л.Фьюер. «Язык программированя Си. Задачи на языке Си». –М.: Финансы и статистика,1985). От фамилий двух первых авторов произошло сокращенное обозначение первого, никем не утверждавшегося,но принятого всеми программистами стандарта Си- K&R.

С 1983 г. за расширенной версией языка Си с классами закрепилось название С++.

Двоичная система счисления

Люди предпочитают десятичную систему, вероятно, потому, что с древних времен считали по пальцам. Но, не всегда и не везде люди пользовались десятичной системой счисления. В Китае, например, долгое время применялась пятеричная система счисления. В ЭВМ используют двоичную систему потому, что она имеет ряд преимуществ перед другими:

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

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

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

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

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

0 + 0 = 0 0 + 1 = 1

1 + 0 = 1 1 + 1 = 0 (перенос в старший разряд)

Таблица умножения для двоичных чисел еще проще:

0 * 0 = 0 0 * 1 = 0 1 * 0 = 0 1 * 1 = 1

Рассмотрим подробнее, как происходит процесс умножения двоичных чисел. Пусть надо умножить число 1101 на 101 (оба числа в двоичной системе счисления). Машина делает это следующим образом: она берет число 1101 и, если первый элемент второго множителя равен 1, то она заносит его в сумму. Затем сдвигает число 1101 влево на одну позицию, получая тем самым 11010, и если, второй элемент второго множителя равен единице, то тоже заносит его в сумму. Если элемент второго множителя равен нулю, то сумма не изменяется. Двоичное деление основано на методе, знакомом вам по десятичному делению, т. е. сводится к выполнению операций умножения и вычитания. Выполнение основной процедуры -- выбор числа, кратного делителю и предназначенного для уменьшения делимого, здесь проще, так как таким числом могут быть только либо 0, либо сам делитель. Следует отметить, что большинство калькуляторов, реализованных на ЭВМ (в том числе и KCalc) позволяют осуществлять работу в системах счисления с основаниями 2, 8, 16 и, конечно, 10.

Достижения отечественной информатики.

40 – 50 годы – разработка синтеза релетивно-контактных схем -> принципы проектирования ЭВМ. Начался серийный выпуск ЭВМ «стрела» и «м-20» (1953 и 1958)

 БЭСМ – 6 (50 годы)  киевские машины «МИР» (60-70гг). «МИР» «Аналитик»  аналитический блок вычислений. С 1952 по 1953 академиком Лягуновым был предложен оперативный метод описания программ. Это положило начало перехода от машинного кода к языкам высокого уровня. В 1953 году им же была поставлена задача автоматизации программирования. В 1953-54 Контаровичем была разработана технология крупноблочного программирования (основы библиотечного программирования, начало основ объективноориентированного программирования) Цетлин положил начало создания теории коллективного поведения технических систем. Ершов: Альфа-трансляторы(теория компиляции и компелирования) и оптимизация программного кода. Машинный перевод и анализ текста под руководством Колмагорова и Ляпунова.

К числу первых алгоритмических языков, получивших достаточно широкое распространение, относятся Фортран (FORTRAN – от FORmula TRANslation, «трансляция формул») и Алгол ( ALGOL – от ALGOrithmic Language, «алгоритмический язык»). Первый из них родился в недрах фирмы IBM в 1954 г. И активно поддерживался этим наиболее могущественным концерном по производству средств вычислительной техники. В нашей стране он стал широко известен в связи с переходом на выпуск ЭВМ Единой Системы (ЕС ЭВМ).

Алгол-60 появился как противовес Фортрану в результате объединенных усилий европейских ученых, представлявших, по большей части, акаденимическую и европейскую наука. Первые сведения о нем были опубликованы в 1958 г., но как стандарт языка он был утвержден в 1960 г. Алгол получил довольно широкое признание в нашей стране. Для него отечественными учебными были разработаны несколько систем программирования- ТА-1М, ТА-2М, Альфа. Однако следующий стандарт языка Алгол-68 практически остался академическим проектом и большого распространения не получил, т.к. в срочном порядке вытеснен Фортраном.

BASIC (Beginner’s All-purpose Symbolic Instruction Code, дословно переводится как «многоцелевой код (язык) символических инструкций для начинающих»). Днем рождения которого считается 1 мая 1964 г. В этот день в Дартмутском колледже (США) проявил первые признаки жизни интерпретатор, созданный студенческим коллективом во главе с профессорами Джоном Кемени и Томасом. Сегодня Бейсик используют в основном для обучения программированию.

Алгоритмический язык Паскаль был придуман в 1968 г. профессором Института информатики при Швейцарской высшей технической школе Ник-лауресом Виртом. В 1970 г. под его руководством был разработан первый компилятор, а в следующем году появилась и первая публикация. Свое название язык получил в честь известного французского математика Блеза Паскаля, который в 19- летнем возрасте изобрел первую суммирующую машину.

Кибернетика

Кибернетика – наука о закономерностях процессов управления и передачи информации в технических, биологических и социальных системах. Основатель – американский математик Винер, выпустивший в 1948 году книгу о кибернетике «О связях в живом и неживом» или «Ораторская связь». Кибернетика выделила общие закономерности управления в различных системах. В общую кибернетику обычно включают теорию информации, теорию алгоритмов, теорию автоматов, техническую кибернетику. Задачи кибернетики: установление факторов, общих для управляемых систем; выявление ограничений и их происхождение; нахождение общих законов, которым подчиняются управляющие системы; определение путей практического использования фактов и закономерностей. Существует несколько понятий кибернетики: управление, управляющая и управляемая система, организация, обратная связь, алгоритм, модуль и др. Для любой природы понятие управление – это воздействие на объект, выбранное на основе информации из множества воздействий, улучшающее его функционирование или развитие. Свойством управляемости может обладать не любая система, необходимое условие – её организованность. Существует 4 условия управления: каналы сбора информации об объекте, канал воздействия на объект, цель управления, алгоритм управления. Обратная связь: связь между объектом и управляющей системой. Если поведение объекта усиливает внешнее воздействие, то обратная связь увеличивается, если уменьшает, то уменьшается.

Пусть m - натуральное число, m1, m2, ..., mt - взаимно простые натуральные числа, произведение которых больше либо равно m.

Теорема

Любое число x: 0

Показать полностью…
Похожие документы в приложении