Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиЛ.С. Корухова, М.Р. Шура-БураВВЕДЕНИЕ В АЛГОРИТМЫ(учебное пособие для студентов 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) ИНТЕРПРЕТАЦИЯ< форма информации > ===> < понимание информации >В этой общей постановке оба понятия обозначены лишь на интуитивно содержательномуровне.Термин "интерпретация" для обозначения понимания подчеркивает условностьпонимания, о котором идет речь.