Билет 32

1. Понятие алгоритма. Интуитивное понятие алгоритма.

Слово алгоритм возникло от algorithm- латинской транслитерации имени великого математика IX века Мохаммеда ибн Муссы аль-Хорезми, который сформулировал правила выполнения четырех арифметических действий над многозначными числами.

Алгоритм - это организованная последовательность действий, понятных для некоторого исполнителя, ведущая к решению поставленной задачи.

Алгоритм - это конечная последовательность однозначных предписаний, исполнение которых позволяет с помощью конечного числа шагов получить решение задачи, однозначно определяемое исходными данными.

Алгоритм – понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение цели.

Алгоритм – это набор однозначно определённых шагов, выполняемых для решения задачи определённого класса.

Интуитивное определение неформально, поскольку отсутствуют формальные определения используемых в нем базовых понятий: элементарного шага, задач, классов задач. Кроме того, даже интуитивное определение элементарного шага основано на понятии алгоритма.

В 30 годы ХХ века в противовес классическим представлениям Альхарезми, возникла гипотеза об алгоритмически неразрешимости нескольких задач.

А) С точки зрения Геделя, алгоритм есть последовательность построения сложных математических функций из более простых, с использованием правил сформулированных на языках математической логики.

Можно ввести математическую абстракцию:

Пусть Х – совокупность входных данных, Y – совокупность выходных данных.

Y=f(X)

В) Черча. λ – исчисление или ввел понятие систем рекурсивно-вычислимых (РВ) функций. В этой системе было выделено 3 базовых функции и 3 оператора, посредством которых мы из базовых РВ функций строим более сложные РВ функции.

Алгоритм – способ определения РВ функции.

С) Алaна Тьюринга. Он предложил модель гипотетического вычислительного устройства (исполнителя). Алгоритм – программа для этого исполнителя.

D) Маркова. Основан на том, что какие бы ни были входные данные, они описываются определённым языком.

ВХОД – строка

ВЫХОД – строка

Алгоритм – набор правил подстановки одних символов вместо других.

Был также обоснован тезис Черча – Тьюринга. Различные подходы к формализации понятия алгоритма эквивалентны между собой с точки зрения понятия алгоритмической неразрешимости. С этой точки зрения, любой компьютер с Фон-неймановской архитектурой или другой ныне известной архитектурой, позволяет реализовать только те алгоритмы, которые можно реализовать на машине Тьюринга.

Свойства алгоритма:

Массовость - алгоритм должен быть применим для класса подобных задач.

Дискретность - алгоритм состоит из ряда дискретных шагов.

Определенность - каждый следующий шаг алгоритма однозначно определяется предыдущими шагами.

Результативность - алгоритм должен приводить к решению поставленной задачи за конечное число шагов

Понятность – алгоритм рассчитан на исполнителя, и должен быть сформулирован на понятном ему языке (СКИ – система команд исполнителя).

Каждый исполнитель алгоритма имеет свою систему команд (набор действий) и свою среду (набор объектов, над которыми совершаются действия), в которой, и только в ней, он работает.

Виды алгоритма:

Линейный - алгоритм, в котором все предписания (шаги) выполняются так, как записаны, без изменения порядка следования, строго друг за другом.

Разветвляющийся - алгоритм, в котором выполнение того или иного действия (шага) зависит от выполнения или не выполнения какого-либо условия.

Циклический - алгоритм, в котором некоторая последовательность действий повторяется несколько раз.

Способы записи алгоритма:

Словесно-формульное описание (на естественном языке с использованием математических формул).

Графическое описание в виде блок-схемы (набор связанных между собой геометрических фигур).

алгоритмический язык – система обозначений и правил для единообразной и точной записи алгоритмов и исполнения их.

Разработка алгоритмов.

Существует два подхода к разработке алгоритмов: операциональный и структурный.

Операциональный:

· минимум памяти;

· минимум операций.

операции:

· присваивание;

· арифметические;

· сравнение;

· условный и безусловный переход;

· вызов подпрограммы.

Каждый алгоритм можно представить в виде суперпозиции трех базовых алгоритмических структур: следование, ветвление, цикл. Такой подход позволяет осуществлять разработку алгоритмов, последовательно их детализируя. Сначала выделяется несколько крупных логических блоков (модулей), затем каждый из них последовательно детализируется до отдельных команд конкретного языка программирования. Кроме того, при таком подходе каждый модуль может реализовываться отдельным программистом, если предварительно разработан способ взаимосвязи между модулями.

