Конспект лекций для специальности «Прикладная информатика в экономике» (стр. 11 )

1®B, F, P, V 4®L

2®G, J, K, Q, S, X, Z 5®M, N

3®D, T 6®R

Ø  соседние одинаковые цифры объединяются;

Ø  формируется код из первой буквы и первых 3 цифр имени (если осталось менее 3 цифр, недостающие позиции дополняются нулями);

Ø  ищутся такие же коды, соответствующие другим именам, в памяти системы. В случае неоднозначного совпадения система запрашивает подтверждения у пользователя.

Например, вводится имя FORBES. Оно преобразуется в код F612. Пусть в системе есть имена FARBES, FFORBES, FORBOUYS, которые имеют такие же числовые коды. Поскольку возникла неоднозначность, пользователю поступает запрос на ее снятие.

·  синонимов. Пользователь выбирает то, что ему ближе. Например, команды MS DOS del и erase удаляют файлы. Пользователь волен выбрать любую (если его не волнует возможность последующего восстановления удаленных файлов). Одна из форм синонимичности – ввод сообщений, набранных любой комбинацией строчных и прописных букв;

·  опережающих вводов ответов;

·  использования ответов по умолчанию и макросов;

·  многоуровневой помощи.

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ

Реляционные модели

1)  Сформировать реляционную модель с описанием состава ближайших родственников – родителей и их родителей. Элементы таблицы имеют структуру (поля): имя (например, Наталья, Ирина, Сергей и т. д.), степень родства относительно автора работы (например, мама, бабушка и т. д.), возраст, род занятий (например, пенсионер, студент, служащий и т. д.), профессия, место проживания. Определить ключевые поля (первичные и вторичные). Первичные ключевые поля выделить полужирным курсивом.

2)  Выполнить дополнительные построения для основной таблицы, сформированной в п.1), для индексно-последовательного, индексно-произвольного методов доступа по первичному ключу. Оформить полученные индексы в виде таблиц.

3)  Выполнить дополнительные построения для основной таблицы, сформированной в п. 1), для методов доступа по вторичному ключу: цепь подобных записей (обычный и оптимизированный варианты), инвертированные файлы. Оформить полученные индексы в виде таблиц.

4)  Для реляционной модели разработать алгоритм для решения задачи (номер варианта задается преподавателем). Алгоритм представить в виде блок-схемы:

1.  Создать последовательный файл фамилий.

2.  Сортировать последовательный файл, созданный в варианте 1, по алфавиту.

3.  Модифицировать алгоритм для решения задачи варианта 1 так, чтобы при создании последовательного файла одновременно выполнялась его сортировка по алфавиту.

4.  Даны N возможно повторяющихся фамилий (исходные данные). Решить задачу создания последовательного файла фамилий, обеспечив при этом уникальность фамилий в файле: при попытке ввода уже имеющейся в файле фамилии выдать диагностическое сообщение и проигнорировать ее.

5.  Найти запись по первичному ключу в неупорядоченном последовательном файле методом последовательного сканирования.

6.  Найти запись по первичному ключу в упорядоченном последовательном файле методом последовательного сканирования, если файл упорядочен по убыванию ключа.

7.  Найти запись по первичному ключу в упорядоченном последовательном файле методом последовательного сканирования, если файл упорядочен по возрастанию ключа.

8.  Добавить запись в неупорядоченный последовательный файл.

9.  Добавить запись в упорядоченный последовательный файл, если он упорядочен по убыванию ключа.

10.  Добавить элемент в упорядоченный последовательный файл, если он упорядочен по возрастанию ключа.

11.  Найти запись блочным способом при условии, что N = m2 (N – число записей в файле, m – целое число), а файл упорядочен по убыванию ключа.

12.  Найти запись блочным способом при условии, что N = m2 (N – число записей в списке, m – целое число), а файл упорядочен по возрастанию ключа.

13.  Найти запись двоичным способом, если файл упорядочен по убыванию ключа.

14.  Найти запись двоичным способом, если файл упорядочен по возрастанию ключа.

15.  Сформировать индекс для индексно-последовательного способа доступа при условии, что N = m2 (N – число записей в файле, m – целое число).

16.  Найти запись индексно-последовательным способом при условии, что индекс сформирован в задаче 15.

17.  Сформировать индекс для ключа, по которому планируются редкие запросы при индексно-произвольном способе доступа.

18.  Найти запись индексно-произвольным способом при условии, что индекс сформирован в задаче 17.

19.  Сформировать индекс для вторичного ключа при способе доступа «Цепь подобных записей».

20.  Найти запись по вторичному ключу без использования индексов.

21.  Модифицировать основной файл адресными ссылками при способе доступа по вторичным ключам «Цепь подобных записей».

22.  Найти запись по вторичному ключу при использовании способа доступа «Цепь подобных записей».

23.  Добавить запись в файл, модифицированный в задаче 21.

24.  Модифицировать индекс с вторичными ключами, если в основной файл добавляется запись (задача 23).

25.  Сформировать индекс для вторичного ключа при оптимизированных цепях подобных записей.

