![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Нелинейные структуры данных.Содержание книги Поиск на нашем сайте
Рекурсии. Общие сведения о деревьях. Представление деревьев в памяти ЭВМ. Операции над деревьями.
Алгоритмы решения задач выбора. Способы решения задач. Применение рекурсий. Дерево решений. Переборные задачи. Алгоритмы с возвратом. Метод ветвей и границ. Метод проб и ошибок. Динамическое программирование. Жадные алгоритмы.
Сортировка данных. Общие понятия. Внутренняя сортировка: основные методы, быстрые методы. Внешняя сортировка.
Алгоритмы комбинаторики. Генерация комбинаторных объектов. Перебор всех вариантов. Перестановки. Сочетания.
Табличные структуры. Виды таблиц. Линейные таблицы. Древовидные таблицы. Таблицы с вычисляемыми входами.
Алгоритмы на графах. Основные определения. Представление графов. Пути в графе. Кратчайшие пути. Обходы графов. Остовное дерево наименьшего веса.
Перечень рекомендуемой литературы: 1. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М., Изд. "Вильямс", 2000 г. 2. Вирт Н. Алгоритмы + структуры данных = программы. М., Изд. "Мир", 1985 г. 3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., «Мир», 1982 г. 4. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., "Мир", 1976 г., (переиздание - М., Изд. "Вильямс", 2000 г.) 5. Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., "Мир", 1978 г., (переиздание - М., Изд. Изд. Вильямс", 2000 г.) 6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Анализ и построение. М., Изд. "БИНОМ", 2000 г. 7. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. – М.: Вильямс, 2005. 8. Липский В. Комбинаторика для программистов. – М.: Мир, 1988. 9. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учебное пособие. – М.: Финансы и статистика, 2004.
Вопросы САОД
1. Динамические типы данных: список, стек, очередь, дек. 2. Нелинейные структуры данных: деревья, представление деревьев в ЭВМ, операции над деревьями. 3. Идеально сбалансированное бинарное дерево. Сбалансированные деревья поиска. 4. Алгоритмы с возвратом. 5. Динамическое программирование. 6. Методы сортировки массивов. 7. Внешняя сортировка. 8. Генерация комбинаторных объектов. Перебор всех вариантов.
9. Генерация комбинаторных объектов. Перестановки. 10. Линейные таблицы: поиск в неупорядоченных и упорядоченных таблицах. 11. Таблицы с вычисляемыми входами. 12. Построение матрицы достижимости (путевая матрица). 13. Кратчайшие пути: алгоритм Дейкстры, алгоритм Флойда. 14. Поиск в ширину и глубину на графе. 15. Остовное дерево минимального веса: алгоритм Прима, алгоритм Крускала.
Задачи САОД 1. Для задачи «Бросание кубика» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q. 2. Для задачи «Выражение» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Расставить между заданными N целыми числами знаки «+» и «-» так, чтобы значение получившего выражения было равно заданному S. 3. Для задачи «Дележ» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Заданные N предметов разделить на две примерно одинаковые части. 4. Для задачи «Максимальный квадрат» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: На заданной дискретной карте найти свободный квадрат максимального размера. 5. Для задачи «Коммивояжер» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Найти последовательность посещения заданных N городов. 6. Для задачи «Маршрут» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: В заданной квадратной таблице размера N найти такой путь из левого верхнего угла в правый нижний, у которого сумма чисел минимальна. 7. Для задачи «Музей» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: В музее регистрируется время прихода и ухода посетителей. Найти максимальное число посетителей, находящихся в музее одновременно. 8. Для задачи «Перемножение матриц» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Вычислить произведение N матриц A1A2…AN за наименьшее количество действий. 9. Для задачи «Монетки» разработать два-три алгоритма её решения, провести анализ их сложности.
Условие задачи: Имеется по две монетки достоинством a1, a2, …, aN. Можно ли ими заплатить сумму в S рублей. 10. Для задачи «Разделение сред» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Имеется N материалов, из которых необходимо сделать перегородку с наибольшим временем разделения сред. 11. Для задачи «Подпоследовательность» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Для двух заданных последовательностей найти общую подпоследовательность наибольшей длины.
12. Для задачи «Рюкзак» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Имеется N предметов различных типов весом ai и стоимостью bi. Найти максимальную стоимость груза, помещающегося в рюкзак, выдерживающий максимальный вес W. 13. Для задачи «Сплочённая команда» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Команда будет сплочённой, если профессионализм каждого не превосходит суммы профессионализмов любых двух других игроков. Сформировать из N игроков наиболее сплочённую команду. 14. Для задачи «Счастливые билеты» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Найти количество счастливых билетов из 2N цифр. 15. Для задачи «Точки» разработать два-три алгоритма её решения, провести анализ их сложности. Условие задачи: Найти количество точек с целочисленными координатами в круге радиуса N. Методологии программирования
Модели вычислений Понятие методологии программирования. Обзор развития языков программирования и методологий. Традиционная архитектура вычислительных машин. Первое понятие о стилях программирования. Модификации традиционной архитектуры. Нетрадиционные архитектуры. Сети данных и параллелизм. Эмуляция и машина программы. Языки программирования Традиционные языки и традиционная архитектура. Структура традиционной программы. Основные традиционные языки. Преобразование текста программы в исполняемый код. Синтаксис, семантика и прагматика языка программирования. Понятие НБФ грамматики. Определение порождающей и распознающей грамматики. Описание процесса трансляции. Формальная теория. Исчисление высказываний. Исчисление предикатов. Модальные логики. Высказывания. Логические связки. Формулы. Интерпретация. Таблица истинности. Логическое следование и логическая эквивалентность. Подстановка. Определение формальной теории. Алфавит. Формула. Аксиома. Правила вывода. Выводимость формулы. Интерпретация формальной теории. Общезначимость и непротиворечивость. Полнота, независимость и разрешимость. Классическое определение исчисления высказываний. Частный случай формулы. Алгоритм унификации. Конструктивное определение исчисления высказываний. Производные правила вывода. Теорема дедукции. Следствия теоремы дедукции. Множество теорем исчисления высказываний. Теорема о непротиворечивости. Определение исчисления предикатов. Связки. Кванторы. Предикаты. Функциональные символы. Формула. Связанные и свободные вхождения переменных в формулу. Замкнутая формула. Терм свободный для переменной в формуле. Правила вывода исчисления предикатов. Понятие о прикладном и чистом исчислении предикатов, исчислении предикатов первого и высших порядков. Интерпретация. Модель множества формул. Общезначимость. Теорема полноты чистого исчисления предикатов. Формальная арифметика. Теоремы Гёделя о неполноте.
Синтаксис модальной логики. Модальные операторы. Темпоральные логики. Семантика Крипке. Семантика темпоральной логики.
|
|||||||
Последнее изменение этой страницы: 2016-09-13; просмотров: 206; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.20.178 (0.008 с.) |