Подпрограммы (процедуры и функции). Рекурсия

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

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

Вспомогательный алгоритм тоже может вызывать другие вспомогательные, длина такой цепочки вызовов теоретически не ограничена. Здесь и далее следующие пары слов используются как синонимы: алгоритм и программа, вспомогательный алгоритм и подпрограмма, команда и оператор, программа и модуль. Вспомогательными и основными алгоритмы являются не сами по себе, а по отношению друг к другу.

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

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

При работе с подпрограммами важными являются понятия формальных и фактических параметров. Формальные параметры — это идентификаторы входных данных для подпрограммы. Если формальные параметры получают конкретные значения, то они называются фактическими. Формальные параметры могут получить конкретные значения только в той программе, где производится обращение к данному модулю-подпрограмме. Тип и порядок записи фактических параметров должны быть такими же, как и формальных параметров. В противном случае результат работы программы будет непредсказуемым. Из этого следует, что фактические параметры используются при обращении к подпрограмме из основной, а формальные параметры — только в самом модуле.

Подпрограмма с параметрами используется для записи многократно повторяющихся действий при разных исходных данных. Подпрограммы с параметрами можно разделить на два типа: подпрограммы-функции и просто подпрограммы с параметрами (их называют процедурами).

При составлении подпрограмм с параметрами надо соблюдать следующие правила:

1) каждая подпрограмма имеет свое имя и список формальных параметров;

2) процедура из основной программы вызывается командой вызова, которая по форме ничем не отличается от вызова команды исполнителя. Результат присваивается одной или нескольким переменным, которые находятся в списке формальных параметров. Но результатом могут быть, конечно, не только значения переменных, но какое либо действие, выполненное ЭВМ.

Подпрограмма.

1) Ввести натуральные числа M, N.2) Если M=N, перейти к п. 5, иначе к следующему пункту.3) Если M>N, то M:=M-N, иначе N:=N-M.4) Перейти к п. 2.5) Передать значение M в основную программу.6) Конец подпрограммы.

Рекурсия

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

Например, приведенное ниже определение двоичного кода является рекурсивным:

<двоичный код>::= <двоичная цифра> | <двоичный код><двоичная цифра> <двоичная цифра>::= 0 | 1

Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".

Вообще, в рекурсивном определении должно присуствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.

Билет №43

Модель данных

В классической теории баз данных, модельданных есть формальная теория представления и обработки данных в системе управления базами данных (СУБД), которая включает, по меньшей мере, три аспекта:

1) аспект структуры: методы описания типов и логических структур данных в базе данных;

2) аспект манипуляции: методы манипулирования данными;

3) аспект целостности: методы описания и поддержки целостности базы данных.

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

Иерархические структуры

 

Дерево (или иерархическая структура) – это конечное множество Т элементов, такое, что выполняются следующие условия:

1. имеется один специально выделенный элемент, называемый корнем дерева;

2. остальные элементы (кроме корня) содержатся в m ≥ 0 попарно не пересекающихся множествах Т₁,....Т_m, каждое из которых в свою очередь является деревом. Деревья Т₁,....Т_m являются поддеревьями данного дерева.

Пример дерева показан на рисунке 5:

 

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

1. исходное множество Т = {Студенты, 01-АС, 02-ВТ, 01-ИЭ, Федоров Ф.Ф., Петров П.П., Иванов И.И., Сидоров С.С., Яковлев Я.Я.};

2. в качестве корня выступает элемент Студенты;

3. непересекающиеся множества в составе:

Аналогичным образом, можно рассматривать вершины, соответствующие фамилиям и инициалам студентов, как вырожденные деревья, представленные только корнями. Для них выполняется условие, когда число непересекающихся подмножеств остальных элементов множества Т равно 0: m = 0.

 

БИЛЕТ №44

1) Модем (акроним, составленный из слов мо дулятор и дем одулятор) — устройство, применяющееся в системах связи для физического сопряжения информационного сигнала со средой его распространения, где он не может существовать без адаптации, и выполняющее функцию модуляции при передаче сигнала и демодуляции при приёме сигнала из канала связи (чаще всего в речевом диапазоне).

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

Модемы широко применяются для связи компьютеров через телефонную сеть (телефонный модем) или кабельную сеть (кабельный модем). Ранее модемы применялись также в сотовых телефонах (пока не были вытеснены цифровыми способами передачи данных).

Сетевая карта

Сетевая плата, также известная как сетевая карта, сетевой адаптер, Ethernet-адаптер, NIC (англ. network interface card) — периферийное устройство, позволяющее компьютеру взаимодействовать с другими устройствами сети. В настоящее время, особенно в персональных компьютерах, сетевые платы довольно часто интегрированы в материнские платы для удобства и удешевления всего компьютера в целом.

Типы

По конструктивной реализации сетевые платы делятся на:

§ внутренние — отдельные платы, вставляющиеся в ISA, PCI или PCI-E слот;

§ внешние, подключающиеся через LPT ^[1] , USB или PCMCIA интерфейс, преимущественно использующиеся в ноутбуках;

§ встроенные в материнскую плату.

На 10-мегабитных сетевых платах для подключения к локальной сети используются 4 типа разъёмов:

§ 8P8C для витой пары;

§ BNC-коннектор для тонкого коаксиального кабеля;

§ 15-контактный разъём AUI трансивера для толстого коаксиального кабеля.

§ оптический разъём (en:10BASE-FL и другие стандарты 10 Мбит Ethernet)

Эти разъёмы могут присутствовать в разных комбинациях, иногда даже все три сразу, но в любой данный момент работает только один из них.

На 100-мегабитных платах устанавливают либо разъём для витой пары (8P8C, ошибочно называемый RJ-45 ^[2] ), либо оптический разъем (SC, ST, MIC ^[3] ).

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

Одной из первых массовых сетевых карт стала серия NE1000/ NE2000 фирмы Novell с разъемом BNC.

Билет №45

1) Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Структура данных часто является реализацией какого-либо абстрактного типа данных.

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

Хорошо спроектированное хранилище данных оптимизирует использование ресурсов (таких как время выполнения операций, используемый объём оперативной памяти, число обращений к дисковым накопителям), требуемых для выполнения наиболее критичных операций.

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

Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров.

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.

Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов STL языка C++.

Фундаментальными строительными блоками для большей части структур данных являются массивы, записи (см. конструкцию struct в языке Си и конструкцию recordв языке Паскаль), размеченные объединения (см. конструкцию union в языке Си) и ссылки. Например, структура данных двусвязный список, может быть построена с помощью записей и зануляемых ссылок, а именно, каждая запись будет предоставлять блок данных (узел, node), содержащий ссылки на «левый» и «правый» узлы, а