Программы, написанные на языках программирования высокого уровня перед выполнением на ЭВМ должны транслироваться в эквивалентные программы, написанные на машинном коде. icon

Программы, написанные на языках программирования высокого уровня перед выполнением на ЭВМ должны транслироваться в эквивалентные программы, написанные на машинном коде.


1 чел. помогло.
Смотрите также:
Рабочая программа по курсу “Программирование на языках высокого уровня” Факультет экономический...
Основные разделы программы Программирование на языке высокого уровня Операционные системы...
Роль и значение языка паскаль в эволюции языков программирования...
Данное пособие поможет написать сочинения для школьников. Внем собраны лучшие сочинения...
Эти произведения автора не относятся к относительно совершенным в литературно духовном и т п...
Параллельные программы главный тормоз 11 2 mpi 11 3 Реализации mpi 12 4 Средства...
«Теория игр и исследование операций» Направления нк, нп 4 курс, 1-й семестр (2008/09 уч год)...
Программы Организации Объединенных Наций по окружающей среде комитет высокого уровня министров...
Рабочая программа по дисциплине Основы алгоритмизации и программирования (язык С/C++) Для...
Составление программы на языке программирования...
Литература [Абрамов89] Абрамов С. А., Зима Е. В...
Алгоритмизация и программирование. Языки программирования высокого уровня...



Загрузка...
страницы: 1   2   3   4   5   6   7   8
вернуться в начало
скачать
^

Типы файловых систем


По способу идентификации данных различают:

  1. Тривиальные ФС, определяющие хранение файлов в единственной «куче», корневом каталоге носителя. Эти системы практически вымерли, и замещены на иерархические. Из применяющихся можно назвать TR-DOS на компьютере Sinclair ZX-Spectrum.

  2. Иерархические ФС, обеспечивающие хранение файлов в древовидной структуре каталогов. Являются самым распространёным видом ФС. В настольных системах начиная с 1990-х применяются практически только они.

  3. Реляционные, ассоциативные, (?) прочие ФС, обеспечивающие другие методы идентификации данных. Применяются крайне редко по причине узкой области применения.

Файловые системы различаются по устойчивости к сбоям:

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

  • Устойчивые к сбоям системы представляют полностью согласованные структуры в любой момент времени существования файловой системы, таким образом, отстутствуют моменты, когда сбой может привестик потерям данных или разрушению ФС. Как правило это журалируемые ФС, дублирующие все изменения структуры в специальной области — журнале, таким образом, в случае сбоя имеющие возможность завершить незавершённую операцию или откратить состояние ФС до сбоя.
^

Специальные возможности файловых систем


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

Разделение прав доступа


Разделение прав доступа существует практически во всех файловых системах, использующихся на многопользовательских ОС. Как правило это возможность установить отдельные права доступа для владельца, группы владельца и остальных пользователей на чтение, запись и исполнение. Такая схема обычна для Posix-совместимых ОС.

В файловой системе NTFS возможна более гибкая настройка прав доступа (для каждого пользователя).

Шифрование


Шифрование — защита информации от считывания непосредственно с носителя, в обход ограничений прав доступа доступно в некоторых файловых системах. У NTFS шифрование — это одна из возможностей, пользователь может выбрать файлы и каталоги, которые он хочет зашифорвать. Некоторые файловые системы специально приспособлены для шифрования данных, это например CryptoFS, или PGPDisk.

Сжатие


Сжатие файлов может обеспечиваться как специальной фаловой системой для этого, так и дополнительной возможностью обычных ФС. Из некогда популярных можно упомянуть DriveSpace, систему, создававшую виртуальный сжатый диск под MS-DOS. Также, сжатие — одна из возможностей, предлагаемых NTFS. При этом файлы с точки зрения пользователя и приложений ничем не отличаются от несжатых, единственное различие — разница в скорости доступа (причём разница неоднозначная, с одной стороны требуется дополнительное процессорное время на сжатие/расжатие, с другой стороны есть выигрыш во времени считывания с носителя) и занимаемом пространстве.
^

Циклические файлы


Возможность создать циклически перезаписываемый файл (англ. rollover) — особенность некоторых файловых систем для AmigaOS. При дописывании в конец циклического файла он не увеличивается в размере, а теряет начало. Такая возможность предоставляет унифицированный механизм для ведения журналов (логов) в приложениях.
^

Восстановление удалённых файлов


Во многих файловых системах при удалении файла он не исчезает бесследно, а только получает отметку «удалён», что означает, что пространство, которое было занято файлом может быть повторно использовано для хранения другой информации. Как правило такие файлы, если поверх них ничего не записано можно восстановить специальными средствами.

Некоторые файловые системы (например Amiga SmartFileSystem) перемещают удалённые файлы в специальный каталог («:.recycled»), из которого их потом можно восстановить стандартным способом — копированием или перемещением. Полное же удаление файла производится лишь при нехватке места или при превышении лимитов.

