Программирование и компьютеры - готовые работы

Введение

За последнее десятилетие развитие вычислительной техники идет семимильными шагами. Осваиваются новейшие технологии, появляется возможность создавать персональные компьютеры и рабочие станции с огромным потенциалом выполняемых функций и технических возможностей. Мощности современных ПЭВМ позволяют заменять собой многие другие средства связи, обработки, управления. Развитие нанотехнологий привело к усложнению внутренней «начинки» компьютера, более широкому спектру решаемых задач и областей применения, менее дорогостоящим и громоздким периферийным и подключаемым устройствам. Соответственно, совершенствуются и они, отвечая требованиям современных вычислительных систем. Переход к чипсетам, выполненным на одном кристалле, инфракрасным портам, шинам сверхбыстрой передачи данных привел к тому, что внутренние детали персональных компьютеров 5-7-ми летней давности существенно отличаются от существующих на сегодняшний день. Уменьшились размеры, цена, увеличилась степень доступности устройств для более широкого класса пользователей.
Такие огромные потенциальные возможности, которые несет в себе вычислительная сеть и тот новый потенциальный подъем, который при этом испытывает информационный комплекс, а так же значительное ускорение процесса обработки информации не дают право игнорировать и не применять их на практике.
Зачастую возникает необходимость в разработке принципиального решения вопроса по организации ИВС (информационно–вычислительной сети) на базе уже существующего компьютерного парка и программного комплекса, отвечающей современным научно–техническим требованиям с учетом возрастающих потребностей и возможностью дальнейшего постепенного развития сети в связи с появлением новых технических и программных решений.
Данный дипломный проект представляет собой модернизацию
информационной системы предприятия ООО «Техно Баланс».

Проработка проекта произведена до уровня эскизного проекта (согласно ГОСТ 34.601 – 90 ЕСКД «Стадии и этапы создания АС» и ГОСТ 2.105 – 95 ЕСКД «Общие требования к текстовым документам»).

Под раскраской графа будем понимать раскрашивание, как ребер графа, так и вершины.

Набор вершин графа называется максимальной независимой системой (МНС), если любые две вершины из этого набора не являются смежными и нельзя включить в этот набор другую вершину, чтобы это условие сохранилось.
Нахождение МНС в графе: берем произвольную вершину, затем находим любую вершину, не смежную с ней, затем находим вершину, не смежную с отобранными вершинами и т. д. МНС в графе может быть много и они могут содержать разное число вершин.
Функцией Гранди - называется функция на вершинах графа, отображающая вершины в множество {1,2,…, a}, причем если вершина xi окрашена в цвет с номером k, то функция Гранди h(xi) = k Хроматическое число(наименьшее число цветов) - является единственным, но функций Гранди может быть много. Нахождение хотя бы одной функции Гранди – значит, найти одну из возможных раскрасок (таких раскрасок может быть много).

Первый алгоритм нахождения раскраски вершин графа.

Пусть имеем граф G, найдем в нем какую-либо МНС, которую обозначим S1, и все вершины, входящие в эту МНС, окрасим в цвет № 1. Далее, удалим из данного графа все вершины, входящие в эту МНС (вместе с ребрами), и для нового графа снова найдем МНС, которую обозначим S2. Новые вершины окрасим в цвет № 2, затем удалим эти вершины из графа вместе с соответствующими ребрами, снова находим МНС, которую окрасим в цвет № 3, и т. д. При любом способе осуществления этой процедуры придем к наилучшей раскраске и найдем некоторую функцию Гранди и хроматическое число данного графа.

Второй алгоритм раскраски ребер в графе.
Простейший алгоритм нахождения раскраски ребер состоит в следующем: по двойственному графу: ребра графа соответствуют вершинам нового (двойственного) графа, причем, если 2 ребра имеют общую вершину, то они являются смежными и в двойственном графе соединены ребром. После этого раскрашиваем наилучшим образом вершины двойственного графа и, переходя к первичному графу, получаем (одну из возможных) реберных раскрасок графов.
Третий алгоритм прямого неявного перебора для определения хроматического числа графа.
1. Построим первоначальную допустимую раскраску по следующему алгоритму:
Окрасим v1 в цвет 1. Каждую из оставшихся вершин окрашиваем последовательно в соответствии с заданным упорядочением:
вершина vi окрашивается в цвет с наименьшим возможным \"номером\" (т.е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, смежной с vi).

