В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543)
Текст из файла
В.А.Антонюк, А.П.ИвановПрограммированиеи информатикаКраткий конспект лекцийМоскваФизический факультет МГУ им.М.В.Ломоносова2015Антонюк Валерий Алексеевич, Иванов Алексей ПетровичПрограммирование и информатика. Краткий конспект лекций. –Физический факультет МГУ им. М.В. Ломоносова, 2015. – 52 с.М.:ISBN 978-5-8279-0126-6Издание представляет собой краткий конспект лекций по информатике, прочитанных на первом курсе физического факультета МГУ в 2012-2015 годах авторамиданного пособия. Обсуждаются как базовые численные, так и нечисленные алгоритмы: решения уравнений (методы дихотомии, хорд, касательных, итераций),вычисления определённых интегралов (формулы левых/правых/центральных прямоугольников, формула Симпсона), поиска (алгоритм Бойера-Мура), сортировки(пузырьковая, выбором, quicksort), методы Монте-Карло и способы получения случайных чисел, методы численного решения дифференциальных уравнений (Эйлера,предиктор/корректор, Рунге-Кутты, алгоритм Верле), интерполяции (многочленыЛагранжа), решения систем линейных уравнений (метод Гаусса), способы организации динамических данных (вектор, стек, дека, очередь, список, двоичные деревьяпоиска, ассоциативные контейнеры, B-деревья, хэш-таблицы).Рассчитано на студентов младших курсов физико-математических специальностей.Авторы – сотрудники кафедры математического моделирования и информатикифизического факультета МГУ.Рецензенты: доцент С.А.Шлёнов, директор ЦДО Д.Н.Янышев.Подписано в печать 28.12.2015.
Объем 3 п.л. Тираж 50 экз. Заказ №. Физическийфакультет им. М.В.Ломоносова, 119991 Москва, ГСП-1, Ленинские горы, д.1, стр. 2.Отпечатано в отделе оперативной печати физического факультета МГУ.ISBN 978-5-8279-0126-6ccФизический факультет МГУим. М.В. Ломоносова, 2015В.А.Антонюк, А.П.Иванов, 2015Содержание1.2.3.4.5.6.7.8.9.Представление чисел в компьютерах .
. . . . . . . . . . . . . . . . .1.1.Представление положительных целых чисел . . . . . . . . . .1.2.Представление отрицательных целых чисел: числа со знаком1.3.Представление вещественных чисел . . . . . . . . . . . . . . .Численное решение уравнений . . . . . . . . . . . . . . .
. . . . . . .2.1.Метод деления отрезка пополам (метод дихотомии) . . . . .2.2.Метод хорд . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.Метод касательных . . . . . . . . . . . . . . . . . . . . . . . .2.4.Метод итераций . . . . . . . . . . .
. . . . . . . . . . . . . . .Вычисление определённых интегралов . . . . . . . . . . . . . . . . .3.1.Квадратурные формулы левых и правых прямоугольников .3.2.Квадратурная формула центральных прямоугольников . . .3.3.Квадратурная формула трапеций . . . . . . . . .
. . . . . . .3.4.Квадратурная формула Симпсона (формула парабол) . . . .Алгоритмы поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1.Поиск элемента в массиве . . . . . . . . . . . . . . . . . . . .4.2.Алгоритм Бойера-Мура . . . . . . . . . . . . . . .
. . . . . . .Алгоритмы сортировки . . . . . . . . . . . . . . . . . . . . . . . . . .5.1.Пузырьковая сортировка . . . . . . . . . . . . . . . . . . . . .5.2.Сортировка выбором . . . . . . . . . . . . . . . . . . . . . . .5.3.Quicksort . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .Метод Монте-Карло . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.1.Определение площадей (объёмов) фигур . . . . . . . . . . . .6.2.Вычисление числа . . . . . . . . . . . . . . . . . . . . . . . .6.3.Численное интегрирование методом Монте-Карло . . . . .
.6.4.Получение случайных чисел . . . . . . . . . . . . . . . . . . .6.5.Линейный конгруэнтный метод . . . . . . . . . . . . . . . . .6.6.Метод регистра сдвига (с линейной обратной связью) . . . .6.7.Метод Фибоначчи с запаздываниями . . . . . . . . . . . . . .6.8.«Вихрь Мерсенна» (Mersenne Twister) . . .
. . . . . . . . . .Решение дифференциальных уравнений . . . . . . . . . . . . . . . .7.1.Обыкновенные дифференциальные уравнения (ОДУ) . . . .7.2.Задача Коши (задача с начальными условиями) . . . . . . .7.3.Ошибки приближённых методов . . . . . . . . . . . . . . . . .7.4.Устойчивость приближённого решения . . . . .
. . . . . . . .7.5.Метод Эйлера (метод ломаных) . . . . . . . . . . . . . . . . .7.6.Метод средней точки (модифицированный метод Эйлера) . .7.7.Метод «предиктор-корректор» (метод Эйлера с пересчётом)7.8.Классический метод Рунге-Кутты . . . .
. . . . . . . . . . . .7.9.Алгоритм Верле . . . . . . . . . . . . . . . . . . . . . . . . . .Интерполяция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8.1.Общая постановка задачи интерполяции . . . . . . . . . . . .8.2.Интерполяционные многочлены Лагранжа . . . . . . . . . .
.Системы линейных уравнений . . . . . . . . . . . . . . . . . . . . . .9.1.Метод Гаусса . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.................................................................................................................................................................................................................................5578101011121214141515161717182020212224252626262728282830303131313232333334353535383810.Динамические данные: способы организации .
. . . . . . . . .10.1. Общие сведения . . . . . . . . . . . . . . . . . . . . . .10.2. Динамический массив (вектор) . . . . . . . . . . . . .10.3. Стек, дека, очередь . . . . . . . . . . . . . . . . . . . .10.4. Список . . . . . . . . . . . . . . . . . . . . . . . . .
. .10.5. Двоичное (бинарное) дерево поиска . . . . . . . . . . .10.6. Ассоциативные контейнеры, B-деревья, хэш-таблицы .4...............................................................414142434548521.1.1.Представление чисел в компьютерахПредставление положительных целых чиселС раннего возраста мы привыкаем к записи чисел (количеств) в так называемой десятичной системе счисления. Каждому количеству сопоставлена некоторая последовательностьсимволов (сами эти символы, кстати, служат для обозначения малых количеств – от нулядо основания системы счисления). Т.е., в нашем (привычном для всех) случае символы,обозначающие малые количества, – это цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Они меньше основаниясистемы счисления (т.е., числа 10) и представляют собой набор всех возможных остатковот деления на значение основания.Поскольку остаток от деления любого числа (количества) на значение основания неизменен, мы можем построить (см.
далее) для каждого количества такую последовательностьостатков, которая будет уникально характеризовать это количество. А так как для остатковимеются специальные отображающие их символы, мы будем иметь для каждого количества соответствующую ему уникальную последовательность символов.Возвращаясь к привычной десятичной записи, мы можем сказать, что количество лет, прошедших от р.Х., записывается нами как 2014, что в реальности означает: это количествоесть 2 · 103 + 0 · 102 + 1 · 101 + 4 · 100 .Видно, что, хотя в применяемой нами записи и используется один и тот же набор цифр,значимость каждой цифры в записи различна.
По этой причине ещё говорят, что используемая нами система записи чисел является позиционной : смысл каждой цифры зависитот её позиции.Какова может быть процедура получения записи числа (количества) в позиционнойсистеме счисления по основанию ? (Далее предполагаем, что ≥ 0, а > 0). Например,она может быть вот такой. Найдём остаток 0 от деления числа на (а заодно – ичастное).
После этих действий мы будем знать представление числа в виде = 0 · + 0 ,где 0 обозначает частное, а 0 – остаток от деления на . Заметим, что 0 < , апотому в случае, когда = 10, мы можем вместо 0 использовать одну из наших десятицифр. Если 0 > 0, то проделаем то же с числом 0 , т.е., найдём остаток 1 от деления0 на и частное 1 :0 = 1 · + 1 ,С полученным числом 1 > 0 проделаем аналогичную процедуру и получим 2 и остаток2 :1 = 2 · + 2 ,Понятно, что последовательность значений 0 , 1 , 2 , ... – строго убывающая, а снизу онаограничена значением 0.
Таким образом, через некоторое (конечное) количество шагов мыпридём к значению = 0, так что последующие значения (+1 и далее), равно каки остатки +1 и далее, будут равны нулю. Возьмём теперь последовательность остатков , ..., 1 , 0 – она и будет уникально характеризовать наше число .
В десятичной системекаждый остаток имеет собственное обозначение – цифру, значит, мы получим при = 10уникальную запись числа в десятичной позиционной системе счисления.Поскольку при обсуждении процедуры мы не делали никаких предварительных предположений о величине числа , всё это будет справедливо и для систем с другими основаниями.5Далее нас особенно будут интересовать основания 2 (так называемая двоичная система,она применяется в современных компьютерах), 8 (восьмеричная система), 16 (шестнадцатиричная система). Символы, используемые для обозначения цифр в этих системах (атакже в десятичной системе), приведены в таблице.Основаниесистемы счисления281016Цифрыдля изображения чисел0,10,1,2,3,4,5,6,70,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9,A,B,C,D,E,FТаким образом, способом получения записи числа в любой позиционной системе счисления может быть последовательное получение остатков от деления на основание системысчисления сначала самого числа, а потом – частных от предыдущего деления, – вплотьдо получения нулевого результата деления.
Причём неважно, в какой системе записаноисходное число и основание, важно, чтобы все вычисления производились всё время в одной и той же системе счисления. Полученные остатки записываются «цифрами» системысчисления в обратном порядке.Для получения записи числа 2014 в двоичной системе последовательно осуществлялосьделение на 2 (основание системы), а сами вычисления производились в привычном десятичном виде. Таким образом, десятичное число 2014 в двоичной системе счисления будетиметь вид:201410 = 111110111102Здесь – для того, чтобы указать, в какой системе счисления записано число, – использованнижний индекс основания системы счисления.Задание.Найдите в качестве упражнения запись этого же числа в восьмеричной и в шестнадцатиричной системах счисления.Как осуществляются простейшие арифметические операции в какой-либо позиционной системе счисления? Рассмотрим, например, сложение и умножение в двоичной системе (длядругих систем действия будут аналогичными).
Прежде всего надо составить таблицы сложения и умножения для цифр рассматриваемой системы.+ 00 01 1× 0 10 0 01 0 11110Таблицы сложения и умножения для двоичной системы счисления будут весьма простыми;таблицы для восьмеричной, десятичной и шестнадцатиричной систем – существенно больше.Вот, например, таблица сложения в шестнадцатиричной системе:6+000102030405060708090A0B0C0D0E0F00000102030405060708090A0B0C0D0E0F010102030405060708090A0B0C0D0E0F100202030405060708090A0B0C0D0E0F101103030405060708090A0B0C0D0E0F101112040405060708090A0B0C0D0E0F101112130505060708090A0B0C0D0E0F101112131406060708090A0B0C0D0E0F101112131415070708090A0B0C0D0E0F101112131415160808090A0B0C0D0E0F101112131415161709090A0B0C0D0E0F1011121314151617180A0A0B0C0D0E0F101112131415161718190B0B0C0D0E0F101112131415161718191A0C0C0D0E0F101112131415161718191A1B0D0D0E0F101112131415161718191A1B1C0E0E0F101112131415161718191A1B1C1D0F0F101112131415161718191A1B1C1D1EВидно, что результат операции над двумя цифрами может выходить за пределы одной цифры,тогда появляется цифра переноса в следующий разряд (переносы показаны красным цветом).Затем разряд за разрядом, начиная с младших, выполняется необходимая операция надпарами цифр, а возникающие переносы корректируют цифры более старших разрядов –так же, как это делается в десятичной системе.1.2.Представление отрицательных целых чисел: числа со знакомВ обычной записи чисел для указания их знака (как правило, отрицательного) используется специальный символ впереди – минус.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
