Практикум (4 курс, весенний семестр) — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Новая страница: «== Общая информация == Семинар проходит по понедельникам с 12:15 до 13:45. Практические занятия…»)
 
(Содержимое страницы заменено на «== Общая информация == Семинар проходит по понедельникам с 12:15 до 13:45. Прак…»)
Строка 2: Строка 2:
 
Семинар проходит по понедельникам с 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;
+
* описание запросов к спроектированной базе и результатов их выполнения.
+
 
+
В отчете должны содержаться следующие запросы:
+
* количество строк в каждой из таблиц спроектированной базы данных;
+
* гистограмма, указывающая число функций с заданной сложностью;
+
* гистограмма, указывающая число схем с заданной сложностью
+
 
+
Дополнительные баллы начисляются за реализацию в базе данных проверки корректности ввода схемы (ее представления).
+
 
   
 
   
 
[[Категория:Семинары кафедры математической кибернетики]]
 
[[Категория:Семинары кафедры математической кибернетики]]

Версия 23:54, 25 декабря 2013

Общая информация

Семинар проходит по понедельникам с 12:15 до 13:45. Практические занятия и самостоятельные работы проходят в аудитории 604.

Семинары ведет Шуплецов Михаил Сергеевич.