2. Объекты и отношения в программировании. Сущность объектного подхода к разработке программных средств. Особенности объектного подхода к разработке внешнего описания программного средства.

Окружающий нас мир состоит из объектов и отношений между ними. Объект воплощает некоторую сущность и имеет некоторое состояние, которое может изменяться со временем как следствие влияния других объектов, находящихся с данным в каком-либо отношении. Он может иметь внутреннюю структуру: состоять из других объектов, также находящихся между собой в некоторых отношениях. Исходя из этого, можно построить иерархическое строение мира из объектов. Однако при каждом конкретном рассмотрении окружающего нас мира некоторые объекты считаются неделимыми ("точечными"), причем в зависимости от целей рассмотрения такими (неделимыми) могут приниматься объекты разного уровня иерархии. Отношение связывает некоторые объекты: можно считать, что объединение этих объектов обладает некоторым свойством. Если отношение связывает n объектов, то такое отношение называется n-местным (n-арным). На каждом месте объединения объектов, которые могут быть связаны каким-либо конкретным отношением, могут находиться разные объекты, но вполне определенные (в этом случае говорят: объекты определенного класса). Одноместное отношение называется свойством объекта (соответствующего класса). Состояние объекта может быть изучено по значению свойств этого объекта или неявно по значению свойств объединений объектов, связываемых вместе с данным тем или иным отношением.

В процессе познания или изменения окружающего нас мира мы всегда принимаем в рассмотрение ту или иную упрощенную модель мира (модельный мир), в которую включаем некоторые из объектов и некоторые из отношений окружающего нас мира и, как правило, одного уровня иерархии. Каждый объект, имеющий внутреннюю структуру, может представлять свой модельный мир, включающий объекты этой структуры и отношения, которые их связывают. Таким образом, окружающий нас мир, можно рассматривать (в некотором приближении) как иерархическую структуру модельных миров.

В настоящее время в процессе познания или изменения окружающего нас мира широко используется компьютерная техника для обработки различного рода информации. В связи с этим применяется компьютерное (информационное) представление объектов и отношений. Каждый объект информационно может быть представлен некоторой структурой данных, отображающей его состояние. Свойства этого объекта могут задаваться непосредственно в виде отдельных компонент этой структуры, либо специальными функциями над этой структурой данных. N-местные отношения для N>1 можно представить либо в активной форме, либо в пассивной форме. В активной форме N-местное отношение представляется некоторым программным фрагментом, реализующим либо N-местную функцию (определяющую значение свойства соответствующего объединения объектов), либо процедуру, осуществляющую по состоянию представлений объектов, связываемых представляемым отношением, изменение состояний некоторых из них. В пассивной форме такое отношение может быть представлено некоторой структурой данных (в которую могут входить и представления объектов, связываемых этим отношением), интерпретируемую на основании принятых соглашений по общим процедурам, независящим от конкретных отношений (например, реляционная база данных). В любом случае представление отношения определяет некоторые действия по обработке данных.

При исследовании модельного мира пользователь может по-разному получать информацию от компьютера. При одном подходе его могут интересовать получение информации об отдельных свойствах интересующих его объектов или результатах какого-либо взаимодействия между некоторыми объектами. Для этого он заказывает разработку того или иного ПС, выполняющего интересующие его функции, или некоторую информационную систему, способной выдавать информацию об интересующих его отношениях, используя при этом соответствующую базу данных. В начальный период развития компьютерной техники (при не достаточно высокой мощности компьютеров) такой подход к использованию компьютеров был вполне естественным. Именно он и провоцировал функциональный (реляционный) подход к разработке ПС. Сущность этого подхода состоит в систематическом использовании декомпозиции функций (отношений) для построения структуры ПС и текстов программ, входящих в него. При этом сами объекты, к которым применялись заказываемые и реализуемые функции, представлялись фрагментарно (в том объеме, который необходим для выполнения этих функций) и в форме, удобной для реализации этих функций. Тем самым не обеспечивалось цельного и адекватного компьютерного представления модельного мира, интересующего пользователя: отображение его на используемые ПС могло оказаться для пользователя достаточно трудоемкой задачей, попытки незначительного расширения объема и характера информации об интересующем пользователя модельном мире, получаемой от таких ПС, могло привести к серьезной их модернизации. Такой подход к разработке ПС поддерживается большинством используемых языков программирования, начиная от языков ассемблеров и процедурных языков (ФОРТРАН, Паскаль) до функциональных языков (ЛИСП) и языков логического программирования (ПРОЛОГ).

