Материал из eSyr's wiki.

[править] Информация о курсе

• Лектор: Ложкин Сергей Андреевич
• Электропочта лектора: mailto:lozhkin@cs.msu.su
• Сайт кафедры: http://mathcyb.cs.msu.su

[править] Содержание курса

Курс состоит из 3 частей:

1. Представление функций с помощью дизъюнктивных нормальных форм
2. Типы управляющих схем, оценка числа преобразований
3. Синтез, сложность и надёжность управляющих схем

По окончании каждой части будет проводиться контрольная (даты приведены на 2007 год):

1. 23 марта
2. 20 апреля
3. 18 мая

Кроме того, будет проведён тест.

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

Дополнительно, на лекциях раз в две недели будут проводиться текущие тесты длительностью 10—15 минут.

При наличии вопросов можно прийти за 10—15 минут до начала пары и задать их лектору.

Положение дел во время весеннего семестра 2011-2012 учебного года на третьем потоке и кафедре маткибернетики(лекции вместе с 3 потоком):

• Курс состоит из 4 частей:

1. Вопросы представления функций алгебры логики;
2. Основные классы управляющих систем, верхние оценки числа схем, эквивалентные преобразования, системы "основных" множеств, их полнота;
3. Синтез управляющих систем, нижние оценки функции Шеннона, оценки сложности;
4. Надежность и контроль схем (тесты таблиц, самокоррекция).

• Лектор выкладывает курс на сайте кафедры в электронном виде в 4 главах (в каждой по 1 части курса - см. ссылку в разделе Литература) , при этом корректируя курс в течение семестра, так что, например, версии 2011 и 2012 года различаются по количеству материала и последовательности тем. При этом он всегда обращает внимание на то, что методичка изменилась, и выкладывает новый вариант. Методичку читать можно, но в неё нужно вникать. Всё равно стоит слушать лектора - он может менять материал от года к году, также он рассказывает главный смысл теорем и приводит примеры задач, а не просто теоремы вводит/доказывает, как в книге. Вместе с методичкой лежат ссылки на программу курса, список экзаменационных вопросов и таблицы успеваемости и посещений.

• По окончании рассмотрения главы проводится тест и контрольная. Тест - 2-3 вопроса одновременно и на знание определений(не доказательств!), и на некоторые методы решения, которые были на семинарах. На всё про всё - 15 минут. Примерно через неделю после теста проходит контрольная - сначала задачи по материалу семинаров, потом - теоретические вопросы. На то и на другое отводится 45 минут, всего же контрольная занимает пару. В 2012 году результаты тестов и контрольных по 3 и 4 главам к экзамену учитывали вместе.

Система оценок:

1. За тест можно получить до 1 балла.
2. За каждую задачу или теоретический вопрос - по 1 баллу.
3. за пропуски могут снять 1 балл (пропуски см. ниже)

Итого: суммарно число баллов сравнивается с максимально возможным. 0%-30% -- оценка "2", 30%-50% -- оценка "3-", 50%-65% -- оценка "3", 65%-80% -- оценка "4", 80%-100% -- оценка "5". "3-" отличается от "2" только возможностью сдать экзамен по упрощённой схеме(см. ниже), а так это по большому счёту всё-равно двойка.

• Лектор проводит проверки посещаемости часто, почти на каждой лекции, но не всех.

Проверяют тех, кто пропускает семинары(по любой причине), тех, у кого до этого много пропусков(4 и больше), тех, кто получил "2" на контрольной, очень редко проверяют весь поток или полностью некоторые группы (например, 320,321 и 322) - в общем, кого будут проверять в следующий раз решает лектор, но его систему легко понять. Фактически, тех, кто пишет контрольные хорошо, практически не проверяют на лекциях после 1 контрольной.

• В конце курса после всех контрольных выводится предварительная оценка. На ней основывается экзамен. ПРЕДВАРИТЕЛЬНУЮ ОЦЕНКУ В ЛЮБОМ СЛУЧАЕ МОЖНО УЛУЧШИТЬ ТОЛЬКО НА 1 БАЛЛ.

Лектор давал возможность переписать 1 (худшую/пропущенную) работу с целью поднабрать баллов на лушую предварительную оценку, но только тем, кого к моменту переписи (почти конец зачётной сессии) допустили к экзаменам. Получившие предварительную пять приглашаются на предэкзамен в конце зачётной сессии, если у них уже будет печать допуска к экзаменам в зачётке. Не попавшие на предэкзамен отличники и остальные с оценками от "3-" и выше могли выбрать 2 варианта экзамена:

1. быстрый экзамен за 5 минут(ВРЕМЕНИ НА ПОДУМАТЬ НЕ ДАДУТ!!!) с ответами по определениям теории и идеям доказательств, за который либо поставят предварительную оценку(за "3-" ставят удовл.), либо отправят на пересдачу - получить оценку выше/ниже (кроме двойки) при таком экзамене нельзя.
2. "стандартный" экзамен с билетом, временем на подготовку, задачами, доказательствами, ответом экзаменатору. Можно получить любую оценку, но не выше чем на 1 балл от предварительной(т.е. при предварительной тройке получить пять уже невозможно ! ).

Получившие предварительную "2" пишут письменный экзамен - по 1 задаче на главу, теория(определения, формулировки, идеи доказательств) по всему курсу. После проверки могут спросить ещё. За этот экзамен поставят либо три, либо два.

Задачи в совокупности учитывались отдельно. "5" по задачам на контрольной освобождает от задачи на эту тему на экзамене, если она выпадает.

[править] Литература

1. Яблонский С. В. Введение в дискретную математику. М., Наука, 1986. Часть V, гл. I, §§1-6.
2. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М., МГУ, 1984.
3. Дискретная математика и математические вопросы кибернетики. М., Наука, 1974, с.116-117,136-137, 72-74.
4. Яблонский С. В. Эквивалентные преобразования управляющих систем. М., МГУ, 1986.
5. Яблонский С. В. Некоторые вопросы надежности и контроля управляющих систем. Сб. «Математические вопросы кибернетики», М., Наука, 1988, с.5-26.
6. Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М., МГУ, 2000.
7. Ложкин С. А. Структурное моделирование и декомпозиция для некоторых классов схем. М., МГУ, 2001.
8. Ложкин С. А. Основы кибернетики. http://mathcyb.cs.msu.su (учебники)
9. Сапоженко А. А. Некоторые вопросы сложности алгоритмов. М., МГУ, 2001.
10. Алексеев В. Б,, Вороненко А. А., Ложкин С. А., Романов Д. С., Сапоженко А. А,, Селезнева С. Н. Задачи по курсу «Основы кибернетики». М., МГУ, 2002.
11. Нигматуллин Р. Г. Сложность булевых функций. М., Наука, 1991.