26.  Модифицировать индекс с вторичными ключами, если в основной файл добавляется запись, при способе доступа «Оптимизированные цепи подобных записей».

27.  Найти запись по вторичному ключу при использовании способа доступа «Оптимизированные цепи подобных записей».

28.  Сформировать индекс для вторичного ключа при способе доступа «Инвертированные файлы».

29.  Найти элемент по вторичному ключу при использовании способа доступа «Инвертированные файлы».

30.  Модифицировать индекс с вторичными ключами, если в основной файл добавляется запись, при способе доступа «Инвертированные файлы».

31.  Удалить запись в упорядоченном последовательном файле.

5)  Построить блок-схему для решения задачи:

1. Дан последовательный файл из N фамилий. Фамилия – первичный ключ. Файл упорядочен по алфавиту. По вводимой фамилии (Кпоиск) двоичным способом определить номер требуемой записи в файле или выдать сообщение о её отсутствии.

2. Дан последовательный файл из N фамилий (N = m2, где m – натуральное число). Фамилия – первичный ключ. Файл упорядочен по алфавиту. По вводимой фамилии (Кпоиск) блочным способом определить номер требуемой записи в файле или выдать сообщение о её отсутствии.

3. Дан последовательный файл из N фамилий (N = m2, где m – натуральное число). Фамилия – первичный ключ. Файл упорядочен по алфавиту. Сформировать индекс для индексно-последовательного способа доступа.

4. Дан последовательный файл из N элементов (N = m2, где m – натуральное число), содержащих поля «фамилия» и «номер зачетной книжки». Фамилия и номер зачетной книжки – первичные ключи. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для индексно-произвольного способа доступа. Доступ организовать по обоим полям, причем поле «фамилия» имеет приоритет.

5. Дан последовательный файл из N фамилий (N = m2, где m – натуральное число). Фамилия – первичный ключ. Файл упорядочен по алфавиту. Сформирован индекс для индексно-последовательного способа доступа (он размещен в отдельном файле). По вводимой фамилии (Кпоиск) индексно-последовательным способом доступа определить номер требуемой записи в основном файле или выдать сообщение об отсутствии искомой записи.

6. Дан последовательный файл из N записей (N = m2, где m – натуральное число), содержащих поля «фамилия» и «номер зачетной книжки». Фамилия и номер зачетной книжки – первичные ключи. Файл упорядочен по алфавиту по полю «фамилия». Построены два индекса для организации индексно-произвольного способа доступа, причем приоритет в поиске принадлежит ключу «фамилия». По ключу Кпоиск, содержащему значение зачетной книжки, индексно-произвольным методом доступа определить значение поля «фамилия» требуемой записи в основном файле или выдать сообщение об отсутствии искомой записи.

7. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для поиска по вторичному ключу способом «Цепи подобных записей», для поиска по обоим вторичным ключам.

8. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Модифицировать основной файл, добавив в него поля ссылок, для организации доступа по каждому из вторичных ключей способом «Цепи подобных записей».

9. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике», а также поля ссылок для организации доступа способом «Цепи подобных записей». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Построены индексы для организации доступа к записям файла по вторичным ключам способом «Цепи подобных записей». Индексы размещены в дополнительных файлах. По ключу Кпоиск, содержащему оценку по математике, способом «Цепи подобных записей», определить фамилии тех, кто имеет искомую оценку.

10. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для поиска по вторичному ключу способом оптимизированных цепей подобных записей для поиска по обоим вторичным ключам.

11. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике», а также поля ссылок для организации доступа способом «Цепи подобных записей». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Построены индексы для организации доступа к записям файла по вторичным ключам методом оптимизированных цепей подобных записей. Индексы размещены в дополнительных файлах. По ключам К1поиск и К2поиск, содержащим оценки по математике и физике, соответственно, методом оптимизированных цепей подобных записей определить фамилии тех, кто имеет искомые оценки.

12. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для поиска по вторичному ключу способом инвертированных файлов для поиска по обоим вторичным ключам.

13. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Построены индексы для организации доступа к записям файла по вторичным ключам способом инвертированных файлов. Индексы размещены в дополнительных файлах. По ключу Кпоиск, содержащему оценку по математике, способом инвертированных файлов определить фамилии тех, кто имеет искомую оценку.

Деревья

1)  По данным последовательного файла из задачи 1 предыдущего задания сформировать свое генеалогическое дерево, в котором указать два поколения предков – своих родителей и их родителей. Себя представить корнем дерева (нулевой уровень), родителей – первым уровнем, их родителей (т. е. своих бабушек и дедушек) – вторым уровнем иерархии. Все элементы дерева обозначить их именами. Изобразить дерево рисунком. Например, если имя студента – Алексей, его родителей – Анна и Сергей, бабушек – Ольга и Марина, а дедушек – Станислав и Иван, то генеалогическое дерево (с учетом родственных связей) будет выглядеть следующим образом:

Алексей

 

Анна Сергей

 

Станислав

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

Сети

