|
|
| (не показана 1 промежуточная версия 1 участника) |
| Строка 1: |
Строка 1: |
| | + | [[Категория:Семинары кафедры математической кибернетики (архив)]] |
| | + | |
| | == Общая информация == | | == Общая информация == |
| | Семинар проходит по понедельникам с 12:15 до 13:45. Практические занятия и самостоятельные работы проходят в аудитории 604. | | Семинар проходит по понедельникам с 12:15 до 13:45. Практические занятия и самостоятельные работы проходят в аудитории 604. |
| | | | |
| − | Семинары ведет Шуплецов Михаил Сергеевич. | + | Семинары ведет [[Шуплецов Михаил Сергеевич]]. |
| − | | + | |
| − | == Второе домашнее задание ==
| + | |
| − | Необходимо спроектировать и реализовать при помощи СУБД Postgres базу данных для информационной поддержки учебного процесса.
| + | |
| − | | + | |
| − | [[Media:Prac_418_spring_2013_task_2.pdf| Текстовое описание базы данных]].
| + | |
| − | | + | |
| − | Задание разбито на несколько этапов:
| + | |
| − | * создание первичной структуры базы данных;
| + | |
| − | * написание типовых запросов;
| + | |
| − | * оптимизация базы данных;
| + | |
| − | * нормализация базы данных;
| + | |
| − | * написание правил и других проверок для поддержания целостности базы данных.
| + | |
| − | | + | |
| − | Каждый этап оценивается отдельно.
| + | |
| − | | + | |
| − | == Первое домашнее задание ==
| + | |
| − | Необходимо спроектировать и реализовать при помощи СУБД Postgres базу данных для хранения инфомации о сложности булевых функций небольшого числа переменных, а также об известных минимальных и близких к ним контактных схемах (и схемах из функциональных элементов --- за дополнительные баллы ). База данных должна содержать все необходимые индексы, первичные и внешние ключи, а также минимальный набор проверок целостности и корректности ввода данных в таблицы.
| + | |
| − | | + | |
| − | База данных должна быть заполнена с использованием следующей информации:
| + | |
| − | | + | |
| − | *[[Media:Mincodes_complexity.rar| Таблица сложностей функций и минкодов]]
| + | |
| − | Примечание. Каждая строка файла содержит информацию о сложности некоторой функции, где четыре числа, разделенные запятой, соответствуют порядковому номеру функции, столбцу значений функции (минкоду), записанному в виде десятичного числа, текущей известной оценки сложности указанной функции и значению сложности контактных схем для этой функции, получаемых методом каскадов.
| + | |
| − | *[[Media:Switching_circuits.rar| Таблица контактных схем]]
| + | |
| − | Примечание. Каждая строка содержит информацию о некоторой контактной схеме, где блоки разделенные запятым соответствуют порядковому номеру схемы, минкоду, который схема реализует схема, служебный блок (для большинства схем значение равно нулю), сложности схемы, описанию схемы и служебный блок, который хранит информацию о том, является ли схема минимальной.
| + | |
| − | | + | |
| − | Опишем формат представления контактной схемы.
| + | |
| − | Пусть задана контактная схема, содержащая $n, n>1$, вершин и $k$, $k \ge 0$,
| + | |
| − | контактов. Считается, что все вершины схемы пронумерованы начиная с $0$ до
| + | |
| − | $(n-1)$. Переменной $x_i$, $1 \leqslant i \leqslant 5$, присвоен номер $i$.
| + | |
| − | Каждый контакт описывается четверкой чисел, где первые два числа являются
| + | |
| − | номерами смежных с контактом вершин схемы, третье число характеризует номер
| + | |
| − | переменной, приписанной контакту, а четвертое число~--- степень этой переменной
| + | |
| − | ($0$~--- переменная входит с отрицанием, $1$~--- переменная входит без отрицания).
| + | |
| − | Для описания контактной схемы используется следующее представление (в расширенной
| + | |
| − | форме Бекуса---Наура; как обычно, фигурные скобки означают возможность пропуска
| + | |
| − | либо повторения произвольное число раз):
| + | |
| − | | + | |
| − | <номер вершины> ::= '0' | ... | 'n-1'
| + | |
| − | <номер переменной> ::= '1' | ... | '5'
| + | |
| − | <степень переменной> ::= '0' | '1'
| + | |
| − | <контакт> ::= <номер вершины> ' ' <номер вершины> ' ' <номер переменной>
| + | |
| − | ' ' <степень переменной>
| + | |
| − | <контактная схема> ::= <номер вершины> ' ' <номер вершины> { ' ' <контакт> }
| + | |
| − | | + | |
| − | Примечание. Лексема \tech{<контакт>} входит ровно $k$ раз. Первые два вхождения
| + | |
| − | лексемы \tech{<номер вершины>} характеризуют входной и выходной полюс схемы
| + | |
| − | соответственно.
| + | |
| − | | + | |
| − | Опишем формат представления схемы из функциональных элементов.
| + | |
| − | Формулы Бекуса---Науэра для строк, описывающих СФЭ, имеют следующий вид:
| + | |
| − | | + | |
| − | | + | |
| − | <код ФЭ> ::= '0' | '1' | '2' | '3'
| + | |
| − | <номер вершины> ::= <НЕОТРИЦАТЕЛЬНОЕ ЦЕЛОЕ>
| + | |
| − | <список дочерних вершин> ::= <номер вершины> { ' ' <номер вершины> }
| + | |
| − | <описание вершины> ::= <номер вершины> ',' <код ФЭ> ','
| + | |
| − | <список дочерних вершин>
| + | |
| − | <список вершин> ::= <описание вершины> { ';' <описание вершины> }
| + | |
| − | <описание СФЭ> ::= <список вершин> '.'
| + | |
| − | | + | |
| − | Считается, что любая СФЭ всегда содержит шесть специальных вершин, которые
| + | |
| − | служат вспомогательным целям и не учитываются при подсчёте её сложности~--- это
| + | |
| − | специальная выходная вершина и одна вершина на каждую из входных переменных. Выходная
| + | |
| − | вершина является стоком; в нее ведет единственная дуга, которая исходит из
| + | |
| − | вершины, являющейся выходом СФЭ. Остальным специальным вершинам взаимно
| + | |
| − | однозначно сопоставлены символы входных переменных $x_1$, $x_2$, $x_3$, $x_4$, $x_5$;
| + | |
| − | они является истоками.
| + | |
| − | | + | |
| − | Для описания СФЭ в списке \tech{<список вершин>} перечисляются (в произвольном
| + | |
| − | порядке) те и только те вершины СФЭ, из которых исходит хотя бы одна дуга.
| + | |
| − | Каждая вершина СФЭ получает в описании уникальный номер \tech{<номер вершины>}. Номер
| + | |
| − | выходной вершины равен нулю. Вершина, которой приписана переменная~$x_i$, $1 \leqslant
| + | |
| − | i \leqslant 5$, имеет номер~$i$. Остальные вершины получают номера,
| + | |
| − | строго большие $5$. Кодами функциональных элементов, реализующих конъюнкцию, дизъюнкцию, отрицание являются
| + | |
| − | соответственно числа 1, 2, 3. Для вспомогательных вершин СФЭ \tech{<код ФЭ>} равен 0,
| + | |
| − | для остальных вершин \tech{<код ФЭ>} принимает значение, равное коду функционального элемента, приписанного
| + | |
| − | данной вершине. Список \tech{<список дочерних вершин>} перечисляет номера тех и только
| + | |
| − | тех вершин, в которые из описываемой вершины исходят
| + | |
| − | дуги.
| + | |
| − | | + | |
| − | В качестве результата выполнения работы присылается отчет, который должен содежать следующую информацию:
| + | |
| − | * описание структуры спроектированной базы данных в виде .sql скрипта, позволяющего создать эту базу данных в системе Postgres;
| + | |
| − | * описание запросов к спроектированной базе и результатов их выполнения.
| + | |
| − | | + | |
| − | В отчете должны содержаться следующие запросы:
| + | |
| − | * количество строк в каждой из таблиц спроектированной базы данных;
| + | |
| − | * гистограмма, указывающая число функций с заданной сложностью;
| + | |
| − | * гистограмма, указывающая число схем с заданной сложностью
| + | |
| − | | + | |
| − | Дополнительные баллы начисляются за реализацию в базе данных проверки корректности ввода схемы (ее представления).
| + | |
| − |
| + | |
| − | [[Категория:Семинары кафедры математической кибернетики]]
| + | |
Семинар проходит по понедельникам с 12:15 до 13:45. Практические занятия и самостоятельные работы проходят в аудитории 604.
