ipzadmin/ November 30, 2017/ Загальне

ІНФОРМАЦІЯ ПРО КУРС

Опис дисципліни. У куpсі “Дискретні структури”  студенти знайомляться з основними типами обчислювальних задач,  класами  складності а також детально вивчають теоретико-числові алгоритми які використовуються в криптографії.

Орієнтований зміст  лекційного курсу.

  • Поняття аксіоматичної теорії, виводу, теореми, доведення. Числення висловлень та числення предикатів як аксіоматичні теорії. Похідні правила виводу.
  • Числення предикатів як аксіоматична теорія. Індуктивне правило виводу .
  • Доведення методом математичної індукції. Пряме доведення, доведення від
  • супротивного, контрапозиція, еквівалентність, перебір варіантів та
  • неконструктивні доведення.
  • Основні поняття теорії складності обчислень, асимптотичні позначення. Типи
  • обчислювальних задач. Класи складності N, NP.
  • Прості і складені числа. Найбільший спільний дільник. Найменше спільне кратне. Ділення з остачею.
  • Основна теорема арифметики. Коефіцієнти Безу. Алгоритм Евкліда. Розширений  алгоритм Евкліда.
  • Властивості простих чисел, розподіл простих чисел. Формули для простих чисел,  прості числа спеціального вигляду.
  • Арифметичні функції, основні мультиплікативні функції.
  • Основи теорії груп. Кільця, поля.
  • Порівняння, модулярна арифметика, кільце Zn, мала теорема Ферма, китайська теорема про остачі, тести простоти
  • Квадратичні лишки, символи Лежандра та Якобі, первісні корені та дискретні логарифми
  • Криптосистеми RSA, Рабина, Ель-Гамаля.

Передумови.  Лінійна алгебра та геометрія, Математичний аналіз, Теорія ймовірностей, Комп’ютерна дискретна математика, Основи програмування.

Розклад.   Одна  лекція в тиждень і одна лабораторна робота.

Онлайн форум. Якщо у вас виникнуть  питання стосовно навчальних матеріалів, напишіть  на форумі дисципліни який знаходиться в Модульному середовищі.

Оцінка.  Ваша оцінка за курс буде виставлена автоматично : лабораторні роботи(50%), контрольні роботи (10%),  теоретичні  завдання (10%), підсумковий іспит (30%).

Література.   Теми занять  охоплюють  матеріал відображений у відомому  підручнику

 Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3th-edition, 2009

Теоретичні завдання. Вправи складаються з коротких питань  які видаються на початку   лекції.

Комп’ютери. Ви можете використовувати комп’ютери  у лабораторії а також користуватися своїм ноутбуком(рекомендовано). Ми надаємо інструкції по налаштуванню середовища програмування Visual Studio 2013.