Informatika_1_1fedorova_1

1)Понятие информатики, информации, кодирования информации.

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

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

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

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

2)Понятие алгоритма, рекурсивные функции.

Алгоритм: определенная последовательность логических действий для решения поставленной задачи.

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

Рекурсивная функция: функция, которая вызывает саму себя. Пример: факториал. Частично рекурсивные функции: рекурсивные функции, определённые не для всех возможных аргументов.

Примитивно рекурсивные функции: рекурсивные функции, построенные без применения операторов минимизации.

Оператор минимизации: оператор построения по первому нулю (µ). Оператор минимизации по заданной функции n+1 аргумента строит функцию n аргументов. f::= µ[f1;(x)], где x – вспомогательный исчезающий аргумент.

Алгоритм, сопутствующий рекурсивной функции: Значение получаемой новой функции f для нулевого значения главного дополнительного аргумента (x) считать значением функции f1 (первое условие), а для каждого последующего значения главного дополнительного аргумента считать значением функции f2, вычисляемой при предыдущем значении главного аргумента и при значении вспомогательного, совпадающего с предыдущим значением определяемой ф-и f(2 условие).

3)Понятия алгоритма, системы текстовых замен.

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

СТЗ: система замен букв в слове или словосочетании На входе - слова, на выходе - слова.

Пара (V,W)єV* называется заменой над V, когда V→W

Конечное множество замен R будем называть системой текстовых замен (СТЗ) над V.

Замена s->t называется применением правила V->W, если имеются слова такие a,v,w,zєV*, что справедливо соотношение s=a◦v◦z t=a◦w◦z. Пусть s=БАНАН => a=БА, v=Н z=АН. Пусть w=РАБ заменяем v->w

Тогда будет t=БАРАБАН.

Слово S называется терминалом множества V, если не существует слова tєV*, такого, что справедливая замена s→t будет являеться результатом применения одного из правил из СТЗ R. Т.о. нельзя больше к слову s применить никакого правила.

Алгоритм Маркова: Алгоритм преобразования над строками путём замены символов, описанных в правиле алгоритма

4)Способы описания языков программирования: БНФ-нотации, синтаксические диаграммы.

Для описания языков программирования используется Бэкуса-Наурова форма (БНФ- нотация) и синтаксические диаграммы.

БНФ-нотация: мета-синтаксический язык, который широко используется для описания других формальных языков и в частности языков программирования. Не весь синтаксис можно описать. Существуют т.н. контекстно-зависимые условия, которые описываются доп.средствами с помощью специальных предикатов.

Пример: десятичное число без ведущих нулей

<десятичное число>::=0|[[{-} <p-цифра> {<цифра>}*] {.{<цифра>}*<p-цифра>}] где <p-цифра>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 , <цифра>::= 0 | <p-цифра>, <> -

вспомогательный символ , ::= - метасимвол "по определению есть", | - или {} - необязательно, но может быть

БНФ-нотация <e> ::= R наз РЕКУРСИВНОЙ, если <e> входит в R. РБНФ-нотации позволяют описывать формальные языки, содержащие вложенные структуры. Предикат: любое математическое высказывание, в котором есть, по меньшей мере, одна переменная.

Метасинтаксические языки и метасемантические описывают синтаксис и семантику.

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

грамматики автоматных языков.

В овальных или круговых рамках на синтаксических диаграммах указываются элементы языка, которые буквально так и воспроизводятся в исходном тексте программ. В прямоугольных рамках приведены элементы, требующие дальнейшего определения, возможно, с помощью других синтаксических диаграмм. Набор таких диаграмм служит формальным описанием синтаксиса языка программирования. Пример синтаксической диаграммы, построенной для оператора if языка C++:

5)Классификация языков программирования, элементы языка программирования С/C++: алфавит, слова, константы.

Машинный: язык кодов машины. Единственный язык, который знает и понимает процессор. Программа на машинном языке – последовательность команд машины, которые знает и понимает конкретный тип процессора.

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