1)  По данным последовательного файла из задачи 1 первого задания сформировать сеть, состоящую из двух деревьев: первое содержит сведения о женщинах, второе - о мужчинах. Связь между деревьями выполняется по вершинам, в которых выражается степень родства соответствующих членов семьи женского и мужского пола. Все элементы сети обозначить их именами. Изобразить сеть рисунком. Например, если женщины семьи имеют имена: Анна, Марина, Ольга, а мужчины - Алексей, Сергей, Станислав и Иван, то сеть (с учетом родственных связей из предыдущего задания) будет выглядеть следующим образом (показана не целиком):

женщины

мать/сын жена/муж мать/сын бабушка/внук сватья/сват жена/муж теща/зять

Иван

мужчины

Здесь в записи <x>/<y> элемент <x> означает степень родства со стороны женщины, а <y> - мужчины.

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

ЛИТЕРАТУРА

1.  Введение в системы баз данных. – М.: Наука, 1980. – 463 с.

2.  Мартин Дж. Организация баз данных в вычислительных системах. – М.: Мир, 1980. – 662 с.

3.  Структуры и базы данных. – М.: Мир, 1986. – 198с.

4.  Олле КОДАСИЛ по управлению базами данных. – М.: Финансы и статистика, 1981. – 285 с.

5.  Солтон Дж. Динамические библиотечно-информационные системы. – М.: Мир, 1979. – 557 с.

6.  Хаббард Дж. Автоматизированное проектирование баз данных. – М.: Мир, 1984. – 292с.

7.  , , Самохвалов и банки данных. – М.: Высшая школа, 1987. – 245 с. Список литературы

8.  Аладьев информатики: учеб. пособие / . – М., 1998. – 496 с.

9.  Бажин системы менеджмента / . – М., 2000. – 688 с.

10.  / Управление информационными ресурсами / , . – М., 1999. – 402 с.

11.  Дракин конечных пользователей с системами обработки данных / , , . – М., 1988. – 288 с.

12.  Информационные системы и технологии в экономике: учебник / под ред. . – М., 2003. – 416 с.

13.  Информационные технологии (для экономиста): учеб. пособие / под ред. . – М., 2001. – 309 с.

14.  Информационные технологии в маркетинге: учебник / под ред. . – М., 2000. – 336 с.

15.  Информационные технологии управления: учеб. пособие для вузов / под ред. . – М., 2003. – 439 с.

16.  Каймин / . – М., 2000. – 232 с.

17.  Карминский бизнеса / , , . – М., 2004. – 620 с.

18.  Карпова данных. Модели, разработка, реализация / . – СПб., 2001. – 304 с.

19.  Козырев технологии в экономике и управлении: учебник / . – СПб., 2000. – 322 с.

20.  Технологии корпоративных сетей. Энциклопедия / М. Кульгин. – СПб., 2000. – 704 с.

21.  Мишенин экономических информационных систем / . - М., 1999. – 187 с.

22.  Могилев / . – М., 1999. – 811 с.

23.  / Реинжиниринг бизнеса: реинжиниринг организаций и информационных технологий / , . – М., 1997. – 336 с.

24.  Острейковский / .– М.,2001. – 511 с.

25.  Попов с ЭВМ на естественном языке / . – М., 1982. – 360 с.

26.  Романов информационные системы в экономике: учеб. пособие для вузов / , . – М.. 2000. – 487 с.

27.  Савельев информатики / . – М., 2001. – 327 с.

28.  Советов технология: учебник / . – М., 1994. – 360 с.

29.  Тарасов XXI века: проблемы проектирования и управления / . - Автоматизация проектирования, № 4, 1998. – С. 46 – 53.

30.  Топоркова : учеб. пособие / . – Калининград, 2001. – 205 с.

31.  Топоркова данных и технологии их обработки: учеб. пособие / . – Калининград, 2003. – 105 с.

32.  Топоркова и синтез формальных текстов: учеб. пособие / . – Калининград, 2002. – 116 с.

33.  Уткин системы и технологии в экономике: учебник / , . – М., 2003. – 335 с.

[1] Выдержка из Государственного образовательного стандарта высшего профессионального образования для специальности «Прикладная информатика (по областям)»

[2] Гносеология – это раздел философии, связанный с теорией познания; он объединяет методологические проблемы получения нового научного знания.

[3] Обратите внимание на изменение формы глагола «отчислить»: для фактических данных он употребляется в прошедшем времени, фиксируя тем самым факт отчисления; для эмпирического закона он имеет смысл «обычно отчисляют» - это уже закономерность.

[4] СУБД – система управления базами данных

[5] об этом стандарте см. далее

[6] Более подробно и строго данные вопросы рассматриваются в курсе «Базы данных»

[7] ER – (Entity-Relationship) – сущность-отношение (или связь)

[8] Напомним, что записи файла упорядочены по возрастанию первичного ключа

[9] Напомним, что ключами для структурированных данных являются поля, а не слова или словосочетания

[10] Интересные описания подобных диалоговых систем и казусов, которые сопровождали их создание, можно найти в книге Б. Рафаэла «Думающий компьютер».