Большинство авторов публикаций, посвященных структурам и организации данных, делают основной акцент на том, что знание структуры данных позволяет организовать их хранение и обработку максимально эффективным образом - с точки зрения минимизации затрат как памяти, так и процессорного времени. Другим не менее, а может быть, и более важным преимуществом, которое обеспечивается структурным подходом к данным, является возможность структурирования сложного программного изделия. Современные промышленно выпускаемые программные пакеты - изделия чрезвычайно сложные, объем которых исчисляется тысячами и миллионами строк кода, а трудоемкость разработки - сотнями человеко-лет. Естественно, что разработать такое программное изделие \"все сразу\" невозможно, оно должно быть представлено в виде какой-то структуры - составных частей и связей между ними. Правильное структурирование изделия дает возможность на каждом этапе разработки сосредоточить внимание разработчика на одной обозримой части изделия или поручить реализацию разных его частей разным исполнителям.
При структурировании больших программных изделий возможно применение подхода, основанного на структуризации алгоритмов и известного, как \"нисходящее\" проектирование или \"программирование сверху вниз\", или подхода, основанного на структуризации данных и известного, как \"восходящее\" проектирование или \"программирование снизу вверх\".
В первом случае структурируют прежде всего действия, которые должна выполнять программа. Большую и сложную задачу, стоящую перед проектируемым программным изделием, представляют в виде нескольких подзадач меньшего объема. Таким образом, модуль самого верхнего уровня, отвечающий за решение всей задачи в целом, получается достаточно простым и обеспечивает только последовательность обращений к модулям, реализующим подзадачи. На первом этапе проектирования модули подзадач выполняются в виде \"заглушек\". Затем каждая подзадача в свою очередь подвергается декомпозиции по тем же правилам. Процесс дробления на подзадачи продолжается до тех пор, пока на очередном уровне декомпозиции получают подзадачу, реализация которой будет вполне обозримой. В предельном случае декомпозиция может быть доведена до того, что подзадачи самого нижнего уровня могут быть решены элементарными инструментальными средствами (например, одним оператором выбранного языка программирования).
Другой подход к структуризации основывается на данных. Программисту, который хочет, чтобы его программа имела реальное применение в некоторой прикладной области не следует забывать о том, что программирование - это обработка данных. В программах можно изобретать сколь угодно замысловатые и изощренные алгоритмы, но у реального программного изделия всегда есть Заказчик. У Заказчика есть входные данные, и он хочет, чтобы по ним были получены выходные данные, а какими средствами это обеспечивается - его не интересует. Таким образом, задачей любого программного изделия является преобразование входных данных в выходные. Инструментальные средства программирования предоставляют набор базовых (простых, примитивных) типов данных и операции над ними. Интегрируя базовые типы, программист создает более сложные типы данных и определяет новые операции над сложными типами. Можно здесь провести аналогию со строительными работами: базовые типы - \"кирпичики\", из которых создаются сложные типы - \"строительные блоки\". Полученные на первом шаге композиции \"строительные блоки\" используются в качестве базового набора для следующего шага, результатом которого будут еще более сложные конструкции данных и еще более мощные операции над ними и т.д. В идеале последний шаг композиции дает типы данных, соответствующие входным и выходным данным задачи, а операции над этими типами реализуют в полном объеме задачу проекта.
Программисты, поверхностно понимающие структурное программирование, часто противопоставляют нисходящее проектирование восходящему, придерживаясь одного выбранного ими подхода. Реализация любого реального проекта всегда ведется встречными путями, причем, с постоянной коррекцией структур алгоритмов по результатам разработки структур данных и наоборот.
Еще одним чрезвычайно продуктивным технологическим приемом, связанным со структуризацией данных является инкапсуляция. Смысл ее состоит в том, что сконструированный новый тип данных - \"строительный блок\" - оформляется таким образом, что его внутренняя структура становится недоступной для программиста - пользователя этого типа. Программист, использующий этот тип данных в своей программе (в модуле более высокого уровня), может оперировать с данными этого типа только через вызовы процедур, определенных для этого типа. Новый тип данных представляется для него в виде \"черного ящика\" для которого известны входы и выходы, но содержимое - неизвестно и недоступно.
Инкапсуляция чрезвычайно полезна и как средство преодоления сложности, и как средство защиты от ошибок. Первая цель достигается за счет того, что сложность внутренней структуры нового типа данных и алгоритмов выполнения операций над ним исключается из поля зрения программиста-пользователя. Вторая цель достигается тем, что возможности доступа пользователя ограничиваются лишь заведомо корректными входными точками, следовательно, снижается и вероятность ошибок.
Современные языки программирования блочного типа (PASCAL, C) обладают достаточно развитыми возможностями построения программ с модульной структурой и управления доступом модулей к данным и процедурам. Расширения же языков дополнительными возможностями конструирования типов и их инкапсуляции делает язык объектно-ориентированным. Сконструированные и полностью закрытые типы данных представляют собой объекты, а процедуры, работающие с их внутренней структурой - методы работы с объектами. При этом в значительной степени меняется и сама концепция программирования. Программист, оперирующий объектами, указывает в программе ЧТО нужно сделать с объектом, а не КАК это надо делать.
Технология баз данных развивалась параллельно с технологией языков программирования и не всегда согласованно с ней. Отчасти этим, а отчасти и объективными различиями в природе задач, решаемых системами управления базами данных (СУБД) и системами программирования, вызваны некоторые терминологические и понятийные различия в подходе к данным в этих двух сферах. Ключевым понятием в СУБД является понятие модели данных, в основном тождественное понятию логической структуры данных. Отметим, что физическая структура данных в СУБД не рассматривается вообще. Но сами СУБД являются программными пакетами, выполняющими отображение физической структуры в логическую (в модель данных). Для реализации этих пакетов используются те или иные системы программирования, разработчики СУБД, следовательно, имеют дело со структурами данных в терминах систем программирования. Для пользователя же внутренняя структура СУБД и физическая структура данных совершенно прозрачна; он имеет дело только с моделью данных и с другими понятиями логического уровня.