Машинно-ориентированные: языки низкого уровня. Используют в своих конструкциях особенности архитектуры конкретного процессора и потому могут быть выполнены только на данном классе процессоров. Пример: Ассемблер. Машинно-независимые: не зависят от архитектуры процессора и программы на таких язках могут быть выполнены на любой вычислительной машине, но при условии, если в её програмн. обеспечение входит в спец.программа - транслятор, осуществляющая перевод программы с машин.-независимого на машинный. Пример:

C/C++ , Pascal.

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

Семантика – набор правил, на основе которых следует истолковывать эти конструкции.

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

Константа: объект, чьё значение в программе не изменяется.

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

К реализации типа данных относится способ представления в компьютере и способ представления операции через алгоритмы и процедуры. Спецификация и реализация типа не зависит от синтаксического представления. Атрибуты объектов представляются с помощью описания или определения типов. Значением может быть множество констант.

6) Переменные, область действия, время жизни, класс памяти

Переменные- область памяти использующие имя(идентификатор) [<класс памяти>][<const>]<тип><идентификатор>[<инициализация>] Описание переменных в C++ задаётся явным образом или по умолчанию.

Класс памяти(auto – ключевой, место в стеке, инициализация осуществляется при каждом обращении к ней, место освобождается в памяти при выходе из блока, в котором она описана, для локальных переменных этот класс по умолчанию, а к глобальным не применим!, extern – переменная будет определяться дальше по тексту проги или в другом файле, для создания переменных, доступных во всех модулях, в которых есть ее определение, static – постоянная, инициализируется 1 раз при первом ее определении, глобальные видны только в том блоке, в котором описаны, register – аналогично auto, если есть возможность, место для нее выделяется в регистрах процессора) определяет время жизни и область видимости. Если класс памяти не указан явным образом, то будет определен по умолчанию компьютером.

Время жизни может быть постоянным/временным.

Область видимости- место в программе, где обращение к переменной осуществляется по ее имени.

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

7)Операции C/C++, выражения, порядок вычисления выражений

Выражения- арифметические логические текстовые Составное выражение, простое выражение

1.обращение к ф-и, определение элементов массива, получение элементов структуры(. и ->)

2.!, битов отр(~), -, ++, --, преобразование типа, sizeof.

3.*, /, %

4.+, -

5.сдвиги <<, >>

6.<, > , <=, >=

7.==, !=

8.бит &

9.исключ или ^

10.бит или |

11.&&

12.||

13.усл опер (выражение?истина:ложь)

14. опер присваивания

8) Структура программы на С/С++, пример программы

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

зависит от исходных данных.

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

Каждая программа состоит из функций. Каждая функция идентифицируется 4-мя элементами:

1-тип возвращаемого значения

2-имя функции

3-список параметров

4-тело функции <тип значения><имя функции>(<список параметров>){<тело функции>}

9) Типы операторов в С/С++, оператор пустой, составной, оператор-выражение,

оператор возврата

<опертор>::=<пустой>|<опер-выражение>|<составной>|<возврата>|<условный>| |<цикл с параметром>|<безусловного перехода>|<переключатель>|<продолжения>| |<завершения> Каждый оператор заканчивается ;

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

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

Составной – произвольное количество любых операций, заключенных в {} Возврата return [<выражение>]; – заканчивает выполнение подпрограммы, в которой он содержится.

10) Оператор условной передачи управления в С/С++, примеры

Условный оператор if..else используется для разветвления процесса обработки данных на два направления

<условный>::=if(<выражение>) <оператор>; {else <оператор>;}

11) Оператор цикла с параметром в С/С++, его использование, примеры

операторы цикла бывают арифметические и итерационные. Количество повторений арифметического известно заранее, итерационного – нет. for(<инициализация>;<выражение>;<модификация>)

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

Модификация выполняется после каждого прохождения цикла, изменяет параметры

12) Оператор цикла с предусловием и постусловием в С/С++, особенности

использования

С предусловием while(b)s

Организует выполнение одного оператора(простого/составного) неизвестное заранее число раз.

Если рез-т выражения b окажется ложным изначально, то тело цикла не выполнится ни разу.

С постусловием do s while b;

Если рез-т выражения b окажется ложным изначально, тело цикла выполнится 1 раз, цикл завершится, и управление передается на оператор, следующий за условием b.