Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы (1107622)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиЛ.С. Корухова, М.Р. Шура-БураВВЕДЕНИЕ В АЛГОРИТМЫ(учебное пособие для студентов I курса)Москва2010УДК 519.6+510.6Печатается по решению Редакционно-издательского советафакультета вычислительной математики и кибернетикиМосковского государственного университета имени М.В. ЛомоносоваРецензенты:профессор В.П. Иванников, доцент В.Н. ПильщиковКорухова Л.С., Шура-Бура М.Р.
Введение в алгоритмы. Учебное пособие длястудентов I курса, 2-е исправленное издание. — М. Издательский отдел факультета ВМиКМГУ (лицензия ИД № 05899 от 24.09.2001 г.); МАКС Пресс, 2010, - 26 с.ISBN 978-5-89407-399-6ISBNУчебное пособие представляет собой введение к основному курсу лекций длястудентов факультета ВМК МГУ "Алгоритмы и алгоритмические языки". Обсуждаетсяроль компьютера в решении проблемы накопления и сохранения знаний, детализируетсяпредставление о задаче обработки информации.
Вводятся понятия процесса обработки иалгоритма. Подчеркивается эквивалентность задачи обработки слов и задачи вычисленияцелочисленных функций, формулируется основная гипотеза теории алгоритмов.Рассматриваются различные формальные уточнения понятия алгоритма: машинаТьюринга, нормальный алгоритм Маркова, и показывается их эквивалентность.Демонстрируется возможность реализации алгоритма реальным автоматом.Для студентов факультета ВМК в поддержку основного лекционного курса“Алгоритмы и алгоритмические языки” и для преподавателей, ведущих практическиезанятия по этому курсу.УДКББКУчебное изданиеКОРУХОВА Людмила Сергеевна, ШУРА-БУРА Михаил РомановичВВЕДЕНИЕ В АЛГОРИТМЫУчебное пособиеИздательский отдел факультета вычислительной математики и кибернетикиМГУ им.
М.В. ЛомоносоваЛицензия ИД N 05899 от 24.09.01 г.119992, ГСП-2, Москва, Ленинские горы, МГУ имени М.В. Ломоносова, 2-й учебный корпусНапечатано с готового оригинал-макетав издательстве ООО "Макс Пресс"Лицензия ИД N 00510 от 01.12.99Подписано к печати 21.12.2009 г. Формат 60х90 1/16 Усл.печ.л. 1,5 Тираж 400 экз. Заказ119992, ГСП-2, Москва, Ленинские горы, МГУ им.
М.В. Ломоносова, 2-й учебный корпус, 627 к..Тел. 939-3890, 939-3891. Тел./Факс 939-3891© Факультет вычислительной математикии кибернетики МГУ имени М.В.Ломоносова, 2010© Корухова Л.С., 20101. О ЗАДАЧЕ ОБРАБОТКИ ИНФОРМАЦИИПрежде всего, буквально несколько слов о предмете изучения курса лекций"Алгоритмы и алгоритмические языки" и его роли в образовании.Машины, о которых идет речь в курсах лекций по информатике, по традиции называлиэлектронно-вычислительными (ЭВМ), несмотря на то, что их роль далеко выходит зарамки понятия вычислений. В настоящее время за такими машинами прочно закрепилосьназвание – компьютеры.Роль вычислений по мере развития человеческого общества постоянно возрастала. Напротяжении многих лет люди, в основном, удовлетворялись так называемыми ручнымивычислениями и весьма примитивными средствами.
Но все же интерес ксовершенствованию способов изображения числовой информации, методов и средстввычислений постоянно сохранялся. Отметим изобретение в XVII веке известным ученымБлезом Паскалем арифмометра, являющегося прототипом одной из главных компонентЭВМ - арифметического устройства. Наряду с появлением новых задач, решение которыхтребовало все более сложных вычислений, существенно увеличивались и объемытрадиционных достаточно простых вычислений. Любопытно отметить, что первыесерьезные шаги в развитии современных средств вычислений связаны с обработкойрезультатов переписи населения в США в конце позапрошлого века.
Как средства такойобработки были использованы перфокарты и появились так называемые счетноаналитические машины - табуляторы. С появлением прикладной атомной физикивозникла острая потребность в сложных вычислениях, способных заменить эксперимент.Несомненно, что появление первых ЭВМ в 40-х годах 20-го века в значительной степенистимулировалось этой потребностью. Принципы работы, сформулированные известнымученым Джоном фон - Нейманом и заложенные в первые ЭВМ, в классическихархитектурах сохранились с 40-х годов по сей день. Однако реальные возможности иразнообразие архитектур компьютеров выросли настолько, что в современном обществеони превратились в один из основных рычагов технического прогресса.Благодаря компьютерам открылись совершенно новые перспективы в решениипроблемы накопления и сохранения знаний, что без преувеличения позволяетрассматривать появление ЭВМ в ряду таких крупных событий в развитии человечества,как появление письменности и изобретение книгопечатания.Создание ЭВМ инициировало появление совершенно новой области человеческойдеятельности - программирования.
Развитие ЭВМ и программирования превратилокомпьютер в незаменимый инструмент для целей хранения, передачи и обработкиинформации. Нет сомнения, что ЭВМ способствовали существенному росту интереса кобработке информации и к ее роли в жизни человечества. Роль какой-либо сферыдеятельности характеризуется числом людей, занятых в этой области. В конце ХIX векатолько 5% людей работали в области обработки информации. В 40-е годы ХХ века этотпроцент возрос до 30%, а сейчас уже и превысил 50%.В рамках настоящего курса мы будем считать понятие информации интуитивно ясными не будем давать определение этого понятия.
Однако уточним, что, имея в видуобработку информации на компьютере, мы ограничиваемся информацией, которуюможно задать в дискретном виде, т.е. конечным числом отдельных знаков. Принимаятакое ограничение, мы исходим из предположения, что любую информацию можно задатьв таком виде. Вернее, что любую информацию в задачах обработки информации можно"подменить" дискретной информацией.
Например, картину можно изобразить в видеописания цветов пусть большого, но конечного числа отдельных точек. Наше3предположение о возможности дискретного изображения информации подкрепленотысячелетиями проверенной практикой использования человечеством письменности.В общем виде обработку информации можно представить себе как извлечениеИСКОМОЙ информации из ИСХОДНОЙ:< ИСХОДНАЯ информация > ЗАДАЧА < ИСКОМАЯ информация >В этом схематическом представлении описание задачи и способа ее решения можновключить в понятие <ИСХОДНАЯ информация> и иметь дело со схемой :< ИСХОДНАЯ информация > ===> < ИСКОМАЯ информация >Если мы внимательно проанализируем эту общую схему, то вынуждены будемпризнать, что <ИСКОМАЯ информация> должна содержаться в исходной и, в принципе,никакой новой информации в результате обработки мы не получаем.
В каком-то смыслетакой довод не лишен основания. Например, при переводе Московского времени во времяпо Гринвичу достаточно вычесть 3 часа и, так сказать, представить ту же информацию вдругой форме.Однако нельзя не согласиться с тем, что форма информации имеет, вообще говоря,существенное значение. Ведь информация нужна лишь в том случае, когда она можетбыть "понята" (воспринята, проинтерпретирована…). Понятность же информации,безусловно, зависит от ее формы. Так, например, приказывая солдату остановитьсясловами "Прошу остановиться" (вместо команды "Стой!"), командир рискует бытьнепонятым.В системе уравнений:X+Y=5X–Y=7конечно, содержится информация о значениях X и Y. Однако эта информация в формеХ=6Y = –1может оказаться куда более понятной и пригодной.Рассмотрим еще одну задачу – определение приговора судом:< суть дела и закон > ====> < приговор >Здесь нет вычислений в традиционном смысле этого слова, но огромна исходнаяинформация и необычайно важна форма искомой информации.В связи с информацией и задачами её обработки и использования следует отметитьналичие двух важных понятий: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}