При передаче информации по каналу связи неизбежно возникают ошибки, для борьбы с ошибками применяют помехоустойчивое кодирование.
Обнаружение ошибок в технике связи - действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) - процедура восстановления информации после чтения её из устройства хранения или канала связи.
Для обнаружения ошибок используют коды обнаружения ошибок, для исправления - корректирующие коды (коды, исправляющие ошибки, коды с коррекцией ошибок, помехоустойчивые коды).

За последние годы компьютерная индустрия сделала ог¬ромный шаг вперед. Многие работы, ранее выполнявшиеся вручную, компьютеризируются, и, как следствие, потребо¬вались средства для введения разного рода информации в компьютерные системы. Это и послужило причиной рос¬та спроса на такую технику, как сканеры, цифровые каме¬ры и др. И если раньше при покупке нового компьютера из периферийных устройств первым делом внимание привле¬кал принтер как единственное устройство для вывода ин¬формации в виде ощутимой «твердой копии», то сегодня акценты сместились в сторону обратной задачи — ввода разного рода информации с бумаги в компьютер. Это не¬удивительно: по мере развития и распространения компью¬терных технологий, все более широкого использования элек¬тронной почты и Интернета, по мере снижения стоимости и увеличения объема накопителей все более востребован¬ными становятся средства хранения и передачи информа¬ции в электронном виде.
Таким образом, сканер постепенно отвоевывает все более выгодные позиции на столе как рядового пользователя, так и профессионала практически в любой области. Однако, даже учитывая все преимущества сканеров, эти устройства все же не смогли бы получить такого распространения, если бы оставались в той же ценовой категории, что и несколько лет назад, когда стоимость сканера была сравнима со сто¬имостью всего компьютера. Не последнюю роль в таком росте популярности сканеров сыграл шаг некоторых фирм-производителей навстречу рядовому пользователю. Срав¬нительно недавно появились общедоступные модели сканеров, которые, несмотря на довольно низкую цену, обла¬дают настолько высокими характеристиками, что могут ис¬пользоваться даже во многих профессиональных областях. Это и послужило толчком к повсеместному их использованию. Итак, для чего может понадобиться сканер? Вот несколько наиболее часто используемых его возможностей:
• Создание электронных фотоальбомов. Вы можете отсканиро¬вать свой домашний фотоархив и получить таким образом возможность редактирования фотографий, изготовления любого количества копий без потерь в качестве, обмена фо¬тографиями в электронном виде (с помощью электронной почты либо на каких-то накопителях).
• Отправка факсов. Если кроме сканера вы имеете еще и модем, то получаете средство для отправки факсов.
• Сканирование и распознавание различной печатной ин¬формации. Вы можете сэкономить немало сил и времени, отсканировав текст вместо ручного набора на клавиату¬ре. Если в дополнение к этому вы используете и про¬грамму-переводчик, то получите возможность читать любую иностранную документацию. Наконец, с помо¬щью сканера вы сможете хранить необходимые докумен¬ты в электронной форме, освободив, таким образом, дом или офис от кипы бумаг.
Здесь не упомянуты многие другие возможности, они огра¬ничены только вашей фантазией.

