ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Розробка системи завдань (алгоритми-програми) з дискретної математики
         

     

    Інформатика, програмування

    Вятський Державний Гуманітарний Університет

    Кафедра прикладної математики

    Курсова робота з інформатики

    Тема: Розробка системи вправ і завдань (алгоритми-програми) з дискретної математики .

    Виконав: Студент 4 курсу факультету інформатики

    Лепешкін Антон Геннад'евіч

    Проверила: Ашихміна Тетяна Вікторівна

    Кіров 2004

    Зміст.

    Зміст. 2


    Введення. 3


    Глава 1 Теоретичний матеріал. 4

    Перебір з поверненням. 4
    Пошук даних. 5

    Логарифмічний (бінарний) пошук 5
    Методи сортування. 6

    Сортування злиттями. 6

    Швидке сортування Хоар. 6
    Графи. 6

    Представлення графа в пам'яті комп'ютера 6

    досяжність 7
    Найкоротші шляху. 8

    Алгоритм Дейкстри 8

    Алгоритм Флойда (найкоротші шляхи між всіма парами вершин). 9

    Глава 2 Система завдань і вправ. 9

    Класифікація задач. 9

    Кімнати музею. 12

    Пірат в підземеллі. 13

    Диспетчер і міліція. 14

    Задача про футболістів. 15

    Задача про сім'ї. 16

    Метро. 16

    Роботи. 17

    Вожатий у таборі 20

    Єгер. 21

    Гра «Знайди друга». 22
    Додаток. 22

    1 22

    2 25

    3 27

    4 30

    5 32

    6 32

    7 34

    8 39

    9 41

    10 43

    Висновок. 45


    Література 45

    Введення.
    Незважаючи на те, що для вирішення завдань в основному використовуються загальні методи,все-таки мислення кожної конкретної людини трохи відрізняється відмислення інших людей, якщо він володіє достатньою базою знань. Такимчином, при вирішенні завдань «починаючи з нуля» можна зайти в глухий кут, якщовибрати невірний шлях вирішення завдання. В даному курсовому проекті мирозробимо власну класифікацію завдань, що дозволяє визначитинайбільш відповідний спосіб вирішення, щоб полегшити процес моделювання таскладання алгоритму і запобігти вибір неправильного способу, такожрозглянемо цю класифікацію з точки зору методики викладанняінформатики. вибір неправильного способу. У цьому полягає актуальністьданого курсового проекту.
    Мета: Розробити власну класифікацію для задач з дискретноїматематики. Для досягнення цієї мети були поставлені наступні завдання:

    1) Розробити власну систему завдань і вправ з дискретної математики.

    2) Визначити способи вирішення даних завдань, використовуючи теоретичний матеріал курсу дискретної математики.

    3) Скласти алгоритм - програму для кожного завдання, що реалізує вибраний способи рішення.

    4) Розробити систему критеріїв класифікації даної системи завдань.
    Глава 1 Теоретичний матеріал.

    Перебір з поверненням.

    Загальна схема
    Дано N впорядкованих множин U1 U2 ,..., Un (N - відомо), і потрібнопобудувати вектор А = (а1 а2, ..., аn), де a1 ? U1, a2 ? U2, ..., an ? Un,задовольняє заданому безлічі умов і обмежень.
    В алгоритмі перебору вектор А будується покомпонентний ліворуч

    направо. Припустимо, що вже знайдені значення першому (до-1)

    компонент, A = (a1, a2, ..., a (k-1)),?, ...,?), Тоді заданий безліч

    умов обмежує вибір наступного компоненти Аk деяким

    безліччю SkCUk. Якщо Sk [] (нічого), ми маємо право вибрати в

    як акнайменший елемент Sk іперейти до вибору ^/^ "^ вибори п« я »,
    (до 1) компоненти ітак далі. Однак/[+ Д Jfcv при цьому а,якщо умови умови а,, ^ іазтакі, що Sk виявилося порожнім, то ми повертаємося до вибору
    (к-1) компоненти, відкидаємоа (k-1) і вибираємо як новий a (k-1) той елемент S (ki), якийбезпосередньо випливає за щойно відкинутим. Може виявитися, що длянового a (k-1) умови завдання допускають непорожній Sk, і тоді ми намагаємосязнову вибрати елемент ак. Якщо неможливо вибрати a (k-1), ми повертаємосяще на крок назад і вибираємо новий елемент а (к-2) і так далі.

    Графічне зображення - дерево пошуку. Корінь дерева (0 рівень)є порожній вектор. Його сини суть безліч кандидатів для вибору а1 і,в загальному випадку, вузли k-го рівня є кандидатами на вибір ак приумови, що а1, а2, ..., a (k-1) вибрані так, як вказують предки цихвузлів. Питання про те, чи має завдання рішення, рівносильний питання, єЧи є які-небудь вузли дерева рішеннями. Розшукуючи всі рішення, ми хочемоотримати всі такі вузли.
    Рекурсивна схема реалізації алгоритму,procedure Backtrack (Beктop, i);beginif then else begin; for a ? Si do Васкtrаск (вектор | | a, i + l); (| | - додавання довектору компоненти)end; end;
    Оцінка тимчасової складності алгоритму. Дана схема реалізації переборупризводить до експоненціальним алгоритмам. Дійсно, Нехай всі рішеннямають довжину N, тоді досліджувати потрібно близько | Si | * | S2 | *...*| SN |вузлів дерева. Якщо значення S; обмежена деякою константою С, тоотримуємо порядку CN вузлів.

    Пошук даних.


    Логарифмічний (бінарний) пошук

    Логарифмічний (бінарний або метод ділення навпіл) пошук даних застосуємодо сортованого безлічі елементів а1 <а2 <... <Ап, розміщенняякого виконано на суміжній пам'яті. Для більшої ефективності пошукуелементів треба, щоб шляху доступу до них стали коротшими, ніж простопослідовний перебір. Найбільш очевидний метод: почати пошук зсереднього елемента, тобто виконати порівняння з елементом а. Результатпорівняння дозволить визначити, в якій половині послідовності а (,а2 ,..., а, 1 + ",,..., ап продовжити пошук,застосовуючи до неї ту ж процедуру, і т.д. Основна ідея бінарного пошукудосить проста, проте «для багатьох хороших програмістів не одна спробанаписати правильну програму закінчилася невдачею ». Щоб доскональнорозібратися в алгоритмі, найкраще представити дані ах <а2 <... <Апу вигляді двійкового дерева порівнянь, яке відповідає бінарного пошуку.
    Двійкове дерево називається деревом порівнянь, якщо для будь-якої його вершини
    (кореня дерева або кореня піддереві) виконується умова:

    (Вершини лівого піддереві)

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status