Понятие алгоритм. Формальные признаки.

Понятие алгоритм. Формальные признаки.

Способы задания алгоритма. Виды алгоритмов.

Теорема Дейкстра.

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

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

· Дискретность (возможность разбиения определяемого алгоритмом вычислительного процесса на конечное число отдельных действий/шагов)

· Понятность (все шаги закончены и понятны для исполнения)

· Детерминированность (алгоритм выдает один и тот же результат при одних и тех же действиях)

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

· Результативность (алгоритм завершает действие и выдает результат за конечное число действий)

Способы задания:

· Словесный

· Формулировочный (словесный + формулы/знаки)

· Графический (блок-схема)

· Язык операторных схем (с помощью операторов)

· Язык программирования

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

· Линейные

· Ветвления (IF)

· Циклические программы(For)

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

Понятие языка программирования. Компилируемые и интерпретируемые языки программирования. История появления.

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

Программа на компилируемом языке при помощи компилятора преобразуется в набор инструкций для данного типа процессора.(C, Pascal)

Если программа на интерпретируемом языке – интерпретатор выполняет программу без перевода в машинный код. Т.е. программа на исходном языке и не может работать без интерпретатора. (HTML, XML)

Компилируемые

Достоинства: компилируемые программы как правило выполняются быстрее и не требуют для выполнения дополнительных программ.

Недостатки: при изменении текста программы требуется ее перекомпиляция; скомпилированная программа может выполняться только на том же типе процессоров (над той же ОС, на которой был рассчитан компилятор); чтобы получить файл для другого процессора, требуется перекомпиляция.

Интерпретируемые

Достоинств а: можно запускать сразу после изменения исходного кода (облегчаемая разработка); можно запустить на разных типах компьютеров и ОС без дополнительных усилий

Недостатки: выполняются медленнее компилируемых и не могут выполняться без программы интерпретатора

Ассемблер – Фортран - Фортран66 – ALGOL - Simula67 - Pascal,Ada,C - C#, J# - C++,Java

 

Классификация языков программирования. Языки низкого уровня. Языки высокого уровня.

Низкий уровень – машинный, машинно-ориентированный

· Машинный – содержание и правила которого реализованы аппаратными средствами компьютера. Это язык центрального процессора компьютера. Символы языка – двоичный код. Достоинства – возможна обработка программы с максимальной производительностью, возможность использования конкретных аппаратных ресурсов. Недостатки – низкая скорость программирования, его трудоемкость.

· Машинно-ориентированный – представление команд, данных, адресов. Это язык ассемблера. Инструкции с ассемблером переводятся 1:1 на машинный язык. Ассемблер состоит из предложений 3 типов: операторы машинных команд, вспомогательные инструкции, макросы. Достоинства – недостатки те же. Отличие – появились такие понятия, как переменные, области памяти хранения данных, типы данных.

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

Основаны на принципах:

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

· Отдаление от деталей, связанных с работой компьютера

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

Недостатки: программа менее эффективна, чем аналог на низком уровне; оторванность от аппаратной реализации компьютера.

 

4.Язык Си. Общие сведения. Элементы языка Си. Лексемы. Комментарии.Ключевые слова. Идентификаторы.

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

Элементы языка С:

Лексема (Tokens), Комментарий (Comments), Ключевые слова, key word), Идентификатор (identifies), Константы, Строки, Разделители и специальные слова

В состав лексем входят:

Key words, Identifiers, Constants, String, Operators, Разделители

