Добавлен: 28.11.2018
Просмотров: 7619
Скачиваний: 71
Темы курсовых работ
по «Технология программирования (Python)»
Тема 1: Раскрашивание карты методом исчерпывающего поиска
Чтобы на географической карте было удобно различать регионы, ее раскрашивают по следующему правилу: два региона должны быть окрашены в разные цвета, если их границы имеют более чем конечное число общих точек. (Обычно составители карт не страдают топологическими патологиями и не ищут вырожденных примеров, противоречащих здравому смыслу.) С другой стороны, картографам предстоит оплачивать типографские счета, поэтому, чем меньше цветов будет использовано, тем лучше. В частности, картографы, расписывающие карту как попало, распишутся лишь в своем легкомыслии: им придется использовать больше красок, чем это необходимо. Свои действия нужно планировать заранее. Итак, задача о раскрашивании карты сводится, в сущности, к определению минимального числа красок.
Для решения этой задачи обратимся к помощи компьютера. Тут нас подстерегают трудности: большинство ЭВМ лишено зрения, поэтому они не могут посмотреть на карту; к счастью, им нужно знать лишь, какие регионы являются соседями, т. е. смежны друг другу. Размер и форма регионов не влияют на раскраску, важно лишь наличие нетривиальных контактов между ними. Для представления отношения смежности полезно воспользоваться неориентированным графом.
Неориентированный граф состоит из конечного множества вершин и конечного множества ребер, связывающих вершины. Любые две вершины связаны не более чем одним ребром; не должно быть двух дублирующих друг друга ребер; кроме того, для рассматриваемой задачи мы запрещаем ребру связывать вершину с самой собой. На рис. 1.1 изображен неориентированный граф, представляющий первые 49 американских штатов. Ввести граф в ЭВМ несложно: достаточно перечислить все вершины, сопроводив каждую списком смежных ей вершин. Граф может не иметь вершин, а значит, и ребер; такой граф называется пустым. Вершина может быть изолированной, если нет ребер, связывающих ее с другими вершинами (примером тому могли бы служить Аляска и Гавайи); точно так же две части графа окажутся изолированными друг от друга, если нет ребер, их связывающих. Аналогия между картами и неориентированными графами столь тесна, что мы будем использовать эти понятия как равнозначные. Ну, а польза, приносимая графами, столь велика, что всем программистам следует иметь представление об их основных свойствах.
Рисунок 1.1. Топологическая карта Соединенных Штатов. Для нее достаточно четырех цветов. (WA — Вашингтон, OR — Орегон, CA — Калифорния, NV — Невада, ID — Айдахо, UT — Юта, AZ — Аризона, МТ — Монтана, WY — Вайоминг, СО — Колорадо, NM — Нью-Мексико, ND — Северная Дакота, SD — Южная Дакота, NE — Небраска, КА — Канзас, ОК — Оклахома, ТХ — Техас, MN — Миннесота, IA — Айова, МО — Миссури, AR — Арканзас, LA — Луизиана, WI — Висконсин, IL — Иллинойс, IN — Индиана, MS — Миссисипи, AL — Алабама, Ml — Мичиган, ОН — Огайо, KY — Кентукки, TN — Теннесси, GA — Джорджия, FL — Флорида, РА — Пенсильвания, WV — Западная Виргиния, VA — Виргиния, NC — Северная Каролина, SC — Южная Каролина, NY — Нью-Йорк, NJ — Нью-Джерси, DE — Делавэр, MD — Мэриленд, DC — округ Колумбия, VT — Вермонт, МА — Массачусетс, СТ — Коннектикут, WE — Мэн, NH — Нью-Гэмпшир, RI — Род-Айленд.)
Тема. Напишите программу, раскрашивающую карту в минимальное число цветов. Исходными данными служит список регионов с указанием соседей каждого региона. Результатом должен быть список регионов с приписанными им цветами и общее число использованных цветов. Обычно проще всего для обозначения регионов и цветов применить положительные числа, но куда приятнее (и полезнее для отладки), если допускается ввод более привычных названий. Исходные данные должны проверяться на непротиворечивость; выявляйте нелепые номера вершин и связанные с собой вершины. Постарайтесь сделать программу по возможности эффективной, иначе раскраска тяжелых случаев окажется для вас слишком дорогим удовольствием.
Указания исполнителю. Исходная карта не обязана быть планарной. В самом деле, вполне допустимыми крайними случаями служат карты, в которых любые два региона — соседи, и карты, в которых никакие два региона не являются соседями. Последний случай соответствует раскраске множества раздельных шаров, когда достаточно только одного цвета. Проверка планарности — важная тема информатики, ей посвящено немало статей. Возможно, вас заинтересует проверка гипотезы о четырех красках, утверждающей, что для любой планарной карты требуется не более четырех красок. Если вам удастся подтвердить или опровергнуть ее, вы сделаете себе имя.
Из ресурсов, требуемых данной задачей, самый важный — время. Конечно, нет смысла перебирать все возможные решения, поскольку их число быстро увеличивается с ростом числа регионов, а доля правильных решений (даже если таковых несколько) мала. Лучше воспользоваться методом перебора с возвратами. Начните с выбора некоторого региона и приписывания ему цвета. В дальнейшем переходите к соседнему нераскрашенному региону и пытайтесь приписать ему какой-нибудь из использованных цветов, совместимый с уже сделанной раскраской. (Может случиться, что раскрашивать больше нечего, тогда задача решена. Возможен и случай, когда не осталось нераскрашенных регионов, соседних с раскрашенными, т. е. попалась несвязная карта.) Если в некоторый момент новый регион не удается раскрасить, отступайте от уже раскрашенных регионов (в соответствии с порядком раскраски) до тех пор, пока не найдется регион, цвет которого можно изменить. Раскрасьте его в цвет, которого он ранее не имел, и снова продвигайтесь вперед. Если при отступлении вы возвратились в регион, раскрашенный первым, добавьте к своей палитре новый цвет и начните сначала.
Развитие темы. При использовании метода перебора с возвратами огромное влияние на время работы оказывает порядок выбора регионов. Учитывая этот эффект, можно заранее упорядочить регионы или использовать некоторые эвристики для выбора очередного региона. По-видимому, те регионы, у которых много соседей, раскрасить труднее, поскольку на их цвет накладывается больше ограничений. Из тех же соображений почти изолированную группу регионов следует рассмотреть отдельно, так как если ее не удастся раскрасить некоторым набором цветов, то и всю карту — тоже. Идея в обоих случаях состоит в том, что, если раскраска какого-либо региона может вызвать затруднения, ее нужно выполнить пораньше, чтобы не тратить время на разрушение почти законченной раскраски. Разумеется, полное решение такой «предварительной» задачи равносильно решению исходной задачи, но ведь и небольшой вклад может принести вполне ощутимую прибыль. Сравните несколько стратегий предварительного упорядочения по стоимости и эффекту.
Тема 2: Автоматическое форматирование текста
Известно, вам или нет, но с недавних пор еще одно тяжкое бремя свалилось с плеч человечества. Заботу о создании и размещении опечаток в тексте взяли на себя компьютеры. Там, где раньше линотипы отливали горячий свинец в строки, теперь небольшие, вполне доступные по цене компьютеры методами фотонабора выдают нескончаемые потоки готовых текстов. Жаль только, что с появлением новых эффективных методов уходит очарование доброго старого времени. Ну какой, скажите, интерес выискивать опечатки в воскресном номере Нью-Йорк Таймс, в которых и заключается весь юмор этого обширного собрания важных скучностей, если вы знаете, что компьютер способен делать ошибки в сотни раз быстрее, чем человек? Такова цена, которую приходится платить за прогресс.
Конечно, реальный прогресс заключен в том, что в издательском деле компьютер привлекается в качестве подмастерья, некоего чудесного помощника, способного выполнять черную работу быстро и — при аккуратном программировании — почти бесплатно. Программисты уже пользуются руководствами по вычислительной технике, изданными при помощи ЭВМ. Такие руководства часто очень неудобны для чтения из-за неудачного шрифта, которым снабжено печатающее устройство машины. Однако большинство людей и не подозревает, что многие журналы, газеты и книги также печатаются с помощью ЭВМ. Они выглядят гораздо привлекательнее благодаря тому, что машина не только редактирует и соответствующим образом располагает текст, но и управляет специальными периферийными фотонаборными устройствами. Последние, обладая десятками шрифтов различной гарнитуры, выдают готовую к изданию продукцию. Черновик настоящей книги также был подготовлен при помощи такой системы, и первые читатели были уверены, что держат в руках фотокопию реальной книги, а вовсе не некий аналог обычного машинописного экземпляра.
Система подготовки публикаций состоит из четырех компонентов. Во-первых, необходима хорошая файловая система, в которой можно хранить готовящиеся и архивные текстовые файлы. Обычно память для хранения файлов предоставляется операционной системой, но известен случай, когда в качестве такой памяти использовался шкаф для перфокарт в кабинете автора. Конечно, перфокарты не самый практичный носитель, когда речь идет об операциях над большими объемами информации, например при издании газет. Во-вторых, нужен редактор текстов, для того чтобы вносить изменения и поправки в файлы перед выдачей на печать. Редакторы текстов также имеются, в большинстве операционных систем, но может понадобиться специальный редактор издания, обладающий именно теми возможностями, которые требуются при подготовке публикаций. Третий элемент — форматор, который умеет размещать заголовки, выбирать размер страницы, располагать материал в таблицах, выделять абзацы и т. п. Форматор работает с такими элементами текста, как слова, предложения, абзацы, т. е. уже на том уровне, на котором текст воспринимается человеком. Наконец, имеется программа-наборщик, которая преобразует форматированный текст в его образ на внешнем носителе. Работа этой программы связана в первую очередь с особенностями шрифтов, физическими размерами, командами выводного устройства, отдельными литерами и тому подобными вещами. Программа-наборщик, так же как и оператор линотипа, готова выдать на печать любой вздор, лишь бы он поместился в отведенное ему место. Функционально файловая система и редактор текстов заботятся о содержании текста, а форматор и наборщик — о том, как он будет выглядеть. Эта тема посвящена форматированию текстов.
Форматор
Процесс форматирования текста вручную проходит несколько этапов. Вначале автор создает черновик рукописи, и он перепечатывается набело. Затем автор вместе с редактором (по крайней мере, когда речь идет о больших публикациях) принимаются терзать эту рукопись, пока там не останется живого места, после чего автор начинает работу над новым вариантом рукописи. Этот цикл повторяется до тех пор, пока и автор, и редактор не будут удовлетворены. Затем рукопись еще раз перепечатывается (как правило, через два интервала) и передается техническому редактору. Он размечает рукопись, давая всевозможные указания относительно наборных шрифтов, размера и расположения заголовков, полосы набора, курсива и прочих деталей, определяющих в конечном счете внешний вид издания. Разметка делается при помощи специальных обозначений, и каждый значок ставится в то место рукописи, к которому он относится. Размеченная рукопись отправляется в наборный цех, где текст набирают и делают корректурный оттиск в нескольких экземплярах, называемый версткой. Верстка возвращается в редакцию, где редактор и корректор сверяют ее с окончательным вариантом рукописи. Мелкие ошибки легко исправить в наборном цехе, заменив одну строку набора другой. Но как быть, если автор вдруг решит, что вся четвертая глава никуда не годится, или художнику покажется, что гарнитура бодони будет выглядеть лучше литературной? Такие изменения повлекут за собой новый набор и обойдутся недешево. Можно только диву даваться, насколько по-разному воспринимаются типографский текст и тот же текст, напечатанный на машинке.
Система подготовки публикаций с помощью ЭВМ исключает из этого цикла большую часть работы и множество людей. Как и прежде, автор должен подготовить первоначальный вариант рукописи. Но затем рукопись поступает не в машинописное бюро, а в файловую систему машины. Текст рукописи можно ввести, как и любую информацию для ЭВМ, либо с перфокарт, либо непосредственно через терминальное устройство машины. (Большая часть этой рукописи была отперфорирована.) Автор исполняет также и функции технического редактора, сопровождая текст простейшими командами для форматора. Текстовый файл с рукописью обрабатывается форматором и наборщиком, в результате чего получается черновая верстка окончательного печатного текста. Эта черновая верстка выглядит куда как более чисто, чем машинописный вариант, — она оформлена в виде отпечатанных типографским способом страниц с правильными номерами, радующим глаз шрифтом и т. п. Заметим, что все это происходит еще до начала какого-либо пересмотра рукописи.
Затем автор и редактор начинают работать над рукописью. Интеллектуальная часть работы точно такая же, как и раньше, но теперь им значительно проще представить себе конечный результат, поскольку рукопись выглядит почти как готовое печатное издание. Да и процесс редактирования уже не такой трудоемкий. Для того чтобы добавить или убрать фразу, не нужно ничего перепечатывать — все изменения вносятся при помощи редактора текстов, подобно тому, как заменяются строки в программах. Переупорядочение больших разделов, а также вызов текстов, временно отсутствующих в основной памяти, осуществляется средствами файловой системы. Поскольку текст в любом случае придется переформатировать, то можно поменять и команды форматора, тоже просто изменив содержимое текстового файла. Наконец, выполнение программы форматора на ЭВМ стоит такие пустяки, что все множество сеансов форматирования текста обойдется наверняка несравненно дешевле, чем одна перепечатка его на машинке при старом способе работы. Имеется, правда, единственное опасение — авторы, зачарованные столь аккуратно оформленной рукописью, будут неохотно вносить в нее изменения; ведь в течение долгих лет за всякое исправление в верстке, противоречащее рукописи, им приходилось расплачиваться из авторского гонорара. Поэтому если мы хотим правильно использовать ЭВМ для подготовки публикаций, то и авторов необходимо должным образом перестроить.