Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Нормальный алгоритм Маркова (НАМ) задаетсяконечной последовательностью подстановок { p1,p 2, … p n } .При этом:(1)если применимо несколько подстановок, применяетсяподстановка, которая встречается в описании алгоритмараньше других;(2)если подстановка применима к нескольким подсловамобрабатываемого слова, выбирается самое левое подслово;(3)после применения терминальной подстановки алгоритмзавершается;(4)если ни одна из подстановок неприменима, алгоритмзавершается.3Нормальные алгоритмы МарковаПример НАМ. Шифр Юлия ЦезаряV = {a, b, c, …, z}, V' = {*}.j-ая буква латинского алфавита шифруется j+h (mod 26)-ой буквойтого же алфавита.Например, для h = 3 подстановки имеют вид(маркер * помечает текущую шифруемую букву, цифра в скобках –номер правила подстановки):(1) *A → D*, (2) *B → E*, (3) *C → F*, …,(23) *W → Z*, (24) *X → A*, (25) *Y → B*,(26) *Z → C*, (27) * →.

, (28) → *Применим построенный НАМ к слову CAESAR:CAESAR (28)→ *CAESAR (3)→ F*AESAR (1)→ FD*ESAR (5)→FDH*SAR (13)→ FDHV*AR (1)→ FDHVD*R (12)→FDHVDU* (27)→ FDHVDU4Нормальные алгоритмы МарковаПроцедура интерпретации НАМ(1)Положить i = 0.(2)Положить j = 1.(3)Если правило pj применимо к σi , перейти к шагу (5).(4)(5)Положить j = j + 1. Если j ≤ n, то перейти к шагу (3).В противном случае – остановка.Применить pj к σi и найти σi+1. Положить i = i + 1.Если pj – нетерминальное правило, то перейти к 2.В противном случае – остановка.Говорят, что НАМ применим к слову σ0, если в результате произойдетостановка.Терминальное правило содержит метасимвол .

(точка).Иногда вместо →. используется метасимвол5Нормальные алгоритмы МарковаПример. Сложение чисел в единичной системе счисления:V = { +, | }, V' = { }.Правила подстановок: { | + → + |; + | → |; | →. | }Пример применения алгоритма:(1)«| | | | + | | + | | |» = «| | | | + | | + | | |» ⇒ «| | | + | | | + | | |»(1)(1)(1)(1)⇒ «| | + | | | | + | | |» ⇒ «| + | | | | | + | | |»(1)⇒ «+ | | | | | | + | | |» ⇒ «+ | | | | | + | | | |» ⇒ …(1)( 2)(2)⇒ «+ + | | | | | | | | |»⇒ «+ | | | | | | | | |» ⇒ «| | | | | | | | |» ⇒( 3)Первое правило «перегоняет» плюсы налево до упора, второе правилоих «стирает», третье правило «убеждается», что плюсов не осталось.6Нормальные алгоритмы МарковаЗаключительные замечанияТезис Маркова. Любой алгоритм в алфавите V может бытьпредставлен нормальным алгоритмом Маркованад алфавитом V.Примерно так же, как и для МТ, можно доказатьалгоритмическую неразрешимость проблемы останова исамоприменимости.Существуют различные НАМ решения одной и той же задачи.Проблема построения алгоритма, который может определитьэквивалентность любых двух НАМ, алгоритмическинеразрешима.Можно построить универсальный НАМ U, который мог быинтерпретировать любой нормальный алгоритм, включаясамого себя.7Заключительные замечанияМожно доказать эквивалентность двух формальных системТьюринга и Маркова конструктивным путем: построитьуниверсальную МТ, которая могла бы интерпретировать любойНАМ и, наоборот, построить универсальный НАМ, которыйинтерпретирует любую МТ.Существуют и другие формальные описания алгоритмов:машина Поста, λ-исчисление, рекурсивные функции и др.Для всех таких формальных систем доказана ихэквивалентность МТ.МТ невозможно реализовать на конечной машине: МТ с лентойконечных размеров не обеспечивает реализации всехалгоритмов.Тезис Тьюринга – Черча (основная гипотеза теорииалгоритмов).

