для телефона
.pdfциклом.Граф называется связным, если любые две его вершины соединены путём. Связный граф без циклов называется деревом. На рис. 54 изображено дерево, в узлах которого располагаются символы.
Примечание. С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.
Для дальнейшей работы с деревьями необходимо определить ряд понятий.
•Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.
•Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.
•Количество непосредственных потомков внутренней вершины называется ее степенью.
•Степенью дерева называется максимальная степень всех вершин. Например:
•вершины F, D, Е являются непосредственными потомками вершины В;
•вершины F, D, Е являются листьями;
•вершины С, G, Н — внутренние;
•степень вершины В — 3, а вершины Н — 1;
•степень дерева равна 3.
Двоичное дерево — это дерево, в котором из каждой вершины исходит не более двух ребер.
6.2. Представление деревьев Дерево — это сложная динамическая структура данных, применяющаяся для
эффективного хранения информации.
Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой — сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два - левое и правое.
Type TreeLink =^Tree; Tree=Record
Data: <mun данных>; Left, Right: TreeLink;
End;
Корень дерева опишем в разделе описания переменных:
Var kd: TreeLink;
6.3. Основные операции над деревом
К основным операциям над деревьями относятся:
•занесение элемента в дерево;
•обход дерева;
•удаление элемента из дерева. Рассмотрим вставку и обход дерева на примере следующей задачи.
6.5. Удаление из дерева Непосредственное удаление элемента из упорядоченного дерева реализуется
достаточно просто, если эта вершина является конечной (рис. 55) или из нее выходит только одно ребро (рис. 56). Для этого нужно изменить соответствующую ссылку у предшествующей вершины.
Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины (рис. 57).Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая:
•удаляемая вершина имеет два поддерева (В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка);
•удаляемая вершина имеет не более одного поддерева (0 или 1);
•удаляемой вершины в дереве нет. Ниже приведена рекурсивная процедура deltree, решающая поставленную задачу. Она отыскивает элемент с заданным ключом и удаляет его.
В процедуре deltree описана вспомогательная процедура dl, которая работает только в первом из трех перечисленных случаев.Вспомогательная процедура dl "движется" по правой ветви левого поддерева исключаемого элемента q^ и заменяет значение ключа в q^ на соответствующее значение из самого правого элемента r^ левого поддерева.
19.
20.Дисциплина программирования, структурный подход программирования. Возникновение объектно –ориентированного программирования.
Цели структурного программирования:1)Обеспечение дисциплины программирования (“Структурное программирование-это дисциплина, которую программист навязывает сам себе”- Э. Дейкстра); 2)Повышение эффективности
(например, разбиение на относительно независимые модули);3)Повышение надежности (облегчение тестирования и отладки);4)Уменьшение времени и стоимости (повышение производительности программистов); 5)Улучшение читабельности программы Основные принципы структурного подхода:1)Принцип абстракции позволяет
рассматривать программу по уровням. Верхний уровень показывает детали реализации (например, восходящее и нисходящие стратегии программирования).2)Разделение программы на отдельные фрагменты (методы), которые просты по управлению и допускают независимую откладку и тестирование 3)Строгий методический подход (принцип формальности) позволяет изучать программы (алгоритмы) как математические объекты, ускорить принятия решений, избежать ошибок Структурный подход включает в себя три основные составные части:1)Нисходящее проектирование;2)Структурное программирование;3)Сквозной структурный контроль. Объе́ктно-ориенти́рованное программи́рование(ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов (либо, в менее известном варианте языков с
прототипированием — прототипов). Класс — это тип, описывающий устройство объектов — экземпляров. Класс можно сравнить с чертежом, согласно которому создаются объекты. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.Прототип — это образцовый объект, по образу и подобию которого создаются другие объекты.Объектное и объектно-ориентированное программирование (ООП) возникло в результате развития идеологии процедурного программирования, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны. Кроме того, в современном объектно-ориентированном программировании часто большое значение имеют понятия события (так называемое событийно-ориентированное программирование) и компонента (компонентное программирование).Объектно-ориентированное программирование в настоящее время является абсолютным лидером в области прикладного программирования (языки Java, C#, C++, JavaScript, ActionScript и др.). В то же время в области системного программирования до сих пор лидирует парадигма процедурного программирования, и основным языком программирования является язык C. Хотя при взаимодействии системного и прикладного уровней операционных систем заметное влияние
стали оказывать языки объектно-ориентированного программирования. Исторически сложилось так, что программирование возникло и развивалось как процедурное программирование, которое предполагает, что основой программы является алгоритм, процедура обработки данных. Объектноориентированное программирование - это методика разработки программ, в основе которой лежит понятие объекта как некоторой структуры, описывающей объект реального мира, его поведение. Задача, решаемая с использованием методики объектно-ориентированного программирования, описывается в терминах объектов и операций над ними, а программа при таком подходе представляет собой набор объектов и связей между ними. Другими словами можно сказать, что объектно-ориентированное программирование представляет собой метод программирования, который весьма близко напоминает наше поведение. Оно является естественной эволюцией более ранних нововведений в разработке языков программирования. Объектноориентированное программирование является более структурным, чем все предыдущие разработки, касающиеся структурного программирования. Оно также является более модульным и более абстрактным, чем предыдущие попытки абстрагирования данных и переноса деталей программирования на внутренний уровень.
21. Классификация программного обеспечения.Языки программирования и их классификация. Метаязыки. Парадигмы и технологии программирования. Трансляторы и их виды.
Программное обеспечение-это совокупность программ, выполненных вычислительной системой. К программному обеспечению (ПО) относится также вся область деятельности по проектированию и разработке (ПО): технология проектирования программ (нисходящее проектирование, структурное программирование и др.); методы тестирования программ; методы доказательства правильности программ; анализ качества работы программ и др.
Программное обеспечение - неотъемлемая часть ЭВМ. Оно является логическим продолжением технических средств ЭВМ, расширяющие их возможности и сферу использования.
Классификация программного обеспечения: -системное програмное обеспечение; -прикладное програмное обеспечение;-инструментарий программирования.
Существует три категории: 1) Прикладные программы, непосредственно обеспечивающие выполнение необходимых пользователям работ.2) Системные программы: управление ресурсами ЭВМ;создание копий используемой информации; проверку работоспособности устройств компьютера;выдачу справочной информации о компьютере и др.. 3) Инструментальные программные системы, облегчающие процесс создания новых программ для компьютера.
Более или менее определенно сложились следующие группы программного обеспечения: операционные системы. системы программирования, инструментальные системы, интегрированные пакеты,динамические электронные таблицы,системы машинной графики,системы управления базами данных (СУБД),прикладное программное обеспечение.
Языки программирования и их классификация
По наиболее распространенной классификации все языки программирования, в соответствии с тем, в каких терминах необходимо описать задачу, делят на языки низкого и высокого уровня.Если язык близок к естественному языку программирования, то он называется языком высокого уровня, если ближе к машинным командам, – языком низкого уровня.В группу языков низкого уровня входят машинные языки и языки символического кодирования: Автокод, Ассемблер. Операторы этого языка – это те же машинные команды, но записанные мнемоническими кодами, а в качестве операндов используются не конкретные адреса, а символические имена. Все языки низкого уровня ориентированы на определенный тип компьютера, т. е. являются машинно– зависимыми.Машинно–ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.).К языкам программирования высокого уровня относят Фортран (переводчик формул Алгол, Кобол (коммерческий язык – используется, в первую очередь, для программирования экономических задач), Паскаль, Бейсик (был разработан профессорами Дармутского колледжа Джоном Кемени и Томасом Курцом.), Си (Деннис Ритч – 1972 году), Пролог (в основе языка лежит аппарат математической логики) и т.д.Программу, написанную на языке
программирования высокого уровня, ЭВМ не понимает, поскольку ей доступен только машинный язык. Языки программирования также можно разделять на
поколения:– языки первого поколения: машинно–ориентированные с ручным управлением памяти на компьютерах первого поколения.– языки второго поколения: с мнемоническим представлением команд, так называемые автокоды.– языки третьего поколения: общего назначения, используемые для создания прикладных программ любого типа. Например, Бейсик, Кобол, Си и Паскаль.– языки четвертого поколения: усовершенствованные, разработанные для создания специальных прикладных программ, для управления базами данных.- языки программирования пятого поколения: языки декларативные, объектно–ориентированные и визуальные. Например, Пролог, ЛИСП (используется для построения программ с использованием методов искусственного интеллекта), Си++, Visual Basic, Delphi.
Языки программирования также можно классифицировать на процедурные и непроцедурные.В процедурных языках программа явно описывает действия, которые необходимо выполнить, а результат задается только способом получения его при помощи некоторой процедуры, которая представляет собой определенную последовательность действий. Среди процедурных языков выделяют в свою очередь структурные и операционные языки. В структурных языках одним оператором записываются целые алгоритмические структуры: ветвления, циклы и т.д. В операционных языках для этого используются несколько операций. Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1. Среди операционных известны Фортран, Бейсик, Фокал. Непроцедурное (декларативное) программирование появилось в начале 70-х годов 20 века, К непроцедурному программированию относятся функциональные и логические языки. В функциональных
языках программа описывает вычисление некоторой функции. Обычно эта функция задается как композиция других, более простых, те в свою очередь делятся на еще более простые задачи и т.д. Один из основных элементов функциональных языков – рекурсия. Оператора присваивания и циклов в классических функциональных языках нет. В логических языках программа вообще не описывает действий. Она задает данные и соотношения между ними. После этого системе можно задавать вопросы. Машина перебирает известные и заданные в программе данные и находит ответ на вопрос.
Парадигмы программирования Парадигма программирования — это система идей и понятий, определяющих стиль написания компьютерных программ, а также образ мышления программиста. Парадигма программирования в
современной индустрии программирования очень часто определяется набором инструментов программиста (язык программирования и операционная система).Парадигма программирования представляет (и определяет) то, как программист видит выполнение программы. Например, в объектноориентированном программировании программист рассматривает программу как набор взаимодействующих объектов, тогда как в функциональном программировании программа представляется в виде цепочки вычисления функций.Приверженность определённого человека какой-то одной парадигме иногда носит настолько сильный характер, что споры о преимуществах и недостатках различных парадигм относятся в околокомпьютерных кругах к разряду так называемых «религиозных» войн.
История термина.
Термин «парадигма программирования» впервые применил Роберт Флойд в своей лекции лауреата премии Тьюринга.Флойд отмечает, что в программировании можно наблюдать явление, подобное парадигмам Куна, но, в отличие от них, парадигмы программирования не являются взаимоисключающими: Если прогресс искусства программирования в целом требует постоянного изобретения и усовершенствования парадигм, то совершенствование искусства отдельного программиста требует, чтобы он расширял свой репертуар парадигм. Таким образом, по мнению Роберта Флойда, в отличие от парадигм в научном мире, описанных Куном, парадигмы программирования могут сочетаться, обогащая инструментарий программиста. Основные модели программирования :Императивное программирование, Функциональное программирование, Логическое программирование,Объектноориентированное программирование.
Подходы и приёмы: Структурное программирование, Процедурное программирование,Декларативное программирование, Обобщённое программирование,Порождающее программирование,Аспектноориентированное программирование,Рекурсия,Автоматное программирование,Событийно-ориентированное программирование,Компонентно-ориентированное программирование Императивное программирование — это парадигма программирования, которая, в отличие от декларативного программирования, описывает процесс вычисления в виде инструкций, изменяющих состояние программы. Императивная программа очень похожа на приказы, выражаемые
повелительным наклонением в естественных языках, то есть это последовательность команд, которые должен выполнить компьютер. Функциональное программирование — раздел дискретной математики и парадигм программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних.
Трансляторы и их виды. для перевода программы с языка программирования на язык машинных кодов используют специальные программы – трансляторы. Существует три вида транслятора: интерпретаторы (это транслятор, который производит пооператорную обработку и выполнение исходного кода программы), компиляторы (преобразует всю программу в модуль на машинном языке, после чего программа записывается в память компьютера и лишь потом исполняется) и ассемблеры (переводят программу, записанную на языке ассемблера, в программу на машинном языке).
22. язык программирования алфавит, синтаксис ,лексема, семантика.Комментарии , пространство имен,ключевые слова. Основными элементами любого языка программирования являются его алфавит, синтаксис и семантика. Алфавит – совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала. Лексика – совокупность правил образования цепочек символов (лексем), образующих идентификаторы (переменные и метки), операторы, операции и другие лексические компоненты языка. Сюда же включаются зарезервированные (запрещенные, ключевые) слова языка программирования, предназначенные для обозначения операторов, встроенных функций и пр. Иногда эквивалентные лексемы, в зависимости от языка программирования, могут обозначаться как одним символом алфавита, так и несколькими. Например, операция присваивания значения в языке Си обозначается как «=», а в языке Паскаль – «:=». Операторные скобки в языке Си задаются символами «{» и «}», а в языке Паскаль – begin и end. Граница между лексикой и алфавитом, таким образом, является весьма условной, тем более что компилятор обычно на фазе лексического анализа заменяет распознанные ключевые слова внутренним кодом (например, begin – 512, end – 513) и в дальнейшем рассматривает их как отдельные символы. Синтаксис – совокупность правил образования языковых конструкций, или предложений языка программирования – блоков, процедур, составных операторов, условных операторов, операторов цикла и пр.
Особенностью синтаксиса является принцип вложенности (рекурсивность) правил построения конструкций. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла.Необходимо строгое соблюдение правил правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации. Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, после каждого оператора. Перед словом End точку с запятой можно не ставить. Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.В БНФ(формула Бекуса – Наура) всякое синтаксическое понятие описывается в виде формулы, состоящей из правой и левой части, соединенных знаком ::=, смысл которого эквивалентен словам «по определению есть». Слева от знака ::= записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки <>, а в правой части записывается формула или диаграмма, определяющая все множество значений, которые может принимать метапеременная. Синтаксис языка описывается путем последовательного усложнения понятий: сначала определяются простейшие (базовые), затем все более сложные, включающие в себя предыдущие понятия в качестве составляющих.
В записях метаформул приняты определенные соглашения. Например, формула БНФ, определяющая понятие «двоичная цифра», выглядит следующим образом: <двоичная цифра>::=0|1 Значок «|» эквивалентен слову «или».В диаграммах стрелки указывают на последовательность расположения элементов синтаксической конструкции; кружками обводятся символы, присутствующие в конструкции.Понятие «двоичный код» как непустую последовательность двоичных цифр БНФ описывает так:<двоичный код>::=<двоичная цифра>|<двоичныйкод><двоичная цифра>Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диаграмма более наглядна, чем БНФ.Синтаксические диаграммы были введены Н. Виртом и использованы для описания созданного им языка Паскаль.Семантика – смысловое содержание конструкций, предложений языка,
семантический анализ – это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорить о допустимости операции с данной переменной. Семантические ошибки возникают при недопустимом использовании операций, массивов, функций, операторов и пр. Пространство имён — некоторое множество, под которым подразумевается модель, абстрактное хранилище или окружение, созданное для логической группировки уникальных идентификаторов (то есть имён). Идентификатор, определенный в пространстве имён, ассоциируется с этим пространством. Один и тот же идентификатор может быть независимо
определён в нескольких пространствах. Таким образом, значение, связанное с идентификатором, определённым в одном пространстве имён, может иметь (или не иметь) такое же значение, как и такой же идентификатор, определённый в другом пространстве. Языки с поддержкой пространств имён определяют правила, указывающие, к какому пространству имён принадлежит идентификатор (то есть его определение). Например, Андрей работает в компании X, а ID (сокр. от англ. Identifier — идентификатор) его как работника равен 123. Олег работает в компании Y, а его ID также равен 123. Единственное (с точки зрения некой системы учёта), благодаря чему Андрей и Олег могут быть различимы при совпадающих ID, это их принадлежность к разным компаниям. Различие компаний в этом случае представляет собой систему различных пространств имён (одна компания — одно пространство). Наличие двух работников в компании с одинаковыми ID представляет большие проблемы при их использовании, например, по платёжному чеку, в котором будет указан работник с ID 123, будет весьма затруднительно определить работника, которому этот чек предназначается.
В больших базах данных могут существовать сотни и тысячи идентификаторов. Пространства имён (или схожие структуры) реализуют механизм для сокрытия локальных идентификаторов. Их смысл заключается в группировке логически связанных идентификаторов в соответствующих пространствах имён, таким образом делая систему модульной. Ограничение видимости переменных может также производиться путём задания класса её памяти. Операционные системы, многие современные языки программирования обеспечивают поддержку своей модели пространств имён: используют каталоги (или папки) как модель