Комментарии – это последовательность символов, которые начинаются /* и заканчиваются /*

Он может включать любую последовательность печатных символов, включая переход на новую строку. Внутри комментария нельзя писать /*.

Комментарий не является лексической единицей компилятора.

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

Ключевые слова.

Это зарезервированные индетификаторы, которые наделены определённым смыслом.

Можно использовать только в соответствии со значением, известным компилятору языка Си. Их нельзя использовать в качестве имен индетификатора.

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

Особенности имен идентификатора:

· Различие букв верхнего и нижнего регистра

· Количество значащих символов в имени идентификатора

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

 

Элементы языка Си. Константы. Целочисленные константы. Константы с плавающей запятой. Константы перечисления.

Константы – это числа, символы, символьные строки, которые могут использоваться в программе как значения

4 типа констант:

· Целочисленные

· С плавающей запятой

· Константы перечисления

· Символьные константы

Целочисленные константы - это десятичные, восьмеричные, шестнадцатеричные числа, которые принимают целые значения.

С плавающей запятой - это константы представляющие вещественные числа.

Константы перечисления - это набор именованных целочисленных констант.

 

Элементы языка Си. Символьные константы. Управляющая последовательность. Строки. Разделители (символы пунктуации) и специальные символы.

Символьные константы - это символ, заключенный в апостроф.

Управляющая последовательность - это способ задания символа с использование специального формата.

Строки – это последовательность символов, заключенных в двойные кавычки.

Разделители (символы пунктуации, специальные символы) – это символы пунктуации в языке Си имеют различные использования от структур исходного кода программ до указания компилятора. Некоторые символы пунктуации используются как операторы. Назначение символов определяется контекстом их использования.

 

 

Типы данных. Производные типы. Перечисления. Объявление нового имени типа.

Перечисление – набор линованных целочисленных констант.

Typedef<имя типа><имя нового типа>;

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

 

Операторы цикла.

Оператор цикла – For. Для него используется условие, которое проверяет условное выражение до начала каждой операции.

3 варианта результата проверки:

· Условие истинно – выполнение цикла

· Условие ложно – выполнение цикла прекращается

· Условие не задано – условие всегда истинно

Этот оператор реализует фундаментальный принцип вычислений в программировании, т.е. принцип итерации.

Итерация – последовательное повторение одних и тех же действий заданное количество раз. В качестве оператора можно использовать функциональный блок. Оператор break завершает выполнение цикла.

Continue заставляет пропустить остаток тела цикла и перейти к следующей итерации.

 

Операторы перехода.

Goto передает управление на оператор, отмеченный меткой (label). Метка располагается в теле функции.

Метка может быть как до goto, так и после.

 

 

Указатель на функцию.

Указатель, полученный взятием адреса функции можно использовать для вызова данной функции.

Адрес функции – адрес начала функции (т.е. первой ассемблерной инструкции).

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

Указатели на функцию: пример способа применения указателя – полиморфные функции.

 

19. Файлы. Файловая система. Свойства файла (имя, расширение, атрибуты, время, владелец и группа, права доступа).

Файлы*

Файловая система(фс)*

Все файлы обладают свойствами, но в зависимости от фс эти свойства различны

Свойства файла для всех:

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

FAT 12, FAT 16 (длина имени – 8 символов+3 на расширение),VFAT (255 байт), FAT 32, HPFS (255 символов), HTFS (256 юникод символов), ext2, ext3 (255 байт)

Есть еще ограничение по набору допустимых символов

MS – DOS можно: только заглав. буквы и цифры

Нельзя: пробел? * > < | \: “ ”

Windows нельзя: |? * > < / \: “ ”

Unix/Linux нельзя: /:

Большинство ОС недопускают наличие в 1 каталоге файлов с одинаковым именем.

· Расширение имени файла как самостоятельный атрибут существует только в FAT 12/FAT 16, во всех остальных расширение это условность (часть имени, отделенная самой правой точкой)

· Атрибуты – это набор значений типа «да/нет» выполняет исключительно информативную роль, на доступ к файлам не влияет

READ ONLY – только для чтения

SYSTEM – системный

HIDDEN – скрытый

ARCHIVE – архивный (требующий архивации)

· Время

У каждого файла есть:

üВремя создание

üВремя последней идентификации

üВремя последнего доступа

· Владелец и группы

Когда создается файл указывается владелец и группа к которой он принадлежит

· Правила доступа

В некоторой фс предусмотрена возможность ограничения доступа пользователем содержимому к файлам

 

Типы файлов

üОбыкновенный (позволяющий выполнять чтение и запись)

üДиректория (каталог) (файл содержащий записи от др. файлов в том числе и под каталог)

üЖесткая ссылка (hard link) (в общем случае одна и та же область памяти может иметь неск. имен, которые указывают на одни и те же данные. В общем случае после создания ссылки нельзя сказать, кто исходный файл, они равноправны. Данные существуют пока сущ. Хотя бы одно из имен. Ссылку можно создать только на одном физическом носителе)

ü Символьная ссылка (soft link) (файл, содержащий в себе ссылку на другой файл или директорию. Файл может ссылаться на любой элемент файловой системе, в том числе на другом носителе)

(Windows: ….enk)

Операции с файлами

· Связанные с открытием

Открытие (указ-ся имя, режим доступа, режим общего доступа) результат – дескриптор этого файла

Закрытие файла (указ-ся дескриптор)

Чтение, запись (дескриптор, буфер)

Перемещение файлового указателя (дескриптор, позиция)

Получение текущего значение файлового указателя (дескриптор)

Сброс файловых буферов (flush) (дескриптор)

модификация

· Не связанные

* операции управляют размером, именем, положением в дереве каталогов (не получают доступ к содержимому файла)

Удаление Переименование

Перемещение Копирование

Создание ссылки Получение /изменение атрибутов

21.Файлы. Функции для работы с файлами. Операции, связанные с открытием файла. Дескриптор файла типа int (Unix), дескриптор файла типа FILE (FILE*) (любая), дескриптор файла типа HANDLE(Windows).

FILE*

Откр.fopen (char* filename, char* mode(тип доступа))

Типы доступа:

“r” – чтение “w” – запись

“a” – запись в конец (добавление) “r+” – чтение и запись

“w+” – открытие нового файла на чтение и запись

“a+” – открытие на чтение и добавление

“rb” “wt” “w+t”* (“b” – бинарный файл “t” – текстовый используются только вместе с осн.)

В случае ошибки – NULL

Закр. fclose (FILE* f)

Чтение

size_t fread (void buf, size_t size, size*. count, FILE* f)

Запись fwrite(…)

Форм. печать

fprintf (FILE* f, char* frm,…)

Форм. скан. fscanf (FILE* f, char* frm,…)

· Fseek – устанавливает текущее значение файлового указателя

(от нач, от кон, от тек. позиции)

Fteel – показывает текущее значение файлового указателя

HANDLE

Откр. Create file (char* file name, DWORD dw Access DWORD dw ShareMode DWORD dw CrDisp DWORD dw Flags SECURITY_ATTRIBUTES lp SecAttr HANDLE hTemplate)

Типы доступа:

 

Create file – созд/откр файл, директорию физ. диск, раздел, буфер консоли, pipe, и другие коммуникационные ресурсы.

CREATE_ALWAYS – созд. нового файла, если есть, то очищается

CREATE_NEW – созд. нового файла, если есть, то ошибка

OPEN_ ALWAYS – откр. существующего, если нет, то созд.

OPEN_EXISTING – откр. существующего, если нет, то ошибка

TRUNCATE_EXISTING – откр. сущ. файла и очищение, если нет, то созд.

 

FILE_ATRIBUTE_NORMAL

FILE_ATRIBUTE_READONLY

FILE_ATRIBUTE_SYSTEM

FILE_FLAG_NO_BUFFERING – без кош/кеш(???)

FILE_FLAG_OVERLAPPED – при работе в асинхронном режиме

В случае ошибки HANDLE возвращает

INVALID_ HANDLE_VALUE

Boolclose Handle (HANDLE hobj) – возвращает бул. значение

BoolReadFile (HANDLE hfile,…)

BoolWriteFile (HANDLE hfile,…)

 

Int

int open (char* file name, int oflag, int pmode)

pmode (тип доступа): _S_IWRITE

_S_IREAD

Oflag: O_RDONLY

O_WRONLY

O_RDWR

O_APPEND – добыв

O_CREAT – созд. нового файла

O_TRUNC – откр. с обрез.

O_TEXT

O_BINARY

(Ctrl +F1)

int close (int fd)

int read (int fd, void buf, size_t count)

int write (int fd)

 

22.Файлы. Функции для работы с файлами. Операции, не связанные с открытием файла (удаление, копирование, перенос/переименование). Функции для работы с каталогами (создание, удаление, получение списка файлов).

Удаление

Win: BoolDeleteFile (char* file name)

Unix: int unlink (char* name) – только файлы

int remove (char* name) – только файлы + каталог пустой

Копирование

Win: BoolCopyFile (char*. name, char* newfile, BOOLbFailIfExists)

Unix: —

Перемещение

Win: MoveFile (char*. name, char* newfile)

Unix: int rename (char* old path, char* new path)

Создание каталога

Win: CreateDirectory (char* Path name(полный путь), SECURITY_ATTRIBUTES* pAttr) (TRUE)

Unix: mkdir (char* pathname(полный путь), int pmode) (0)

Удаление каталога

Win: BoolRemoveDirectory (char* lpPathName) (TRUE)

Unix: rmdir (char* pathname, int pmode) (0)

Показ списка каталогов

Win: HANDLE FindFirstFife (char* pFile name(строго пути до файла или каталога с символами маски), WIN32_FIND_DATA* pDATA (указатель на структуру, в которой сохраняется информация о первом найденном bvtyb))

* функция открывает идентификатор поиска и заполняет параметр pDATA первым найденным именем, если не верно, то INVALID_ HANDLE_VALUE

Символы маски: *(любое кол-во произвольных символов в том числе и 0)

?(1 произвольный символ)

 

Bool FindNextFife (HANDLE hfind(идентификатор поиска из первой функции), WIN32_FIND_DATA* pDATA)

* функция продолжает поиск и заполняет структуру pDATA следующим найденным именем или каталогом (TRUE, FALSE)

 

FindClose (HANDLE hfind) (TRUE)

Unix: DIR* opendir (char* name(путь до каталога)) функция возвращает указатель на открытый файл или NULL

Необходимо подключить <sys/types.h> <dirent.h>

Dirent* readdir (DIR* dir) – чтение след. записи каталога

функция возвращает указатель на Dirent* или NULL

int closedir (DIR* dir(указатель на структуру описания директории)) (0, -1)

 

Линейные

Массив, список, очередь, стек, дек, хэш-таблица

Массив (яд, индекс. массив) – сд, эл-ты которой расположены в памяти др. за др., доступ к ним осущ-ся по индексам

Кол-во используемых индексов различно

Операции:

· Получение значения эл-та по индексу

· Установка значения эл-та по индексу

Дост.:

Легкость вычисления адреса эл-та по индексу

Одинаковое время доступа ко всем эл-там

Мин. Размер эл-в (только собственные данные)

Недост.:

Для статич. массива это отсутствие динамики (удаление и вставка эл-та, сдвигая другие)

Для динамич. более низкое быстродействие по сравнению со статич. и доп. расходы на поддержку динамич св-в

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

Список — сд, её эл-ты расположены в памяти в произв. порядке, эл-ты связаны м/д собой, образуя лин. последовательность, порядок эл-в в списке может не совпадать с порядком расположения в памяти. Каждый эл-т содержит соб. данные и 1-2 ссылки на соседние эл-ты (односвязный двусвязный) Операции:

· удалить из списка

· поместить в список

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

Операции:

· вставка в очередь

· удаление из очереди

 

 

24. Структуры данных. Понятие Структуры данных. Линейные структуры данных (стек, дек, хеш-таблица).

См в №23

Стек - сд доступ к данным по принципу LIFO

Стек м/б реализован на базе массива или списка

Операции:

· push (добавление в стек)

· pop (удаление из стека)

Дек – (двусвязная очередь) сд, в которой эл-ты добав. и удал. как в начале так и в конце

Операции:

· push Back (добав. эл-т – последний)

· pop Front (добав. эл-т – первый)

· push Front (2 эл-т с конца– последний)

· pop Back(2 эл-т с конца – первый)

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

Ключ – некий уник. идентификатор данных эл-та

Обычно ключ получается применением Hash функций к данным эл-та

Типы:

· таблица в которой не допускается дублирование ключей

· таблица в которой возможно хранение эл-в с одинак. ключами

Hash Table – допускается дубл.

Ассоциатив-й масс. – по опр. не допускается дубл.

Hash Table чаще всего реализуется на базе масс. в этом случае ключ – индекс

Операции:

· Добавление эл-та (в 3 этапа)

1. расчет знач. ключа

2. проверка возможности добав. эл-та в табл.

3. добав.

· Удаление эл-та (в 3 этапа)

1. расчет знач. ключа

2. проверка наличия эл-та

3. удаление

· Поиск эл-та в таблице

1. расчет знач. ключа

2. поиск (проверка есть или нет)

 

См в №23

Циклический список

· односвязный (посл. эл-т ссылается на первый)

· двусвязный (посл. на первый, первый на посл.)

Операции аналогично лин. списку

Циклическая очередь

Циклический дек

Осн. назначение

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

См в №23

И лин. и цикл. структуры – частный случай нелинейных

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

Узлы – данные

Ребра – связи

Свойства:

· на каждый эл-т может указывать множество ссылок

· каждый эл-т может ссылаться на множество др.

эл-в

· каждая связь может иметь направление и вес

Неориентированный граф – граф у которого все ребра не имеют направления

Ориентированный граф – граф у которого все ребра имеют заданное направление

Смешанный граф – граф у которого нек. ребра ориентированы, а нек. нет.

Дерево – частный случай графа, это ориент. или неориент. граф, хар-ся 3 св-ми:

· не содержит цикл (сущ. только 1 способ добраться от 1 вершины к др.)

· выделена 1 вершина – корень, на него не ссылается ни одна вершина

· на каждую вершину дерева кроме корня имеется одна единственная ссылка

листья, поддерево!!!

Высота – число уровней вершин

Бинарное дерево

N-нарное дерево

? дерево любого вида м/б представлено эквивалентный бинарным деревом

Типовые операции:

· поиск узла в дереве

· удаление узда или поддерева

· добавление узла

· обход дерева в зад. направлении

Дост:

Хорошо подходит для работы с отсорт. данными

По совокуп. операций эта структура обеспечивает наилучшую проив-сть

Недост.: сложность реализации алгоритмов типовых оперций

Понятие алгоритм. Формальные признаки.

Способы задания алгоритма. Виды алгоритмов.

Теорема Дейкстра.

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

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

· Дискретность (возможность разбиения определяемого алгоритмом вычислительного процесса на конечное число отдельных действий/шагов)

· Понятность (все шаги закончены и понятны для исполнения)

· Детерминированность (алгоритм выдает один и тот же результат при одних и тех же действиях)

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

· Результативность (алгоритм завершает действие и выдает результат за конечное число действий)

Способы задания:

· Словесный

· Формулировочный (словесный + формулы/знаки)

· Графический (блок-схема)

· Язык операторных схем (с помощью операторов)

· Язык программирования

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

· Линейные

· Ветвления (IF)

· Циклические программы(For)

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