Университет Натальи Нестеровой.

Кафедра информатики.

Основы информационных технологий

Тезисы лекций Преподаватель: доц. Носков Ю.М.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

 

1.      Понятие информатики.

2.      История развития информатики. Место информатики в ряду других фундаментальных наук.

3.      Мировоззренческие, экономические и правовые аспекты информационных технологий.

4.      Понятие информации и ее измерение.

5.      Количество и качество информации. Единицы измерения информации.

6.      Информация и энтропия.

Информатика – наука об информационных процессах.

Информационный процесс: процесс, связанный с хранением, обработкой, или передачей информации.

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

Свойства информации: Объективность и субъективность, полнота, достоверность, адекватность, доступность, актуальность.

Данные представляют собой зарегистрированные сигналы. Метод регистрации сигналов может быть любым.

Операции с данными:

Сбор данных: накопление информации с целью обеспечения достаточной полноты для принятия решений.

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

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

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

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

Защита: комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных.

Преобразование данных: перевод данных из одной формы в другую или из одной структуры в другую.

Кодирование данных двоичным кодом

Система двоичного кодирования.  Бит: от английского binary digit – двоичная цифра. Одним битом выражаются два понятия: 0 (ложь) и 1 (истина). Если увеличить количество бит до двух, то можно выразить уже четыре понятия: 00, 01, 10, 11.

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

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

Кодирование текстовых данных выполняется следующим образом. Для каждого символа отводится код фиксированной длины. Это может быть 8, или 16 бит: один или два байта соответственно. В первом случае мы имеем код ASCII, во втором – так называемый Unicode.

 

 Контрольные вопросы

1.      Перечислить типы информационных процессов.

7.      Привести примеры операций с данными: сбора, формализации, фильтрации, сортировки, архивации, защиты, преобразования.

8.      Что такое прямой, обратный и дополнительный коды. Привести примеры.

 

Домашнее задание

2.      Перевести число, полученное путем сложения Вашего года рождения и даты рождения из десятичной формы в двоичную.

3.      Представить число 12, 35 в форме с плавающей запятой.

4.      Записать Вашу фамилию и имя в коде ASCII.

 

Тезисы лекции №  2.

 

Начала теории множеств

Будем полагать, что существуют объекты, называемые атомами. Атом является  понятием, то есть, не определяется.

Принадлежность - также абстрактное понятие. Если b принадлежит B, то пишут b Î B.

Отрицание этого утверждения будем обозначать b Ï B.

Если а - атом, то ему ничего не принадлежит.

Множества - объекты, не являющиеся атомами. Если А - множество, то его элементы - это те объекты а, для которых а Î А.

Каждый элемент множества - атом или другое множество.

Каждый элемент множества появляется в нем один раз. Если А содержит конечное число элементов. то оно называется конечным множеством, и его можно записать, перечислив все элементы: {а1,...,аN}, если а1...аN - все элементы А и ai ¹  aj для i ¹ j.

Существует пустое множество (не содержит элементов). Обозначим его O.

Запись: #А = 3 означает, что множество А содержит 3 элемента.

Примеры множеств: {1,2,5}; {Белый, Черный};{0,1}. Последнее из приведенных множеств называется бинарным алфавитом.

Определение множеств с помощью предиката. Предикат – утверждение, которое может быть либо истинным, либо ложным. Множество содержит те элементы, для которых предикат является истинным.

Пример:

Т = {"n|(n – целое)Ù(n / 2 – целое}

Этот предикат определяет множество всех четных чисел.

Теоретико-множественные операции

Пусть А,  В и С – множества, например

Операция

Предикат, определяющий операцию

Результат, если А={1,2,3}; B={2,4,1}

Объединение C=AÈB

С = {c|(cÎA) Ù (cÎB}

С = {1,2,3,4}

Пересечение C=AÇB

С = {c|(cÎA) Ú (cÎB}

С = {2}

Разность C=A-B

С = {c|(cÎA) Ù (cÏB}

С = {3}

Множество А есть подмножество  множества В ( A Í B ), если каждый элемент из А является элементом В. Также говорят, что В содержит (или включает) А. А - подмножество В, В- надмножество А.

Если В содержит хотя бы один элемент, не принадлежащий А, и А содержится в В, то говорят, что А собственное подмножество В (или что В собственно включает А).

Тогда А - собственное подмножество В, а В - собственное надмножество В.

 A Ì B

 

Два множества А и В называются равными, если А содержится в В и В содержится в А. Разность равных множеств – пустое множество.

 

Контрольные вопросы

1.      Дать определения понятий, приводимых в лекции.

9.      Привести примеры.

10.  Будет ли пустым множество {a,b,c}-{b,a,c}?

11.  Является ли множество {0,1} (собственным) подмножеством {0,1,2}?

Домашнее задание

Пусть A = {a,b,c,d,e}; B = {d,b,s,a}. Найти:

 

1.      Объединение, пересечение и разность этих множеств.

2.      Множество всех подмножеств А.

3.      Множество всех подмножеств для множества C=AÇB.

 

Тезисы лекции №  3.

 

1.      Формальные системы, определение, частные случаи формальных систем.

12.  Понятие об отношении на множестве.

13.  Бинарные и n-арные отношения.

14.  Терминология теории отношений.

15.  Свойства отношений.

16.  Степень отношения. Транзитивное замыкание отношения R.

17.  Отношение порядка. Частичный порядок. Рефлексивный частичный  порядок.

Формальные системы

Формальная система состоит из следующих элементов: множество символов; множество правил образования; аксиомы; правила вывода

Отношения

Декартово произведение множества А на множество В есть множество всех пар вида (аi,bj), где аi - элемент множества А, bj - элемент множества В.

Отношение R из множества А на множество В есть любое подмножество декартова произведения этих множеств. Иначе говоря, отношение - это произвольное множество пар элементов этих множеств.

n-арное отношение. Для его определения обобщается понятие декартова произведения на случай n множеств. Каждый элемент такого произведения называется кортеж. n-арное отношение - это множество кортежей.

Свойства отношений.

Отношение R может обладать, или не обладать рядом свойств. Важнейшие из них: рефлексивность, транзитивность и симметричность.

Отношение R рефлексивно если (a r a), то есть, если все пары вида (а,а) принадлежат R.

Отношение R транзитивно, если для любых (a,b) (b,c) из R найдется пара (a,c).

Отношение R симметрично, если для любой (a,b) из R найдется обратная ей пара (b,a).

Рефлексивное, транзитивное и симметричное отношение называется отношением эквивалентности.

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

1.       Каждый элемент множества А принадлежит одному и только одному классу.

2.      Объединение всех классов эквивалентности равно множеству А.

Контрольные вопросы

3.      Дать определение формальной системы. Привести пример.

4.      Дать определение отношения. Привести примеры из математики, программирования и из обыденной жизни.

5.      Относится ли отношение «Быть братом»  к классу рефлексивных? Обосновать ответ.

6.      Относится ли отношение «Больше» к классу транзитивных? Обосновать ответ.

7.      Относится ли отношение «Иметь одинаковый цвет» к классу симметричных? Обосновать ответ.

8.      Является ли отношение «Иметь одинаковый рост» к классу отношений эквивалентности? Обосновать ответ.

 

Домашнее задание

1.      Пусть даны множества: А = {4,3,2}, В = {d,e}

1.1. Построить декартово произведение А х В.

1.2. Построить произвольное отношение из множества А на множество В.

1.3. Можно ли построить симметричное отношение из множества А на множество В?

2.      Пусть дано множество А={x, y, z, p}. Заполнить следующую таблицу.

Отношение

Рефлексивно

Транзитивно

Симметрично

{(x,x),(x,y),(x,z),(y,x)}

 

 

 

{(x,x),(y,y),(z,z),(p,p)}

 

 

 

{(x,y),(y,x),(x,z,),(z,p),(x,p}

 

 

 

{(x,p),(p,x),(x,x),(p,p)}

 

 

 

{(x,y),(y,z),(z,p),(p,z),(x,z)}

 

 

 

При заполнении таблицы проставить знак +, если отношение обладает соответствующим свойством.

Литература

  1. А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.
  2. Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  4.

 

1.      Отображения  (функции). 

2.      Инъективное и биективное отображения.

3.      Равномощные    множества.    Понятие    бесконечного множества. Счетное и несчетное бесконечные множества.

4.      Элементы теории графов. Определения

 

Отображения  (функции)

Отображение - отношение, обладающее свойством однозначности. Для каждой пары (a,b), одному а может соответствовать только одно b.

Инъективное и биективное отображения

Отображение инъективно, если для каждой пары (a,b) одному b может соответствовать только одно a.

Инъективное отображение биективно, если каждый элемент множества А является первым элементом какой-нибудь пары этого отображения и каждый элемент множества B является вторым элементом какой-нибудь пары этого отображения.

Равномощные множества. Понятие бесконечного множества

Множества А и В равномощны, если можно построить биективное отображение из А в В. Для конечных множеств это означает, что количество элементов в каждом из них одинаково.

Множество бесконечно, если оно равномощно какому-либо своему собственному подмножеству.

Бесконечное множество счетно, если оно равномощно множеству целых положительных чисел. В противном случае оно несчетно (континуум).

Элементы теории графов. Определения

Граф - это пара (A, R), где A - множество, R - отношение на этом множестве. Часто граф изображают в виде чертежа, состоящего из n точек, называемых  вершинами и m векторов, называемых ребрами графа. Здесь n - число элементов множества A, m - число пар отношения R. Чертеж строится по следующим правилам: если пара (a,b) принадлежит R, то проводится линия, направленная от точки a в точку b. Например, если A = {a,b,c,d,e}, R = {(a,e), (a,c), (b,a), (b,e), (c,b)}, то чертеж может получиться таким:

Граф G=(A,R)
 
 

 

 

 

 

 

 


Вершина называется изолированной, если она не принадлежит ни одной паре отношения. В графе G вершина d - изолированная.

Путь - из a1 в aN -  это последовательность пар (a1,a2), (a2,a3), … , (aN-1,aN), каждая из которых принадлежит отношению R. Если существует путь из a1 в aN то вершина AN достижима из A1

Цикл - замкнутый путь, то есть такой, в котором A1 = AN . В графе G последовательность (a, e, b, a) - цикл. Граф, содержащий цикл, называется циклическим. Граф, в котором нет циклов - ациклический.

Контрольные вопросы

1.      Дать определения: отображения, инъективного и биективного отображений. Привести примеры:

Отношения, не являющегося отображением.

Отображения, не обладающего свойством инъективности.

Инъективного, но не биективного отображения.

Биективного отображения.

2.      Привести пример бесконечного множества и найти его собственное подмножество, равномощное ему.

3.      Привести примеры счетного и несчетного бесконечных множеств.

4.      Дать определения и привести примеры циклического и ациклического графов.

 

 

Домашнее задание

1.      Построить произвольный граф G1 6 вершин и 8 ребер.

2.      В графе G1  найти все пути между вершинами.

3.      В графе G1  найти все циклы.

4.      Найти все вершины, достижимые из вершины A1 в графе G1.

Литература

18.  А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

19.  Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  5.

 

1.      Конечные автоматы.

20.  Представление автомата в виде графа.

21.  Детерминированные и недетерминированные автоматы.

22.  Элементы теории неориентированных графов. Основные понятия.

23.  Матричное представление неориентированного графа.

Конечные автоматы

Конечный автомат (КА) - четверка (А,S,g,a0,at), где А - множество состояний; S - множество символов (алфавит) g - функция переходов; a0 - начальное состояние, at - конечное состояние.

Такт автомата - переход из состояния ai в состояние aj  в соответствии с функцией переходов.

Представление автомата в виде графа

КА отображается с помощью графа так: множество состояний соответствует множеству узлов, а функция переходов - множеству дуг графа. Символы, соответствующие переходам, используются в качестве пометок около дуг. Ниже представлен КА ({a0,1,a2,a3},{0,1},g,a0и соответствующий ему помеченный граф.

Детерминированные и недетерминированные автоматы

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

Элементы теории неориентированных графов. Основные понятия

Неориентированный граф - тройка вида (V,E,I), где V -множество вершин, E - множество ребер, I - отношение инцидентности: I является подмножеством декартова произведения VxE. Вершина может быть инцидентна произвольному числу ребер, ребро - не более чем двум вершинам.

Путь в графе между вершинами V1 и V2 - непрерывная последовательность ребер, проходящих через произвольные вершины, если она начинается в V1 и заканчивается в V2.

Цикл - путь, в котором V1 = V2 .

Дерево - граф без циклов.

Граф плоский, если его ребра пересекаются только в вершинах.

Два графа G1 = (V1,E1,I) 1 G2 = (V2,E2,I2)  изоморфны друг другу, если можно построить биективные отображение (V1 ->V2, E1 -> E2  так, что будет сохранятся отношение инцидентности.

Граф планарен, если он изоморфен плоскому графу.

 

 

Матричное представление неориентированного графа

 

Контрольные вопросы

1.      Дать определение конечного автомата: детерминированного и недетерминированного. Привести пример автомата с 5 вершинами и 10 ребрами.

2.      Сколько ребер имеет неориентированные полный граф с N вершинами?

3.      Дать определения: графа. Привести примеры:

 

Домашнее задание

1.      Построить произвольный граф G1 6 вершин и 8 ребер.

2.      Найти в графе G1 все циклы.

3.      Построить матрицы смежности и инцидентности для графа G1.

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

Литература

1.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

2.  Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  6.

 

  1. Алфавит, цепочка и язык

  2. Операции над языками.

  3. Проблемы.

  4. Алгоритмы: частичные и всюду определенные. Примеры алгоритмов.

  5. Алгоритмически неразрешимые проблемы.

 

Алфавит – множество символов.

Цепочка определяется рекурсивно: Пусть дан алфавит

  1. Пустая цепочка есть цепочка в алфавите.

  2. Если х – цепочка в алфавите, а – символ алфавита, то ха – цепочка в алфавите. Здесь ха – конкатенация, или сцепление цепочек.

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

Проблема: вопрос, на который можно дать ответ: «Да», или «Нет». Такой ответ называется решением проблемы.

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

 

Контрольные вопросы

1.      Привести пример языка в алфавите {0,1}; в алфавите {a,b,c,d}.

2.      Дать определения проблемы. Привести примеры.

3.      Какие проблемы называются алгоритмически неразрешимыми?

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

Домашнее задание

1.      Описать первый и второй алгоритмы Евклида.

2.      Описать алгоритм поиска наименьшего общего кратного двух чисел

Литература

1.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

2.  Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  7

 

  1. Алгоритмическая неразрешимость проблемы: «Является ли частичный  алгоритм всюду определенным?».

  2. Проблема соответствий Поста. Частный случай проблемы. Алгоритмическая неразрешимость проблемы.

  3. Машина Тьюринга как метод  описания алгоритмов. Тезис Тьюринга-Черча.

  4. Постановка задачи компиляции. Проблемы  компиляции. Синтаксис и семантика программы

 

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

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

Пример неразрешимой проблемы: Дан произвольный частичный алгоритм. Является ли он всюду определенным?

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

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

Контрольные вопросы

1.      Дать определение проблемы. Привести примеры.

2.      Какие проблемы называются алгоритмически неразрешимыми?

3.      Доказать, что множество всех алгоритмов счетно.

36.  Доказать, что проблема «Является ли частичный  алгоритм всюду определенным?» является алгоритмически неразрешимой

 

Домашнее задание

1.      Описать частичный алгоритм решения проблемы соответствий Поста.

2.      Найти решение проблемы соответствий Поста для частного случая:

3.      {(ab,ba),(a,a),(abc,cab)}. Является ли это решение единственным?

4.      Привести пример частного случая проблемы соответствий Поста, для которого не существует решения.

 

Литература

1.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

37.  Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  8

 

1.      Состав компилятора. Задачи лексического анализа; работы с таблицами; синтаксического анализа; генерации кода; оптимизации  кода.

2.      Лексический анализатор (сканер). Понятие о лексеме. Прямой  и непрямой лексические анализаторы.

3.      Задачи, возникающие при работе  с таблицами и подход к их решению.

4.      Синтаксический анализ. Получение дерева разбора.

5.      Методика решения задач генерации и оптимизации кода.

 

Компилятор состоит из следующих компонентов:

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

Cost := Price * 1.1 + H;

Лексемы

Cost

:=

Price

*

1.1

+

H

;

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

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

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

Задача Оптимизации кода решается с целью улучшения емкостных и/или временных характеристик. Различают машинно-независимую и машинно-зависимую оптимизацию.

Контрольные вопросы

1.      Перечислить фазы компилятора и описать задачи, решаемые на каждой фазе.

2.      Привести примеры операторов на языке Паскаль и выполнить для них лексический анализ.

3.      Сколько в среднем операций сравнения потребуется выполнить для таблицы, содержащей 1024*1024 строки при использовании:

а) линейного поиска?

б) логарифмического поиска?

4.      Почему при генерации кода используются тройки? Привести пример тройки для генерации кода арифметического оператора.

5.      Почему при изменении позиции некоторых предложений в тексте программы улучшаются временные характеристики программы?

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

 

Домашнее задание

1.      Найти все лексемы в следующем предложении на языке Паскаль:

X2 := Alpha – (Beta + Delta3)/(Beta - Delta3) + 3.14;

2.      Построить дерево разбора для выражения:

a + b * c

3.      Построить график зависимости времени логарифмического поиска от объема таблицы.

Литература

1.      Д. Кнут. Искусство программирования  Том 2: Сортировка и поиск. М.: 2000

2.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  9

 

1.      Нормальная форма Бэкуса-Наура.

2.      Грамматика как формальная математическая система для  задания языка.

3.      Вывод в грамматике.

4.      Выводимые цепочки.

5.      Язык,  определяемый грамматикой.

6.      Классификация грамматик в зависимости от вида правил.

 

Нормальная форма Бэкуса-Наура (БНФ)– это формальная система для определения одних понятий на основе  других. Пример:

<Цифра>::=1|2|3|4|5|6|7|8|9|0

Для более сложных понятий используется рекурсия, например:

<Число без знака>::=<Цифра>

<Число без знака>::=<Цифра><Число без знака>

Развитием идеи БНФ является грамматика.

Грамматика – это четверка вида: G = (N,S,P,S), где:

N – множество нетерминальных символов (нетерминальный алфавит);

S - множество терминальных символов (терминальный алфавит);

P – множество правил;

S – начальный символ. SÎN

Правило – это отношение из множества N*ÈS*ÈN на множество N*ÈS*. Каждая пара отношения записывается в виде a®b, где a и b - цепочки в соответствующих алфавитах.

Цепочка a выводима в грамматике G, если выполняется следующее условие:

  1. S – выводимая цепочка;

  2. Если:

abc- выводимая цепочка

b®d - правило данной грамматики

то adc - выводимая цепочка.

Язык, определяемый грамматикой - это множество всех цепочек терминальных символов, выводимых в грамматике.

Классификация грамматик

Грамматика G = (N,S,P,S) называется:

Праволинейной, если любое правило имеет вид: A®xB, или A®x, где A,BÎN, xÎS*.

Контекстно-свободной, если любое правило имеет вид: A®a, где AÎN, aÎ(NÈS)*.

Контекстно-зависимой, если в ней имеется  правило вида: a®b, где |a|£|b|.

Общего вида, если в ней имеется хотя бы одно правило, не удовлетворяющее перечисленным выше ограничениям.

 

Контрольные вопросы

 

1.      Дать определение нормальной формы Бэкуса-Наура. Привести пример.

2.      Дать определение грамматики.

3.      Привести примеры грамматик каждого из типов.

4.      Дать определение цепочки, выводимой в грамматике.

5.      Что такое Язык, определяемый грамматикой? Как определяется тип языка в зависимости от типа грамматики?

6.      Привести пример вывода в грамматике.

7.      Привести примеры грамматик, определяющих:

·              Пустой язык;

·              Конечный язык

·              Бесконечный язык.

 

Домашнее задание

1.      Определить тип грамматики:

G0 = ({E,T,F},{a,+,*,(,)},P,E),

Если Р = { E®E+T|T,

                  T®T*F|F

                  F®(E)|a }

2.      Показать, что цепочка (a+a)*a выводима в грамматике G0

3.      Показать, что цепочка  (a++a) не выводима в грамматике G0

Литература

1.      Д. Кнут. Искусство программирования. М.: 2000

2.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  10

 

1.      Распознаватели как средство задания языка.

2.      Определение распознавателя. Начальная конфигурация. Такт работы  распознавателя.

3.      Цепочка, допускаемая распознавателем.

4.      Язык, определяемый распознавателем.

 

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

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

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

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

Поведение памяти для заданного класса распознавателей характеризуется с помощью двух функций: доступа к памяти и преобразования памяти. Тип распознавателя определяется типом его памяти. Например, если память – магазинная, то распознаватель - автомат с магазинной памятью.

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

1.      Входная головка сдвигается на одну ячейку влево, вправо, или сохраняет прежнее положение.

2.      В память помещается некоторая информация.

3.      Изменяется состояние управляющего устройства.

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

Распознаватель допускает входную цепочку w, если, начиная с начальной конфигурации, в которой цепочка w записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией.

Язык, определяемый распознавателем, - это множество входных цепочек, которые он допускает.

Классификация языков

Язык L праволинейный, Û он определяется односторонним детерминированным конечным автоматом.

Контекстно-свободный Û он определяется односторонним недетерминированным автоматом с магазинной памятью.

Контекстно-зависимый Û он определяется двусторонним недетерминированным линейно ограниченным автоматом.

Рекурсивно перечислимый Û когда он определяется машиной Тьюринга.

 

 

Контрольные вопросы

 

1.      Дать определение распознавателя. Привести пример.

2.      Привести пример конечного автомата. Привести пример цепочки, допускаемой этим автоматом.

3.       Дать определение цепочки, выводимой в грамматике.

4.      Что такое Язык, определяемый распознавателем? Как определяется тип языка в зависимости от типа распознавателя?

5.      Привести пример цепочки, выводимой детерминированным конечным автоматом.

6.      Привести примеры распознавателей, определяющих:

·        Пустой язык;

·        Конечный язык

·        Бесконечный язык.

 

Домашнее задание

1.      Является ли детерминированным конечный автомат A, если его функция переходов описывается таблицей:

 

0

1

2

A

b, c

a, c

 

B

a

b

d

c

b, a, c

b

 

d

c,a

 

a, b, c, d

Начальное состояние – a, а множество заключительных состояний – {c,d}?

2.      Нарисовать граф переходов автомата А.

3.      Является ли язык, определяемый автоматом А: пустым, непустым, но конечным, или бесконечным?

Литература

1.      Д. Кнут. Искусство программирования. М.: 2000

2.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  11

 

1.      Трансляция арифметических выражений. Стековый метод. 

2.      Понятие о польской записи арифметического выражения (АВ).

3.      Алгоритм получения польской записи произвольного АВ.

4.      Использование польской записи для подсчета значения АВ.

Задача трансляции АВ состоит в получении троек вида: X = AÅB, где Å - знак арифметической операции. Для решения задачи применяется стековый метод, в результате чего получается бесскобочная (польская) запись АВ.

Польская запись АВ бывает двух видов: прямая и обратная. Ниже рассматривается обратная польская запись. Определение представим в виде таблицы:

 

АВ=a

Польская запись

Пример

aÅb

abÅ

X*Y

XY*

(aÅb)

abÅ

(X*Y)

XY*

aÅa

aaÅ

(X+Y)*Z

XY+Z*

 

 

X+Y*Z

XYZ*+

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

Использование польской записи для подсчета значения АВ. Символы читаются из стека и, в зависимости от типа символа, выполняется соответствующая операция, либо прочитанный операнд записывается в стек Е.

 

 

Контрольные вопросы

 

1.      Дать определение стека.

2.      Дать определение польской записи АВ. Привести пример

3.      Описать алгоритм получения польской записи АВ.

4.      В каком случае алгоритм получения польской записи дает ошибку?

5.      Как используется польская запись для вычисления значения АВ?

 

Домашнее задание

1.Следующие АВ написать в бесскобочной форме (обратная польская запись)

А) (x-y)*((x+y)/z

Б) (x*y-z)*((x/z+y/z)/*t

В) (x-(y-z)/t)/(t-x*y)

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

 

Литература

1.      Д. Кнут. Искусство программирования. М.: 2000

2.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  12

1.      Регулярные множества и регулярные выражения (РВ).

2.      Свойства  регулярных выражений.

3.      Уравнения и системы уравнений с регулярными  коэффициентами.

Регулярные множества и регулярные выражения

Пусть S - алфавит.

Регулярное множество в S определяется так:

Регулярное выражение

4.      Æ - регулярное множество в S;

Æ

5.      {e} – регулярное множество в S;

e

6.      {a} - регулярное множество в S, если a Î S;

a

7.      Если P и Q – регулярные множества в S, то таковы же и множества: RÈQ, RQ, P*.

RÈQ p+q

RQ pq

P* p*

 

8.      Ничто другое не является регулярным множеством в S.

 

РВ – это компактный способ обозначения регулярных множеств. В левом столбце таблицы приведено определение РВ. Используется также обозначение p+ для сокращенной записи выражения PP*.

Два РВ эквивалентны, если они обозначают одинаковые регулярные множества: p=q, если P=Q.

Свойства  регулярных выражений

9.      a+b=b+a

10.  Æ*=e

11.  a(bc)=(ab)c

12.  a+(b+c)=(a+b)+c

13.  a(b+c)=ab+ac

14.  (a+b)c=ac+bc

15.  ae=ea=a

16.  Æa=aÆ=Æ

17.  a*=a+a*

18.  (a*)*=a*

19.  a+a=a

20.  a+Æ=a

Уравнения и системы уравнений с регулярными  коэффициентами

Уравнения, в которых РВ используются в качестве коэффициентов и в качестве неизвестных. Решение уравнения – значения неизвестных, которые после подстановки обращают уравнение в тождество. Пример:

Решением уравнения: X = aX + b   (1)

является X = a*b  (2)

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

Контрольные вопросы

 

1.      Дать определения регулярного множества и регулярного выражения. Привести примеры.

2.      Перечислить свойства регулярных выражений. Привести обоснования свойств.

3.      Доказать, что решением уравнения (1) является выражение (2).

 

Домашнее задание

Решить систему уравнений с регулярными коэффициентами:

X=a1X+a2Y+a3

Y=b1X+b2Y+b3

Литература

 

1.      Д. Кнут. Искусство программирования. М.: 2000

2.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство “Питер”, 1999,- 640 с.

 

Тезисы лекции №  13

 

1.      Уравнения и системы уравнений с регулярными  коэффициентами (продолжение).

2.      Алгоритм решения стандартной системы.

3.      Использование систем уравнений с регулярными коэффициентами для описания регулярных языков.

Стандартная система уравнений с множеством неизвестных D={X1,X2,…,Xn}:

X1=a10+a11X1+a12X2+…+a1nXn

(1)
 
X2=a20+a21X1+a22X2+…+a2nXn

…       

Xn=an0+an1X1+an2X2+…+annXn

Алгоритм решения стандартной системы

Вход: Стандартная система Q уравнений в виде (1).

Выход: Решение системы Q в виде X1=a1, X2=a2,…, Xn=an

Метод: (Подобен алгоритму Гауссова исключения)

1.      i=1

2.      Если i=n, перейти к (4). Иначе с помощью тождеств, описанных на предыдущей лекции, записать уравнения для Xi в виде Xi=aXi+b, где a - регулярное выражение в S, а b - регулярное выражение вида b0+b1xi+1+…+bnxn     причем все bi  - регулярные выражения в алфавите S. Затем в правой части уравнений для xi+1,…,xn заменить xi регулярным выражением a*b.

3.      Присвоить i значение i+1 и перейти к шагу 2.

4.      Записать уравнение для xn в виде xn=axn+b, где a и b - регулярные выражения в алфавите S. (при этом i = n).

5.      Уравнение для xi имеет вид: xi=axi+b, где a и b - регулярные выражения в алфавите S. Записать значение результата: xi = a*b и в уравнения для xi+1 … x1 подставить эту величину вместо xi.

6.      Если i = 1 остановиться. В противном случае присвоить i значение i-1 и перейти к шагу 5.

Пример Пусть множество неизвестных D = {X1,X2,X3 }. Решим систему уравнений:

X1=1X1+0X2+e

X2=0X3+1X2

X3=0X1+1X2

 

В уравнении для x1 получаем: X1=1*(0X2+e). Подстановка в уравнение для X3 дает: X3= 01*(0X2+e)+1X2. Выполнив остальные шаги алгоритма, приходим к решению:

X1=1*(01*0(01*01*0+1)*01*+e)

Контрольные вопросы

 

1.      Как записывается стандартная система уравнений с регулярными коэффициентами?

2.      Дополните фразу: Если какой-либо элемент Xi в стандартной системе отсутствует, то можно считать, что коэффициент при данном элементе равен…

3.      Дополните фразу: Если коэффициент при элементе Xi в стандартной системе отсутствует, то можно считать, что этот коэффициент равен…

4.      Описать последовательность выполнения прямого и обратного хода алгоритма решения системы уравнений с регулярными коэффициентами.

 

Домашнее задание

Решить систему уравнений с регулярными коэффициентами:

X=a1X+a2Y+a3

Y=b1X+b2Y+b3

Литература

 

1.      Д. Кнут. Искусство программирования. М.: 2000

2.      А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  14

1.      Понятие об информационной системе (ИС). Классификация ИС. Особенности информационных запросов в ИС обоих типов.

2.      Понятие об информационном запросе. Сущность и связь. Типы связей.

3.      Задача управления данными. Система управления базой данных (СУБД). Функции СУБД. Уровни управления данными, их взаимодействие. Концептуальный и физический уровни.

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

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

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

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

Сущность – это обобщенное понятие, обозначающее любой предмет, или явление, группу предметов, или явлений, процесс и так далее. Любая ИС хранит информацию о сущностях. Между сущностями имеются связи. Различают связи следующих типов:

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

1:N, когда одной сущности первого вида может соответствовать более чем одна сущность второго вида, например, связь "Государство – Город".

M:N, когда несколько сущностей первого вида могут соответствовать нескольким сущностям второго вида, например, связь "Врачи – Больные".

Компьютерная ИС строится в виде одной, или нескольких баз данных.

База данных состоит из информационной и программной компонент. Программная компонента – это система управления базой данных (СУБД).

СУБД – это программный комплекс, используемый для создания и поддержки базы данных. Основные функции СУБД:

Интерфейс между различными уровнями представления данных;

Обеспечение физической и логической целостности данных;

Обеспечение секретности и проверка прав доступа;

Синхронизация обращений (управление транзакциями).

 

 

Контрольные вопросы

 

1.      Дать определение и привести примеры документальных и фактографических ИС.

2.      Что такое сущность и связь?

3.      Дать определение и привести примеры связей типов 1:1, 1:N, M:N.

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

5.      Как обеспечивается логическая и физическая целостность данных?

Домашнее задание

Построить таблицу с описанием10 – 15 книг. Выбрать структуру таблицы. Занести информацию в таблицу. Привести примеры информационных запросов к таблице.

Литература

 

1.      Д. Кнут. Искусство программирования. М.: 2000

2.      Л.В. Зайцева, Е.И. Константинова, Ю.М. Носков. Информационные технологии в управлении. М.: НГУ, 1999.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Тезисы лекции №  15

Представление данных и знаний

1.      Индуктивные и дедуктивные модели представления знаний.

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

3.      Определение логического следствия. Две теоремы о логическом следствии. Запись утверждений на естественном языке в виде формул логики высказываний.

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

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

Формула в логике высказываний может содержать атомы и пять функций: конъюнкцию Ù, дизъюнкцию Ú, отрицание Ø, импликацию ®, и эквивалентность «. Ранее рассматривались способы преобразования формул к классическому базису: {Ù, Ú, Ø}.

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

1.      Индивидные символы или константы, например: Джон, Конфуций, 3.

4.      Символы переменных, например: x, y, z.

5.      Функциональные символы, например, f, g, h, плюс.

6.      Предикатные символы, например, P, Q, R, БОЛЬШЕ.

Для переменных используются два специальных символа: " - квантор всеобщности и $ - квантор существования.

Примеры формул в логике предикатов:

Утверждение

Предикатная формула

Каждое рациональное число есть вещественное число

("x)(Q(x) ® R(x))

Существует число, называемое простым

($x)(P(x)

Для каждого числа x существует такое число y, что x<y.

("x)($y)(МЕНЬШЕ(x,y)

 

Контрольные вопросы

 

1.      Дать определение и привести примеры формул в логике предикатов.

2.      Дать определение и привести примеры формул:

2.1. Всюду истинных (тавтологических);

2.2. Всюду ложных (невыполнимых);

2.3. Истинных для одних значений переменных и ложных – для других.

3.      Что такое интерпретация формулы в логике предикатов?

4.      Какие формулы в логике предикатов называются эквивалентными?

5.      Как преобразуются формулы: (x®y) и (x«y) к классическому базису?

Домашнее задание

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

1)      Париж любит каждый, кто любит какой-нибудь город.

2)      Каждый человек любит какой-нибудь город

3)      Каждый человек любит Париж.

Какое из этих утверждений является следствием других?

Литература

 

1.      Д. Кнут. Искусство программирования. М.: 2000

2.      Ч. Чень, Р. Ли Математическая логика и автоматическое доказательство теорем. - М.: Наука, 1983.

3.      Информатика. Базовый курс / Симонович С.В. и др. – СПб.: Издательство «Питер», 1999,- 640 с.

 

Hosted by uCoz