11. [18] Вообразите себя в роли Управления внутренних доходов Министерства финансов США. Вы получаете миллионы информационных карточек от организаций о том, сколько денег они выплатили различным лицам, и миллионы налоговых деклараций (карточек) о доходах от налогоплательщиков. Как бы вы стали отыскивать людей, которые сообщили не обо всех своих доходах?

12. [М25] (Транспонирование матрицы.) Имеется магнитная лента, содержащая миллион слов, которые представляют собой элементы матрицы 1000 х 1000, записанные по строкам: ai,i ai,2 • •. ai.iooo 12,1 • «2,1000 •. • 11000,1000. Ваша задача - получить ленту, на которой элементы этой матрицы были бы записаны по столбцам: ai,i 02,1 ... aiooo.i 11,2 • • • 11000,2 •.. 11000,1000 • (Постарайтесь сделать не более десяти просмотров данных.)

13. [М26] В вашем распоряжении есть довольно большой файл из Л слов. Как бы вы его "перетасовали" случайным образом?

14. [20] Вы работаете с двумя вычислительными системами, в которых по-разному упорядочены литеры (буквы и цифры). Как заставить первую систему сортировать файлы с буквенно-цифровой информацией, предназначенные для использования во второй системе?

15. [18] Имеется довольно большой список людей, родившихся в США, с указанием штата, в котором они родились. Как подсчитать тех, кто родился в каждом штате? (Предполагается, что ни один человек не указан в списке более одного раза.)

16. [20] Чтобы облегчить внесение изменений в большие программы, написанные на языке FORTRAN, желательно написать программу, которая формирует таблицу перекрестных ссылок. Входными данными для нее служит программа на FORTRAN, а в результате получается листинг исходной программы, снабженный указателем всех случаев употребления каждого идентификатора (т, е. имени) в программе. Как написать такую программу?

► 17. [33] {Сортировка библиографических карточек каталога.) До появления компьютерных баз данных в каждой библиотеке существовал каталог библиографических карточек, с помощью которого читатели могли отыскать интересующие их издания. Но сортировка карточек в порядке, удобном для читателей, усложняется по мере увеличения библиотечного фонда. В следующем "алфавитном" списке содержатся рекомендации, взятые из правил регистрации и хранения каталожных карточек Американской библиотечной ассоциации (Чикаго, 1942).

Текст карточки Замечания

R. Accademia nazionale dei Lincei, В названиях иностранных (кроме британских) Rome учреждений слово "royalty" (королевский)

игнорируется

1812; ein historischer Roman Achtzehnhundertzwolf (числительное 1812 на

немецком языке)

Bibliotheque dhistoire revolutionnaire В французском тексте апостроф рассматривается

как пробел

Bibliotheque des curiosites Диатонические Знаки игнорируются

Brown, Mrs. J. Crosby Указание положения (Mrs.) игнорируется

Brown, John Фамилии с датами следуют за фамилиями без дат

Brown, John, mathematician ..., которые упорядочиваются

Brown, John, of Boston no описательным словам

Brown, John, 1715-1766 Одинаковые фамилии упорядочиваются по датам

рождения

BROWN, JOHN, 1715-1766 Работы о нем идут после его работ

Brown, John, d. 1811 Иногда год рождения определяется приблизи-

тельно

Текст картонки Brown, Dr. John, 1810-1882 Brown-Williams, Reginald Makepeace Brown America

Brown к Dallisons Nevada directory Brownjohn, Alan

Den, Vladimir Eduardovich, 1867-The den

Den lieben langen Tag

Dix, Morgan, 1827-1908 1812 ouverture

Le XIXe siecle frangais

The 1847 issue of U. S. stamps

1812 overture

I am a mathematician

IBM journal of research and development ha-I ha-ehad la; a love story

International Business Machines Corporation

al-Khuwarizmi, Muhammad ibn Musa,

fl. 813-846 Labour. A magazine for all workers Labor research association Labour, see Labor McCalls cookbook McCarthy, John, 1927-Machine-independent computer

programming. MacMahon, Maj. Percy Alexander,

1854-1929 Mrs. Dalloway Mistress of mistresses Royal society of London

St. Petersburger Zeitung

Saint-Saens, Camille, 1835-1921 Ste-Marie, Gaston P Seminumerical algorithms Uncle Toms cabin U. S. bureau of the census