Крупнейший математик XVIII века Леонард Эйлер (1707-1783) родился в швейцарском городе Базеле. С двадцатилетнего возраста он жил в Петербурге, в Берлине, потом снова в Петербурге. Эйлер сыграл выдающуюся роль в развитии математики, механики, физики и техники.
В 1758 г. Л. Эйлер опубликовал в \"Записках Петербургской академии наук\" доказательство формулы.
Для двумерных изображений формула эйлеровой характеристики имеет вид:
 = В-Р+Г,
Для одномерных изображений формула эйлеровой характеристики имеет вид:
= В-Р.
Эта формула связывает число вершин В, число ребер Р, и число граней Г.
Если задано какое-то множество то, как бы мы ни разбивали его на части (грани, ребра, вершины), определенным образом \"примыкающие\" друг к другу, сумма В-Р+Г, называемая эйлеровой характеристикой, сохраняет постоянное значение.
Эйлерова характеристика  это число, которое ставится в соответствие фигуре и не изменится при топологических деформациях.
Формула Эйлера имеет огромное значение в геометрии. Эта формула породила новое направление в математике – топологию. Эйлерова характеристика не зависит ни от длин рёбер, ни от площадей граней, а так же не меняется при увеличении их числа.

топологически эквивалентны

топологически эквивалентны

В данной дипломной работе исследуются расстояния и другие меры близости на множестве цифровых черно-белых изображений зависящие от характеристического набора коэффициентов, полученных благодаря неизменности значения эйлеровой характеристики, анализируются и сами характеристические наборы изображений построенные на основе прямоугольной решетки, а также большая база подписей на предмет их численного различения и определения возможности идентификации человека по его подписи.
Задача данной работы состоит в следующем:
• построение функций для вычисления эйлеровой характеристики
• изучение характеристического набора коэффициентов черно-белых цифровых изображений
• получение необходимых условий того, чтобы набор неотрицательных целых чисел являлся характеристическим набором некоторого черно-белого цифрового изображения,
• построение подхода к численному различению изображений
• программная реализация алгоритма различения и идентификации подписей на основе определения расстояний и других мер близости для изображений, построенных на прямоугольной решетке
В дальнейшем под цифровым изображением, построенным на основе прямоугольной решетки, понимается изображение, для которого аналогами пикселей являются прямоугольные элементы некоторой прямоугольной решетки, через аij будем обозначать как сам этот элемент, так и значение его цветности. Изображение можно представить в виде матрицы A=(аij) размера m*n, у которой элементы могут принимать значения либо 0, либо 1, т. е черно либо белое изображение.

Фрагментом Si размера 2*2 будем называть фрагменты вида:
При вычислении  возникает вопрос: связно ли множество такого типа:


Существует такая функция F, для подсчета эйлеровой характеристики изображения, построенного на основе прямоугольной решетки, где:
,
Si – фрагменты вида: S0 S1 S2 S3 S4 S5
…
и так далее всевозможные комбинации из черных и белых пикселов. Фрагменты задаются подматрицей из 4 элементов матрицы А:
ai j ai j+1
ai+1 j ai+1 j+1.
Существует 16 различных фрагментов такого вида. Набор неотрицательных целых чисел, являющихся количеством фрагментов каждого типа, будем называть характеристическим набором коэффициентов изображения А, построенных по системе фрагментов размера 2х2. Таким образом, вычислив функцию F на всевозможных фрагментах данного изображения, можно вычислить эйлерову характеристику изображения.
В работе используется построение аналогов расстояний на основе понятия характеристического набора коэффициентов черно-белого изображения.



Предлагаемые подходы позволяют не только решать задачи различения изображений (а подпись у нас будет рассматриваться как черно-белое изображение), но также дают возможность численно оценить меру их сходства.
Также в работе описываются свойства характеристических наборов коэффициентов черно-белых изображений, построенных на прямоугольной решетке, выводятся необходимые условия того, чтобы наборы из 16 неотрицательных целых чисел являлись характеристическими наборами коэффициентов для черно-белых цифровых изображений, построенных на основе прямоугольной решетки. Решается задача численного различения и идентификации 300 подписей. При сравнении характеристических наборов подписей использовалось два метода. Первый способ – новая разработка, основанная на поэлементном анализе характеристического набора. Мной был сформирован алгоритм, который позволяет получить шкалу допустимых погрешностей по каждому из коэффициентов для существующей базы подписей. Способ позволяет определять поддельная или истинная вводится подпись. Второй способ – определение расстояний между изображениями, то есть работа с характеристическим набором как с единым целым. Позволяет идентифицировать личность по подписи, если ранее он был занесен в базу.