Для любой интуитивно вычислимой функциисуществует вычисляющая её значения МТ.8Критика модели вычислений ТьюрингаМедленная (неускоряемая)частые копирования данных: у нормальных МТ каждоенеэлементарное действие выполняется над крайнимиправыми словами лентыотказ от нормальных вычислений приведет кпостоянному поиску данных и усложнит алгоритмчисло состояний МТ часто зависит от числа символовв алфавите МТ9Введение в язык программирования СиСхема простейшего компьютераПроцессорАЛУРегистрыШинаОсновнаяпамятьВнешниеустройства10Язык программирования СиСи разрабатывался как язык для реализации первойв мире универсальной операционной системы UNIX1973 – первая версия Си1978 – выход книги Б. Кернигана и Д.

Ритчи «Языкпрограммирования Си» (K&R C). Русский переводвышел в 1985 году.1989 – первый стандарт ANSI C (C89)1999 – стандарт C992011 – стандарт C11 (ранее назывался C1X)11Введение в язык программирования СиХарактеристики языка СиИмперативный языкУдобный синтаксисПозволяет естественно оперировать «машинными»понятиямиПереносимость на уровне исходного кодаКонфигурируемостьХорошие системные библиотекиХорошие оптимизирующие компиляторы12Первая программа на Си#include <stdio.h>int main (void){printf ("Hello, world\n");return 0;}Программа:объявления переменных или функцийопределения функций13Первая программа на Си#include <stdio.h>int main (void){printf ("Hello, world\n");return 0;}Директивы препроцессораСистемные библиотекиСтроковые константыУправляющие последовательности14Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекции 5-61Введение в язык программирования СиСхема простейшего компьютераПроцессорАЛУРегистрыШинаОсновнаяпамятьВнешниеустройства2Си-машинаПроцессорРегистрыАЛУОсновная памятьШинаПрограмма истатические данныеВнешниеустройстваКучаСтек3Си-машинаКлассы памятиРегистровые переменныеАвтоматические переменныеСтатические переменныеГлобальные переменныеПроцессорРегистрыАЛУШинаОсновная памятьПрограмма истатические данныеВнешниеустройстваКучаСтек4Типы данныхБазовые типы данных: char (символьный),int (целый), float (с плавающей точкой),double (двойной точности),_Complex (C99, комплексный)Тип void (без значения)Модификаторы базовых типов: signed, unsigned,long, short, long long (C99)к типу int применимы все модификаторык типу char – только signed и unsignedк типу double – только long (C99)5Типы данныхПредставление целых чисел: позиционнаядвоичная системаБайты в представлении числа идут подрядПорядок байт не гарантируется, то естьзависит от аппаратуры (big/little endian)Порядок бит в байте также не гарантируется(и его может быть невозможно узнать)Отрицательные числа часто представляютсяв дополнительном коде (n бит):- самый значащий бит (n-1) является знаковым- биты от 0 до n-2 – значения- положительные значения – как обычно- отрицательные значения: 2n - |x|6Типы данных≤ ≤ ≤ ≤sizeof – размер типа (любого объекта типа)int x -> sizeof(x) == sizeof(int)Файл limits.h задает минимальные имаксимальные значения целых типовsizeof(char) == 1sizeof(short)≥ 2sizeof(int) ≥ 2sizeof(long) ≥ 4sizeof(long long)≥ 8Файл inttypes.h задает знаковые ибеззнаковые целые типы фиксированныхразмеров (8, 16, 32, 64 бита)7Типы данныхТип _Bool (C99, значения 0/1, целый беззнаковый)Необходимо включить stdbool.h для объявленийbool, true, falseТип _Complex (C99, float/double/long double)Необходимо включить complex.h для объявленийcomplex, I и т.п.Тип _Imaginary (C99) является необязательным8ПеременныеПеременная = тип + имя + значениеКаждая переменная является объектом программыКлючевые слова (C89 – 32, C99 – C89 + 5) не могутбыть именами переменныхОбъявление переменной:тип список_переменныхМожно задать класс памяти и начальное значениепеременной9Область действия переменнойПеременная может быть объявлена:(1)(2)(3)внутри функции или блока (локальная);в объявлении функции (параметр функции);вне всех функций (глобальная).Область действия (видимости)локальной переменной – блок, в котором она объявлена(C99 – начиная со строки объявления)глобальной переменной – программный файл, начинаясо строки объявленияВ одной области действия нельзя объявлять болееодной переменной с одним и тем же именем10Область действия переменной и классы памяти#include <stdio.h>int count;/* глобальная переменная */void func (void){int count;/* автоматическая переменная */count = count - 2;}static int mult = 0;/* статическая переменная */int sum (int x, int y){count++;return (x + y) * (++mult);}int main (void){register int s = 0;/* регистровая переменная */count = 0;s += sum (5, 7);s += sum (9, 4);func ();printf ("Сумма равна %d, вызвали функцию %d раз\n", s, count);return 0;}11Инициализация переменнойПри объявлении переменной:int x = 42;автоматические переменные инициализируются каждыйраз при входе в соответствующий блок;если нет инициализации, значение соответствующейпеременной не определено!глобальные и статические инициализируются толькоодин раз в начале работы программы;если нет инициализации, они обнуляются компиляторомвнешние переменные инициализируются только в томфайле, в котором они определяютсяпри инициализации переменной типа с квалификаторомconst она является константой и не может изменятьсвое значение12ЛитералыЛитералы задают константу (фиксированное значение)символьные константы 'c', L'%', '\0x4f', '\040'тип символьной константы – int!целые константы 100, -34l, 1000U, 999lluконстанты с плавающей точкой 11.123F, 4.56e-4f,1.0, -11.123, 3.1415926l, -6.626068e−34Lтип вещественной константы без суффикса – double!шестнадцатеричные константы 0x80(128)восьмеричные константы 012(10)строковые константы "a", "Hello, World!",L"Unicode string"специальные символьные константы \n, \t, \b13Операции над целочисленными данными АрифметическиеОдноместные:изменение знака, или «одноместный минус» (–),одноместный плюс (+).Двухместные:сложение (+), вычитание (–), умножение (*),деление нацело (/), остаток от деления нацело (%).(a/b) * b + (a%b) == a Отношения (результат 0/1 типа int)больше (>), больше или равно (>=),меньше (<), меньше или равно (<=) Сравнения (результат 0/1 типа int)равно (==), не равно (!=) Логическиеотрицание (!), конъюнкция (&&), дизъюнкция (||)ложное значение – 0, истинное – любое ненулевое“ленивое” вычисление && и ||14Операции присваиванияПобочные эффекты: изменение объекта, вызов функцииlvalue = rvaluelvalue –выражение, указывающее на объектпамятиrvalue –выражениеПримерa = b = c = d = 0;Укороченное присваивание: lvalue op= rvalueгде op - двухместная операцияПример a += 15;Инкремент и декремент (++ и --)префиксные и постфиксныеПоследовательное вычисление: операция запятая (,)Пример a = (b = 5, b + 2);15Точки следованияПобочные эффекты: изменение объекта, вызовфункцииТочка следования (sequence point): момент во времявыполнения программы, в котором все побочныеэффекты предыдущих вычислений закончены,а новых – не начатыпервый операнд &&, ||, ,окончание полного выражениямежду двумя точками следованияизменение значения переменной возможноне более одного раза(a=2) + (a=3)i++ + ++iстарое значение переменной читается толькодля определения новогоa = b++ + b16Форматный ввод-вывод#include <stdio.h>int main (void){int s = 0;int a, b;scanf ("%d%d", &a, &b);s += a + b;printf ("Сумма равна %d\n", s);return 0;}17Форматный ввод-выводСпецификаторы ввода-вывода%d, %ld, %lld – напечатать/считать число типа int, long,long long%u, %lu, %llu – напечатать/считать число типа unsigned,unsigned long, unsigned long long%f, %Lf – напечатать число типа double, long double%f, %lf , %Lf – считать число типа float , double, long double%c – напечатать/считать символ%4d – вывести число типа int минимум в четыре символа%.5f – вывести число типа double c пятью знаками%% – напечатать знак процентаФункция scanf возвращает количество удачно считанных элементов18Пример Си-программы/* Решение квадратного уравнения */#include <stdio.h>#include <math.h>int main (void) {int a, b, c, d;/* Введем коэффициенты */if (scanf ("%d%d%d", &a, &b, &c) != 3) {printf ("Нужно ввести три коэффициента!\n");return 1;}if (!a) {printf ("Уравнение не квадратное!\n");return 1;}d = b*b – 4*a*c;if (d < 0)printf ("Решений нет\n");else if (d == 0) {double db = -b;printf ("Решение: %.4f\n", db/(2*a));} else {double db = -b;double dd = sqrt (d);printf ("Решение 1: %.4f, решение 2: %.4f\n", (db+dd)/(2*a), (db-dd)/(2*a));}19return 0;}Пример Си-программы/* Решение квадратного уравнения */#include <stdio.h>#include <math.h>int main (void) {int a, b, c, d;/* Введем коэффициенты */if (scanf ("%d%d%d", &a, &b, &c) != 3) {printf ("Нужно ввести три коэффициента!\n");return 1;}if (!a) {printf ("Уравнение не квадратное!\n");return 1;20}Пример Си-программыd = b*b – 4*a*c;if (d < 0)printf ("Решений нет\n");else if (d == 0) {double db = -b;printf ("Решение: %.4f\n", db/(2*a));} else {double db = -b;double dd = sqrt (d);printf ("Решение 1: %.4f, решение 2: %.4f\n",(db+dd)/(2*a), (db-dd)/(2*a));}return 0;}21Преобразование типовПри присваивании: a = b“Широкий” целочисленный тип в “узкий”: отсекаютсястаршие битыЗнаковый тип в беззнаковый: знаковый бит“становится” значащимsigned char c = -1; /* sizeof(c) == 1 */((unsigned char) c) -> 255Плавающий тип в целочисленный: отбрасываетсядробная часть“Широкий” плавающий тип в “узкий”: округление илиусечение числаЯвное приведение типов: (type) expressionПримерd = ((double) a+b)/2;22Приведение типовНеявное приведение типов: происходит, когда операндыдвухместной операции имеют разные типы (6.3.1.8)Если один из операндов – long double, то и второйпреобразуется к long double (так же для double и float)long double + double -> long double + long doubleint + double -> double + doublefloat + short -> float + int -> float + floatЕсли все значения операнда могут быть представлены в int,то операнд преобразуется к int,так же и для unsigned int(англоязычный термин – integer promotion)unsigned short(2) + char(1) -> int(4) + int(4)unsigned short(4) + char(1) -> unsigned int(4)+ int(4)Если оба операнда – соответственно знаковых илибеззнаковых целых типов, то операнд более “узкого”типа преобразуется к операнду более “широкого” типаint + long -> long + longunsigned long long + unsigned ->unsigned long long + unsigned long long23Приведение типовНеявное приведение типов: происходит, когда операндыдвухместной операции имеют разные типыЕсли операнд беззнакового типа более “широк”,чем операнд знакового “узкого” типа, то операнд“узкого” типа преобразуется к операнду “широкого” типаint + unsigned long -> unsigned long +unsigned longint(4) / unsigned int(4) -> unsigned int(4) /unsigned int(4)/* Неверные значения */Если тип операнда знакового типа может представитьвсе значения типа операнда беззнакового типа, тооперанд беззнакового типа преобразуется к операндузнакового типаunsigned int(4) + long(8) -> long(8) + long(8)unsigned short + long long -> long long + long longОба операнда преобразуются к беззнаковому типу,соответствующему типу операнда знакового типаunsigned int(4)+ long(4) -> unsigned long(4) +unsigned long(4)Числа типа float не преобразуются автоматически к double24Старшинство операцийОперацииАссоциативность( ) [ ] -> .Слева направо! ~ ++ -- + - sizeof (type) * &Справа налево* / %Слева направо+ -Слева направо<< >>< <= > >=== !=&^|Слева направоСлева направоСлева направоСлева направоСлева направоСлева направо&&Слева направо||Слева направо?:Справа налево= += -= *= /= %= &= ^= |= <<= >>=Справа налево,Слева направо25ОператорыВыражение-оператор: expression;Составной оператор: {}Условный оператор: if (expr) stmt; else stmt;else всегда относится к ближайшему if:if (x >if (yy =elsez =2)> z)z;if (x > 2) {if (y > z)y = z;}y;elsez = y;Оператор выбора:switch (expr) {case const-expr: stmt;case const-expr: stmt;default: stmt;}Оператор break – немедленный выход из switch.26ОператорыЦикл while: while (expression) stmt;Цикл for:for (decl1; expr2; expr3)decl1;stmt;while (expr2) {decl1 - возможноstmt;определение переменнойexpr3;с инициализатором}for ( ; ; ) stmt; – бесконечный цикл.Цикл do-while: do { stmt; } while (expression);Проверка условия выхода из цикла после выполнения тела.Операторы break и continue: выход из внутреннего цикла и переходна следующую итерациюОператор goto: переход по меткеgoto label…label:Областью видимости метки является вся функция27Пример программы.

Характеристики

Список файлов лекций