При другом подходе к исследованию модельного мира с помощью компьютера пользователя может интересовать наблюдение за изменением состояний объектов в результате их взаимодействий. Это требует достаточно цельного представления в компьютере интересующего пользователя объекта, а программные компоненты, реализующие отношения, в которых участвует этот объект, явно связываются с ним. Для реализации такого подхода приходилось строить программные средства, моделирующих процессы взаимодействия объектов (модельного мира). С помощью традиционных средств разработки это оказалось довольно трудоемкой задачей. Правда, появились языки программирования, специально ориентированные на такое моделирование, но это лишь частично упростило задачу разработки требуемых ПС. Наиболее полно отвечает решению этой задачи объектный подход к разработке ПС. Сущность его состоит в систематическом использовании декомпозиции объектов при построении структуры ПС и текстов программ, входящих в него. При этом функции (отношения), выполняемые таким ПС, выражались через отношения объектов разных уровней, т. е. их декомпозиция существенно зависела от декомпозиции объектов.

Говоря об объектном подходе следует также четко понимать о какого рода объектах идет речь: объектах модельного мира пользователя, об их информационном представлении, об объектах программы, с помощью которых строится ПС. Кроме того, следует различать собственно объекты (объекты "пассивные") и субъекты (объекты "активные").

Особенности объектного подхода к разработке внешнего описания программного средства

Определение требований заключается в неформальном описании модельного мира, который пользователь собирается изучать или просто использовать с помощью требуемого ПС. При этом повышается роль прототипирования, которое при этом подходе часто окупается уменьшением объема работы на последующих этапах разработки ПС. Часто определение требование завершается разработкой диаграммы вариантов использования, в которой фиксируются, в каких случаях будет использоваться ПС. Это позволяет при разработке ПС ограничиться только такими ее функциональными возможностями, которые поддерживают эти случаи (варианты) использования.

Существенно изменяется содержание процесса спецификации требований: вместо разработки функциональной спецификации ПС создается формальное описание модельного мира, состоящее из трех частей:

• объектной модели,

• динамической модели,

• функциональной модели.

Назначение этих частей можно определить следующим образом: объектная модель определяет то, с чем что-то случается; динамическая модель определяет, когда это случается; функциональная модель определяет то, что случается.

Объектная модель показывает статическую объектную структуру модельного мира, который должно представлять разрабатываемое ПС (программная система). Она включает определения используемых классов объектов и отношений между этими классами, а также определение используемых объектов этих классов и отношения между этими объектами.

Обычно класс объектов в объектной модели представляется в виде тройки (Имя класса, Список атрибутов, Список операций).

Каждый атрибут представляется некоторым именем и может принимать значения определенного типа. По существу, атрибут класса выражает некоторое простое свойство объектов этого класса. Представление некоторых простых свойств объектов атрибутами весьма удобно, особенно когда по значениям этих атрибутов осуществляется классификация объектов. Операции, указываемые в представлении класса, отражают другие свойства объектов этого класса (как простые, так и ассоциативные). Они показывают, что можно делать с объектами этого класса (или что могут делать сами эти объекты).

В объектной модели отношение между объектами некоторых классов обобщаются в отношения между этими классами. При этом используются, как правило, только одноместные и двуместные отношения между объектами. Более сложные отношения приводит к неоправданному усложнению объектных моделей, а с другой стороны, такие отношения всегда могут быть сведены к двуместным за счет определения дополнительных классов. Одноместные отношения называют атрибутами, причем некоторые атрибуты объекта получаются из атрибутов класса присвоением им конкретных значений. Отношение между двумя (и более) объектами называют связями, а их обобщение (отношение между классами) обычно называют ассоциациями. Ассоциации определяют допустимые связи между объектами. Различают следующие виды ассоциаций:

• взаимодействия состояний объектов,

• агрегирования (структурирования) объектов,

• абстрагирования (порождения) классов.

