1.4. Тематические планы изучения учебной дисциплины

№

ТЕМА

ЛЕКЦИИ

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1

Множества. Мощность. Счетность рациональных чисел. Нечетность действительных чисел, диагональный метод Кантора. Мощность множества подмножеств.

4

4

2

Булевы функции. Операции . Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.

4

4

3

Кванторы и Предикаты. Логика высказываний и логика предикатов.

4

4

4

Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.

4

4

5

Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).

2

2

6

Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.

4

4

7

Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.

2

2

8

Замкнутые классы. Полнота. Теорема Поста.

4

4

9

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

2

2

10

Алгоритм полиномиальной и экспоненциальной сложности. Классы P и NP. Выполнимость К.Н.Ф. NP – полные задачи.

6

6

ВСЕГО:

36

36

№

ТЕМА

ЛЕКЦИИ

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1

Булевы функции. Операции . Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.

4

4

2

Кванторы и Предикаты. Логика высказываний и логика предикатов.

3

4

3

Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.

2

4

4

Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).

1

2

5

Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.

2

4

6

Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.

1

2

7

Полнота. Теорема Поста.

2

2

8

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

1

2

ВСЕГО:

16

24

№

ТЕМА

ЛЕКЦИИ

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1

Булевы функции. Операции . Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.

4

4

2

Кванторы и Предикаты. Логика высказываний и логика предикатов.

4

4

3

Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.

2

4

4

Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).

2

2

5

Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.

4

4

6

Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.

2

4

7

Полнота. Теорема Поста.

2

2

8

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

2

4

9

Алгоритм полиномиальной и экспоненциальной сложности. Классы P и NP. Выполнимость К.Н.Ф. NP – полные задачи.

2

4

ВСЕГО:

24

32

№

ТЕМА

ЛЕКЦИИ

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1

Булевы функции. Операции . Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.

4

4

2

Кванторы и Предикаты. Логика высказываний и логика предикатов.

4

4

3

Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.

2

4

4

Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).

2

2

5

Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.

4

4

6

Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.

2

4

7

Полнота. Теорема Поста.

2

2

8

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

2

2

9

Алгоритм полиномиальной и экспоненциальной сложности. Классы P и NP. Выполнимость К.Н.Ф. NP – полные задачи.

2

2

ВСЕГО:

24

28

№

ТЕМА

ЛЕКЦИИ

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1

Булевы функции. Операции . Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.

4

2

2

Кванторы и Предикаты. Логика высказываний и логика предикатов.

4

2

3

Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.

4

2

4

Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).

1

0,5

5

Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.

2

2

6

Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.

2

0,5

7

Полнота. Теорема Поста.

2

2

8

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

1

1

ВСЕГО:

20

12

№

ТЕМА

ЛЕКЦИИ

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1

Булевы функции. Операции . Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.

2

2

2

Кванторы и Предикаты. Логика высказываний и логика предикатов.

2

2

3

Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.

2

2

4

Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.

2

0,5

5

Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.

2

0,5

6

Замкнутые классы. Полнота. Теорема Поста.

2

1

ВСЕГО:

12

8