Замечания Указание положения (Dr.) игнорируется Дефис рассматривается как пробел Названия книг указываются после составных фамилий

к в английском тексте превращается в "and"

Апостроф в именах игнорируется

Артикль в начале текста игнорируется

..., если существительное стоит в именительном

падеже

Фамилии идут раньше других слов Dix-huit cent douze (числительное 1812 на французском языке)

Dix-neuvieme (числительное XIX-й на французском языке)

Eighteen forty-seven (числительное 1847 на английском языке)

Eighteen twelve (числительное 1812 на английском языке)

(а book by Norbert Wiener) (книга Норберта Винера)

Аббревиатуры рассматриваются как ряд однобук-венных слов

Артикль в начале текста игнорируется Знаки препинания в названиях игнорируются

Начальное "al-" в арабских именах игнорируется Заменяется словом "Labor"

Ссылка на другую карточку в картотеке Апостроф в английском тексте игнорируется Мс = Мае

Дефис рассматривается как пробел

Указание положения (Maj.) игнорируется "Mrs." заменяется словом "Mistress"

В названиях британских учреждений слово

"royalty" (королевский) учитывается

"St." заменяется словом "Saint", даже в немецком

тексте

Дефис рассматривается как пробел Sainte

(а book by Donald Ervin Knuth)

(a book by Harriet Beecher Stowe)

"U. S." заменяется словами "United States"

Текст карточки Замечания

Vandermonde, Alexandre Theophile, 1735-1796

Van Valkenburg, Mac Elwyn, 1921- Пробел после префикса в фамилиях игнорируется Von Neumann, John, 1903-1957

The whole art of legerdemain Артикль в начале текста игнорируется

Whos afraid of Virginia Woolf ? Апостроф в текстах на английском языке игнори-

руется

Wijngaarden, Adriaan van, 1916- Фамилия никогда не начинается со строчной

литеры

(У большинства из этих правил есть исключения; кроме того, существует много других правил, которые здесь не упомянуты.)

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

18. [М25] (Э. Т. Паркер (Е. Т. Parker).) Леонард Эйлер высказал предположение [iVova Acta Acad. Sci. PetTopolkanse 13 (1795), 45-63, §3; написана в 1778], что уравнение

«V -I- XV у" =

не имеет нетривиальных решений среди целых неотрицательных чисел и, v, w, х, у, z. Одновременно он предположил, что уравнение

Xi +---+X„ i =ж„

не имеет решения в положительных целых числах при гг > 3, но это предположение было опровергнуто уже в наше время, когда с помощью компьютера было найдено тождество 275 + 84-1-110-1-133 = 144 [см. L. J. Lander, Т. R. Parkin, and J. L. Selfridge, Math. Сотр. 21 (1967), 446-459]. Множество аналогичных примеров было обнаружено и при п = 4 Н. Д. Элкисом (N. D. Elkies) [Math. Сотр. 51 (1988), 825-835]. Подумайте, как можно было бы использовать сортировку для поиска примеров, опровергающих предположение Эйлера при тг = 6.

► 19. [24] Файл содержит большое количество 30-разрядных двоичных слов: xi,...,xn. Придумайте хороший способ нахождения в нем всех пар с взаимно дополняющими элементами {xijXj}. (Два слова называются взаимно дополняющими, если второе содержит нули во всех разрядах, в которых были единицы в первом слове, и наоборот; таким образом, они взаимно дополняющие тогда и только тогда, когда их сумма равна (И ... 1)2, если они рассматриваются как двоичные числа.)

► 20. [25] Имеется файл, содержащий тысячу 30-разрядных двоичных слов xi,..., хюоо-Как бы вы стали составлять список всех пар {xi,Xj), таких, что xt отличается от Xj не более чем в двух разрядах?

21. [22] Как бы вы поступили, если бы вам нужно было найти все пятибуквенные анаграммы, такие как CARET, CARTE, CATER, CRATE, REACT, RECTA, TRACE; CRUEL, LUCRE, ULCER; DOWRY, ROWDY, WORDY? [Или если бы вы, допустим, захотели узнать, существуют ли в английском языке наборы из десяти или более анаграмм, кроме замечательной серии

APERS, ASPER, PARES, PARSE, PEARS, PRASE, PRESA, RAPES, REAPS, SPAER, SPARE, SPEAR,

к которой можно еще добавить французское слово APRES.]