Ассоциация «взаимодействие», по существу, означает, что объекты классов, находящихся в таком отношении, могут быть параметрами некоторых операций. Ассоциация «агрегирование» означает, что объект одного из классов, находящихся в таком отношении, включает (или может включать) в себя (как часть) объекты другого из этих классов. Ассоциация «абстрагирование» означает, что один из классов, находящихся в таком отношении, наследует свойства другого из этих классов и может обладать также и другими (дополнительными) свойствами.

Для представления объектной модели часто используются графические языки спецификации объектов (например, язык UML). На таких языках классы и объекты задаются прямоугольниками, в которых указывается специфицирующая их информация. Для задания отношений между двумя классами соответствующие им прямоугольники связываются линией, снабженной различными графическими значками и некоторыми надписями. Графические значки специфицируют характер (вид) отношения между этими классами, а надписи обеспечивают полную идентификацию этого отношения (делают его конкретным).

Следует заметить, что объектная модель полностью включает описание внешней информационной среды при реляционном подходе.

Динамическая модель показывает допустимые последовательности изменений состояний объектов из объектной модели модельного мира, который должно представлять разрабатываемое ПС (программная система). Она описывает последовательности операций в ответ на внешние сигналы (взаимодействия) без рассмотрения того, что эти операции делают. Динамическая модель необходима, если в соответствующей объектной модели имеются активные объекты.

Основные понятия динамической модели: события и состояния объектов. Под событием здесь понимается элементарное воздействие одного объекта на другой, происходящее в определенный момент времени. Одно событие может логически предшествовать другому или быть не связанным с другим. Другими словами, события в динамической модели частично упорядочены. Под состоянием объекта здесь понимается совокупность значений атрибутов объекта и представления текущих связей этого объекта с другими объектами. Состояние объекта связывается с интервалом времени между некоторыми двумя событиями, на которые реагирует этот объект. Объект переходит из одного состояния в другое в результате реакции на некоторое событие (в конце интервала, связанного с этим состоянием).

В связи с этим в динамической модели для каждого класса активных объектов строится своя диаграмма состояний. Она представляет собой граф, вершинами которого являются состояния, а дугами – переходы между этими состояниями (переходы часто обозначаются именами событий). Некоторые переходы могут быть связаны с условиями, разрешающими эти переходы. Условие – это предикат, зависящий от значений некоторых атрибутов объекта. Каждое условие указывается на дуге, переходом по которой управляет это условие. Существенно, что в диаграмме состояний с некоторыми состояниями или событиями связываются определенные операции. Операция, связываемая с событием, обозначает реакцию объекта на это событие и считается, что она выполняется мгновенно (в точке некоторого временного интервала). Такая операция называется действием. Операция, связываемая с состоянием, выполняется в рамках временного интервала, с которым связано это состояние (т.е. имеет продолжительность, ограниченную этим интервалом). Такая операция называется деятельностью. Диаграмма состояний определяет управление активизацией указанных операций. Таким образом, диаграмма состояний описывает поведение одного класса объектов.

Динамическая модель в целом объединяет все диаграммы состояний с помощью событий между классами.

Функциональная модель показывает, как вычисляются выходные значения из входных без указания порядка, в котором эти значения вычисляются. Она определяет все операции, условия и ограничения, используемые в объектной и динамической моделях (внешние операции). Функциональная модель соответствует определению внешних функций при реляционном подходе к разработке ПС.

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

Процессы могут выражаться терминальными операциями (определяемые непосредственно) или с помощью других потоковых диаграмм. Таким образом, потоковые диаграммы являются иерархическими.

Терминальные операции определяются так же, как и при реляционном подходе. Впрочем, и диаграммы потоков данных используются при реляционном подходе.

Таким образом, основным содержанием этапа внешнего описания при объектном подходе является объектное моделирование. При этом широко используются формальные языки спецификаций, в том числе и графические. Одним из наиболее употребительных в настоящее время таких языков является язык UML.

3. Указать к какому классу относится каждый из перечисленных IP адресов:

192.168.0.15

127.0.0.1

112.0.0.15

167.58.13.21

Определить к какому классу относится каждый IP-адрес

Старший октет адреса представляем в двоичном коде: если старший бит = 0 (класс А), = 10 (класс B), = 11 (класс С)

192.168.0.15

Ответ: Класс С

127.0.0.1

Ответ: Класс А

112.0.0.15

Ответ: Класс А

167.58.13.21

Ответ: Класс В