Потоки


Возможность создания «потоков» файла — специальная возможность файловой системы NTFS. Поток — отдельный массив данных, связанный с файлом, но с доступом через специальный суффикс в пути к файлу. В этом потоки похожи на отдельные файлы, но отличаются тем, что копируются и удаляются вместе с основным потоком, а также имеют общие атрибуты.
^

Перечень файловых систем

Тривиальные

^

Простые иерархические

Журналируемые

^

Файловые системы для компакт-дисков



13. Парадигмы программирования. Машина Тьюринга, нормальные алгоритмы Маркова


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


^ Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

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

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

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

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

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

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

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

Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины D и входные данные X, которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные X.

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

На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).

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

^ Норма́льный алгори́тм Ма́ркова — один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 1940-х годов.

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам в котором алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите | * abc может служить схема



Процесс применения нормального алгоритма к произвольному слову ^ V в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгоритма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая верхняя. Если эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгоритма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDS считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову | * | | последовательно возникают слова | b * | , ba | * | , a | * | , a | b * , aba | * , baa | * , aa | * , aa | c, aac, ac | и c | | , после чего алгорифм завершает работу с результатом | | . Другие примеры смотрите ниже.

Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

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

Пример 1


Использование алгоритма Маркова для преобразований над строками:

Правила:

  1. "А" → "апельсин"

  2. "кг" → "килограмм"

  3. "М" → "магазинчике"

  4. "Т" → "том"

  5. "магазинчике" → ·"ларьке" (заметьте, это заключительная формула!)

  6. "в том ларьке" → "на том рынке"

Исходная строка:

"Я купил кг А в Т М."

При выполнении алгоритма строка претерпевает следующие изменения:

  1. "Я купил кг апельсинов в Т М."

  2. "Я купил килограмм апельсинов в Т М."

  3. "Я купил килограмм апельсинов в Т магазинчике."

  4. "Я купил килограмм апельсинов в том магазинчике."

  5. "Я купил килограмм апельсинов в том ларьке."

На этом выполнение алгоритма завершится (так как будет достигнута формула №5, которую мы сделали заключительной).


14. Парадигмы программирования. Императивное и структурное программирование


Императи́вное программи́рование — это парадигма программирования, которая, в отличие от декларативного программирования, описывает процесс вычисления в виде инструкций, изменяющих состояние программы. Императивная программа очень похожа на приказы, выражаемые повелительным наклонением в естественных языках, то есть это последовательность команд, которые должен выполнить компьютер.

Императивные языки программирования противопоставляются функциональным и логическим языкам программирования. Функциональные языки, например, Haskell, не представляют собой последовательность инструкций и не имеют глобального состояния. Логические языки программирования, такие как Prolog, обычно определяют что надо вычислить, а не как это надо делать.

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

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

Императивное программирование является противоположностью декларативного программирования; второе описывает, что необходимо сделать, а первое — как именно это сделать.


^ Структу́рное программи́рование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом.

В соответствии с данной методологией

  1. Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

    • последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

    • ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;

    • цикл — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие (условие продолжения цикла).

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

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

  2. Разработка программы ведётся пошагово, методом «сверху вниз».

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

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

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

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

  3. Сильно упрощается процесс тестирования и отладки структурированных программ.


15. Парадигмы программирования. Объектно-ориентированное программирование


Объе́ктно-ориенти́рованное программи́рование (ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов (либо, в менее известном варианте языков с прототипированием, — прототипов).

Класс — это тип, описывающий устройство объектов. Понятие «класс» подразумевает некоторое поведение и способ представления. Понятие «объект» подразумевает нечто, что обладает определённым поведением и способом представления. Говорят, что объект — это экземпляр класса. Класс можно сравнить с чертежом, согласно которому создаются объекты. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.

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

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

Прототип — это объект-образец, по образу и подобию которого создаются другие объекты.

Абстракция данных 

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

Инкапсуляция 

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

Сокрытие данных 

Сокрытие данных — неотделимая часть ООП, управляющая областями видимости. Является логическим продолжением инкапсуляции. Целью сокрытия является невозможность для пользователя узнать или испортить внутреннее состояние объекта.

Наследование 

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

Полиморфизм 

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

объектно-ориентированный подход заключается в следующем наборе основных принципов (цитируется по вышеупомянутой книге Т. Бадда[1]).

  1. Всё является объектом.

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

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

  4. Каждый объект является представителем (экземпляром) класса, который выражает общие свойства объектов.

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

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

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

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




оставить комментарий
страница5/8
Дата02.10.2011
Размер0.79 Mb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы: 1   2   3   4   5   6   7   8
хорошо
  1
отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх