FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Email: Нажмите что бы посмотреть
Лекция 1
Информация существует в виде различных материальных форм, тогда как сама по себе является общим абстрактным содержанием в различных формах представления.
В различных областях науки существуют свои определения понятия «информация».
Информационные системы и технологии
анализ и обработка сигналов
распознавание образов
информатика – сбор, хранение, поиск, обработка и выдача информации в знаковой форме
Информационные системы и технологии
Данные ― факты, идеи, сведения в знаковой форме, позволяющей производить их передачу, обработку и интерпретацию
Информационные системы и технологии
ИТ экспертных систем
предметно-ориентированные ИТ для решения конкретны задач в определенной сфере
проблемно-ориентированные ИТ для решения типовых прикладных задач
технологии обработки числовой информации
технологии обработки графической информации
технологии обработки звуковой информации
технологии работы в глобальных сетях
социальные информационные технологии
Информационные системы и технологии
Этапы информатизации общества
Изобретение письменности
Изобретение книгопечатания (середина XVI века)
Прогресс средств связи (конец XIX века)
Появление микропроцессорной техники (70-ые гг. XX века)
Информационное общество
Информатизация общества влечет за собой отток людей из сферы прямого материального производства в информационную сферу
(вторая половина XX века)
Информационные системы и технологии
информационный кризис
применение информационных технологий
Информационные системы и технологии
Лекция 1
Алгебраический подход:
Символ ― знак, который имеет специальный смысл.
Исходных знаков для представления информации не достаточно.
Получить из конечного множества знаков неограниченный запас сообщений можно путем составления последовательностей первичных знаков.
Формальная математическая модель ― формальные языки.
Информационные системы и технологии
Информационные системы и технологии
Информационные системы и технологии
Информационные системы и технологии
Лекция 1
Информационные системы и технологии
Алгебраическая теория программирования
Автоматическое программирование:
«программирующие программы» ― трансляторы
Механико-математический факультет МГУ:
1953 – семинар по программированию
1954 – первый выпуск по специальности «программирование»
Лекция 1
Информационные системы и технологии
Первый оптимизирующий транслятор Альфа:
Многопроходная система трансляции. Оптимизирующие преобразования промежуточного представления программ. АЛЬФА-6 (1973), АИСТ, проект БЕТА: внутренний язык.
Язык СИГМА – символьная обработка, генерация программ
Лекция 1
Информационные системы и технологии
Лекция 1
Информационные системы и технологии
Лекция 1
Информационные системы и технологии
Лекция 1
Информационные системы и технологии
Лекция 1
Информационные системы и технологии
Лекция 1
Компилятор ― языковой процессор (программа), который воспринимает программу на некотором входном языке в качестве входных данных, а на выходе выдает эквивалентную программу на другом языке.
Задача ― получить эквивалентную программу
Информационные системы и технологии
Синтезирующая часть компилятора, в соответствии с некоторой грамматикой, разбивает промежуточное представление программы и создает программу в машинных кодах
Лекция 1
Информационные системы и технологии
Лекция 1
Информационные системы и технологии
Лекция 1
Информационные системы и технологии
k
Информационные технологии
Лекция 1
Формальный язык
Словесное описание
Алгебраическое описание
Порождающие правила
Алгоритм распознавания
Формальная грамматика
Порождающая
Распознающая
Информационные технологии
Лекция 1
G = (T, N, P, S)
Порождающая грамматика задает правила, с помощью которых можно построить любое слово языка
Информационные технологии
Лекция 1
Терминал (терминальный символ) — это объект, непосредственно присутствующий в словах языка, соответствующего грамматике и имеющий конкретное, неизменяемое значение (0, 1, 2, 3, 4, 5, 6, a, b, c и т.д.)
Нетерминал (нетерминальный символ) — это объект, обозначающий какую-либо сущность языка (ФОРМУЛА, ВЫРАЖЕНИЕ, КОМАНДА и т.д.) и не имеющий конкретного символьного значения
Вывод цепочки
Понятие выводимости:
Если αYβ последовательный набор символов языка G, а
Y→x («х непосредственно выводится из Y») правило этого языка, то набор символов αxβ непосредственно выводится из набора символов αYβ в языке G
αYβ → αxβ
Информационные технологии
Лекция 1
Вывод цепочки
1 способ
S→T+S→a+S→a+T+S→a+b+S→a+b+T→a+b+a
2 способ
S→T+S→T+T+S→T+T+T→T+T+a→T+b+a→a+b+a
3 способ
S→T+S→T+T+S→T+T+T→a+T+T→a+b+T→a+b+a
Информационные технологии
Лекция 1
S→T+S→a+S→a+T+S→a+b+S→a+b+T→a+b+a
S→T+S→T+T+S→T+T+T→T+T+a→T+b+a→a+b+a
S→T+S→T+T+S→T+T+T→a+T+T→a+b+T→a+b+a
Информационные технологии
Лекция 1
Информационные технологии
Лекция 1
Информационные технологии
Лекция 1
Рассматриваем два алфавита – конечные множества A и B
И последовательности букв из A и B:
(a(1), a(2), …, a(t), …) и (b(1), b(2), …, b(t), …)
И отображения f: A* B*
Лекция 1
Функция f: (a(1), a(2), …, a(t), …) (b(1), b(2), …, b(t), …) называется детерминированной, если b(t) однозначно определяется первыми t членами.
a(1), a(2), …, a(t).
Информационные системы и технологии
Детерминированные функции можно задавать на бесконечных деревьях:
Лекция 1
Конечно детерминированные функции или автоматы – детерминированные функции
в деревьях которых содержится лишь конечное число различных (не изоморфных между
собой) поддеревьев. Изоморфизм здесь подразумевается как биекция, сохраняющая
записанные на ребрах буквы.
Информационные системы и технологии
Лекция 1
В общем случае для детерминированных функций достаточно знать конечное число конечных фрагментов дерева, чтобы найти образ любой последовательности букв исходного алфавита. Эти части могут задаваться диаграммами переходов (диаграммами Мура).
Каждому ребру приписывается
пара символов, первая компонента которой
соответствует направлению движения,
а вторая - элементу алфавита,
приписанному ребру, по которому
происходит движение.
q0
1
0
0
1
q1
q0
q0
q1
q1
(0,1)
(0,0)
(1,1)
(1,0)
q0
q1
Информационные системы и технологии
Автоматные функции можно задавать двумя функциями:
функцией перехода G(a(t), q(t)) = q(t+1)
функцией выхода F(a(t), q(t)) = b(t)
q(t) – состояние в момент t
a(t) – очередная буква, подданная на вход,
b(t) – очередная буква на выходе.
Удобно по умолчанию считать q(0) = 0, когда это имеет смысл.
Для функции четности:
q
G(a, q)
(a, F(a, q))
Информационные системы и технологии
функция перехода G(a(t), q(t)) = a(t)
функция выхода F(a(t), q(t)) = q(t)
q(t+1) = a(t)
b(t) = q(t)
q(0) = 0
(1,1)
(0,0)
(1,0)
(0,1)
q0
q1
Информационные системы и технологии
Задача №1
Лекция 1
Информационные системы и технологии
Задача №2
Лекция 1
Информационные системы и технологии
Задача №3
Лекция 1
Информационные системы и технологии
Задача №4
Лекция 1
Информационные системы и технологии